Вот тут есть реализация теста Миллера-Рабина, и меня смущает одна строка:
(define (miller-rabin-test n)
(define (try-it a)
(define (check-it x)
(and (not (= x 0)) (= x 1))) ;;вот это что?
(check-it (miller-rabin-expmod a (- n 1) n)))
(try-it (+ 1 (random (- n 1)))))
Если я правильно понимаю, это проверка ((x != 0) AND (x = 1)). Почему не просто проверка х на равенство с единицей? Синтаксис: The <test> expressions are evaluated from left to right, and the value of the first expression that evaluates to a false value (see section 6.3.1) is returned. Any remaining expressions are not evaluated. [...] То есть сначала происходит сравнение с нулем, и если х = 0, сразу возвращается #f? Это не то же самое, что и просто
Все ждут, когда придет кто-то умнее их и все разложит по полочкам?
Давайте я первым сделаю предположение.
Есть два варианта ответа на вопрос:
1. Автор банально перетрудился (ну с кем не бывает?) и сделал опечатку. Двойная проверка не нужна. 2. Так как на вход функции check-it передается функция, а не просто значение, то двойная проверка может иметь смысл, если значение функции расчитывается каждый раз, однако, насколько я знаю, в схеме это не так и значение x в обоих сравнениях будет одинаковым, а потому смысла в лишних действиях я опять не вижу.
Нет, я же вон скопипастил из стандарта вроде. Только если все #t, то возвращается последнее знаечение, а если, идя слева направо, встречается #f, оно сразу возвращается.
Если кто-то может подсказать по самому тесту - у меня есть подозрение, что это and относится и к первому, и ко второму условиям.
Я уже увидел. miller-rabin-expmod возвращает либо 0, либо 1, причем при одинаковых аргументах всегда возвращает одинаковый результат. Смысла делать проверку дважды нет никакого.
Во-первых, я немного пока такой код не понимаю, во-вторых, я, хоть и мало кода на ским видел, но ни в одном авторы не заморачивались низкоуровневыми оптимизациями) попробую поискать аналоги от других авторов - интересно, что там.
Только это тест а не доказательство. Доказывать тут нечего, так как это аксиома (conjunction elimination).
либо здесь какие-то низкоуровневые причины
Всё равно для обоих выражений в лучшем случае будет cmp 1 r1; sete r2. При сравнении с нулём - test r1, r1; sete r2, но тут сравнение с нулём не нужно.
Вообще, интересно получается. Рассуждают о какой-то оптимизации лишнего сравнения с нулем, а забывают при этом, что каждое замыкание обычно сопровождается созданием нового объекта на куче, в данном случае функции :)
Ну у меня такого пока нет в сикпе, не дошел, наверное. Там написано просто - вложенные определения удобны с точки зрения целостности программы, понятно, что к чему и не нужно лишних параметров передавать. Все что-то скрывают, везде обман:(
Да, ладно, не переживай. Языки ФП, вообще, очень прожорливы до кучи. Обнадеживает лишь то, что их сборщики мусора, как правило, заточены под частое выделение маленьких объектов, таких как эти вложенные функции.
Там почти нет замыканий, в основном вложенные функции, только m в miller-rabin-expmod и n в miller-rabin-test замыкаются - вряд ли это существенно повлияет на скорость обсчёта.
а они стоят дорого
При использовании очень тупого компилятора (или вообще при неиспользовании), нужно добавить :) В gcc, например, такой код:
int miller_test(int n) {
int try_it(int a) {
int check_it(int x) {
return x == 1;
};
check_it(expmod(a, n - 1, n));
};
try_it(1 + random(n - 1));
}
Это при дефолтных оптимизациях. Функции из flet и labels активно раскрываются, функция в куче может аллоцироваться только при возвращении замыкающей лямбды или при возвращении flet/labels функции, так что она уже не будет локальной. Тут ещё можно видеть, что вывод типов работает (но не полностью - непонятно зачем ALLOC-SIGNED-BIGNUM). Правда, в CCL не будет никакого вывода типов и функция из flet будет аллоцироваться, но это проблемы CCL.
Я только на PDP-11 писал когда-то, поэтому твои примеры в полной мере оценить не могу :)
Ты пишешь, что CCL делает так, как я написал, а остальные хорошо оптимизируют. Допускаю, что в данном частном случае оптимизация возможна, но все же, есть другие случаи, и это не только возвращение функции, где происходит создание объекта на куче. А что если добавить в замыкание вычислимое поле? Как тогда? По-моему не останется других вариантов, как создавать объект.
Мой опыт здесь основан на изучении результатов компиляции F# с помощью рефлектора. Там есть необходимость вписаться в объектную модель дотнета. Предполагаю, что компилятор Scala создает примерно такой же код, как и F#. Возможно, что они более ограничены в выборе средств оптимизации, чем упомянутые тобою компиляторы gcc и sbcl. Поэтому о некоторых оптимизациях мог не знать.
А что если добавить в замыкание вычислимое поле? Как тогда?
А что такое вычислимое поле?
Возьмём тот пример:
(define (miller-rabin-test n)
(define (try-it a)
(define (check-it x)
(and (not (= x 0)) (= x 1)))
(check-it (miller-rabin-expmod a (- n 1) n)))
(try-it (+ 1 (random (- n 1)))))
тут есть вложенная функция check-it тело которой свободно от переменных окружения, то есть оно их не замыкает, так что, если такие функции остаются локальными, компилятор может их переписать как
(define (check-it x)
(and (not (= x 0)) (= x 1)))
(define (miller-rabin-test n)
(define (try-it a)
(check-it (miller-rabin-expmod a (- n 1) n)))
(try-it (+ 1 (random (- n 1)))))
вторая вложенная функция try-it уже замыкает n - в её теле используется переменная из окружающего скопа. Тем не менее, эта функция также локальна, поэтому её можно переписать явно передавая замыкаемые параметры:
(define (check-it x)
(and (not (= x 0)) (= x 1)))
(define (try-it a n)
(check-it (miller-rabin-expmod a (- n 1) n)))
(define (miller-rabin-test n)
(try-it (+ 1 (random (- n 1))) n))
при -O0 gcc это и делает (там адрес n помещается в r10), если сделать readelf -s, то можно увидеть try_it и check_it помеченные как LOCAL. А дальше уже к функциям можно применить инлайнинг как к обычным функциям.
Какие могут быть проблемы с обычными вложенными и замыкающими функциями пока они остаются локальными? Во вложенных функциях можно менять значения замыкаемых переменных и изменения будут сохранятся между вызовами вложенных функций если им передавать адреса замыкаемых переменных, а не их значения (то есть как gcc и делает).
Проблемы могут быть с возвращаемыми замыканиями вместе с возможностью изменять замыкаемые переменные, это, буквально, нарушают линейность:
typedef int(bar)(int);
bar foo(int x) {
int bar(int y) {
x += y;
printf("%i\n", x);
};
return bar;
}
то каждый раз foo должна аллоцировать bar в куче. Также нужно решать проблему сборки функций в куче (в функциональном языке с активным созданием таких функций кроме GC мало вариантов).
