在“小策士” Y组合讨论在“小策士” Y组合讨论(Y combinator discussion i

所以，我花了很多时间阅读和重新阅读中的小策士 ，其中应用性Y组合被用于开发第9章的结尾的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版）规定，甲

返回一个函数，当我们将其运用到的参数

而B

不返回功能

由此产生的自应用无穷倒退。我被这个难住了。如果B被这个问题所困扰，我没有看到一个如何避免它。

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

第一拉姆达项是什么被称为欧米伽组合子。当一些应用，它会导致这个词的自我应用。因此，上述等效于

(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功能-将被调用，执行将最终得到的点(gg)自应用程序了，和上面概述将再次进行同样的还原步骤。但不早。

现在，这本书的作者希望在Y组合到达，所以他们采用一些代码转换第一个表达式，以某种方式为自己的应用程序安排(gg)自动执行-因此，我们可以写递归函数的应用以正常方式， (fx)而不必把它写成((gg) 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))))))))

在这里，麻烦来了：的自申请(gg)过早进行，甚至可以返回内部拉姆达之前，作为一个封闭，到运行时系统。我们只希望当执行到了lambda表达式内这一点上，它可以减少封被称为后。拥有它之前减少甚至创建的闭包是荒谬的。一个微妙的错误。 :)

当然，由于g势必h ， (gg)减少到(hh)我们又回来了，我们开始的地方，应用h的h 。循环。

当然，作者是意识到了这一点。他们希望我们能够理解这一点。

因此，罪魁祸首很简单-它是评价的应用性顺序：之前的绑定是函数的形参和参数的值的评估形成的说法。

该代码转换是不完全正确。它会一直下工作的正常秩序，其中参数不事先评估。

这是补救很轻松地通过“ 埃塔膨胀 ”，这延迟的应用程序，直到实际调用点： (lambda (x) ((gg) x))实际上是说：“ 将调用((gg) 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))被称为（闭包中），它减少到((gg) (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))

然后选择教学语言“中级学员与拉姆达”。然后点击按钮步进（绿色三角形后跟一个栏）。

这是第一个步骤是这样的：