Recently wrote a toy asynchronous runtime in Racket, inspired by the new OCaml 5 effect system, as an example of where continuations can be useful.
Here's a gist with the full code: https://gist.github.com/sporkl/ebf4e11397249f17477bf2bebb9ace3e
The rest of this page is a more detailed explanation of how this works, assuming a basic knowledge of Scheme or Racket. Note that I'm not an expert in this, and this was largely written for my own curiosity/learning. Please feel free to let me know if any of this seems amiss!
First a brief explanation of continuations. In Racket, continuations can be created with (let/cc k ...) and introduce a function (here named k) into scope for the ....
This function causes (let/cc k ...) to return whatever values the function was applied to. If the function is never applied, it just returns whatever the return value of the ... is.
A few examples:
(let/cc k
(k 5))
; returns 5(let/cc never-use-this-k-for-some-reason
5)
; returns 5(let/cc k
(letrec
([f ; seems like it would loop infinitely... (it recursively calls itself without a base case)
(lambda ()
(begin
(k 5) ; ... but we return 5 from the outer let/cc before it has the chance to
(f)))])
(f)))
; returns 5The last example demonstrates that one use of continuations is to do early returns for recursive functions.
It's also possible to do funky stuff like returning the continuation itself from the let/cc block, which is something that will come in handy.
(let ([cont (let/cc k k)])
(cont cont))
; loops infinitelyHere, the let/cc returns the continuation that causes the let/cc itself to return. This continuation, when called, causes program execution to "rewind" back to the let/cc and have it return instead whatever the continuation is called with. In this example, the continuation is called with itself as an argument, causing the let/cc to return the same continuation every time, resulting in an infinite loop. Because continuations are able to "rewind" like this, they are often considered to be the time travel of programming. In which case this program would be one of those time loop movies I guess.
To demonstrate how continuations are useful, I'll use a toy asynchronous runtime that lets some functions wait while others do work, such that the waiting functions don't get in the way of the working ones. In the real world, waiting functions could be waiting for user input, or for network queries, or the like; because these are doing something besides just executing a program, we call them "effects." But to keep things simple here, the only ones we'll worry about are: doing nothing for a certain number of milliseconds, outputting something, or exiting from the runtime.
Here's some example programs that we'll be able to run:
(run
(list
(lambda (ei)
(begin
(wait 5000 ei)
(output "a" ei)))
(lambda (ei)
(begin
(wait 3000 ei)
(output "c" ei)))
(lambda (ei)
(begin
(wait 500 ei)
(output "b" ei)))))
; outputs "b" "c" "a" (on separate newlines)(run
(list
(lambda (ei)
(letrec
([f
(lambda (x)
(begin
(output x ei)
(f (add1 x))))])
(f 0)))
(lambda (ei)
(begin
(wait 3000 ei)
(exit 'done ei)))))
; prints increasing numbers for 3 seconds
; then stops, returning 'done
The basic idea is that we have functions for producing effects (such as wait) and a function for handling effects. The functions that produce effects will grab a continuation and pass it, along with information about their effect, to a queue of effects. Then they'll pass control over to the effect handling function. The effect handling function (will call it "effect handler" going forward) iterates over the effect queue, handling effects, and returning control of executions back to the functions (by using the provided continuations) as neccesary.
Firstly, defining a representation of effects:
; an effect is one of
; `(exit ,any)
; `(wait-until ,time ,k)
; `(output ,s ,k)
; `(continue ,k)Here we're using tagged lists to hold onto the needed information for effects. As mentioned above, the effects we're enabling here are:
time argument, before calling its continuationHere's some straightforward code for the queue of effects:
(define pop-effect!
(lambda (es)
(match (unbox es)
[`() `(exit (void))]
[`(,a . ,d)
(begin
(set-box! es d)
a)])))
(define queue-effect!
(lambda (e es)
(set-box!
es
(append (unbox es) (list e)))))Note that we have it return an exit effect when there's nothing left in the queue, so that the effect handler stops running
Next up, the functions that create effects and add them to the queue:
(define exit
(lambda (any ei)
(match-let ([`(effect-info ,eh ,es) ei])
(begin
(queue-effect! `(exit ,any) es)
(eh eh)))))
(define wait
(lambda (ms ei)
(match-let ([`(effect-info ,eh ,es) ei])
(let/cc k
(begin
(queue-effect! `(wait-until ,(+ (current-milliseconds) ms) ,k) es)
(eh eh))))))
(define output
(lambda (s ei)
(match-let ([`(effect-info ,eh ,es) ei])
(let/cc k
(begin
(queue-effect! `(output ,s ,k) es)
(eh eh))))))
(define continue
(lambda (ei)
(match-let ([`(effect-info ,eh ,es) ei])
(let/cc k
(begin
(queue-effect! `(continue ,k) es)
(eh eh))))))Note that, beyond the information relevant to their effects, these functions also expect an ei (short for effect info) argument.
Here, it's expected to be a tagged list with two pieces of information: a continuation that jumps to the effect handler (eh), and the effect queue (es).
We need the effect queue so that we can add effects to it, and a continuation to the effect handler so that we can pass control to it.
Also note that that the wait effect function adds a wait-until effect, with a target time calculated by adding the current time to the number of milliseconds that should be waited.
Next up is the effect handler itself:
(define handle-effects
(lambda (es)
(let ([eh (let/cc k k)])
(match (pop-effect! es)
[`(exit ,any) any]
[`(wait-until ,time ,k)
(cond
[(> (current-milliseconds) time)
(begin
(k `(effect-info ,eh ,es))
(eh eh))]
[else
(begin
(queue-effect! `(wait-until ,time ,k) es)
(eh eh))])]
[`(output ,s ,k)
(begin
(println s)
(k `(effect-info ,eh ,es))
(eh eh))]
[`(continue ,k)
(begin
(k `(effect-info ,eh ,es))
(eh eh))]))))
This function takes in the effect queue, then grabs a continuation to the top of its own execution. It then processes the top item in the queue, before jumping back to the top using its continuation. Each effect is handled as follows:
Note that the exit effect would not work properly if we just called effect-handler, rather than jumping to its continuation. This is because we want the exit effect to return from the earliest effect-handler call; if we don't do this, then a piece of code that calls the exit effect before some other code will end up executing the other code. For example, the second example program above ("prints increasing numbers for 3 seconds") wouldn't work properly.
Also note that we provide an effect-info when calling the continuations that return control. This is to "inject" the necessary information into the functions which use effects. I'll explain this more in a bit. The final step is to provide a way to actually run the effect hander:
(define run
(lambda (l)
(let
([initial-effects
(map
(lambda (f)
`(continue ,f))
l)])
(handle-effects (box initial-effects)))))Here, the run function expects a list of functions that each take one argument. It wraps these in continue effects, then uses them as the initial effects list for the effect handler.
Remember that continuations are called the same way as functions. Therefore, defining functions can be used to "manually" create continuations (this should be familiar to those who know about continuation-passing style).
Also, because the functions which queue effects need the effect-info parameter, we take this as an argument to the functions. This is why we "inject" effectinfos in the effect handler above. It might've been clearer to have a "start" effect instead of a "continue" effect, which would be the only one that injects an effect-info. Then effects would be open to have other values when returning, so it would be possible to define e.g. a "read-input" effect. But for this toy example, I don't think it matters too much.
That's about it, hopefully this makes sense. Please feel free to let me know if there's anything I should clarify. Thanks for reading!
Further information: