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)) return 1.

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

Answer 1

我建议检查 DrRacket 步进器中的程序。步进器允许您检查计算中的各个步骤。你甚至可以回去。

唯一的问题是程序不能按原样运行在步进器中。因此，我做了一些细微的改动，希望足够接近。

(define (A k x1 x2)
  (local [(define (B _) (A (- k 1) B x1))]
    (if (< k 2) (x2 '_) (B '_))))

(A 2 (lambda (_) 1) (lambda (_) -1))

程序在正常 Scheme 中为：

(define (A k x1 x2)
  (define (B _) (A (- k 1) B x1))
  (if (< k 2) (x2 '_) (B '_)))

但教学语言要求您使用 local 进行本地定义。我还添加了参数 _ 到 B。它从未被使用过。教学语言至少需要一个参数，所以我添加一个并忽略它。

下面是一步计算方式的屏幕截图：

Answer 2

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

下面开始调用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调用A，它自己和 x1（现在是 B1）。所以调用是 (A 0 B2 B1)，现在新的环境集是：

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

最后，在检查测试为真后，A 调用 x2，即 F1，即 returns 1. 最后！

How Scheme evaluates the man or boy test?