Смущает преобразование let в лямбда
В настоящее время я прохожу этот отличная статья о Y-комбинаторе от Майк Ванье. В пояснении опущена следующая строка:
It turns out that any let expression can be converted into an equivalent lambda expression using this equation:
(let ((x <expr1>)) <expr2>) ==> ((lambda (x) <expr2>) <expr1>)
Статья иллюстрирует это утверждение путем преобразования:
(define (part-factorial self)
(let ((f (self self)))
(lambda (n)
(if (= n 0)
1
(* n (f (- n 1)))))))
к:
(define (part-factorial self)
((lambda (f)
(lambda (n)
(if (= n 0)
1
(* n (f (- n 1))))))
(self self)))
Теперь я понимаю, как и почему два приведенных выше фрагмента кода идентичны, хотя я не могу понять тот факт, что общее уравнение для преобразования let в lambda:
(let ((x <expr1>)) <expr2>)
==> ((lambda (x) <expr2>) <expr1>)
Буду признателен за подробное объяснение.
re: эпиграф статьи, по-видимому, это Джон фон Нейман сказал: «В математике ничего не понимаешь. Просто привыкаешь».
Ответы 3
Я сам в этом разобрался =).
То, что мне не хватало, это то, что в:
(let ((x <expr1>)) <expr2>)
==> ((lambda (x) <expr2>) <expr1>)
x присутствует где-то внутри <expr2>, так что это больше похоже на:
(let ((x <expr1>)) <expr-containing-x>)
==> ((lambda (x) <expr-containing-x>) <expr1>)
С учетом сказанного, если мы заменим x на f в:
(define (part-factorial self)
(let ((f (self self)))
(lambda (n)
(if (= n 0)
1
(* n (f (- n 1)))))))
а также в:
(define (part-factorial self)
((lambda (f)
(lambda (n)
(if (= n 0)
1
(* n (f (- n 1))))))
(self self)))
и выделит x, <expr1> и <expr2> разными цветами, тогда формула преобразования должна стать понятной:
x не нужно нигде использовать - (let ((x 0)) 99) такой же, как ((lambda (x) 99) 0).
для меня все наоборот: (x => ...x...) val"средства"let {x = val} in ...x... , который не требует пояснений («открыть новый фрейм окружения; создать в нем место с именем x; поместить в это место значение val; продолжить ...»).
В примерах следует использовать более значимые имена. Не могло бы вас смутить это: ((lambda (param) body ...) arg) <--> (let ((param arg)) body ...)?
Вы должны представить себе, что у вас очень мало шепелявого языка, в котором есть lambda, но нет let. Ты хочешь сделать:
(let ((nsq (square n)))
(+ nsq nsq))
Вы знаете, что nsq - это новая переменная, и что тело let можно сделать функцией:
(lambda (nsq) (+ nsq nsq))
Затем вам нужно использовать это, чтобы получить то же значение:
((lambda (nsq) (+ nsq nsq)) (square n))
Представьте, что ваша простая схема содержит макросы и, следовательно, вы реализуете ее как let:
(define-syntax let
(syntax-rules ()
[(let ((binding value) ...)
body ...)
((lambda (binding ...)
body ...)
value ...)]))
Обратите внимание, что во многих реализациях это действительно происходит именно так.
let позволяет вам открыть новую среду, в которой доступны переменные. В терминах языка программирования мы говорим, что это «открывает новый фрейм».
Когда вы пишете (let ((x 42)) <body>), вы создаете фрейм, в котором x доступен внутри <body>, и присваиваете ему значение 42.
Что ж, есть еще один инструмент, который позволяет открывать новые кадры. Фактически, это обычно основной кирпич, из которого вы можете создавать более абстрактные конструкции: он называется lambda.
lambda открывает новый фрейм, в котором его аргументы доступны его телу.
Когда вы пишете (lambda (x) <body>), вы делаете x доступным для <body> функции.
Единственное различие между lambda и let состоит в том, что let немедленно присваивает значение x, тогда как lambda ожидает значение в качестве аргумента.
Следовательно, если вы хотите обернуть <body> напрямую присвоенным значением с помощью lambda, вам просто нужно передать это значение!
((lambda (x) <body>) 42)
Что делает его в точности эквивалентным:
(let ((x 42)) <body>)