Y Схема реализации схемы

Question

Я действительно новичок в программировании функциональных схем. Недавно я встретил функцию Y-combinator в исчислении лямбда, что-то вроде этого Y ≡ (λy.(λx.y(xx))(λx.y(xx))). Я хотел реализовать его в схеме, я искал alot, но я не нашел никакой реализации, которая точно соответствует приведенной выше структуре. Некоторые из них я нашел, приведены ниже:

(define Y 
(lambda (X) 
    ((lambda (procedure) 
    (X (lambda (arg) ((procedure procedure) arg)))) 
    (lambda (procedure) 
    (X (lambda (arg) ((procedure procedure) arg))))))) 

и

(define Y 
    (lambda (r) 
    ((lambda (f) (f f)) 
    (lambda (y) 
     (r (lambda (x) ((y y) x))))))) 

Как вы можете видеть, что они не совпадают со структурой этой функции Y ≡ (λy.(λx.y(xx))(λx.y(xx))) комбинатора. Как я могу реализовать его в схеме точно так же?

Answer 1

На ленивом языке, таком как Lazy Racket, вы можете использовать обычную версию заказа, но не на любом языке программирования прикладного порядка, таком как Scheme. Они просто перейдут в бесконечный цикл.

аппликативном версия Y часто называют Z комбинатор:

(define Z 
    (lambda (f) 
    ((lambda (g) (g g)) 
    (lambda (g) 
     (f (lambda args (apply (g g) args))))))) 

Теперь первое, что происходит, когда это применяется в (g g) и так как вы всегда можете заменить целое приложение с расширением его тела тело функции можно переписать на:

(define Z 
    (lambda (f) 
    ((lambda (g) 
     (f (lambda args (apply (g g) args)))) 
    (lambda (g) 
     (f (lambda args (apply (g g) args))))))) 

Я ничего не изменил. Это всего лишь немного больше кода, который делает то же самое. Обратите внимание, что эта версия использует apply для поддержки нескольких функций аргументов. Представьте себе функцию Аккермана:

(define ackermann 
    (lambda (m n) 
    (cond 
     ((= m 0) (+ n 1)) 
     ((= n 0) (ackermann (- m 1) 1)) 
     (else (ackermann (- m 1) (ackermann m (- n 1))))))) 

(ackermann 3 6) ; ==> 509 

Это может быть сделано с Z так:

((Z (lambda (ackermann) 
     (lambda (m n) 
     (cond 
     ((= m 0) (+ n 1)) 
     ((= n 0) (ackermann (- m 1) 1)) 
     (else (ackermann (- m 1) (ackermann m (- n 1)))))))) 
3 
6) ; ==> 509 

Обратите внимание, что реализация точно так же, и разница, как обрабатывается ссылка на себя.

EDIT

Итак, вы спрашиваете, как оценка получает с задержкой. Ну нормальная версия заказа выглядит следующим образом:

(define Y 
    (lambda (f) 
    ((lambda (g) (g g)) 
    (lambda (g) (f (g g)))))) 

Если посмотреть на то, как это будет применяться с аргументом, вы заметите, что Y никогда не возвращается, так как прежде чем он сможет применить f в (f (g g)) он должен оценить (g g), которые в свою очередь оценивает (f (g g)) и т. д. Для спасения мы не применяем (g g) сразу. Мы знаем, что (g g) становится функцией, поэтому мы просто даем f функцию, которая при применении генерирует фактическую функцию и применяет ее. Если у вас есть функция add1, вы можете сделать обертку (lambda (x) (add1 x)), которую вы можете использовать, и она будет работать. Точно так же (lambda args (apply (g g) args)) - это то же самое, что и (g g), и вы можете видеть это, просто применяя правила замещения. Ключ здесь заключается в том, что это фактически останавливает вычисление на каждом шаге, пока оно фактически не будет использовано.