Lil*_*ung 5 scheme continuations 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*,以及如何将这些不同版本的方案之间变化的报告,以及不同方案的实现.在试验这个片段时,我做了一些研究,并在此处报告结果.
如果你在精神上完成了这个片段的执行,那么两个问题应该对你很重要:
Q1.初始化子句的顺序x和y评估顺序是什么？
Q2.是否首先评估了所有初始化子句,并缓存了它们的结果,然后是之后的所有赋值x和y执行？或者是否已经评估了一些初始化子句之前的一些分配？
因为letrec,计划报告说Q1的答案是"未指明的".实际上,大多数实现都会以从左到右的顺序评估子句; 但你不应该依赖这种行为.
Scheme R6RS和R7RS引入了一种新的绑定结构letrec*,它确定了从左到右的评估顺序.它在某些其他方面也有所不同letrec,正如我们将在下面看到的那样.
回到letrec过去,该计划报告至少可以追溯到R5RS 似乎指定Q2的答案是"在进行任何分配之前评估所有初始化条款".我说"似乎指明",因为语言并不像它可能需要的那样明确.事实上,许多Scheme实现都不符合这个要求.这就是你的片段中"预期"和"观察"行为之间的差异的原因.
让我们来看看你的片段,记住Q2.首先,我们为两个"位置"(参考单元格)预留x并y绑定.然后我们评估其中一个初始化子句.让我们说这是它的条款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的答案,此时x可能会或可能不会分配0到(再次).
然后我们开始评估(letrec (...) ...)表达式的主体(第二次).现在cont是#f,所以我们得到了(+ x y).这将是(+ 1 0)或者(+ 0 0),取决于在x我们调用保存的延续时是否重新分配0 .
您可以通过使用某些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),并用参数调用了continuation 'new而不是0.
我使用几种不同的"语言模式"在Racket 5.2中运行该片段,也在Chicken 4.7中运行.结果如下.两个实现首先评估了xinit子句,然后评估了y第二个子句,尽管我说这个行为是未指定的.
使用#lang r5rs并#lang r6rs符合Q2规范的球拍,因此我们得到在0调用延续时重新分配给另一个变量的"预期"结果.(当试验r6rs时,我需要将最终结果包装成a display来查看它会是什么.)
这是跟踪输出:
(xinit #<undefined> #<undefined> #f)
(yinit #<undefined> #<undefined> #<continuation>)
(body 0 0 #<continuation>)
(body 0 new #f)
(0 . new)
球拍#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)
现在,至于Scheme报告确实需要什么.以下是R5RS的相关部分:
库语法:(letrec <bindings> <body>)
语法:<Bindings>应该具有形式((<variable1> <init1>)...),<body>应该是一个或多个表达式的序列.<variable>在绑定的变量列表中出现多次是错误的.
语义:<variable>绑定到包含未定义值的新位置,<init>在结果环境中(以某种未指定的顺序)进行计算,每个<variable>都分配给相应的<init>的结果,在生成的环境中计算<body>,并返回<body>中最后一个表达式的值.<variable>的每个绑定都将整个letrec表达式作为其区域,从而可以定义相互递归的过程.
Run Code Online (Sandbox Code Playgroud)(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>而不分配或引用任何 <variable> 的值.如果违反此限制,那么这是一个错误.限制是必要的,因为Scheme通过值而不是名称传递参数.在letrec的最常见用法中,所有<init>都是lambda表达式,并且自动满足限制.
"语义"部分的第一句话听起来要求在评估完所有初始化子句之后发生所有赋值; 但是,正如我先前所说,这并不像它可能那样明确.
在R6RS和R7RS中,对该部分规范的唯一重大改变是增加了以下要求:
不应多次调用每个<init>的延续.
R6RS和R7RS也增加了另一种绑定结构:letrec*.这与letrec两种方式不同.首先,它确实指定了从左到右的评估顺序.相关地,上面提到的"限制"可以稍微放松.现在可以引用已经分配了初始值的变量的值:
必须可以评估每个<init>而不分配或引用<bindings>中跟随它的任何绑定的相应<variable>或<variable>的值.
第二个区别在于我们的Q2.有了letrec*,规范现在要求在评估每个初始化子句之后进行赋值.这是R7RS(草案6)中"语义学"的第一段:
语义:<variable>被绑定到新的位置,每个<variable>按从左到右的顺序分配给评估相应的<init>的结果,<body>在结果环境中进行评估,并且返回<body>中最后一个表达式的值.尽管从左到右的评估和赋值顺序,<variable>的每个绑定都将整个letrec*表达式作为其区域,从而可以定义相互递归的过程.
所以Chicken和Racket使用#lang racket---和许多其他实现 - 实际上似乎是将它们letrec作为letrec*s 来实现.