lambda - Scheme 如何评估 man or boy 测试？

Question

这是 Man or boy测试方案代码:

(define (A k x1 x2 x3 x4 x5)
  (define (B)
    (set! k (- k 1))
    (A k B x1 x2 x3 x4))
  (if (<= k 0)
      (+ (x4) (x5))
      (B)))

为了简化评估过程，我改写为:

(define (A k x1 x2)
  (define (B)
    (set! k (+ k -1))
    (A k B x1))
  (if (> 1 k)
      (x2)
      (B)))

我无法理解为什么 (A 2 (lambda () 1) (lambda () -1)) 返回 1。

谁能解释一下 Scheme 解释器是如何一步步计算这个表达式的。如果能附上环境图就更好了:)

Answer 1

这个问题很微妙，一开始我以为这个调用会导致无限循环。但真正的事情是这样的:

下面开始调用F1和F2这两个第一次传给A的函数，也就是

F1 = (lambda() 1)
F2 = (lambda() -1)

因此，在第一次调用 (A 2 F1 F2) 之后，A 建立了以下环境，我们将其命名为 E1:

现在测试为假，所以 A 调用 B1。 B1 首先递减 E1 中的 k，然后再次调用 A，传递 1、自身和 x1 ，即 F1。所以这是用参数替换它们的值的调用:(A 1 B1 F1)。而此次调用(E2)建立的新环境如下图所示:

测试还是假的，所以A调用B2，它先修改E2中的k，然后使用 0、自身和 x1(现在是 B1)调用 A。所以调用是 (A 0 B2 B1)，现在新的环境集是:

现在测试为真，所以A调用x2，也就是B1。现在 B1 在其环境中修改 k(即 E1)，然后用 0 本身调用 A， x1 的值，在 E1 中，是 F1。所以调用是(A 0 B1 F1)，调用建立的环境如下图所示:

最后，在检查测试为真后，A 调用 x2，即 F1，返回 1。最后!