Использование lambda для определения cons/car/cdr в SICP

Я только начинал чувствовать, что у меня было смутное понимание использования лямбда в ракетке и схеме, когда я натолкнулся на следующие "альтернативные" определения недостатков и автомобилей в SICP

(define (cons x y)
   (lambda (m) (m x y)))

(define (car z)
  (z (lambda (p q) p)))

(define (cdr z)
  (z (lambda (p q) q)))

В моей жизни я просто не могу их разобрать.

Может ли кто-нибудь объяснить, как разбирать или расширять их таким образом, который имеет смысл для общих неофитов?

Ответы

Ответ 1

Это интересный способ представления данных: как функции. Обратите внимание, что это определение cons возвращает a lambda, который закрывается по параметрам x и y, фиксируя их значения внутри. Также обратите внимание, что возвращенная лямбда получает функцию m в качестве параметра:

;creates a closure that "remembers' 2 values
(define (cons x y)    (lambda (m) (m x y)))
;recieves a cons holding 2 values, returning the 0th value
(define (car z)       (z (lambda (p q) p)))
;recieves a cons holding 2 values, returning the 1st value
(define (cdr z)       (z (lambda (p q) q)))

В приведенном выше коде z есть замыкание, то же самое, что было создано cons, а в тело процедуры мы передаем ему еще один lambda в качестве параметра, помните m? это просто так! ожидаемую функцию.

Понимая вышеизложенное, легко увидеть, как работают car и cdr; Давайте анализировать, как car, cdr оценивается интерпретатором по одному шагу за раз:

; lets say we started with a closure `cons`, passed in to `car`
(car (cons 1 2))

; the definition of `cons` is substituted in to `(cons 1 2)` resulting in:
(car (lambda (m) (m 1 2)))

; substitute `car` with its definition
((lambda (m) (m 1 2)) (lambda (p q) p))

; replace `m` with the passed parameter
((lambda (p q) p) 1 2)

; bind 1 to `p` and 2 to `q`, return p
1

Подводя итог: cons создает замыкание, которое "запоминает" два значения, car получает это замыкание и передает его вдоль функции, которая действует как селектор для нулевое значение и cdr действует как селектор для первого значения. Ключ чтобы понять, что lambda действует как closure. Как здорово это? нам нужны только функции для хранения и получения произвольных данных!

В большинстве LISP вложенные композиции car и cdr определены до 4 глубины. Пример:

(define caddr (lambda (x) (car (cdr (cdr x)))))

Ответ 2

Это должно быть легко понять с помощью combinatory нотации (неявно переведенной на Схему как функции currying, f x y = z ==> (define f (λ (x) (λ (y) z)))):

cons x y m = m x y
car z = z _K          ; _K p q = p
cdr z = z (_K _I)     ; _I x = x     _K _I p q = _I q = q

поэтому получим

car (cons x y) = cons x y  _K     = _K  x y   =  x
cdr (cons x y) = cons x y (_K _I) = _K _I x y = _I y = y

поэтому определения делают то, что мы ожидаем. Легко.

На английском языке значение cons x y - это функция, которая гласит: "Если вы дадите мне функцию из двух аргументов, я назову ее двумя аргументами, которые я держу. Позвольте ей решить, что с ними делать, тогда!".

Другими словами, он ожидает функцию продолжения и вызывает его с двумя аргументами, используемыми в его создании ( "пары" ).

Ответ 3

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

(define (cons x y)
    (lambda (m) (m x y))

Что бы ни было m, и мы подозреваем, что это функция, потому что она появляется рядом с (, она должна применяться как для x, так и для y: это определение cons ing x и y.

(define (car z)
    (z (lambda (p q) q)))

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

Для примера "что-то, что принимает функции как его вход", нам просто нужно вернуться к определению cons. Таким образом, это означает, что car принимает cons в качестве своего ввода.

(car (cons 1 2)) ; looks indeed familiar and reassuring
(car (cons 1 (cons 2 '()))) ; is equivalent
(car '(1 2)) ; is also equivalent
(car z)
; if the previous two are equivalent, then z := '(1 2)

Последняя строка означает: список - это "то, что принимает функцию как свой вход".

Не позволяй своей голове вращаться в этот момент! В любом случае список будет принимать только функции, которые могут работать с элементами списка. И это имеет место именно потому, что мы переопределили cons способ, которым мы располагаем.

Я думаю, что основным моментом этого упражнения является "вычисление - объединение операций и данных вместе, и неважно, в каком порядке вы их объединяете".