在Scheme中,如何使用lambda创建递归函数？

Question

我在一个Scheme类中,我很好奇在不使用define的情况下编写递归函数.当然,主要的问题是,如果没有名称,你就无法调用自身内部的函数.

我确实找到了这个例子:它是一个只使用lambda的阶乘生成器.

((lambda (x) (x x))
 (lambda (fact-gen)
   (lambda (n)
     (if (zero? n)
         1
         (* n ((fact-gen fact-gen) (sub1 n)))))))

但我甚至无法理解第一次调用,(lambda(x)(xx)):究竟是做什么的？你在哪里输入你想要得到的阶乘值？

这不是为了上课,这只是出于好奇.

Answer 1

(lambda (x) (x x))是一个函数,它自己调用参数x.

您发布的整个代码块产生一个参数的函数.你可以这样称呼它:

(((lambda (x) (x x))
  (lambda (fact-gen)
    (lambda (n)
      (if (zero? n)
          1
          (* n ((fact-gen fact-gen) (sub1 n)))))))
 5)

用5调用它,然后返回120.

想想这个在较高的水平,最简单的方式是第一个函数(lambda (x) (x x)),是给X到自身的引用所以现在X可以参照自身,因此递归.

Answer 2

该表达式(lambda (x) (x x))创建一个函数,当使用一个参数(必须是函数)进行求值时,将该函数与其自身一起作为参数应用.

给定的表达式求值为一个函数,该函数接受一个数字参数并返回该参数的阶乘.尝试一下:

(let ((factorial ((lambda (x) (x x))
                  (lambda (fact-gen)
                    (lambda (n)
                      (if (zero? n)
                          1
                          (* n ((fact-gen fact-gen) (sub1 n)))))))))
  (display (factorial 5)))

在您的示例中有几个层,值得逐步完成并仔细检查每个层的作用.

Answer 3

(lambda (x) (x x)) 获取一个函数对象,然后使用一个参数(函数对象本身)调用该对象.

然后使用另一个函数调用它,该函数在参数名称下获取该函数对象fact-gen.它返回一个带有实际参数的lambda n.这是如何((fact-gen fact-gen) (sub1 n))工作的.

如果你能遵循它,你应该阅读The Little Schemer的示例章节(第9章).它讨论了如何构建这种类型的函数,并最终将此模式提取到Y组合器中(通常可用于提供递归).

Answer 4

基本上你所拥有的是一种类似于 Y 组合器的形式。如果您重构出阶乘特定代码以便可以实现任何递归函数，那么剩余的代码将是 Y 组合器。

为了更好地理解，我自己已经完成了这些步骤。
https://gist.github.com/z5h/238891

如果你不喜欢我写的东西，就去谷歌搜索 Y Combinator（这个函数）。

Answer 5

你这样定义:

(let ((fact #f)) 
  (set! fact 
        (lambda (n) (if (< n 2) 1 
                               (* n (fact (- n 1)))))) 
  (fact 5))

这是多么的letrec真实.见LISP由基督教Queinnec.

在你要问的例子中,自应用组合器被称为" U组合器",

(let ((U  (lambda (x) (x x)))
      (h  (lambda (g)
            (lambda (n)
              (if (zero? n)
                  1
                  (* n ((g g) (sub1 n))))))))
  ((U h) 5))

这里的细微之处在于,由于采用了let范围规则,lambda表达式不能引用所定义的名称.

当((U h) 5)被调用时,它被缩减为((h h) 5)应用程序,在let表单创建的环境框架内.

现在的应用程序h来h创建新的环境帧,其中g指出h在它上面的环境:

(let ((U  (lambda (x) (x x)))
      (h  (lambda (g)
            (lambda (n)
              (if (zero? n)
                  1
                  (* n ((g g) (sub1 n))))))))
  ( (let ((g h))
      (lambda (n)
              (if (zero? n)
                  1
                  (* n ((g g) (sub1 n)))))) 
    5))

(lambda (n) ...)这里的表达式是从那个g指向h它上面的环境框架内部返回的- 作为一个闭包对象.即一个参数的函数,n,其中还记得绑定g,h和U.

因此,当调用此闭包时,n将分配5,并输入if表单:

(let ((U  (lambda (x) (x x)))
      (h  (lambda (g)
            (lambda (n)
              (if (zero? n)
                  1
                  (* n ((g g) (sub1 n))))))))
    (let ((g h))
      (let ((n 5))
              (if (zero? n)
                  1
                  (* n ((g g) (sub1 n)))))))

的(g g)应用程序被还原成(h h)应用程序,因为g对点h中,其中所述封闭对象的创建环境上方的环境框架限定.也就是说,在那里,以最高的let形式.但是我们已经看到了(h h)调用的减少,它创建了闭包,即一个参数n的factorial函数,作为我们的函数,在下一个迭代中将被调用4,然后3等.

是否将是一个新的闭包对象或相同的闭包对象将被重用,取决于编译器.这可能会影响性能,但不会影响递归的语义.