Letrec 和可重入延续 [英] Letrec and reentrant continuations

问题描述

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

I have been told that the following expression is intended to evaluate to 0, but that many implementations of Scheme evaluate it as 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 的基础知识，但是我能得到这个表达式的详细解释吗?

I must admit that I cannot tell where even to start with this. I understand the basics of continuations and call/cc, but can I get a detailed explanation of this expression?

推荐答案

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

This is an interesting fragment. I came across this question because I was searching for discussions of the exact differences between letrec and letrec*, and how these varied between different versions of the Scheme reports, and different Scheme implementations. While experimenting with this fragment, I did some research and will report the results here.

如果你在精神上完成了这个片段的执行，那么两个问题对你来说应该是突出的:

If you mentally walk through the execution of this fragment, two questions should be salient to you:

第一季度.x 和 y 的初始化子句是按什么顺序计算的?

Q1. In what order are the initialization clauses for x and y evaluated?

第 2 季度.是否首先评估所有初始化子句，并缓存它们的结果，然后执行对 x 和 y 的所有赋值?还是在评估某些初始化子句之前进行了一些赋值?

Q2. Are all the initialization clauses evaluated first, and their results cached, and then all the assignments to x and y performed afterwards? Or are some of the assignments made before some of the initialization clauses have been evaluated?

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

For letrec, the Scheme reports say that the answer to Q1 is "unspecified." Most implementations will in fact evaluate the clauses in left-to-right order; but you shouldn't rely on that behavior.

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

Scheme R6RS and R7RS introduce a new binding construction letrec* that does specify left-to-right evaluation order. It also differs in some other ways from letrec, as we'll see below.

回到 letrec，Scheme 报告至少可以追溯到 R5RS seem 指定 Q2 的答案是在执行任何初始化之前评估所有初始化子句的任务."我说似乎指定"是因为语言并没有像它可能那样明确地说明这一点.事实上，许多 Scheme 实现并不符合这个要求.这就是造成片段预期"和观察到"行为之间差异的原因.

Returning to letrec, the Scheme reports going back at least as far as R5RS seem to specify that the answer to Q2 is "evaluate all the initialization clauses before making any of the assignments." I say "seem to specify" because the language isn't as explicit about this being required as it might be. As a matter of fact, many Scheme implementations don't conform to this requirement. And this is what's responsible for the difference between the "intended" and "observed" behavior wrt your fragment.

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

Let's walk through your fragment, with Q2 in mind. First we set aside two "locations" (reference cells) for x and y to be bound to. Then we evaluate one of the initialization clauses. Let's say it's the clause for x, though as I said, with letrec it could be either one. We save the continuation of this evaluation into cont. The result of this evaluation is 0. Now, depending on the answer to Q2, we either assign that result immediately to x or we cache it to make the assignment later. Next we evaluate the other initialization clause. We save its continuation into cont, overwriting the previous one. The result of this evaluation is 0. Now all of the initialization clauses have been evaluated. Depending on the answer to Q2, we might at this point assign the cached result 0 to x; or the assignment to x may have already occurred. In either case, the assignment to y takes place now.

然后我们开始评估 (letrec (...) ...) 表达式的主体(第一次).cont 中存储了一个延续，因此我们将其检索到 c 中，然后清除 cont 和 set!x 和 y 为 1.然后我们用值 0 调用检索到的延续.这回到最后评估的初始化子句---我们已经假设成为 y 的.然后使用我们提供给延续的参数代替 (call-with-current-continuation (lambda (c) (set! cont c) 0))，并将被分配给 <代码>y.根据对 Q2 的回答，将 0 分配给 x 可能会也可能不会在此时(再次)发生.

Then we begin evaluating the main body of the (letrec (...) ...) expression (for the first time). There is a continuation stored in cont, so we retrieve it into c, then clear cont and set! each of x and y to 1. Then we invoke the retrieved continuation with the value 0. This goes back to the last-evaluated initialization clause---which we've assumed to be y's. The argument we supply to the continuation is then used in place of the (call-with-current-continuation (lambda (c) (set! cont c) 0)), and will be assigned to y. Depending on the answer to Q2, the assignment of 0 to x may or may not take place (again) at this point.

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

Then we begin evaluating the main body of the (letrec (...) ...) expression (for the second time). Now cont is #f, so we get (+ x y). Which will be either (+ 1 0) or (+ 0 0), depending on whether 0 was re-assigned to x when we invoked the saved continuation.

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

You can trace this behavior by decorating your fragment with some display calls, for example like this:

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

我还用 (cons xy) 替换了 (+ xy)，并使用参数 'new 而不是 调用了延续>0.

I also replaced (+ x y) with (cons x y), and invoked the continuation with the argument 'new instead of 0.

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

I ran that fragment in Racket 5.2 using a couple of different "language modes", and also in Chicken 4.7. Here are the results. Both implementations evaluated the x init clause first and the y clause second, though as I said this behavior is unspecified.

带有 #lang r5rs 和 #lang r6rs 的球拍符合 Q2 的规范，因此我们得到了重新分配 0 的预期"结果 调用延续时到另一个变量.(在使用 r6rs 进行试验时，我需要将最终结果包装在 display 中以查看结果.)

Racket with #lang r5rs and #lang r6rs conforms to the spec for Q2, and so we get the "intended" result of re-assigning 0 to the other variable when the continuation is invoked. (When experimenting with r6rs, I needed to wrap the final result in a display to see what it would be.)

这是跟踪输出:

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

带有#lang racket 和Chicken 的球拍不符合这一点.相反，在评估每个初始化子句后，它会被分配给相应的变量.所以当调用 continuation 时，它只会为最终值重新分配一个值.

Racket with #lang racket and Chicken don't conform to that. Instead, after each initialization clause is evaluated, it gets assigned to the corresponding variable. So when the continuation is invoked, it only ends up re-assigning a value to the final value.

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

Here is the trace output, with some added comments:

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

现在，Scheme 报告真正需要什么.以下是 R5RS 的相关部分:

Now, as to what the Scheme reports really do require. Here is the relevant section from R5RS:

库语法:(letrec )

library syntax: (letrec <bindings> <body>)

语法:<绑定>应该有表格(( ) ...),和<身体>应该是一个或多个表达式的序列.这是一个错误对于<变量>在被绑定的变量列表中出现不止一次.

Syntax: <Bindings> should have the form ((<variable1> <init1>) ...), and <body> should be a sequence of one or more expressions. It is an error for a <variable> to appear more than once in the list of variables being bound.

语义:<variable>s 绑定到新位置，保持未定义值，<init>s 在结果环境中进行评估(在某些情况下)未指定的顺序)，每个 <variable>分配给结果对应的<init>，<body>在结果环境中进行评估，并且<body>中最后一个表达式的值是(是)返回.每个绑定<变量>将整个 letrec 表达式作为其区域，使其成为可能定义相互递归的过程.

Semantics: The <variable>s are bound to fresh locations holding undefined values, the <init>s are evaluated in the resulting environment (in some unspecified order), each <variable> is assigned to the result of the corresponding <init>, the <body> is evaluated in the resulting environment, and the value(s) of the last expression in <body> is(are) returned. Each binding of a <variable> has the entire letrec expression as its region, making it possible to define mutually recursive procedures.

(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 的一个限制非常重要:它必须能够评估每个 <init>不分配或引用 any 的值.如果违反此限制，则为错误.限制是必要的因为 Scheme 通过值而不是名称传递参数.在最letrec 的常见用法，所有 都是 lambda 表达式，而自动满足限制.

One restriction on letrec is very important: it must be possible to evaluate each <init> without assigning or referring to the value of any <variable>. If this restriction is violated, then it is an error. The restriction is necessary because Scheme passes arguments by value rather than by name. In the most common uses of letrec, all the <init>s are lambda expressions and the restriction is satisfied automatically.

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

The first sentence of the "Semantics" sections sounds like it requires all the assignments to happen after all the initialization clauses have been evaluated; though, as I said earlier, this isn't as explicit as it might be.

在 R6RS 和 R7RS 中，规范这一部分的唯一实质性变化是增加了一项要求:

In R6RS and R7RS, the only substantial changes to this part of the specification is the addition of a requirement that:

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

the continuation of each <init> should not be invoked more than once.

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

R6RS and R7RS also add another binding construction, though: letrec*. This differs from letrec in two ways. First, it does specify a left-to-right evaluation order. Correlatively, the "restriction" noted above can be relaxed somewhat. It's now okay to reference the values of variables that have already been assigned their initial values:

必须能够评估每个 无需分配或引用相应<变量>的值；或者<变量> 中跟在它后面的任何绑定.

It must be possible to evaluate each <init> without assigning or referring to the value of the corresponding <variable> or the <variable> of any of the bindings that follow it in <bindings>.

第二个不同之处在于我们的 Q2.使用 letrec*，规范现在要求在评估每个初始化子句之后进行赋值.这是来自 R7RS(草案 6)的语义"的第一段:

The second difference is with respect to our Q2. With letrec*, the specification now requires that the assignments take place after each initialization clause is evaluated. Here is the first paragraph of the "Semantics" from R7RS (draft 6):

语义:<变量>被绑定到新的位置，每个<变量>按从左到右的顺序分配给评估结果对应的，在结果中评估环境，以及 <body> 中最后一个表达式的值.是回.尽管是从左到右的评估和分配顺序，但每个<变量>的绑定将整个 letrec* 表达式作为其区域，使得定义相互递归的过程成为可能.

Semantics: The <variable>s are bound to fresh locations, each <variable> is assigned in left-to-right order to the result of evaluating the corresponding <init>, the <body> is evaluated in the resulting environment, and the values of the last expression in <body> are returned. Despite the left-to-right evaluation and assignment order, each binding of a <variable> has the entire letrec* expression as its region, making it possible to define mutually recursive procedures.

So Chicken 和 Racket 使用 #lang racket---以及许多其他实现---似乎实际上将它们的 letrec 实现为 letrec*s.

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

这篇关于Letrec 和可重入延续的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！