“小小的策士”中的Y组合讨论
所以我花了很多时间阅读和重读The Little Schemer第9章的结尾，其中适用的Y组合器是为“长度”函数而开发的。 我认为我的困惑归结为一个单一的陈述，对比两个版本的长度（在组合因子被排除之前）：
A: ((lambda (mk-length) (mk-length mk-length)) (lambda (mk-length) (lambda (l) (cond ((null? l) 0 ) (else (add1 ((mk-length mk-length) (cdr l)))))))) B: ((lambda (mk-length) (mk-length mk-length)) (lambda (mk-length) ((lambda (length) (lambda (l) (cond ((null? l) 0) (else (add1 (length (cdr l))))))) (mk-length mk-length)))) （第四版）指出，A“在我们将它应用于参数时返回一个函数”，而B“不返回函数”，从而产生自我应用的无限回归。 我被这个难住了 如果B被这个问题困扰，我不会看到A如何避免它。
伟大的问题。 为了那些没有function的DrRacket安装（包括我自己）的好处，我会尽力回答。
首先，让我们使用明智的名字，很容易被人眼/心灵追踪：
((lambda (h) ; A. (hh)) ; apply h on h (lambda (g) (lambda (lst) (if (null? lst) 0 (add1 ((gg) (cdr lst)))))))
第一个lambda术语是所谓的ω组合器 。 应用于某些事物时，会导致该词的自我应用。 因此以上相当于
(let ((h (lambda (g) (lambda (lst) (if (null? lst) 0 (add1 ((gg) (cdr lst)))))))) (hh))
当在h上应用h ，形成新的绑定：
(let ((h (lambda (g) (lambda (lst) (if (null? lst) 0 (add1 ((gg) (cdr lst)))))))) (let ((gh)) (lambda (lst) (if (null? lst) 0 (add1 ((gg) (cdr lst)))))))
现在没有什么可以应用的了，所以内部的lambda表单被返回，连同与环境框架（即那些允许绑定）的隐藏链接一起被返回。
lambdaexpression式与其定义环境的这种配对称为闭包 。 对外界来说，它只是一个参数的另一个函数， lst 。 目前还没有更多的减less步骤在那里执行。
现在，当这个闭包 – 我们的list-length函数 – 将被调用时，执行最终将达到(gg)自适应的程度，并且将再次执行如上所述的相同的减less步骤。 但不是更早。
现在，这本书的作者想要到达Y组合器，所以他们对第一个expression式应用一些代码转换，以某种方式自动执行自我应用(gg) – 所以我们可以编写recursion函数应用程序以正常方式(fx) ，而不必为所有recursion调用写((gg) x) ：
((lambda (h) ; B. (hh)) ; apply h on h (lambda (g) ((lambda (f) ; 'f' to become bound to '(gg)', (lambda (lst) (if (null? lst) 0 (add1 (f (cdr lst)))))) ; here: (fx) instead of ((gg) x)! (gg)))) ; (this is not quite right)
现在，经过几步减less步骤，我们到达
(let ((h (lambda (g) ((lambda (f) (lambda (lst) (if (null? lst) 0 (add1 (f (cdr lst)))))) (gg))))) (let ((gh)) ((lambda (f) (lambda (lst) (if (null? lst) 0 (add1 (f (cdr lst)))))) (gg))))
相当于
(let ((h (lambda (g) ((lambda (f) (lambda (lst) (if (null? lst) 0 (add1 (f (cdr lst)))))) (gg))))) (let ((gh)) (let ((f (gg))) ; problem! (under applicative-order evaluation) (lambda (lst) (if (null? lst) 0 (add1 (f (cdr lst))))))))
在这里出现问题： (gg)的自行应用程序执行得太早， 在内部lambda甚至可以作为闭包返回到运行时系统。 我们只希望在执行到达lambdaexpression式中的那一点时，在调用闭包之后，才能减less它。 在封闭之前减less它是荒谬的。 一个微妙的错误。 🙂
当然，由于g与h绑定， (gg)减less到(hh) ，我们又回到开始的地方，将h应用于h 。 循环。
当然作者知道这一点。 他们也希望我们也能理解。
所以罪魁祸首就是简单 – 它是评价的适用顺序 ：在绑定形成之前对函数的forms参数和参数的值进行评价 。
这种代码转换是不正确的。 它会按照正常的顺序工作，其中参数不被预先评估。
通过“ eta-expansion ”可以很容易地解决这个问题，它会延迟应用程序直到实际的调用点： (lambda (x) ((gg) x))实际上说：“ 将会调用((gg) x)一个x的论点“。
而这其实就是代码转换本来应该放在第一位的：
((lambda (h) ; C. (hh)) ; apply h on h (lambda (g) ((lambda (f) ; 'f' to become bound to '(lambda (x) ((gg) x))', (lambda (lst) (if (null? lst) 0 (add1 (f (cdr lst)))))) ; here: (fx) instead of ((gg) x) (lambda (x) ((gg) x)))))
现在可以执行下一个减less步骤：
(let ((h (lambda (g) ((lambda (f) (lambda (lst) (if (null? lst) 0 (add1 (f (cdr lst)))))) (lambda (x) ((gg) x)))))) (let ((gh)) (let ((f (lambda (x) ((gg) x)))) (lambda (lst) (if (null? lst) 0 (add1 (f (cdr lst))))))))
并且闭包(lambda (lst) ...)被形成并且没有问题地返回，并且当(f (cdr lst))被调用时（在闭包内），它简化为((gg) (cdr lst))正如我们想要的那样。
最后，我们注意到C中的(lambda (f) (lambda (lst ...))expression式不依赖于h和g任何一个，所以我们可以把它取出来，使它成为一个参数，与… Y组合：
( ( (lambda (rec) ; D. ( (lambda (h) (hh)) (lambda (g) (rec (lambda (x) ((gg) x)))))) ; applicative-order Y combinator (lambda (f) (lambda (lst) (if (null? lst) 0 (add1 (f (cdr lst)))))) ) (list 1 2 3) ) ; ==> 3
所以现在，在一个函数上调用Y相当于从它中取出一个recursion定义：
( y (lambda (f) (lambda (x) .... (fx) .... )) ) === define f = (lambda (x) .... (fx) .... )
…但使用letrec （或名为let） 更好 – 更高效， 在自引用环境框架中定义闭包 。 对于那些不可能的系统来说，整个Y系统是一个理论性的练习 – 也就是说，在不可能命名的地方 ，创build与“指向”事物的名称的绑定 ，指的是事物。
顺便说一句，指向事物 的能力 是将高等灵长类与其他动物王国/活着的生物区分开来的，或者是我所听到的。 🙂
要查看发生了什么，请使用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)))))))) '(abc))
然后select教学语言“拉姆达中级学生”。 然后点击步进button（绿色的三angular形后面跟着一个小节）。
这是第一步的样子：
然后为第二个函数做一个例子，看看出了什么问题。
