1

我正在尝试学习 lambda 演算和 Scheme Lisp。关于 lambda 演算的教程可以在这里找到http://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf。

我面临的问题是我不知道如何正确实现迭代。

(define (Y y) (((lambda (x) (y (x x))) (lambda (x) (y (x x))))))
(define (sum r n) ((is_zero n) n0 (n succ (r (pred n)))))
(display ((Y sum) n5))

我总是收到这个错误：

中止！：超出最大递归深度

我知道问题在于评估顺序：该方案(Y sum)首先解释，这导致无限递归：

((Y sum) n5) -> (sum (Y sum) n5) -> ((sum (sum (Y sum))) n5) -> .... (infinite recursion)

但我想要

((Y sum) n5) -> ((sum (Y sum) n5) -> (n5 succ ((Y sum) n4)) -> .... (finite recursion)

我怎么解决这个问题？谢谢。

4

2 回答 2

1

Lambda 演算是一种正常顺序评估语言。因此，它与 Haskell 的共同点多于 Scheme，后者是一种应用顺序评估语言。

在 DrRacket 中，你有一个 dialect #lang lazy，它与你得到的 Scheme 一样接近，但由于它很懒，你有正常的顺序评估：

#!lang lazy

(define (Y f) 
  ((lambda (x) (x x)) 
   (lambda (x) (f (x x)))))

(define sum
  (Y (lambda (r)
       (lambda (n)
         ((is_zero n) n0 (n succ (r (pred n))))))))

(church->number (sum n5))

如果您无法更改语言，则可以将其包装在 lambda 中以使其延迟。例如。

ifr是 arity 1 的函数，lambda 演算中的所有函数都是，then(lambda (x) (r x))是对r. 它将停止无限递归，因为您只获得包装器，并且即使评估是急切的，它也只会在您每次递归时应用它。热切语言中的 Y 组合子称为 Z：

(define (Z f) 
  ((lambda (x) (x x)) 
   (lambda (x) (f (lambda (d) ((x x) d))))))

如果你想在 Scheme 中做 Z，例如使用多参数递归函数，你可以使用其余参数：

(define (Z f) 
  ((lambda (x) (x x)) 
   (lambda (x) (f (lambda args (apply (x x) args))))))

((Z (lambda (ackermann)
      (lambda (m n)
        (cond
          ((= m 0) (+ n 1))
          ((= n 0) (ackermann (- m 1) 1))
          (else (ackermann (- m 1) (ackermann m (- n 1))))))))
 3
 6) ; ==> 509
于 2017-08-29T20:08:29.043 回答
1

延迟计算的标准方法是通过 eta-expansion：

(define (Y y) ((lambda (x) (y (x x))) (lambda (x) (y (x x) )) ))
=~
(define (YC y) ((lambda (x) (y (lambda (z) ((x x) z))))
                (lambda (x) (y (lambda (z) ((x x) z)))) ))

因此

((YC sum) n5) 
=
  (let* ((y sum)
         (x (lambda (x) (y (lambda (z) ((x x) z)))) ))
    ((y (lambda (z) ((x x) z))) n5))
= 
  (let ((x (lambda (x) (sum (lambda (z) ((x x) z)))) ))
    ((sum (lambda (z) ((x x) z))) n5))
= 
  ...

并且评估(sum (lambda (z) ((x x) z)))只使用包含自我应用程序的 lambda 函数，但尚未调用它。

扩展将达到目的

(n5 succ ((lambda (z) ((x x) z)) n4))
=
(n5 succ ((x x) n4))    where x = (lambda (x) (sum (lambda (z) ((x x) z))))

并且只有在那时才会执行自我应用程序。

因此，(YC sum) = (sum (lambda (z) ((YC sum) z)))，而不是发散（在评估的应用顺序下）(Y sum) = (sum (Y sum))。

于 2017-08-29T10:30:02.883 回答