scheme - Letrec 和可重入延续

有人告诉我，以下表达式旨在计算为 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))))

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

最佳答案

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

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

一季度。 x 的初始化子句的顺序是什么？和 y评价？

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

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

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

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

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

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

然后我们开始评估(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 带#lang r5rs和 #lang r6rs符合 Q2 的规范，因此我们得到了重新分配 0 的“预期”结果调用延续时到另一个变量。 (在试验 r6rs 时，我需要将最终结果包装在 display 中以查看结果。)

这是跟踪输出:

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

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

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

(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 的相关部分:

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.

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
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.

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

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

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

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

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)的“语义”的第一段:

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.

所以鸡和 Racket 使用 #lang racket ---以及许多其他实现---实际上似乎实现了他们的 letrec s 为 letrec* s。

关于scheme - Letrec 和可重入延续，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13078165/

scheme - Letrec 和可重入延续

上一篇：r - 多个 ggplots 导致图例问题

下一篇：workflow - 如何在流程图中表示多个线程