Ткните носом, что я пропустил

5 подписавшихся и ни одного ответа. :)

Все ждут, когда придет кто-то умнее их и все разложит по полочкам?

Давайте я первым сделаю предположение.

Есть два варианта ответа на вопрос:

1. Автор банально перетрудился (ну с кем не бывает?) и сделал опечатку. Двойная проверка не нужна.
2. Так как на вход функции check-it передается функция, а не просто значение, то двойная проверка может иметь смысл, если значение функции расчитывается каждый раз, однако, насколько я знаю, в схеме это не так и значение x в обоих сравнениях будет одинаковым, а потому смысла в лишних действиях я опять не вижу.

(try-it (+ 1 (random (- n 1))))

Хотя... А точно второй раз x не будет вычисляться (допустим, (not (= x 0)) выдало #t)?

Нет, я же вон скопипастил из стандарта вроде. Только если все #t, то возвращается последнее знаечение, а если, идя слева направо, встречается #f, оно сразу возвращается.

Если кто-то может подсказать по самому тесту - у меня есть подозрение, что это and относится и к первому, и ко второму условиям.

Не, ты не понял.

Предположим, что (not (= x 0)) вернуло #t. Тогда нам придется сделать второе сравнение. При этом x нова будет вычисляться или нет?

Дело в том, что x тут тождественна (+ 1 (random (- n 1)))

Понимаешь, о чем я говорю?

А, не. Что-то я не туда посмотрел...

А, понял. Нет, в этой области х - заранее известная величина, это параметр функции. С любым порядком вычислений. А иначе и смысла бы не было.

Я уже увидел. miller-rabin-expmod возвращает либо 0, либо 1, причем при одинаковых аргументах всегда возвращает одинаковый результат. Смысла делать проверку дважды нет никакого.

точно второй раз x не будет вычисляться

Точно.

expmod возвращает не только 0 или 1, а, собственно, то, для чего предназначена - степень числа по модулю.

Вот вам доказательство эквивалентности:

(define (proof N)
  (let ((test-list (map (lambda (x) (- x (quotient N 2))) (iota N)))
	(simple (lambda (x) (= x 1)))
	(complicated (lambda (x) (and (not (= x 0)) (= x 1)))))
    (equal? (map simple test-list)
	    (map complicated test-list))))      

Найдете контрпример?

По сему, предположу, что либо автор заработался, либо здесь какие-то низкоуровневые причины.

Во-первых, я немного пока такой код не понимаю, во-вторых, я, хоть и мало кода на ским видел, но ни в одном авторы не заморачивались низкоуровневыми оптимизациями) попробую поискать аналоги от других авторов - интересно, что там.

Вероятно, автор когда-то активно писал на каком-нибудь асме :)

Вот вам доказательство эквивалентности

Только это тест а не доказательство. Доказывать тут нечего, так как это аксиома (conjunction elimination).

либо здесь какие-то низкоуровневые причины

Всё равно для обоих выражений в лучшем случае будет cmp 1 r1; sete r2. При сравнении с нулём - test r1, r1; sete r2, но тут сравнение с нулём не нужно.

Только это тест а не доказательство

По Лакатосу — это доказательство :)

test r1, r1; sete r2

Есть setnz.

Вы это серьезно?? Asm и Scheme в одном треде? У меня разрыв шаблона!

Есть setnz.

И ещё три десятка set*. Всё равно будет две инструкции, с какой константой ни сравнивай.

Ну я имел в виду, что первый и единственный аргумент функции в данном случае хранится в аккумуляторе.

Все, нашел. http://www.billthelizard.com/2010/03/sicp-exercise-128-miller-rabin-test.html

Решение той же проблемы, но своими руками. Никаких лишних сравнений нет.

Написано ужасно.

Что именно? Как лучше?

Здесь лишние замыкания (вложенные define), а они стоят дорого.

Вообще, интересно получается. Рассуждают о какой-то оптимизации лишнего сравнения с нулем, а забывают при этом, что каждое замыкание обычно сопровождается созданием нового объекта на куче, в данном случае функции :)

Ну у меня такого пока нет в сикпе, не дошел, наверное. Там написано просто - вложенные определения удобны с точки зрения целостности программы, понятно, что к чему и не нужно лишних параметров передавать. Все что-то скрывают, везде обман:(

Это ж в сикпе так принято :)

Да, ладно, не переживай. Языки ФП, вообще, очень прожорливы до кучи. Обнадеживает лишь то, что их сборщики мусора, как правило, заточены под частое выделение маленьких объектов, таких как эти вложенные функции.

(define (miller-rabin-test n) 
   (define (try-it a) 
     (define (check-it x) 

Фигасе....

Ну у меня такого пока нет в сикпе, не дошел, наверное.

И не надо. Преждевременная оптимизация - корень всех бед. (c)

Здесь лишние замыкания (вложенные define)

Там почти нет замыканий, в основном вложенные функции, только 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));
}

при -O0 даёт

check_it.1593:
	pushq	%rbp
	movq	%rsp, %rbp
	movl	%edi, -4(%rbp)
	cmpl	$1, -4(%rbp)
	sete	%al
	movzbl	%al, %eax
	popq	%rbp
	ret
try_it.1590:
	pushq	%rbp
	movq	%rsp, %rbp
	subq	$16, %rsp
	movl	%edi, -4(%rbp)
	movq	%r10, %rax
	movl	(%rax), %edx
	leal	-1(%rdx), %ecx
	movl	(%rax), %edx
	movl	-4(%rbp), %eax
	movl	%ecx, %esi
	movl	%eax, %edi
	movl	$0, %eax
	call	expmod
	movl	%eax, %edi
	call	check_it.1593
	leave
	ret
miller_test:
	pushq	%rbp
	movq	%rsp, %rbp
	subq	$16, %rsp
	movl	%edi, %eax
	movl	%eax, -16(%rbp)
	movl	-16(%rbp), %eax
	subl	$1, %eax
	movl	%eax, %edi
	movl	$0, %eax
	call	random
	addl	$1, %eax
	leaq	-16(%rbp), %rdx
	movq	%rdx, %r10
	movl	%eax, %edi
	call	try_it.1590
	leave
	ret

функции не в куче, и даже не на стеке, а просто в CS, при том что n тут замыкается. При -O1 всё просто заинлайнится:

miller_test:
	movq	%rbx, -16(%rsp)
	movq	%rbp, -8(%rsp)
	subq	$24, %rsp
	movl	%edi, %ebx
	leal	-1(%rbx), %ebp
	movl	%ebp, %edi
	movl	$0, %eax
	call	random
	leal	1(%rax), %edi
	movl	%ebx, %edx
	movl	%ebp, %esi
	movl	$0, %eax
	call	expmod
	movq	8(%rsp), %rbx
	movq	16(%rsp), %rbp
	addq	$24, %rsp
	ret

С SBCL будет та же история:

(declaim (ftype (function (fixnum fixnum fixnum) fixnum) expmod)
         (ftype (function (fixnum) (or null boolean)) miller))

(defun miller (n)
  (flet ((try (a)
           (flet ((check (x) (= x 1)))
             (check (expmod a (- n 1) n)))))
    (try (+ 1 (random (- n 1))))))

; CL-USER> (disassemble #'miller)
; disassembly for MILLER
; 02F6F556:       488B55F8         MOV RDX, [RBP-8]           ; no-arg-parsing entry point
;      55A:       48C1FA03         SAR RDX, 3
;      55E:       4883EA01         SUB RDX, 1
;      562:       488D5C24F0       LEA RBX, [RSP-16]
;      567:       4883EC18         SUB RSP, 24
;      56B:       486BC208         IMUL RAX, RDX, 8
;      56F:       710E             JNO L0
;      571:       488BC2           MOV RAX, RDX
;      574:       4C8D1C2590050020 LEA R11, [#x20000590]      ; ALLOC-SIGNED-BIGNUM-IN-RAX
;      57C:       41FFD3           CALL R11
;      57F: L0:   488BD0           MOV RDX, RAX
;      582:       488B0567FFFFFF   MOV RAX, [RIP-153]         ; #<FDEFINITION object for RANDOM>
;      589:       B908000000       MOV ECX, 8
;      58E:       48892B           MOV [RBX], RBP
;      591:       488BEB           MOV RBP, RBX
;      594:       FF5009           CALL QWORD PTR [RAX+9]
;      597:       4883C208         ADD RDX, 8
;      59B:       488B45F8         MOV RAX, [RBP-8]
;      59F:       48C1F803         SAR RAX, 3
;      5A3:       4883E801         SUB RAX, 1
;      5A7:       488D5C24F0       LEA RBX, [RSP-16]
;      5AC:       4883EC18         SUB RSP, 24
;      5B0:       486BF808         IMUL RDI, RAX, 8
;      5B4:       710E             JNO L1
;      5B6:       488BF8           MOV RDI, RAX
;      5B9:       4C8D1C25C6060020 LEA R11, [#x200006C6]      ; ALLOC-SIGNED-BIGNUM-IN-RDI
;      5C1:       41FFD3           CALL R11
;      5C4: L1:   488B75F8         MOV RSI, [RBP-8]
;      5C8:       488B0529FFFFFF   MOV RAX, [RIP-215]         ; #<FDEFINITION object for EXPMOD>
;      5CF:       B918000000       MOV ECX, 24
;      5D4:       48892B           MOV [RBX], RBP
;      5D7:       488BEB           MOV RBP, RBX
;      5DA:       FF5009           CALL QWORD PTR [RAX+9]
;      5DD:       480F42E3         CMOVB RSP, RBX
;      5E1:       4883FA08         CMP RDX, 8
;      5E5:       BA17001020       MOV EDX, 537919511
;      5EA:       41BB4F001020     MOV R11D, 537919567
;      5F0:       490F44D3         CMOVEQ RDX, R11
;      5F4:       488BE5           MOV RSP, RBP
;      5F7:       F8               CLC
;      5F8:       5D               POP RBP
;      5F9:       C3               RET

Это при дефолтных оптимизациях. Функции из flet и labels активно раскрываются, функция в куче может аллоцироваться только при возвращении замыкающей лямбды или при возвращении flet/labels функции, так что она уже не будет локальной. Тут ещё можно видеть, что вывод типов работает (но не полностью - непонятно зачем ALLOC-SIGNED-BIGNUM). Правда, в CCL не будет никакого вывода типов и функция из flet будет аллоцироваться, но это проблемы CCL.

В GHC будет работать lambda lifting.

return забыл:

int miller_test(int n) {
    int try_it(int a) {
        int check_it(int x) {
            return x == 1;
        };
        return check_it(expmod(a, n - 1, n));
    };
    return try_it(1 + random(n - 1));
}

Я только на PDP-11 писал когда-то, поэтому твои примеры в полной мере оценить не могу :)

Ты пишешь, что CCL делает так, как я написал, а остальные хорошо оптимизируют. Допускаю, что в данном частном случае оптимизация возможна, но все же, есть другие случаи, и это не только возвращение функции, где происходит создание объекта на куче. А что если добавить в замыкание вычислимое поле? Как тогда? По-моему не останется других вариантов, как создавать объект.

Мой опыт здесь основан на изучении результатов компиляции F# с помощью рефлектора. Там есть необходимость вписаться в объектную модель дотнета. Предполагаю, что компилятор Scala создает примерно такой же код, как и F#. Возможно, что они более ограничены в выборе средств оптимизации, чем упомянутые тобою компиляторы gcc и sbcl. Поэтому о некоторых оптимизациях мог не знать.

Bigloo и Gambit, кстати, тоже не создали новых объектов.

А что если добавить в замыкание вычислимое поле? Как тогда?

А что такое вычислимое поле?

Возьмём тот пример:

(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;
}

теперь если сделать

    bar bar1 = foo(1);
    bar bar2 = foo(2);
    bar1(1); // -> 2
    bar2(1); // -> 3
    bar1(1); // -> 3
    bar2(1); // -> 4
    bar1(-2); // -> 1
    bar2(2); // -> 6

то каждый раз foo должна аллоцировать bar в куче. Также нужно решать проблему сборки функций в куче (в функциональном языке с активным созданием таких функций кроме GC мало вариантов).

Проверил в студии для F#. Лишние объекты создаются только в режиме Debug. В режиме Release оптимизируется все хорошо. Прогресс.

F# в режиме Release тоже не создает.