方案中的Y组合子使用教堂编号爆炸，但在常规编号上工作

Question

我刚刚读了劳尔·罗哈斯的“Lambda演算1教程介绍”。我将lambda表达式放入Scheme (TinyScheme)中以试用它们。除了使用Y-combinator计算教堂数0,1，...，N的总和的递归函数外，一切都正常工作，Y-combinator耗尽了内存。奇怪的是，如果我使用常规数字计算和，Y-combinator会起作用。

这是我的Y-combinator

(define myY
  (lambda (y) 
    ((lambda (x) (x x)) 
      (lambda (x) 
        (y (lambda (a) ((x x) a)))))))

这是一个递归函数，可以得到N个正规数的和，

(define sum1
  (lambda (r)
    (lambda (x)
      (cond
        ((zero? x) 0)
        (else (+ x (r (sub1 x))))))))

这是可行的

> ((myY sum1) 10)
55

在本教程第15页的底部，使用递归函数R=Lrx.Zx0(NS(r(PN)来计算N个数字的和(L=lambda)。在这个表达式中，r将是递归函数，x将是教堂数，Z是零函数的测试，0是零作为教堂数，N是教堂数，S是后继函数，P是前导函数。我将其转换为Scheme，如下所示

(define myR
  (lambda (r)
    (lambda (x)
      (((myZ x) my0) ((x myS) (r (myP x))))
     )))

然而，即使取0的和也会爆炸。

> ((((myY myR) my0) add1) 0)
No memory!

在上面的代码行中，((myY myR) my0)应该返回教会编号0。我只是获取教会编号，以便对add1执行操作，以便获得人类可读的教会编号。

最初，我认为Y-combinator才是问题所在，但正如我所展示的，它适用于使用正规数的递归函数。教堂编号的定义如本教程中所述，lambda表达式的Scheme版本适用于算术(加法、乘法、不等式)。

编辑:函数myZ是λ表达式Z=Lx.xF¬F，其中F=Lxy.y为False (True为T=Lxy.x)，¬=Lx.xFT不为False。函数Z实现了条件测试，因为Z0=T和ZN=F其中0是零的教会编号(0=Lxy.y)，N是非零的教会编号(1=Lxy.xy，2=Lxy.x(xy)等)。实现Z的方案代码myZ是，

(define myZ
  (lambda (x)
    (((x myF) myNeg) myF)
    ))

Answer 1

lambda演算只适用于正常的降阶(即，只有在需要它们的值时才计算参数)，而Scheme使用适用的降阶(首先计算参数)，但在“特殊形式”中除外。

您的代码使用常规数字并不是因为这些数字，而是因为cond，它最多只能计算一个子句。

如果您将sum1中的cond替换为常规函数，您的计算也不会以常规数字终止。

; This does not work
(define (conditional b t e)
  (if b t e))

(define sum1
  (lambda (r)
    (lambda (x)
      (conditional
        (zero? x)
        0
        (+ x (r (sub1 x)))))))

您可以通过添加一个间接层来修复此问题；通过将分支包装在函数中来暂停对它们的求值：

(define sum1
  (lambda (r)
    (lambda (x)
      ((conditional
        (zero? x)
        (lambda (y) 0)
        (lambda (y) (+ x (r (sub1 x)))))
       "some argument"))))

相应的转换将在您的实现中工作。