A continuation represents the management state of computation at a given level throughout analysis. Delimited Continuations is a programming mechanism that can be utilized to implement varied management stream constructs. Thermometer continuations implement delimited continuation utilizing exceptions and state, notably centered on saving and resuming interactive or concurrent computations at particular factors; they usually require extra context or constructs to be totally realized.
In a 2018 paper, “Capturing the Future by Replaying the Previous,” Koppel et al. confirmed that in any language with exception and state, thermometer continuations can be utilized. This enables many of the languages to implement thermometer continuations. Koppel offered Java, OCaml and SML reference implementations as a part of the paper; Python implementation is obtainable right here, the place the creator devised a option to overcome python generator’s lack of ability to run the continuation a number of occasions.
A curious notion is that Scala offered a delimited continuation plugin in earlier variations, however it’s suspended in Scala 3 as a result of varied technical difficulties, with an intention so as to add continuation as a brand new language function. This intention is in Pre-SIP stage to collect neighborhood suggestions. The Pre-SIP proposed two choices: add a brand new key phrase droop, or using compiler-desugared Droop context features.
Since Scala helps Exceptions and state, implementing delimited continuations within the Scala customary library is viable. As this strategy is extra simple and requires the least language adjustments, this may be the third choice. The implementation could shed mild to implement a extra generalized delimited continuation and different specialised continuations akin to Escape Continuations, Backtracking continuations, Coroutine Continuations and Logic continuations, and many others.
On this article, we reveal that thermometer continuation may be carried out in Scala; we additionally clarify the nuances and twists within the implementation. We justify the implementation via varied take a look at situations.
Delimited Continuation in Scala
The research of continuation in programming goes means again. It’s not the intention of this text to debate the historical past and extent of the analysis. An in depth rationalization may be discovered right here.
Not like non-delimited continuation that represents the whole remainder of the computation from a sure level, delimited continuation is composable—it captures a particular portion of this system, bounded by delimiters, because it permits breaking down complicated management stream operations into smaller, manageable, and reusable items. This composability makes it simpler to mix and stack totally different management stream constructs in a modular means. Delimited continuations function inside express boundaries outlined by constructs reset and shift in Scheme. This implies we will isolate particular segments of our code for continuation capturing and manipulation.
Implementation varies relying on programming languages. Earlier Scala plugins used reset/shift operators with Continuation Passing Fashion (CPS) technique. The plugin transforms the components of this system contained inside a name to reset into continuation-passing type. Inside the remodeled a part of this system, continuations may be accessed by calling shift. We proceed utilizing this technique to implement these operators.
With this technique, reset{} defines a block that establishes a “boundary” for the continuation; shift{} captures the present continuation as much as the closest enclosing reset and passes it to the operate okay, okay known as like every other operate, successfully altering this system’s stream. This paper explains this idea intimately.
For example, a continuation takes this manner:
reset(2 * shift(1 + okay(5))) //”okay” replaces as much as the closest “reset”Shift captures the continuation (* 2 …), and inside it, okay(5) known as, yields 5. That is substituted by the multiplication 2*5, yields 10. Including 1 inside the shift block, ends in 1 + 10. So the analysis yields 1+ (2*5) = 11.
Writing it in Scala 3, the code seems like this:
reset {
2 * shift { (okay: Int => Int) => 1 + okay(5)
}
Thermometer Continuation
The concept behind thermometer continuations is to implement delimited continuations utilizing exceptions and state. As a substitute of capturing an intermediate state of the computation straight, thermometer continuations replay the whole computation from the beginning, guiding it utilizing a recording in order that the identical factor occurs till the captured level.
By saving the present values of previous and future onto a stack earlier than every execution, and restoring them afterwards, the algorithm successfully beneficial properties the power to avoid wasting the state of every execution for replay, till reset{} reaches a worth.
If the analysis inside a reset reaches a name to shift, then the argument of shift is invoked with a delimited continuation okay equivalent to the whole analysis context till the closest reset name.
There are two conditions when shift is being known as. In a single case when shift is being invoked from working the continuation, then state won’t be NONE, and it ought to return the worth in state; the second case is when shift is run with continuation, it units up a continuation, runs shift with that continuation, and passes the outcome to the enclosing reset by elevating an exception.
Thermometer Continuation Implementation in Scala 3
Let’s take a look at the code to see how thermometer continuation is carried out.
First we outline the information construction we’ll use within the implementation.
Three mutable attributes—future, previous and curExpr—are used to seize the present state of the execution: values of future executions, values of previous executions, and the operate of present execution.
var future = Listing.empty[Option[A]]
var previous = Listing.empty[Option[A]]
var curExpr: Choice[() =>A] = None
A mutable stack is used as recording of every continuation:
var recording: mutable.Stack[(Option[() => A], Listing[Option[A]], Listing[Option[A]])] = mutable.Stack((curExpr, previous, future))An exception is outlined to seize the results of an execution:
closing personal case class Achieved[A](worth: A) extends ExceptionReset() operate takes this system physique as a operate and initiates the execution by passing the operate physique to thermometer, resets the state to NONE, and runs the physique. The operate physique successfully is the boundary of the continuation.
thermometer(() =>func, Listing.empty[Option[A]])Shift() operate takes the continuation operate as its parameter; if it finds that there isn’t any future execution, an exception is thrown to mark the tip of the execution, the exception carries the worth of the present execution again to the thermometer:
state.future match
case Nil => thermoDone(func)
case None :: tail =>
state.future = tail
thermoDone(func)
The exception can be captured in thermometer. When future is exhausted, earlier than throwing the exception, we reverse the long run to previous for replay, add the worth of continuation operate to the long run (in our implementation, operate okay()), re-run the thermometer successfully, substitute the continuation operate with computation to the closest reset—because the title of Koppel’s paper suggests, “Capturing the Future by Replaying the Previous”:
val newFuture = state.previous.reverse
val newExpr = state.curExpr.orNull
val okay = (v: A) => thermometer(newExpr, newFuture :+ Some(v))
state.pushPast(None)
throw Achieved[A](func(okay))
In any other case, the long run is consumed, and the results of present execution is pushed to previous.
case Some(worth) :: tail =>
state.future = tail
state.pushPast(Some(worth))
worth
Thermometer() operate pushes the present execution within the recording, runs the given operate physique, returns the outcome within the exception if no extra future execution, in any other case, continues to the long run.
state.pushRecording(func, funcFuture)
strive {
func()
} catch {
case Achieved(e) => e.asInstanceOf[A]
}
val outcome = run()
state.popRecording()
outcome
The method continues till all of the states have been replayed backwards recursively, till the result’s returned again to reset() operate.
Notice that the execution context is handed to reset(), shift() and thermometer() features implicitly, lowering boilerplates:
(utilizing state:ContinuationState[A])Testing
Our take a look at covers following situations:
reset {
2 * shift { (okay: Int => Int) => 1 + okay(5)
}
}
Ok(5) evaluated as 5, substituted by 2*5, proceed the analysis. The take a look at yields 2*5 + 1 = 11.
- A number of parallel continuation features:
reset {
1 + shift{
(okay: Int =>Int) => okay(1) * okay(2) * okay(3)
}
}
Ok(1) is substituted as 1+1, okay(2) is substituted by 1+2, okay(3) is substituted by 1+3.
The take a look at yields (1+1) * (1+2) * (1+3) = 24.
1 + reset {
2 + shift {
(okay: Int => Int) => 3 * shift{(l: Int => Int) => l(okay(5))}
}
}
Ok(5) is the continuation of the outer shift, thus, it’s substituted by 2+5 = 7; l(7) is the continuation operate of internal shift, thus, it’s substituted by 3* 7.
The exams yields 1 + (3*(2+5)) = 22.
reset {
2 * shift{(okay: Int => Int) => 1 +okay(5)} + shift{(okay: Int => Int) => 2 +okay(6)}
}
Ok(5) is substituted by 2*5, the primary time period is evaluated as 1+2*5 = 11; okay(6) is substituted by 11+6;
The take a look at yields 2 + (((1 + (2*5)) +6) = 19.
- Nested continuation operate:
reset {
2 * shift { (okay: Int => Int) => 1 + okay(okay(5)) }
}
Internal continuation operate is evaluated, okay(5) is substituted by 2*5 = 10; outer continuation operate okay(10) is evaluated subsequent, substituted by 2*20, the take a look at yields
1+2*2*5 = 21
reset {
1 + shift {
(okay: Int => Int) => reset{
{
2 * shift{
(l: Int => Int) => l(3) + l(5) + okay(4)
}
}
}
}
}
Continuation operate okay belongs to the outer reset, substituted by 1+4, l belongs to internal reset, l(3) and l(5) are substituted by 2*3 and a couple of*5, respectively;
The take a look at yields (2*3) + (2*5) + (1+4) = 21
- A continuation operate just isn’t current:
reset{
1 + shift{(okay: Int => Int) => 2+3}
}
Then a continuation operate just isn’t current in shift, continuation doesn’t happen.
The take a look at yields 2+3 = 5.
- Reply kind aside from Int:
reset{
"a" + shift{(okay: String => String) => "b" + okay("c")}
}
We are able to see that the reply kind could also be of sorts aside from Int.
The take a look at yields “b”+(”a”+”c”) = “bac”.
Limitations
Since Scala is statically typed, it isn’t potential to implement polymorphic sorts to reset and shift. We’ve got demonstrated that differing types may be supported by totally different kind of givens, nonetheless, the reply kind is static underneath sure context. We consider this limitation applies to all of the statically typed languages.
Abstract
In Koppel’s 2018 paper, an fascinating thought was demonstrated to implement delimited continuation to any language that helps exceptions and state. We take Scala 3 because the host language and demonstrated the implementation. We demonstrated that regardless of the simplicity, the implantation covers a variety of situations.
The reference implementation may be discovered right here.
