Как можно определить Лисп в терминах y-комбинатора?
Я смотрю лекцию SICP 7A и пытаюсь понять «Определить Lisp как Y-комбинатор (время 1:16:15)»
Думаю, я понял, что (вычисление экспоненты числа типа x^n) можно выразить через Y-комбинатор и лямбду.
Если я прав, я могу думать об этом уравнении как о рекурсивном выражении.
x = 2x - 4
Потому что определяется с использованием самого себя.
Поэтому я могу выразить приведенное выше выражение как
f(x) = 2x - 4
.
Такx
является фиксированной точкойf
:x = f(x)
.
И используя эту стратегию (и весь код выражается как схема )
Сначала выразите как,
(define expt
(lambda (x n)
(if (= n 0)
1
(* x (expt x (- n 1))))))
и как вышеF
является
F = (lambda (g)
(lambda (x n)
(if (= n 0)
1
(* x (g x (- n 1))))))
Такexpt
есть ( Y — комбинатор Y,(Y F) = (F (Y F))
)
expt = F expt = fixed point of F = (F(F(F(F... (F ?) ...)))) = (Y F)
.
Итак, мой вопрос здесь,
Как сказал Суссман (лектор видео (ссылка выше)):
What Lisp is is the fixed point of the process which says,
if I know what lisp was and substituted it in for
eval and apply and so on,
on the right hand sides of all those recursion equations,
then if it was a real good lisp, is a real one then
the left hand side would also be lisp.
Могу ли я выразить Лисп как
L = (lambda (lisp)
(lambda (eval apply)
(lisp eval apply))))
Итак, можно ли назвать этот код (ниже) правильным?
Lisp = L Lisp = fixed point of L = (L(L(L(L ... (L ?) ... )))) = (Y L)