Continuations in our language

In the Generators section, we saw how Racket’s let/cc construct can enable us to express the idea of generators, a concept found in other languages like Python and Javascript.

Our language so far does not have an equivalent construct. How can we add such a construct to our language without this construct being present in the “host” language? i.e. if Racket didn’t have let/cc, can we still add this as a capability to our language? If so, how and how would it change our language?

Why shouldn’t we use Racket’s let/cc?

Because we don’t learn anything about its nature if we simply borrow the underlying Racket construct into our language. Also, we’ll not know how to implement it in a language that does not provide the construct. This is the same reason we didn’t use Racket’s box construct to implement Mutations in our language.

So far, all our functions (values of type FnV) take a Val and produce a Val. Reproducing these types below for convenience of reference.

(struct (e) fn ([arg : Symbol] [body : e])
    #:transparent)
(struct id ([sym : Symbol])
    #:transparent)
(struct (e) app ([fexpr : e] [valexpr : e])
    #:transparent)

(struct FnV ([env : Env] [arg : Symbol] [body : ExprCore])
    #:transparent)
(struct Val (U GenV FnV Real))

(define-type Env (-> Symbol Val))

(: interp (-> Env ExprCore Val))
(define (interp env expr)
  (match expr
    ...
    [(id sym)
     (lookup env sym)]
    [(fn arg body)
     (FnV env arg body)]
    [(app fexpr valexpr)
     (match-let ([(FnV denv arg body) (fnv (interp env fexpr))]
                 [v (interp env valexpr)])
         (interp
            (extend denv arg v)
            body))]
    ...))

We may model the continuations made available by let/cc as functions that do not have a return value in Racket, for simplicity – i.e. as the type (-> Val Void). To get access to these continuations without having to use let/cc, we’ll have to transform our interpreter into its CPS-style or “/ret” form.

(: interp/ret (-> Env ExprCore (-> Val Void) Void))
(define (interp/ret env expr return)
  (match expr
    [(konst v)
     (return (GenV (a:konst v)))]
    ...
    [(id sym)
     (return (lookup env sym))]
    [(fn arg body)
     (return (FnV env arg body))]
    [(app fexpr valexpr)
     (interp/ret env fexpr
       (λ (fv)
         (match-let ([(FnV denv arg body) (fnv fv)])
           (interp/ret env valexpr
             (λ (v)
               (interp/ret
                 (extend denv arg v)
                 body
                 return))))))]
    ...))

Adding letcc

Now we’re ready to add a letcc construct to our language analogous to Racket’s because we have the continuations at any point available via the return argument of the interp/ret procedure.

(struct (e) letcc ([cont : Symbol]
                   [body : ExprCore])
    #:transparent)

(struct ContV ([fn : (-> Val Void)]))

(define-type Val (U GenV FnV Real ContV))

We need to interpret the letcc term, as well as be ready to apply a ContV type procedure to a value in addition to a FnV type procedure.

(define (interp/ret env expr return)
  (match expr
    ...
    [(letcc cont body)
     (interp/ret
       (extend env cont (ContV return))
       body
       return)]
    [(app fexpr valexpr)
     (interp/ret env fexpr
       (λ (fv)
         (match fv
           [(FnV denv arg body)
            (interp/ret env valexpr
              (λ (v)
                (interp/ret
                  (extend denv arg v)
                  body
                  return)))]
           [(ContV k)
            (k v)]
           [_ (error "Invalid function")])))]
    ...))

Note that the continuation call occurs in the tail position - i.e. as the final step of the interpreter and the return argument does not get used in that case - i.e. the whole “stack” gets thrown away and replaced by what the continuation represents instead. This is why such a call is often referred to as a “continuation jump” – you “jump” to another point in the history of evaluation that you’d saved away as the continuation.

Term: “Reified continuation”

A “continuation” is not a thing, but a concept that applies to all programming languages – since they all have to deal with sequencing computations and therefore there is always a notion of “what remains to be done right now?” that is applicable at every step. When such a continuation concept is made available as a value in a programming language, it is considered to have been “reified” – “to reify” meaning “to make real”, because now we can manipulate it like any other value which lends it a notion of “a real thing” for us in this context.

So what we’ve done here is to add “reified continuations” to our language.

Reflection

We’re now exposing a raw Racket lambda function to our interpreter. Is that a good thing?

We aren’t exposing general lambda procedures from Racket into our language. We’re only introducing the continuation procedures that our interpreter constructs into the language as a ContV value. We could do this equivalently by representing the pending computations as a stack (perhaps using an accumulating list) and that would have the same scope.

Isn’t Racket’s call/cc more fundamental than let/cc? Why didn’t we implement letcc in terms of a callcc?

We could’ve also gone the route of defining callcc analogous to Racket’s call/cc and then defined letcc as syntactic sugar in terms of callcc. That would offer slightly more generality since the procedure receiving the continuation can be reused in multiple contexts, unlike the raw body of letcc. However, the principle is the same and the above code serves to illustrate how to bring such a concept to life in our language. With call/cc, there is an additional layer of lambda to parse and keep in mind which is avoided when using let/cc. This is helpful when learning about continuations (I think). Once you learn that, it is easy to switch to call/cc when you need that extra bit of flexibility.