Consider the following Scheme expression:

(begin (display "The sum of 32 and 10 is: ") (display 42) (newline))

Let us identify all of the sub-expressions in this expression, annotating them with unique labels:

(begin (display "The sum of 32 and 10 is: ") |k1 k2 k0 (display 42) |k4 k5 k3 (newline)) |k7 k6

Each of these labels identifies a point in a program. One label may be
the continuation of another label. For example, the continuation of
`k7`

is `k6`

. This is because after evaluating the value of
`newline`

, performed by the expression labelled `k7`

, we
continue to apply it in `k6`

.

Which expression has `k0`

as its continuation? It is either the
expression labelled `k1`

or the expression labelled `k2`

.
Scheme does not have a fixed order of evaluation of arguments, though it
does guarantee that they are evaluated in some order. Unlike general
Scheme, continuation-passing style makes evaluation order explicit. In
Guile, this choice is made by the higher-level language compilers.

Let us assume a left-to-right evaluation order. In that case the
continuation of `k1`

is `k2`

, and the continuation of
`k2`

is `k0`

.

With this example established, we are ready to give an example of CPS in Scheme:

(lambda (ktail) (let ((k1 (lambda () (let ((k2 (lambda (proc) (let ((k0 (lambda (arg0) (proc k4 arg0)))) (k0 "The sum of 32 and 10 is: "))))) (k2 display)))) (k4 (lambda _ (let ((k5 (lambda (proc) (let ((k3 (lambda (arg0) (proc k7 arg0)))) (k3 42))))) (k5 display)))) (k7 (lambda _ (let ((k6 (lambda (proc) (proc ktail)))) (k6 newline))))) (k1))

Holy code explosion, Batman! What’s with all the lambdas? Indeed, CPS is by nature much more verbose than “direct-style” intermediate languages like Tree-IL. At the same time, CPS is simpler than full Scheme, because it makes things more explicit.

In the original program, the expression labelled `k0`

is in effect
context. Any values it returns are ignored. In Scheme, this fact is
implicit. In CPS, we can see it explicitly by noting that its
continuation, `k4`

, takes any number of values and ignores them.
Compare this to `k2`

, which takes a single value; in this way we
can say that `k1`

is in a “value” context. Likewise `k6`

is
in tail context with respect to the expression as a whole, because its
continuation is the tail continuation, `ktail`

. CPS makes these
details manifest, and gives them names.