"The Little Schemer"中的Y组合讨论

Question

因此,我花了很多时间阅读并重新阅读The Little Schemer中第9章的结尾,其中应用Y组合器是为该length功能开发的.我认为我的困惑归结为一个单独的声明,对比两个版本的长度(在组合器被分解之前):

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))))

第170页(第4版)指出A.

当我们将它应用于参数时返回一个函数

而B

不返回功能

从而产生自我应用的无限回归.我很难过.如果B受到这个问题的困扰,我不知道A如何避免它.

Answer 1

好问题.为了没有运行DrRacket安装(包括我自己)的人的利益,我会尝试回答它.

首先,让我们使用理智的名字,可以通过人眼/思维轻松追踪:

((lambda (h)     ; A.   
     (h h))            ; apply h on h
 (lambda (g)
     (lambda (lst)
       (if (null? lst) 0
         (add1 
               ((g g) (cdr lst)))))))

第一个lambda术语是所谓的欧米茄组合.当应用于某些东西时,它会导致该术语的自我应用.因此,上述等同于

(let ((h (lambda (g)
           (lambda (lst)
             (if (null? lst) 0
               (add1 ((g g) (cdr lst))))))))
  (h h))

何时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返回内部表单 - 以及与环境框架(即那些允许绑定)之间隐藏的链接.

lambda表达式与其定义环境的这种配对称为闭包.对于外界来说,它只是一个参数的另一个功能lst.目前还没有更多的减少步骤来执行.

现在,当list-length调用该闭包 - 我们的函数 - 时,执行将最终达到(g g)自我应用的程度,并且将再次执行与上述相同的缩减步骤.但不是更早.

现在,那本书的作者想要到达Y组合子,所以他们在第一个表达式上应用了一些代码转换,以某种方式安排(g g)自动执行自我应用程序- 所以我们可以在正常情况下编写递归函数应用程序方式,(f x)而不是像((g g) x)所有递归调用一样写它:

((lambda (h)     ; B.
     (h h))            ; apply h on 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)执行得太早,之后内部lambda甚至可以作为闭包返回到运行时系统.我们只希望当执行到了这一点它可以减少内部的lambda表达式,关闭被称为后.在关闭甚至创建之前减少它是荒谬的.一个微妙的错误.:)

当然,由于g必然h,(g g)降低到(h h)和我们又回来了,我们开始的地方,应用h上h.循环.

当然作者都知道这一点.他们希望我们也理解它.

因此罪魁祸首很简单 - 它是评估的应用顺序:在绑定由函数的形式参数及其参数值组成之前评估参数.

代码转换并不完全正确.它将在正常的顺序下工作,其中参数不会提前评估.

通过" eta-expansion " 可以很容易地解决这个问题," eta-expansion "将应用程序延迟到实际的调用点:(lambda (x) ((g g) x))实际上说:" 调用时会调用".((g g) x)x

这实际上是代码转换应该首先应该是什么:

((lambda (h)     ; C.
     (h h))            ; apply h on 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))))
      (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和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)更好 - 更有效,在自引用环境框架中定义闭包.整个Y事件是系统的理论练习,在那里不可能 - 即不可能命名的东西,创建具有"指向"事物的名称的绑定,指的是事物.

顺便说一句,指向事物的能力是高等灵长类动物与其他动物王国/生物的区别,或者我听说过.:)

Answer 2

要查看会发生什么,请使用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))))))))
 '(a b c))

然后选择教学语言"中级学生与lambda".然后单击步进按钮(绿色三角形后跟一个条).

这是第一步:

然后为第二个函数做一个示例,看看出了什么问题.