Delimited Continuations

本文绝大部分来自 https://gist.github.com/sebfisch/2235780

Delimited continuations manipulate the control flow of programs. Similar to control structures like conditionals or loops, they allow to deviate from a sequential flow of control.

We use exception handling as another example for control flow manipulation and later show how to implement it using delimited continuations. Finally, we show that nondeterminism can also be expressed using delimited continuations.

Exception Handling

Many programming languages provide a mechanism to throw and handle exceptions. When an exception is thrown, the normal flow of control is aborted and a surrounding exception handler is invoked. Exception handling is built into many languages using special keywords to throw and catch exceptions. A (hypothetical) language may provide the following syntax:

try A catch (e -> B)

The result of such an expression is the result of A or, if A throws an exception e, the result of B. e->B表示常见的arrow function，定义了一个匿名lambda表达式。

For example, the result of

try (17+4) catch (e -> 42)

is 21 and the result of

try (17 + throw 4) catch (e -> 42 + e)

is 46. throw 4作为一个单元先算，这有点像lisp，4是throw的参数。

A call to throw transfers control to the surrounding try/catch block which determines the final result. Because try/catch and throw manipulate control flow, they may be called control operators.

Delimited Continuations

Let’s consider a different kind of control operators. 下面添加两条新语法

这两条语法可以互相结合使用。capture A就是直接计算A。如果没特殊情况，返回值就是A。如果A产生了某种effect，如第二条语法定义的escape effect，那么capture这个作用域会计算这个escape effect，于是capture A的最终返回值就成了B。Inside B it is possible to continue the computation of A: if B contains a call continue C then the computation of A is continued using C as result of the call to escape. 直接用escape (c -> B)也可以，不一定要包在capture里面。但你一定是在某个上下文中运行escape，若如此做，escape会把当前上下文的信息保存在c，然后跳到更上层的通过capture创建的上下文。

这很像stackful coroutine。yield语句直接暂停当前程序，一层层往上停，直到当前fiber的创建者（Fiber.new的函数体），把控制权交给它。

Figure 1的语法没有对B作任何要求——它不需要使用c。但如果要用capture、escape模拟stackful coroutine，B大概需要返回一个tuple (x,y)，x是yield的那个值，然后y是一个function，evaluate y就表示继续刚才的计算。这就要求B一定会使用c，因为c保存了刚才的计算状态。

The way capture and escape modify control flow is best explained using examples.

The result of

capture (2 * escape (_ -> 42))

is 42 because calling escape inside capture changes the result of the call to capture to the result of the function passed to escape. In this case, the original computation inside capture is discarded and the result is replaced by the result of a new computation. _->42仍然是lambda表达式，_ is a discard or throwaway variable。

We can also continue the original computation inside capture by using the c argument of the function passed to escape. The result of

capture (2 * escape (c -> 17 + c 4))

is 25. 就像前面的throw 4，c 4是一个function application or beta reduction，c必须是一个function。那正好啊，escape的前面是2 *，就是一个function。所以整个表达式相当于17 + 2 * 4 = 25。

These control operators may seem confusing to the uninitiated but they are quite powerful. For example, we can use them to implement exception handling. ::=用于定义和化简。

throw e ::= escape (_ -> (h -> h e))
try a catch h ::= (capture (let x = a in _ -> x)) h

The implementation of throw uses escape to abort the surrounding computation. The passed function ignores the given continuation and yields another function that takes an exception handler h and applies it to the thrown exception e. 同样，throw e可以在单独使用，不一定要在try/catch里。若如此做，该语句会中断整个程序，除非外层的某个地方有try/catch。

The implementation of catch uses capture to evaluate the argument a (假设我们的这个语言不用lazy evaluation) If throw is not called inside a then the call to capture returns a function that ignores the exception handler and yields the result of a. 但仔细来想，右手边我们始终会evaluate h，而左手边在a不throw exception的情况下不需要evaluate h。

下面用Figure 2的定义计算两个例子。

try (17+4) catch (e -> 42)
::= (capture (let x = 17+4 in (_ -> x))) (e -> 42)
::= (_ -> 21) (e -> 42)
::= 21

try (17 + throw 4) catch (e -> 42 + e)
::= (capture (let x = 17 + throw 4 in _ -> x)) (e -> 42 + e)
::= (capture (let x = 17 + escape (_ -> (h -> h 4)) in _ -> x)) (e -> 42 + e)
::= (h -> h 4) (e -> 42 + e)   （A）
::= (e -> 42 + e) 4
::= 42 + 4
::= 46

注意Step A，它没有跳步。evaluate escape就是会直接跳到capture所在层。

Nondeterminism and Encapsulated Search

Nondeterministic programs make use of an operator ? to nondeterministically choose one of its argument. For example

0 ? 1

evaluates to 0 or 1 nondeterministically.

In order to collect all values of a nondeterministic expression a nondeterministic language may provide the following syntax

values (() -> A)

注意我们的语言仍旧采用eager evaluation。如果我们写values A，A会被计算，再把结果传入values，非确定性已经产生。The result of such an expression is a set of all possibly nondeterministic results of A. for example, the result of

values (() -> 0 ? 1)

is the set {0,1} because 0 and 1 are all possible results of 0 ? 1.

我们现在尝试用delimited continuations实现? and values。我们先规定原先x ? y ::= x ?? y。x ?? y代表语言的内部非确定性机制，??只是用来表示，不是程序语法的一部分。

x ? y ::= (x ?? y, () -> escape (continue -> continue x ∪ continue y))
values f ::= capture {f ()}

这个部分和原文不一样。因为x ? y的语义要求它返回x、y中的一个值，所以Figure 3把x ? y的返回值视为一个tuple，the first item由语言内部机制产生。

The definition of ? uses the passed continuation twice to execute the surrounding computation with either of the arguments x and y. It then collects the results of both computations using set union. This requires that the surrounding computation returns a set which is ensured by the implementation of values which uses a singleton set as argument of capture.

Example 1:

values (() -> 0 ? 1)
::= capture ((() -> escape (co -> co 0 [latex]a \cup c[/latex] co 1)) ())
::= capture (escape (co -> co 0 ∪ co 1)))
::= {0} ∪ {1}
::= {0,1}

Example 2:

values (()->(1?2)*(3?4))
::= capture ((1?2)*(3?4))
::= capture ((escape(co->co 1 ∪ co 2))*(3?4))
::= 1 * (3?4) ∪ 2 * (3?4)

我在这里用了和原文不同的approach。我们发现最外层的capture消失了，而?操作符仍存在。这说明Figure 3的定义是有错的。

我用Mathematica实现了该语言，其运行结果也证明Figure 3的定义出错。（注：Mathematca自动进行了函数全展开和乘法交换律，在此不深究。）

Apart from nondeterministic choice, nondeterministic languages also provide an operation failure that does not have any results. values (() -> failure) should represent the empty set ∅. Moreover, if failure is part of a computation, as in 1 + failure, then the result of this computation should itself fail to produce results. On the other hand, if failure is an argument of ? then there might still be results from the other argument of ?.

我们可将failure定义为

failure ::= escape (_ -> ∅)

failure与throw比较，相同点是它们都忽视escape的context parameter，所以即使被capture捕获，都不能重回原来的位置继续执行。它们的不同点是，failure更简单，自身不带有参数e。

With this definition the expression 1 + failure indeed does not yield any results:

values (() -> 1 + failure)
::= capture (1 + escape (_ -> ∅))
::= ∅

However, the expression failure ? 42 also does not yield any results. 注意这里的结果甚至不是空集，而是HALT直接停机。

values (() -> failure ? 42)
::= capture (failure ? 42)
::= capture (escape (c -> c failure ∪ c 42))
::= failure ∪ 42
::= escape (_ -> ∅) ∪ 42
::= HALT

This result is not intended. Instead the result should be {42}.

We can fix both the duplication of nested nondeterminism above and the unintended failure observed here by using a different definition of ?:

x ? y ::= escape (co -> capture (co x) ∪ capture (co y))

Further Reading

Usually, the control operators escape and capture are called shift and reset, respectively. A more detailed introduction to delimited continuations with shift and reset can be found in the tutorial notes of a tutorial given at the Continuation Workshop 2011.