在"The Little Schemer"中对Y组合器的讨论. [英] Y combinator discussion in "The Little Schemer"

问题描述

因此，我花了很多时间阅读和重新阅读 Little Schemer 中第9章的结尾，其中为length函数开发了适用的Y组合器.我认为我的困惑归结为一个单一的陈述，该陈述对比了两种长度的形式(在排除组合器之前):

So, I've spent a lot of time reading and re-reading the ending of chapter 9 in The Little Schemer, where the applicative Y combinator is developed for the length function. I think my confusion boils down to a single statement that contrasts two versions of length (before the combinator is factored out):

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页(第四版)指出A

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

returns a function when we applied it to an argument

而B

不返回函数

does not return a function

因此，产生了自我应用的无限回归.我为此感到难过.如果B受此问题困扰，我看不出A如何避免这种情况.

thereby producing an infinite regress of self-applications. I'm stumped by this. If B is plagued by this problem, I don't see how A avoids it.

推荐答案

好问题.为了那些没有安装DrRacket的人的利益(包括我自己)，我将尝试回答.

Great question. For the benefit of those without a functioning DrRacket installation (myself included) I'll try to answer it.

首先，让我们使用理智的名称，人眼可以轻松地对其进行跟踪:

First, let's use sane names, easily trackable by a human eye/mind:

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

第一个lambda术语是 omega组合器.当应用于某些事物时，它会导致该术语的自我应用.因此，以上等同于

The first lambda term is what's known as omega combinator. When applied on something, it causes that term's self-application. Thus the above is equivalent to

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

在h上应用h时，会形成新的绑定:

When h is applied on h, new binding is formed:

(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表单-以及在其上方的与环境框架(即那些让装订者)的隐藏链接.

Now there's nothing to apply anymore, so the inner lambda form is returned - along with the hidden linkages to the environment frames (i.e. those let bindings) up above it.

这种lambda表达式与其定义环境的配对称为闭包 .对于外部世界，它只是一个参数lst的另一个功能.目前，无需再执行任何减少操作的步骤了.

This pairing of a lambda expression with its defining environment is known as closure. To the outside world it is just another function of one parameter, lst. No more reduction steps left to perform there at the moment.

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

Now, when that closure - our list-length function - will be called, execution will eventually get to the point of (g g) self-applicaiton, and the same reduction steps as outlined above will again be performed. But not earlier.

现在，该书的作者希望到达Y组合器，因此他们在第一个表达式上应用了一些代码转换，以某种方式安排自动执行该自我应用程序(g g)-因此我们可以编写递归函数应用程序通常以(f x)的方式进行，而不必为所有递归调用将其编写为((g g) x):

Now, the authors of that book want to arrive at the Y combinator, so they apply some code transformations on the first expression, to somehow arrange for that self-application (g g) to be performed automatically - so we may write the recursive function application in a normal manner, (f x), instead of having to write it as ((g g) x) for all recursive calls:

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

现在，我们经过几步减少步骤后得出

Now after few reduction steps we arrive at

(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表达式内 的那一点时减少它.在关闭创建之前就减少它是荒谬的. 细微错误. :)

And here comes trouble: the self-application of (g g) is performed too early, before that inner lambda can be even returned, as a closure, to the run-time system. We only want it be reduced when the execution got to that point inside the lambda expression, after the closure was called. To have it reduced before the closure is even created is ridiculous. A subtle error. :)

当然，由于g绑定到h，所以(g g)简化为(h h)，我们又回到了开始的位置，在h上应用了h.循环播放.

Of course, since g is bound to h, (g g) is reduced to (h h) and we're back again where we started, applying h on h. Looping.

作者当然知道这一点.他们也想让我们 理解它.

Of course the authors are aware of this. They want us to understand it too.

罪魁祸首很简单-它是评估的适用顺序:评估参数 before ，绑定由函数的形式参数及其参数的 value 组成.

So the culprit is simple - it is applicative order of evaluation: evaluating the argument before the binding is formed of the function's formal parameter and its argument's value.

该代码转换不太正确.它将按照正常顺序进行操作，在此情况下不会预先评估参数.

That code transformation wasn't quite right. It would've worked under normal order where arguments aren't evaluated in advance.

" eta扩展 "，这会将应用程序延迟到实际的调用点:(lambda (x) ((g g) x))实际上说:" 将 在调用x时调用((g g) x)".

This is remedied easily enough by "eta-expansion", which delays the application until the actual call point: (lambda (x) ((g g) x)) actually says: "will call ((g g) x) when called upon with an argument of x".

这实际上是应该首先进行的代码转换:

And this is actually what that code transformation should have been in the first place:

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

现在可以执行下一个还原步骤:

Now that next reduction step can be performed:

(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))，正如我们所希望的那样.

and the closure (lambda (lst) ...) is formed and returned without a problem, and when (f (cdr lst)) is called (inside the closure) it is reduced to ((g g) (cdr lst)) just as we wanted it to.

最后，我们注意到C.中的(lambda (f) (lambda (lst ...))表达式不依赖于h和g中的任何一个.这样我们就可以将其取出来作为参数，并留下... Y组合器:

Lastly, we notice that (lambda (f) (lambda (lst ...)) expression in C. doesn't depend on any of the h and g. So we can take it out, make it an argument, and be left with ... the Y combinator:

( ( (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等效于在函数上进行递归定义:

So now, calling Y on a function is equivalent to making a recursive definition out of it:

( y (lambda (f) (lambda (x) .... (f x) .... )) ) 
===  define f = (lambda (x) .... (f x) .... )

...但使用letrec(或命名为let)的效果更好 -绑定.

... but using letrec (or named let) is better - more efficient, defining the closure in self-referential environment frame. The whole Y thing is a theoretical exercise for the systems where that is not possible — i.e. where it is not possible to name things, to create bindings with names "pointing" to things, referring to things.

顺便说一句，指向事物的能力是区分高级灵长类动物与动物界其他部分的能力.活着的生物，或者我听到了.:)

这篇关于在"The Little Schemer"中对Y组合器的讨论.的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！