# Delimited Continuations

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. 下面添加两条新语法

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 4c 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. ::=用于定义和化简。

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。

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

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

values (() -> 0 ? 1)

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

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 $$a \cup c$$ 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)

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 ::= 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))

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.