Introduction

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.

It's a 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.

Continuations

An expression's continuation is "the computation that will receive the result of that expression". Also, it can be perceived 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 the variable.

(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 set! for example). The call/cc is a shorthand for call-with-current-continuation. Now we can use the value of kont 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 of (call/cc ...)):

(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

If 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 hi and hello will be printed and return value of the whole expression will be 5, however when we resume continuation (kont 10) only hello will be printed and return value will be 5 again.

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.

Continuation-Passing Style

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 simple (* 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 Continuations

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 shift and reset has call-with-prompt and friends.

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.

Conclusion

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.

The good entry point for in-depth materials on the topic are on Oleg Kiselyov's site. More links and examples in Andrew Tropin's personal notes.

Acknowledgments. Thanks to all the great Computer Scientists, Engineers and Writers, who bring the light of knowledge and such power.