5

有人告诉我，以下表达式的计算结果为 0，但 Scheme 的许多实现将其计算为 1：

(let ((cont #f))
  (letrec ((x (call-with-current-continuation (lambda (c) (set! cont c) 0)))
           (y (call-with-current-continuation (lambda (c) (set! cont c) 0))))
    (if cont
        (let ((c cont))
          (set! cont #f)
          (set! x 1)
          (set! y 1)
          (c 0))
        (+ x y))))

我必须承认，我什至不知道从哪里开始。我了解 continuation 和 的基础知识call/cc，但我能得到这个表达式的详细解释吗？

4

2 回答 2

6

这是一个有趣的片段。letrec我遇到了这个问题，因为我正在寻找关于和之间的确切差异的讨论letrec*，以及这些在不同版本的 Scheme 报告和不同的 Scheme 实现之间如何变化。在试验这个片段时，我做了一些研究，并将在这里报告结果。

如果您在脑海中走过这个片段的执行过程，那么您应该注意两个问题：

Q1。初始化子句的顺序x和y评估顺序是什么？

Q2。是否首先评估所有初始化子句，并缓存它们的结果，然后再进行所有分配x和y执行？还是在评估某些初始化子句之前进行了一些分配？

对于letrec，Scheme 报告说 Q1 的答案是“未指定”。大多数实现实际上会以从左到右的顺序评估子句；但你不应该依赖这种行为。

方案 R6RS 和 R7RS 引入了一个新的绑定结构letrec*，它指定了从左到右的评估顺序。letrec正如我们将在下面看到的，它在其他一些方面也与 不同。

回到letrec，Scheme 报告至少可以追溯到 R5RS似乎指定 Q2 的答案是“在进行任何分配之前评估所有初始化子句”。我说“似乎指定”是因为语言并没有像它可能的那样明确说明这是必需的。事实上，许多 Scheme 实现并不符合这个要求。这就是你的片段中“预期”和“观察到”行为之间差异的原因。

让我们看看你的片段，记住 Q2。x首先，我们为和y绑定两个“位置”（参考单元格）留出空间。然后我们评估其中一个初始化子句。假设它是 for 的子句x，尽管正如我所说，letrec它可能是任何一个。我们将此评估的延续保存到cont. 此评估的结果为 0。现在，根据 Q2 的答案，我们要么立即将该结果分配给 ，要么将其x缓存以稍后进行分配。接下来我们评估另一个初始化子句。我们将其延续保存到cont中，覆盖前一个。这个评估的结果是 0。现在所有的初始化子句都被评估了。根据 Q2 的答案，我们此时可能会将缓存结果 0 分配给x; 或者分配到x可能已经发生。在任何一种情况下，分配到y现在都会发生。

然后我们开始评估表达式的主体(letrec (...) ...)（第一次）。有一个延续存储在 中cont，所以我们将它检索到c，然后清除每个cont和到1。然后我们用值 0 调用检索到的延续。这又回到了最后评估的初始化子句——我们已经假定为'。我们提供给延续的参数然后用于代替, 并将分配给。根据对 Q2 的回答，此时可能会或可能不会（再次）发生 0 的分配。set!xyy(call-with-current-continuation (lambda (c) (set! cont c) 0))yx

然后我们开始计算表达式的主体(letrec (...) ...)（第二次）。现在cont是#f，所以我们得到(+ x y). 这将是(+ 1 0)或，这取决于我们调用保存的延续时(+ 0 0)是否重新分配了 0 。x

您可以通过使用一些调用来装饰您的片段来跟踪此行为display，例如：

(let ((cont #f))
 (letrec ((x (begin (display (list 'xinit x y cont)) (call-with-current-continuation (lambda (c) (set! cont c) 0))))
          (y (begin (display (list 'yinit x y cont)) (call-with-current-continuation (lambda (c) (set! cont c) 0)))))
  (display (list 'body x y cont))
  (if cont
   (let ((c cont))
    (set! cont #f)
    (set! x 1)
    (set! y 1)
    (c 'new))
   (cons x y))))

我还替换(+ x y)为(cons x y), 并用参数'new而不是0.

我使用几种不同的“语言模式”在 Racket 5.2 和 Chicken 4.7 中运行了该片段。这是结果。两种实现都x首先评估 init 子句，然后评估y子句，尽管正如我所说，这种行为是未指定的。

Racket with #lang r5rsand#lang r6rs符合 Q2 的规范，因此我们得到了在0调用延续时重新分配给另一个变量的“预期”结果。（在试验 r6rs 时，我需要将最终结果包装在 adisplay中以查看结果。）

这是跟踪输出：

(xinit #<undefined> #<undefined> #f)
(yinit #<undefined> #<undefined> #<continuation>)
(body 0 0 #<continuation>)
(body 0 new #f)
(0 . new)

Racket with#lang racket和 Chicken 不符合这一点。相反，在评估每个初始化子句之后，它被分配给相应的变量。因此，当调用延续时，它最终只会重新分配一个值给最终值。

这是跟踪输出，并添加了一些注释：

(xinit #<undefined> #<undefined> #f)
(yinit 0 #<undefined> #<continuation>) ; note that x has already been assigned
(body 0 0 #<continuation>)
(body 1 new #f) ; so now x is not re-assigned
(1 . new)

现在，关于计划报告的真正要求。以下是 R5RS 的相关部分：

库语法：(letrec <bindings> <body>)

语法：<Bindings> 应该具有 ((<variable1> <init1>) ...) 的形式，并且 <body> 应该是一个或多个表达式的序列。<variable> 在被绑定的变量列表中出现多次是错误的。

语义：<variable> 被绑定到新的位置，包含未定义的值，<init> 在结果环境中被评估（以某种未指定的顺序），每个 <variable> 被分配给相应 <init> 的结果， <body> 在结果环境中进行评估，并返回 <body> 中最后一个表达式的值。<variable> 的每个绑定都将整个 letrec 表达式作为其区域，从而可以定义相互递归的过程。

(letrec ((even?
          (lambda (n)
            (if (zero? n)
                #t
                (odd? (- n 1)))))
         (odd?
          (lambda (n)
            (if (zero? n)
                #f
                (even? (- n 1))))))
  (even? 88))   
===>  #t

对 letrec 的一个限制非常重要：必须可以在不分配或引用任何<variable> 的值的情况下评估每个 <init>。如果违反此限制，则为错误。该限制是必要的，因为 Scheme 通过值而不是名称传递参数。在 letrec 最常见的用法中，所有 <init> 都是 lambda 表达式，并且自动满足限制。

“语义”部分的第一句听起来像是要求所有的赋值都在所有初始化子句都被评估之后发生；但是，正如我之前所说，这并不像它可能的那样明确。

在 R6RS 和 R7RS 中，对规范这一部分的唯一实质性更改是添加了以下要求：

每个 <init> 的延续不应被多次调用。

不过，R6RS 和 R7RS 还添加了另一个绑定结构：letrec*. 这letrec在两个方面有所不同。首先，它确实指定了从左到右的评估顺序。相应地，上面提到的“限制”可以稍微放宽一些。现在可以引用已经分配了初始值的变量的值：

必须可以评估每个 <init> 而不分配或引用相应 <variable> 的值或 <bindings> 中跟随它的任何绑定的 <variable>。

第二个区别是关于我们的 Q2。有了letrec*，规范现在要求在评估每个初始化子句之后进行分配。这是来自 R7RS（草案 6）的“语义”的第一段：

语义： <variable> 绑定到新的位置，每个 <variable> 以从左到右的顺序分配给评估相应 <init> 的结果，<body> 在结果环境中评估，并且<body> 中最后一个表达式的值被返回。尽管评估和赋值顺序是从左到右，但 <variable> 的每个绑定都将整个 letrec* 表达式作为其区域，从而可以定义相互递归的过程。

So Chicken, and Racket using #lang racket---and many other implementations---seem in fact to implement their letrecs as letrec*s.

于 2012-11-04T15:31:55.913 回答
0

将其评估为 1 的原因是因为(set! x 1). 如果您将 x 设置为 0 而不是 1，那么它将导致零。这是因为存储延续的延续变量cont实际上是为y而不是存储延续，x因为它在 x 之后被设置为 y 的延续。

于 2012-10-26T10:51:00.537 回答