Continuations are quite flexible and powerful mechanism and can be used in a good number of different scenarios: early return, proper tail-recursion, generators, exception handling, coroutines, multiple return values, etc.
GOTO in the world of functional programming: they give a
power to control the flow of execution, but feels much more high
level, more involved and require time to understand.
Continuations were first discovered in 1964 and later rediscovered a few times in different settings by different people. They are first-class citizens and a part of Scheme Language and appears one way or another here and there. It make sense to learn this concept to get a better understanding of Scheme Language and its ecosystem and this article is a brief sum up on the topic.
An expression's continuation is "the computation that will receive the result of that expression". Also, it can be persived as a checkpoint or quick-save, where you can come back later.
(+ 4 (+ 1 2))
The continuation of the expression
(+ 1 2) will be something that
adds 4 to the value, like
(lambda (x) (+ 4 x)) would do, BUT!
continuation is not a function, it doesn't return a value. When
resumed (called), it jumps to the place, where it was captured and
continue the execution of the program from that point and never jumps
back. Let's rewrite the example above, but storing continuation in
(define kont) (+ 4 (call/cc (lambda (k) (set! kont k) (k (+ 1 2))))) ; (+ 4 (+ 1 2)) kont ;; => #<continuation 7f7a1cc269c0>
Contiunations implicitly exist everywhere, but to get it we need to
capture it with
call/cc and store it somewhere (with
call/cc is a shorthand for
call-with-current-continuation. Now we can use the value of
and resume a continuation in a similiar way as we call one-argument
functions (by passing one argument to it, which will be used in place
(kont 6) ;; => 10
However, the big difference here is that continuations change the flow of the execution and doesn't return (as functions do) and thus can't be composed.
(kont (kont 6)) ;; => 10
kont was a function it would return
16 in the example above,
but the continuations are NOT functions. To demonstrate it better,
let's add a few side effects, which print strings.
(begin (display "hi\n") (+ 4 (call/cc (lambda (k) (set! kont k) (k (+ 1 2))))) (display "hello\n") 5)
After evaluation of this expression
hello will be printed
and return value of the whole expression will be
5, however when we
(kont 10) only
hello will be printed and
return value will be
While [undelimited] continuations provide a lot of flexibility and power, the programs written with them are hard to reason about, the perfomance and memory usage can be suboptimal, the continuations themselves are not composable, and better, more generalized alternatives exist. Read more about potential problems in An argument against call/cc.
The simple code snippets above should give a basic understanding of continuations, but more advanced examples available in wikipedia article, Functional Programming in Scheme relevant chapter and The call/cc Yin-Yang Puzzle.
The style of programming in which the execution flow is controlled
explicitly through continuations passed as function argument. The
analogy of callbacks is floating somewhere around. Let's write a
(* 3 (+ 1 2)) expression in CPS:
(define return) (display (call/cc (lambda (k) (set! return k) (k "hi")))) ;; You can think about it somehow like this: ;; (define return (lambda (x) (display x) (exit)) (define (+& a b k) (k (+ a b))) (define (*& a b k) (k (* a b))) (+& 1 2 (lambda (x) (*& x 3 return))) ;; prints 9
There are more examples comparing the direct and continuation-passing styles. In CPS some things, which were implicit in direct style become explicit (returning a value for example), but the code becomes somewhat turned inside-out, more verbose and harder to reason about, so this style of programming is quite uncommon among developers, however it can be useful for some use case (representing intermediate compilation targets, programming language researches, etc).
Delimited continuation (aka prompt) is a generalization of continuation, instead of capturing the context up to the beginning of expression, it captures the context only up to delimiter, also, it returns a value and can be composed in contrast to usual one.
(use-modules (ice-9 control)) ;; for reset and shift (define kont) (* 2 (reset (+ 1 (shift k (set! kont k) (k 5))))) ;; => 12 kont ;; => #<procedure 7f29fdf05040 at <unknown port>:64:17 vals> (kont 3) ;; => 4 (kont (kont 3)) ;; => 5 ;; Example with side effects (* 2 (reset (begin (display "hi\n") (let ((r (+ 1 (shift k (set! kont k) (k 5))))) (display "hello\n") r)))) ;; => 12 ; prints hi hello (kont 3) ;; => 4 ; prints hello (kont (kont 3)) ;; => 5 ; prints hello two times
It's clear from example that
(* 2 <>) is not captured as a part of
continuation and delimited continuation are functions, can be used as
such and thus can be composed. There are different names and
interfaces in different languages, even Guile Scheme in addition to
Dynamic Wind and Continuation Barriers
There are two mechanism, which are tightly related to non-local enters, exits and reenters. Dynamic Wind allows to trigger actions on [re-]enter and exits, it can be useful for setting up or cleaning up resources and maybe some other use cases.
(* 2 (reset (+ 1 (dynamic-wind (lambda () (display "entered\n")) ; on-enter hook (lambda () (shift k (set! kont k) (k 5))) (lambda () (display "exited\n")))))) ; on-exit hook ;; => 12, prints entered exited two times because we call k in shift (kont 3) ;; => 4, prints entered exited
Continuation Barriers prevents non-local enters and exits by erecting the fence, impassable for continuations.
(with-continuation-barrier (lambda () (define tmp #t) (display (+ 1 (call/cc (lambda (k) (set! kont k) 3)))) (when tmp (set! tmp #f) (kont 6)))) ;; prints 4 7 ;; In procedure %continuation-call: invoking continuation would cross continuation ;; barrier: #<continuation 171 @ 7faffed6d800> (kont 3)
It only applies to non-local enters and exits, which tries to cross the barier, if they jump around inside barier they are good and will work without problems.
It's good and sometimes necessary to know about
call/cc to better
understand how things works in Scheme in particular and in programming
in general, however it usually should not be used in production code.
The first-class support for it is a controversial design decision, but
it's already a part of Scheme, so let's just embrace it.
Delimited continuations are a generalization and overall a better alternative to undelimited continuations, however they should be used with a great care as well.
Acknowledgments. Thanks to all the great Computer Scientists, Engineers and Writers, who bring the light of knowledge and such power.