Representations of Continuations: An exploration using Factorial
Table of Contents
1 Revision History
- Created.
2 Introduction
The purpose of this note is to explore different representations of continuations. To illustrate the transformations, we use as an example, the factorial function.
We start with the factorial written in direct style using
recursion. Then we transform it to CPS. Then we abstract
the representation and application of continuations. They
are still procedures but only apply-k and the continuation
constructors know this. Next, continuations are turned from
procedures to data (records). As an alternative,
continuations are represented as records containing closures
and other continuations.
3 Direct Style
;;; fact: nat? -> nat?
(define fact
(lambda (n)
(if (zero? n)
1
(* n (fact (sub1 n))))))
4 CPS with continuations as procedures
4.1 Factorial in CPS
A value-continuation takes a expressible value (natural
number here). We write a continuation that receives a value
of type T as (k T). Since continuations don't return a
value, we can think of the type (k T) as the `return only
to top-level function' T->ans? where ans? has the effect
of printing a value on the screen and returning that value
to the top level.
A more precise way to think about effects (like I/O to a stream) is using Monads, but we won't be doing that in this course.
;;; factorial with continuations:
;;; fact/k : [nat? (k nat?)] -> ans?
(define fact/k
(lambda (n k)
(if
(zero? n)
(k 1)
(fact/k (sub1 n)
(lambda (v)
(k (* n v)))))))
4.2 Top-level continuation
top-k simply prints the answer, but returns the value (at
the top-level). The return value is used only print the
final value or feed it to a test case.
;;; top-k : (k nat?)
(define top-k
(lambda (v)
(printf "CPS: ans=~a~n" v)
v))
4.3 Factorial top-level interface
Interface to factorial.
;;; nat? -> nat?
(define fact
(lambda (n)
(fact/k n top-k)))
5 Representation independence
Note that fact/k assumes continuations are procedures.
This version introduces explicit operations to construct and
apply a continuation. This isolates any assumptions about
representation to these functions.
5.1 Continuation Constructors
From now on, we will use the notation k? to mean (k
nat?). top-k constructs the top-level continuation.
fact1-k takes a natural and a continuation and constructs
a new continuation.
;;; top-k: [] -> k?
(define top-k
(lambda ()
(lambda (v)
(printf "REP-IND: ans=~a~n" v)
v)))
;;; fact1-k : [nat? k?] -> k?
(define fact1-k
(lambda (n k)
(lambda (v)
(apply-k k (* n v)))))
Note that a continuation maker abstracts out as its formals,
the free identifiers in the body of the continuation being
constructed. For instance, fact1-k has as its formals,
n and k, which are the free identifiers in the body of
the continuation being returned.
5.2 Applying the continuation
Since a continuation is a function, apply-k simply applies
its argument k to the value v.
;;; continuation application
;;; apply-k : [k? nat?] -> ans?
(define apply-k
(lambda (k v)
(k v)))
5.3 Factorial fact/k with representation independence
Note the use of apply-k and make-fact1-k. These
functions help in abstracting the representation of
continuations. Looking at fact/k, there is no need to
assume that fact-k relies on k being a procedure.
;;; fact/k : [nat? k?] -> ans?
(define fact/k
(lambda (n k)
(if
(zero? n)
(apply-k k 1)
(fact/k (sub1 n)
(fact1-k n k)))))
5.4 Top-level factorial interface
;;; fact : nat? -> nat?
(define fact
(lambda (n)
(fact/k n (top-k))))
6 Record representation
Continuations are now represented as data, or more accurately, records.
6.1 Continuation makers
The continuation makers simply gather the free identifiers in a continuation and tag them.
(define-datatype k k? [top-k] [fact1-k (val nat?) (saved-k k?)])
6.2 Applying the continuation
apply-k does the heavy lifting by taking actions based on
the continuation type. Applying a continuation k of type
fact-1-k to a value v entails the following: extract the
saved continuation saved-k and a value val from k and
then apply saved-k to (* val v). So the multiplications
happen at the time of invoking apply-k. Since apply-k
(and in fact all the procedures) are invoked as tail calls,
the second formal to apply-k effectively performs the role
of an accumulator. This becomes evident when we define
a traceable version of apply-k.
(trace-define apply-k
(lambda (c v)
(cases k c
[top-k ()
(printf "DATA-REP: ans=~a~n" v) v]
[fact1-k (val saved-k)
(apply-k saved-k (* val v))])))
6.3 fact/k and fact
There are no changes to these functions. We are cashing in on the investment into abstraction.
7 Closure representation
Each continuation (except the top one) is now seen as a record consisting of a closure followed by a continuation.
7.1 Continuation are records that contain closures
The clo-k constructor takes a closure and a continuation
and returns a new continuation.
(define-datatype k k? [top-k] [clo-k (clo procedure?) (k k?)])
7.2 Applying the continuations: apply-k
The behaviour of apply-k is the same as earlier for
top-k. When holding a continuation of type clo-k, it
extracts the closure into clo and the continuation into
k. Then apply-k simply runs the closure on v and
tail-recursively invokes apply-k.
(define apply-k
(lambda (c v)
(cases k c
[top-k ()
(printf "CC: ans=~a~n" v)
v]
[clo-k (clo k)
(apply-k k
(clo v) ; this is a simple computation
; whose result is passed to the waiting
; continuation k
)])))
Note that apply-k is quite generic: all factorial specific
computation is abstracted away into the the closure clo.
7.3 fact/k
(define fact/k
(lambda (n k)
(if (zero? n)
(apply-k k 1)
(fact/k (- n 1)
(clo-k
(lambda (v) (* n v))
k)))))
Note that the continuation constructed by clo-k employs a
closure whose operations are all simple. clo-k separates
the `simple' closure from the waiting continuation k.
Contrast this with the continuation in the CPS version:
(lambda (v) (k (* n v)))
8 Conclusion
We have seen five different versions of the factorial program. the first is direct style factorial. The CPS style uses continuations as procedures. This representation is abstrated next. Finally continuations are turned into tagged data: as records containing primitive data (natural number), and alteratively as records containing closures. These closures encapsulate simple computations.
Further transformations like transformation to imperative form, register-transformation and the stepper transformation may be done. These are left as exercises.