All Articles

A Primer On Continuations

Motivation

Suppose there is a function that performs a lot of computation. In order to showcase continuations, this needs to be an inefficient program to make a point.

(define (add-to x)
  (+ (first (range 10))
     (second (range 10))
     (third (range 10))
     (fourth (range 10))
     (fifth (range 10))
     (sixth (range 10))
     (seventh (range 10))
     (eighth (range 10))
     (ninth (range 10))
     (tenth (range 10))
     x))

In this example, calling range 10 repeatedly is highly inefficient. However, it illustrates that programs can consume a lot of resources to achieve their result. Whenever the program needs to calculate a different result, add-to is called using a new value of x. Considering how everything prior to adding x in the program is always the same, there should be a way to store that computation for later use. In other words, the program should be able to go back to that state and continue where it left off.

Continuations

A continuation is the state of a program at a “captured” moment in time during its execution. Using the previous example, the state of the program can be stored and reused for later use.

; Initially empty state
(define stored-state (void))

(define (add-to x)
  (+ (first (range 10))
     (second (range 10))
     (third (range 10))
     (fourth (range 10))
     (fifth (range 10))
     (sixth (range 10))
     (seventh (range 10))
     (eighth (range 10))
     (ninth (range 10))
     (tenth (range 10))
     (let/cc state
       ; Save the state
       (set! stored-state state) x)))

In this other example, executing add-to creates a continuation state and stores it in stored-state for later use. Otherwise, state would be out-of-scope and would never be used.

; (Creates and stores continuation)
(add-to 10) ; => 55

; Use continuation
(stored-state 10) ; => 55
(stored-state 100) ; => 145

As illustrated above, the continuation stored-state can be used repeatedly to try out new outcomes using different values; without the need of recomputing the body of the function add-to. However, there is a drawback to continuations when nesting them within other procedures.

(+ 1000 (stored-state 100)) ; => 145

The output is not 1145 given that continuations change the flow of execution of a program; much like a goto statement would. The program continues exactly where it left off, and loses context of what it was doing. In other words, the program will not resume what it was doing after the continuation finishes.

Summary

Continuations save the state of program mid-way through its execution. They can prevent a program from wasting resources on operations that are expensive or remain the same. They also allow programs to test different values given the state that was saved. However, continuations discard the program’s current state, in favour of the stored one.

Published 7 Dec 2015