是什么决定了Scheme延续的外部边界



对于continuation的解释,通常会说continuation代表"程序的其余部分"(或类似的措辞)。但显然存在一个边界,在该边界处,连续性停止收集这些剩余的计算步骤边界是什么?程序的最高级别?还是别的什么?

这些解释往往是从这样一个玩具例子开始的。

(+ 1 (call/cc
(lambda (cc)
(cc 2))))

这等于3,因为(cc 2)的意思是"将2放入由call/cc形式刻出的表达式中的孔中"。该表达式变为(+ 1 2),也就是3

现在考虑这个例子:

(define lc #f)
(+ 1 (call/cc
(lambda (cc)
(set! lc cc)
(cc 2))))
(displayln "done")
(lc 42)

在这里,我们将延续cc存储在变量lc中。在计算表达式之后,我们显示done,并再次使用延续作为(lc 42)。我们得到了什么?

3
done
43

但是…为什么?如果延续是"程序的其余部分",为什么延续不捕获call/cc之后发生的一切,包括对displaylnlc的后续调用?在这种解释下,延续将产生一个无限循环。

很明显,事实并非如此。相反,继续似乎捕获了程序的其余部分,直到它到达一个后续表达式,它忽略了该表达式(以及任何其他表达式)。

但现在考虑这个例子:

(define lc #f)
(define (f)
(displayln (+ 1 (call/cc
(lambda (cc)
(set! lc cc)
(cc 2)))))
(displayln "done"))
(f)
(displayln "outer")
(lc 42)

这种情况下的结果是:

3
done
outer
43
done

也就是说,延续确实捕获了f中的(displayln "done"),尽管在调用f之后它仍然没有捕获(displayln "outer")(lc 42)

最后一个例子——我们将所有内容都转移到一个新函数g:中

(define lc #f)
(define (g)
(define (f)
(displayln (+ 1 (call/cc
(lambda (cc)
(set! lc cc)
(cc 2)))))
(displayln "done"))
(f)
(displayln "outer")
(lc 42))
(g)

这一次,我们得到了前面例子中预测的无限循环:

3
done
outer
43
done
outer
43
···

因此,最初的直觉并不是完全偏离了基础。这只是高层绝望的又一个例子吗?或者,对于延续的程度,有没有更简洁的解释?

短语"最高级别是无望的";通常指的是(1)允许相互递归的单个顶层环境和(2)按顺序扩展和评估每个顶层形式(例如REPL交互)的组合所产生的问题。相反,在一个模块中,整个模块主体被部分展开以首先揭示定义,然后整个环境被用于展开所有表达式。扩展顺序的差异意味着,当扩展器遇到对它的前向引用时,它更有可能已经知道绑定


您对";程序的其余部分";是发明提示的原因之一,分隔延续。例如参见关于";交互式解释器";在";第一课堂提示的理论与实践;(Felleisen,POPL 1988)。

在Racket中,每个REPL交互和每个模块级表单都有一个提示

您可以使用提示来进一步界定call/cc捕获的连续部分。这里有一个小例子:

> (require racket/control)
> (define c #f)
> (list 'a (prompt
(* 1000
(let/cc k
(set! c k)
5))))
'(a 5000)
> (list 'b (c 6))
6000

请注意,在最后的交互中,由于提示,没有(list 'a _)包装器,也没有(list 'b _)包装器,因为捕获的延续中止了使用站点延续的该部分。我们也可以通过使用prompt来保护部分使用站点的延续不被中止:

> (list 'c (prompt (list 'd (c 7))))
'(c 7000)

只有部分";在";提示被丢弃。

人们有时谈论";捕获定界的延续";是错误的和误导性的。在Racket中,所有连续捕获操作,甚至是call/cc,都由提示分隔。不过,一些操作,如controlshift,会捕获可组合的延续,这些延续可以在不中止使用站点延续的情况下使用。因此,Racket基元是call-with-composable-continuation而不是call-with-delimited-continuation

这是与上面相同的示例,但使用control而不是let/cc:

> (require racket/control)
> (define c #f)
> (list 'a (prompt
(* 1000
(control k
(set! c k)
5))))
'(a 5)
> (list 'b (c 6))
'(b 6000)

据我所知,这是Racket中有意为之。module的文档说明:

表达式或定义的每个求值都用默认prompt标记的延续提示(请参阅使用延续提示的调用)包装,并使用一个提示处理程序重新中止并将其参数传播到下一个封闭提示。

我的猜测(这可能是完全错误的)是这样做是为了模仿REPL中的行为。

#lang racket
1
2

打印12,就像:

> 1
1
> 2
2

既然我们有了这个,为每个表达式安装提示似乎是合乎逻辑的下一步

其他没有模块系统的实现似乎具有您所期望的行为。例如,在Guile中,如果运行上面的程序(将displayln更改为display,将call/cc更改为call-with-current-continuation,因为Guile没有这些函数),则会得到3doneouter43doneouter43doneouter...的无限循环。

顺便说一句:据我所知;最高境界是无望的";不引用模块内部的顶层。它指的是模块之外的那些。例如,当您使用REPL时,或者当您使用没有模块系统的实现时。

我猜您是在将其输入到一个文件中,然后将其加载到Scheme解释器中。Scheme解释器并不把它看作一个程序,而是把它看作是一系列主要独立的表达式,这些表达式是它一个接一个地求值的。

在您的第一个示例中,当解释器获取表达式时:

(+ 1 (call/cc
(lambda (cc)
(set! lc cc)
(cc 2))))

它不知道CCD_ 39接下来会到来。因此,当它在那里创建延续时,整个表达式的延续只是对解释器的返回。当最后一个表达式CCD_ 40再次调用延续时;程序的其余部分";在创建延续时,只需执行+1,然后返回Scheme解释器。此时,解释器已经读取了所有的输入流,没有更多的内容可读取,因此没有无限循环。

因此,基本上可以归结为I/O系统具有未被延续捕获的内部状态。它已经读取到输入的末尾,并且继续操作不会倒带该状态位。

最新更新