Большой вопрос. В интересах тех, у кого нет установленной установки DrRacket (включая меня), я постараюсь ответить на нее.
Во-первых, давайте использовать вменяемые имена, легко отслеживаемых человеческим глазом/ум:
((lambda (h) ; A.
(h h)) ; apply h on h
(lambda (g)
(lambda (lst)
(if (null? lst) 0
(add1
((g g) (cdr lst)))))))
Первый член лямбда-это то, что известно как omega combinator. При применении к чему-то это вызывает самоприменение этого термина. Таким образом, выше эквивалентно
(let ((h (lambda (g)
(lambda (lst)
(if (null? lst) 0
(add1 ((g g) (cdr lst))))))))
(h h))
Когда h наносится на h, новая привязка формируется:
(let ((h (lambda (g)
(lambda (lst)
(if (null? lst) 0
(add1 ((g g) (cdr lst))))))))
(let ((g h))
(lambda (lst)
(if (null? lst) 0
(add1 ((g g) (cdr lst)))))))
Теперь нет ничего, чтобы применить больше, так что внутренняя lambda форма возвращается - вместе с скрытые связи с кадрами среды (т.е. те, которые связывают привязки) вверх над ним.
Это спаривание лямбда-выражения с его определяющей средой известно как closure. Для внешнего мира это просто еще одна функция одного параметра, lst. В настоящий момент больше не осталось шагов по восстановлению.
Теперь, когда это закрытие - наша функция list-length будет вызвана, выполнение в конечном итоге достигнет точки самообслуживания (g g), и снова будут выполнены те же шаги восстановления, что и выше. Но не раньше.
Теперь авторы этой книги хотят, чтобы прибыть в Y Combinator, поэтому они применяются некоторые преобразования кода на первое выражение, чтобы как-то организовать для этого самоприменения (g g) должны быть выполнены автоматически - так мы можем написать приложение рекурсивной функции обычного способа, (f x), вместо того, чтобы писать, как ((g g) x) для всех рекурсивных вызовов:
((lambda (h) ; B.
(h h)) ; apply h on h
(lambda (g)
((lambda (f) ; 'f' to become bound to '(g g)',
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst)))))) ; here: (f x) instead of ((g g) x)!
(g g)))) ; (this is not quite right)
Теперь после нескольких этапов сокращения приходит
(let ((h (lambda (g)
((lambda (f)
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst))))))
(g g)))))
(let ((g h))
((lambda (f)
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst))))))
(g g))))
что эквивалентно
(let ((h (lambda (g)
((lambda (f)
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst))))))
(g g)))))
(let ((g h))
(let ((f (g g))) ; problem! (under applicative-order evaluation)
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst))))))))
И здесь приходит проблему: само-приложение (g g) выполняется слишком рано, до того что внутренняя лямбда может быть даже вернулась, как закрытие, к RUN- времени. Мы только хотим, чтобы это было уменьшено, когда выполнение дошло до этого момента внутри выражение лямбда, после того, как было вызвано закрытие. Чтобы оно было уменьшено до того, как закрытие было даже создано, это смешно. A тонкий ошибка. :)
Конечно, поскольку g связан с h, (g g) сводится к (h h) и мы снова, где мы начали, применяя h на h. Циклический.
Конечно, авторы знают об этом. Они хотят нас, чтобы понять это тоже.
Так преступник просто - это applicative order of evaluation: оценки Аргумент перед тем связывание формируется формального параметра функции и значение своего аргумента.
Это преобразование кода было не совсем правильным. Он работал бы под normal order, где аргументы не оценивались заранее.
Это исправляется достаточно легко «eta-expansion», которая задерживает применение до фактической точки вызова: (lambda (x) ((g g) x)) фактически говорит: «будет вызова ((g g) x) когда призвал с аргументом x».
И это на самом деле то, что преобразование кода должно быть в первую очередь:
((lambda (h) ; C.
(h h)) ; apply h on h
(lambda (g)
((lambda (f) ; 'f' to become bound to '(lambda (x) ((g g) x))',
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst)))))) ; here: (f x) instead of ((g g) x)
(lambda (x) ((g g) x)))))
Теперь, следующий шаг восстановления может быть выполнена:
(let ((h (lambda (g)
((lambda (f)
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst))))))
(lambda (x) ((g g) x))))))
(let ((g h))
(let ((f (lambda (x) ((g g) x))))
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst))))))))
и закрытие (lambda (lst) ...) формируется и возвращается без проблем, и когда вызывается (f (cdr lst)) (внутри закрытия), он сводится к ((g g) (cdr lst)) так же, как мы этого хотели.
Наконец, мы замечаем, что (lambda (f) (lambda (lst ...)) выражение в C. не зависит от какой-либо из h и g. Таким образом, мы можем принять его, сделать его аргумент, и не останется ... в Y Combinator:
(((lambda (rec) ; D.
((lambda (h) (h h))
(lambda (g)
(rec (lambda (x) ((g g) x)))))) ; applicative-order Y combinator
(lambda (f)
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst)))))))
(list 1 2 3)) ; ==> 3
Итак, вызов Y на функции эквивалентно сделать рекурсивное определение из него:
(y (lambda (f) (lambda (x) .... (f x) ....)))
=== define f = (lambda (x) .... (f x) ....)
... но используя letrec (или с именем LET) является лучше - более эффективным, defining the closure in self-referential environment frame. Вся вещь - теоретическое упражнение для систем, где это невозможно. — т. Е. Где невозможно имя вещи, чтобы создать привязки с именами, «указывающими» на вещи, ссылаясь на вещи.
Кстати, способность точки к вещам, это то, что отличает высшие приматы от остального животного мира ⁄ живых существ, так я слышал. :)
Отличный ответ !!! – soegaard
спасибо !! :) Я думаю о добавлении заключительного шага к выведению самого Y ... это следующая логическая задача. Я помню, что я был озадачен всей вещью/тайной. Неправильно. Слишком часто он представлен ex-machina. Есть все виды метафорических описаний, но не фактический вывод. Мне нравится видеть оправдание, а затем вывод. В * маленьких шагах *. :) –
Спасибо за это объяснение. Я застрял в этой самой части, и у меня возникло ощущение, что первое выражение «лямбды», упомянутое выше, также было равнозначно форме 'let', но я не был полностью уверен, пока не прочитал это, не говоря уже о том, что он был назван «омега-комбинатор». Эта информация была бы полезной. Я думаю, мне все равно придется потратить некоторое время на отслеживание выхода Y-комбинатора, но он чувствует себя намного менее грязным, чем (на мой взгляд) довольно слабое объяснение этой концепции авторами. – dtg