Tuesday, February 26, 2008

Three things are needed to support continuation-passing-style programming:
  1. First-class procedure objects or some equivalent.
  2. General tail recursion.
  3. A type system that won't have conniptions if you try to program in CPS.


This last one can be a serious problem. Let me demonstrate with a simple example. Suppose I have a table that can contain aliases for keys. An entry in a table could map a key to a value, or it could map a key to another key. The basic way to probe the table would be with this CPS function:
(define (lookup key table if-alias if-key if-not-found)
   ....)

(lookup 'my-key *the-table*
    (lambda (another-key) ....)
    (lambda (value) ...)
    (lambda () ...))
.
Of course the point of the aliases is to have multiple names sharing the same value, so the typical use would be to perform a chained lookup if you find an alias. You'd have a procedure like this:
(define (chained-lookup key table if-found if-not-found)
  (lookup key table
     (lambda (another-key)
       (chained-lookup another-key table if-found if-not-found))
     if-found
     if-not-found))
.
Scheme is a unityped language. (Bear with me here. I'm going to use the terminology of the static type community.) Both `if-found' and `if-not-found' will produce the same type of object: a `Scheme object'. And whoever consumes the result will expect nothing more nor less. But what if our language has static types?
Chained-lookup clearly produces an object of the same type as lookup, so we'll start there. Lookup consumes a key, a table that maps keys to values or keys, and three procedures that are constrained by the logic of lookup.
lookup: K x Table x (K -> R1) x (V -> R2) x ( - -> R3) -> R
This is a bit nasty. There is a key and value type, K and V respectively, but what are these R1, R2, and R3? The continuations can pretty much compute what they want, so R1, R2, and R3 are the return value types. We know that the lookup will return one of these, so R is the most narrow supertype of R1 R2 and R3. I'm cheating a little bit here. The argument of the continuation K->R1 can accept objects of a narrower subtype than K. So in the type description above, the different types actually express upper and lower limits on the types of the arguments. (The upper limits are co-variant and the lower limits are contra-variant.)
So what about chained lookup? Intuitively it ought to be this:
chained-lookup: K x Table x (V -> R2) x ( - -> R3) -> R
But is chained-lookup calling lookup correctly? What is that first continuation? Intuitively, we know it maps K -> R (where R is the most narrow supertype of R2 and R3), but is the compiler's type system able to deduce or accept this?
Well, that depends. Some languages have pretty complex type systems that can figure out what is going on. Others have ways to decorate your code with type variables (templates or generics). Others have ways to turn off the type checking (casting to void * and back). Or you may be screwed.
The point I'm trying to make here is that even if your language supports first-class procedures and tail recursion, it still might be impractical to write in continuation-passing-style because the type decorations become unmanageable.

No comments: