Y combinator обсуждение в разделе "Маленькая схема"

Ответ 1

Отличный вопрос. В интересах тех, у кого нет работоспособной установки 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) self-applicaiton, и снова будут выполнены те же шаги восстановления, что и выше. Но не раньше.

Теперь авторы этой книги хотят прийти к 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) выполняется слишком рано, прежде чем эта внутренняя лямбда может быть даже возвращена, как замыкание, во временную систему. Мы только хотим, чтобы это было уменьшено, когда выполнение дошло до этой точки внутри выражения лямбда, после того, как было вызвано закрытие. Чтобы оно было уменьшено до того, как закрытие было даже создано, это смешно. Тонкая ошибка.:)

Конечно, поскольку g привязано к h, (g g) сводится к (h h), и мы снова возвращаемся туда, где мы начали, применяя h к h. Циклический.

Конечно, авторы знают об этом. Они хотят, чтобы мы это понимали.

Таким образом, виновник прост - это аппликативный порядок оценки: оценка аргумента перед привязкой формируется из формального параметра функции и его значение аргумента.

Это преобразование кода было не совсем правильным. Он работал бы под нормальный порядок, где аргументы не оценивались заранее.

Это исправляется достаточно легко с помощью eta-expand ", который задерживает приложение до фактической точки вызова: (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 (или named let) - более эффективно, определяя закрытие в рамке самореференциальной среды. Вся вещь - теоретическое упражнение для систем, где это невозможно. то есть там, где невозможно назвать вещи, создавать привязки с именами, "указывающими" на вещи, ссылаясь на вещи.

Кстати, способность указывать на вещи - это то, что отличает высших приматов от остальной части животного царства & frasl; живых существ, или так я слышу.:)

Ответ 2

Чтобы узнать, что произойдет, используйте stepper в DrRacket. Шагомер позволяет вам видеть все промежуточные шаги (и идти туда и обратно).

Вставьте следующее в DrRacket:

(((lambda (mk-length)
    (mk-length mk-length))
  (lambda (mk-length)
    (lambda (l)
      (cond
        ((null? l) 0 )
        (else (add1
               ((mk-length mk-length)
                (cdr l))))))))
 '(a b c))

Затем выберите язык обучения "Промежуточный студент с лямбдой". Затем нажмите кнопку шага (зеленый треугольник, за которым следует панель).

Вот как выглядит первый шаг:

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