函数定义中的自引用 [英] Self-reference in function definition

问题描述

在 Y-combinator 的解释中 (https://mvanier.livejournal.com/2897.html),

(定义几乎阶乘(λ(f)(λ (n)(如果(= n 0)1(* n (f (- n 1))))))))(定义阶乘A(几乎阶乘阶乘A))

它说在标准方案中，factorialA 的定义将进入无限循环，但是实现它会出现错误，说 factorial A 未定义.

我认为这是预期的，因为当我们定义时(如果不是使用 lambda)，我们正在评估最终将计算参数的定义，其中一个是尚未定义的相同函数.

这是否正确，那么我们如何解释上述文章?谢谢

解决方案

考虑表达式 (define p M)，其中 M 是一些表达式，p 是一个变量.

假设我们在环境 E 中计算这个表达式.评估 (define p M) 应该做两件事:

1. 它应该在环境E中评估M；令结果为 x.
2. 它应该修改环境E，使p绑定到x.

那么当我们在环境 E 中评估 (define factorialA (almost-factorial factorialA)) 时会发生什么，其中 factorialA 尚未存在定义?

首先，我们尝试在环境 E 中评估 (almost-factorial factorialA).为此，我们首先评估 almost-factorial，它成功了.然后我们评估 factorialA，它失败了，因为 factorialA 没有在环境 E 中定义.因此，整个事情应该会失败.

另一方面，如果我们尝试

(define (returns-factorialA) (almost-factorial (returns-factorialA)))(定义 factorialA(返回-factorialA))

这确实陷入了无限循环.这大概就是这篇文章的作者要找的.

In this explanation of Y-combinator (https://mvanier.livejournal.com/2897.html),

  (define almost-factorial
    (lambda (f)
      (lambda (n)
        (if (= n 0)
            1
            (* n (f (- n 1)))))))


  (define factorialA (almost-factorial factorialA))

it says that the definition of factorialA would go into an infinite loop in standard scheme, however implementing it gives an error saying factorial A isn't defined.

I think this is expected as when we are defining (if not with a lambda) we are evaluating the definition which will end up calculating the arguments, one of which is the same function not yet defined.

Is this correct and how can we explain the above article then? Thanks

解决方案

Consider the expression (define p M), where M is some expression and p is a variable.

Let's suppose we're evaluating this expression in environment E. Evaluating (define p M) should do two things:

1. It should evaluate M in environment E; let the result be x.
2. It should modify environment E so that p is bound to x.

So what should happen when we evaluate (define factorialA (almost-factorial factorialA)) in an environment E where factorialA is not already defined?

First, we try to evaluate (almost-factorial factorialA) in environment E. To do this, we first evaluate almost-factorial, which succeeds. We then evaluate factorialA, which fails because factorialA is not defined in environment E. Thus, the whole thing should be expected to fail.

On the other hand, if we try

(define (returns-factorialA) (almost-factorial (returns-factorialA)))
(define factorialA (returns-factorialA))

This does indeed run into an infinite loop. This is probably what the writer of the article was looking for.

这篇关于函数定义中的自引用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！