A continuation represents the control state of computation at a given point during evaluation. Delimited Continuations is a programming mechanism that can be used to implement various control flow constructs. Thermometer continuations implement delimited continuation using exceptions and state, particularly focused on saving and resuming interactive or concurrent computations at specific points; they often require additional context or constructs to be fully realized.

In a 2018 paper, “Capturing the Future by Replaying the Past,” Koppel et al. showed that in any language with exception and state, thermometer continuations can be used. This allows most of the languages to implement thermometer continuations. Koppel provided Java, OCaml and SML reference implementations as part of the paper; Python implementation is available here, where the author devised a way to overcome python generator’s inability to run the continuation multiple times.

A curious notion is that Scala provided a delimited continuation plugin in earlier versions, but it is suspended in Scala 3 due to various technical difficulties, with an intention to add continuation as a new language feature. This intention is in Pre-SIP stage to gather community feedback. The Pre-SIP proposed two options: add a new keyword suspend, or the use of compiler-desugared Suspend context functions.

Since Scala supports Exceptions and state, implementing delimited continuations in the Scala standard library is viable. As this approach is more straightforward and requires the least language changes, this can be the third option. The implementation may shed light to implement a more generalized delimited continuation and other specialized continuations such as Escape Continuations, Backtracking continuations, Coroutine Continuations and Logic continuations, etc.

In this article, we demonstrate that thermometer continuation can be implemented in Scala; we also explain the nuances and twists in the implementation. We justify the implementation through various test scenarios.

Delimited Continuation in Scala

The study of continuation in programming goes way back. It’s not the intention of this article to discuss the history and extent of the research. A detailed explanation can be found here.

Unlike non-delimited continuation that represents the entire rest of the computation from a certain point, delimited continuation is composable—it captures a specific portion of the program, bounded by delimiters, as it allows breaking down complex control flow operations into smaller, manageable, and reusable pieces. This composability makes it easier to combine and stack different control flow constructs in a modular way. Delimited continuations operate within explicit boundaries defined by constructs reset and shift in Scheme. This means we can isolate specific segments of our code for continuation capturing and manipulation.

Implementation varies depending on programming languages. Earlier Scala plugins used reset/shift operators with Continuation Passing Style (CPS) strategy. The plugin transforms the parts of the program contained within a call to reset into continuation-passing form. Within the transformed part of the program, continuations can be accessed by calling shift. We continue using this strategy to implement these operators.

With this strategy, reset{} defines a block that establishes a “boundary” for the continuation; shift{} captures the current continuation up to the nearest enclosing reset and passes it to the function k, k is called like any other function, effectively altering the program’s flow. This paper explains this concept in detail.

For instance, a continuation takes this form:

reset(2 * shift(1 + k(5)))   //”k” replaces up to the nearest “reset”

Shift captures the continuation (* 2 …), and within it, k(5) is called, yields 5. This is substituted by the multiplication 2*5, yields 10. Adding 1 within the shift block, results in 1 + 10. So the evaluation yields 1+ (2*5) = 11.

Writing it in Scala 3, the code looks like this:

reset { 2 * shift { (k: Int => Int) => 1 + k(5) }

Thermometer Continuation

The idea behind thermometer continuations is to implement delimited continuations using exceptions and state. Instead of capturing an intermediate state of the computation directly, thermometer continuations replay the entire computation from the start, guiding it using a recording so that the same thing happens until the captured point.

By saving the current values of past and future onto a stack before each execution, and restoring them afterwards, the algorithm effectively gains the ability to save the state of each execution for replay, until reset{} reaches a value.

If the evaluation inside a reset reaches a call to shift, then the argument of shift is invoked with a delimited continuation k corresponding to the entire evaluation context until the closest reset call.

There are two situations when shift is being called. In one case when shift is being invoked from running the continuation, then state will not be NONE, and it should return the value in state; the second case is when shift is run with continuation, it sets up a continuation, runs shift with that continuation, and passes the result to the enclosing reset by raising an exception.

Thermometer Continuation Implementation in Scala 3

Let’s look at the code to see how thermometer continuation is implemented.

First we define the data structure we will use in the implementation.

Three mutable attributes—future, past and curExpr—are used to capture the current state of the execution: values of future executions, values of past executions, and the function of current execution.

var future = List.empty[Option[A]] var past = List.empty[Option[A]] var curExpr: Option[() =>A] = None

A mutable stack is used as recording of each continuation:

var recording: mutable.Stack[(Option[() => A], List[Option[A]], List[Option[A]])] = mutable.Stack((curExpr, past, future))

An exception is defined to capture the result of an execution:

final private case class Done[A](value: A) extends Exception

Reset() function takes the program body as a function and initiates the execution by passing the function body to thermometer, resets the state to NONE, and runs the body. The function body effectively is the boundary of the continuation.

thermometer(() =>func, List.empty[Option[A]])

Shift() function takes the continuation function as its parameter; if it finds that there is no future execution, an exception is thrown to mark the end of the execution, the exception carries the value of the current execution back to the thermometer:

state.future match case Nil => thermoDone(func) case None :: tail => state.future = tail thermoDone(func)

The exception will be captured in thermometer. When future is exhausted, before throwing the exception, we reverse the future to past for replay, add the value of continuation function to the future (in our implementation, function k()), re-run the thermometer effectively, substitute the continuation function with computation to the nearest reset—as the name of Koppel’s paper suggests, “Capturing the Future by Replaying the Past”:

val newFuture = state.past.reverse val newExpr = state.curExpr.orNull val k = (v: A) => thermometer(newExpr, newFuture :+ Some(v)) state.pushPast(None) throw Done[A](func(k))

Otherwise, the future is consumed, and the result of current execution is pushed to past.

case Some(value) :: tail => state.future = tail state.pushPast(Some(value)) value

Thermometer() function pushes the current execution in the recording, runs the given function body, returns the result in the exception if no more future execution, otherwise, continues to the future.

state.pushRecording(func, funcFuture) try { func() } catch { case Done(e) => e.asInstanceOf[A] } val result = run() state.popRecording() result

The process continues until all the states have been replayed backwards recursively, until the result is returned back to reset() function.

Note that the execution context is passed to reset(), shift() and thermometer() functions implicitly, reducing boilerplates:

(using state:ContinuationState[A])

Testing

Our test covers following scenarios:

  • Basic reset/shift:
reset { 2 * shift { (k: Int => Int) => 1 + k(5) } }

K(5) evaluated as 5, substituted by 2*5, continue the evaluation. The test yields 2*5 + 1 = 11.

  • Multiple parallel continuation functions:
reset { 1 + shift{ (k: Int =>Int) => k(1) * k(2) * k(3) } }

K(1) is substituted as 1+1, k(2) is substituted by 1+2, k(3) is substituted by 1+3. 

The test yields (1+1) * (1+2) * (1+3) = 24.

  • Nested shifts:
1 + reset { 2 + shift { (k: Int => Int) => 3 * shift{(l: Int => Int) => l(k(5))} } }

K(5) is the continuation of the outer shift, thus, it is substituted by 2+5 = 7; l(7) is the continuation function of inner shift, thus, it is substituted by 3* 7. 

The tests yields 1 + (3*(2+5)) = 22.

  • Parallel shifts:
reset { 2 * shift{(k: Int => Int) => 1 +k(5)} + shift{(k: Int => Int) => 2 +k(6)} }

K(5) is substituted by 2*5, the first term is evaluated as 1+2*5 = 11; k(6) is substituted by 11+6; 

The test yields 2 + (((1 + (2*5)) +6)   = 19.

  • Nested continuation function:
reset { 2 * shift { (k: Int => Int) => 1 + k(k(5)) } }

Inner continuation function is evaluated, k(5) is substituted by 2*5 = 10; outer continuation function k(10) is evaluated next, substituted by 2*20, the test yields

1+2*2*5 = 21

  • Nested resets
reset { 1 + shift { (k: Int => Int) => reset{ { 2 * shift{ (l: Int => Int) => l(3) + l(5) + k(4) } } } } }

Continuation function k belongs to the outer reset, substituted by 1+4, l belongs to inner reset, l(3) and l(5) are substituted by 2*3 and 2*5, respectively;  

The test yields (2*3) + (2*5) + (1+4) = 21

  • A continuation function is not present:
reset{ 1 + shift{(k: Int => Int) => 2+3} }

Then a continuation function is not present in shift, continuation does not take place. 

The test yields 2+3 = 5.

  • Answer type other than Int:
reset{ "a" + shift{(k: String => String) => "b" + k("c")} }

We can see that the answer type may be of types other than Int. 

The test yields “b”+(”a”+”c”) = “bac”.

Limitations

Since Scala is statically typed, it is not possible to implement polymorphic types to reset and shift. We have demonstrated that different types can be supported by different type of givens, however, the answer type is static under certain context. We believe this limitation applies to all the statically typed languages.

Summary

In Koppel’s 2018 paper, an interesting idea was demonstrated to implement delimited continuation to any language that supports exceptions and state. We take Scala 3 as the host language and demonstrated the implementation. We demonstrated that despite the simplicity, the implantation covers a wide range of scenarios.

The reference implementation can be found here.

Similar Posts