如何使用方案Lisp实现Lambda演算的迭代? [英] How to implement iteration of lambda calculus using scheme lisp?

问题描述

我正在尝试学习lambda演算和Scheme Lisp.可在此处找到有关Lambda微积分的教程 http://www .inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf .

I'm trying to learn lambda calculus and Scheme Lisp. The tutorial on lambda calculus can be found here http://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf.

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

The problem I'm facing is I don't know how to properly implement iteration.

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

我总是会收到此错误:

正在中止！:超过最大递归深度

Aborting!: maximum recursion depth exceeded

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

I know the problem is about the evaluation order: the scheme interprets (Y sum) first, which results in infinite recursion:

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

我该如何解决这个问题?谢谢.

How can I solve this problem? thanks.

推荐答案

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

The standard way to delay a computation is by 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函数，但尚未调用它.

and evaluating (sum (lambda (z) ((x x) z))) just uses the lambda-function which contains the self-application, but doesn't invoke it yet.

扩展将达到目的

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

，只有在这一点上，才会执行自我申请.

and only at that point will the self-application be performed.

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

Thus, (YC sum) = (sum (lambda (z) ((YC sum) z))), instead of the diverging (under the applicative order of evaluation) (Y sum) = (sum (Y sum)).

这篇关于如何使用方案Lisp实现Lambda演算的迭代?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！