函数定义中的自引用

Question

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

它说阶乘 A 的定义在标准方案中会进入无限循环，但是实现它会给出一个错误，说明阶乘 A 未定义。

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

这是否正确，那么我们如何解释上面的文章呢？谢谢

Answer 1

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

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

它应该在环境 E 中评估 M；让结果为 x.
它应该修改环境 E 以便 p 绑定到 x。

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

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

另一方面，如果我们尝试

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

这确实运行进入了无限循环。这可能是文章作者所寻找的。

Answer 2

从 SICP 的角度来看，这不是一个自引用过程，因为 factorialA 是一个值，而不是过程。

在开发方案评估器的第 4 章 Representing Expressions 中，我们有：

(define (definition-value exp)
  (if (symbol? (cadr exp))
      (caddr exp)
      (make-lambda (cdadr exp)   ; formal parameters
                   (cddr exp)))) ; body

这意味着如果 define 之后的表达式是像 factorialA 这样的原始符号，那么它将立即计算表达式的主体并将其值赋给 factorialA。但如果它是一个像 (factorialA) 或 (factorialA n) 这样的列表，那么它将创建一个 lambda 表达式。当计算 lambda 表达式时，将创建一个过程，这意味着仅在调用该过程时才计算主体。

函数定义中的自引用

Self-reference in function definition

lisp

scheme

scope

y-combinator

sicp