Great question. For the benefit of those without a functioning DrRacket installation (myself included) I'll try to answer it.
首先,让我们使用一些合理的(短的)变量名称,易于人眼/思维跟踪:
((lambda (h) ; A.
(h h)) ; apply h to h
(lambda (g)
(lambda (lst)
(if (null? lst) 0
(add1
((g g) (cdr lst)))))))
第一个 lambda 项被称为小欧米茄,或者U组合器。当应用于某事物时,它会导致该术语的自我应用。因此上式等价于
(let ((h (lambda (g)
(lambda (lst)
(if (null? lst) 0
(add1 ((g g) (cdr lst))))))))
(h h))
When h
应用于h
,新的绑定形成:
(let ((h (lambda (g)
(lambda (lst)
(if (null? lst) 0
(add1 ((g g) (cdr lst))))))))
(let ((g h))
(lambda (lst)
(if (null? lst) 0
(add1 ((g g) (cdr lst)))))))
现在已经没有什么可以应用的了,所以内部lambda
返回形式 - 以及与环境框架的隐藏链接(即那些let
绑定)位于其上方。
lambda 表达式与其定义环境的这种配对称为closure。对于外界来说,它只是一个参数的另一个函数,lst
。目前没有更多的减少步骤需要执行。
现在,当关闭时——我们的list-length
function — 将被调用,执行最终会到达(g g)
自行应用,并且将再次执行与上述相同的减少步骤(重新计算the same关闭)。但不是更早。
现在,该书的作者想要达到Y组合器,因此他们对第一个表达式应用一些代码转换,以某种方式安排该自我应用(g g)
自动执行 - 因此我们可以以正常方式编写递归函数应用程序,(f x)
,而不必将其写为((g g) x)
对于所有递归调用:
((lambda (h) ; B.
(h h)) ; apply h to h
(lambda (g)
((lambda (f) ; 'f' to become bound to '(g g)',
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst)))))) ; here: (f x) instead of ((g g) x)!
(g g)))) ; (this is not quite right)
现在经过几个简化步骤我们得到
(let ((h (lambda (g)
((lambda (f)
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst))))))
(g g)))))
(let ((g h))
((lambda (f)
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst))))))
(g g))))
这相当于
(let ((h (lambda (g)
((lambda (f)
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst))))))
(g g)))))
(let ((g h))
(let ((f (g g))) ; problem! (under applicative-order evaluation)
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst))))))))
麻烦来了:自我应用(g g)
执行得太早,before内部 lambda 甚至可以作为闭包返回到运行时系统。我们只希望当执行到那个点时减少它inside拉姆达表达式,after宣布关闭。在关闭之前就减少它是荒谬的。 Asubtle错误。 :)
当然,自从g
一定会h
, (g g)
减少为(h h)
我们又回到了开始的地方,申请h
to h
。循环播放。
作者们当然意识到了这一点。他们要us也去理解它。
所以罪魁祸首很简单——就是评估的应用顺序: 评估论证before绑定由函数的形式参数及其参数组成value.
那么,代码转换不太正确。它会在下面工作正常秩序其中参数没有提前评估。
这很容易通过“eta 扩展”,这会将应用程序延迟到实际调用点:(lambda (x) ((g g) x))
实际上说:“will call ((g g) x)
当被要求提出论据时x
".
这实际上是代码转换首先应该做的:
((lambda (h) ; C.
(h h)) ; apply h to h
(lambda (g)
((lambda (f) ; 'f' to become bound to '(lambda (x) ((g g) x))',
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst)))))) ; here: (f x) instead of ((g g) x)
(lambda (x) ((g g) x)))))
现在可以执行下一个减少步骤:
(let ((h (lambda (g)
((lambda (f)
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst))))))
(lambda (x) ((g g) x))))))
(let ((g h))
(let ((f (lambda (x) ((g g) x)))) ; here it's OK
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst))))))))
和关闭(lambda (lst) ...)
形成并毫无问题地返回,并且当(f (cdr lst))
被称为(在闭包内)它被简化为((g g) (cdr lst))
正如我们所希望的那样。
最后,我们注意到(lambda (f) (lambda (lst ...))
表达于C.
不依赖于任何h
and g
。所以我们可以把它拿出来,让它成为一个论点,然后剩下……Y组合器:
( ( (lambda (rec) ; D.
( (lambda (h) (h h))
(lambda (g)
(rec (lambda (x) ((g g) x)))))) ; applicative-order Y combinator
(lambda (f)
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst)))))) )
(list 1 2 3) ) ; ==> 3
所以现在,打电话Y在函数上相当于对其进行递归定义:
( y (lambda (f) (lambda (x) .... (f x) .... )) )
=== define f = (lambda (x) .... (f x) .... )
...但是使用letrec
(或命名为let)是better- 更高效,在自参照环境框架中定义闭包。整体Y这是对系统的理论练习,但这是不可能的——即不可能name事物,创造bindings有名字“指点”对事物,指称对事物。
顺便说一句,有能力 point 对事物的认识是高等灵长类动物与动物王国其他生物的区别,至少我是这么听说的。 :)