Hacking trampolining CPS

I spent some quality time today trying to hack together a continuation passing style system in Ruby, to clarify some of my thinking. I ended up with something that is more or less a very small interpreter for S expressions, that uses a trampolining CPS interpreter. The language is not in any way complete, such things as assignment isn’t there, there is only one global scope and so on, so the continuations in this system is really not useful for anything except for hacking with it to gain understanding.

As such, I thought people might find it a bit interesting. I wish I’d seen something like this 5 or 10 years ago… Note that this code is extremely hacky and incomplete and bad and whatnot. Be warned. =)

OK, first you need to “gem install sexp”. This provides dead easy parsing of S expressions. Since that wasn’t the main purpose of this code, doing it with a Gem was easier.

The first part of the code we need is the requires, and structures to represent continuations:

require 'rubygems'
require 'sexpressions'

class Cont
  def initialize(k)
    @k = k

class BottomCont < Cont
  def initialize(k, &block)
    @f = block

  def resume(v)

class IfCont < Cont
  def initialize(k, et, ef, r)
    @et, @ef, @r = et, ef, r

  def resume(v)
    evaluate((v ? @et : @ef), @r, @k)

class CallCont < Cont
  def initialize(k, r)
    @r = r

  def resume(v)
    evaluate(v, @r, @k)

class ContCont < Cont
  def initialize(k, v, r)
    @r, @v = r, v

  def resume(v)
    evaluate(@v, @r, v)

class NextCont < Cont
  def initialize(k, ne, r)
    @ne, @r = ne, r

  def resume(v)
    evaluate(@ne, @r, @k)

BottomCont is is what we use to do something at the end of the program. We could print something, or anything else. IfCont is used to implement a conditional. It’s quite easy – once we resume we check the truth value and evaluate the next part based of the result. CallCont will invoke some existing S expressions in a variable. It just takes the value and evaluates that. ContCont is a bit trickier. It will take a value, and then when asked to resume will assume that the parameter to resume is a continuation and invoke that continuation with the value it got earlier. Finally, NextCont is used to implement basic sequencing. It basically just throws away the earlier value and uses the next instead.

The actual code for evaluate and a helper function looks like this:

def evaluate_sexp(sexp)
  cont = BottomCont.new(nil) do |val|
    return val

  env = {
    :haha => proc{|x| puts "calling proc"; 43 },
    :print => proc{|x| puts "printing" },
    :save_cont => proc{|x| puts "saving cont"; env[:saved] = x; true },
    :foo => 42,
    :bar => 33,
    :flux => "(call flux)".parse_sexp.first

  c = evaluate(sexp, env, cont)

  while true
    c = c.call

def evaluate(e, r, k)
  if e.is_a?(Array)
    case e.first
    when :if
      evaluate(e[1], r, IfCont.new(k,e[2],e[3],r))
    when :call
      evaluate(e[1], r, CallCont.new(k, r))
    when :continue
      p [:calling, :continue, e[1]]
      evaluate(e[1], r, ContCont.new(k, e[2], r))
    when :prog2
      evaluate(e[1], r, NextCont.new(k, e[2], r))
    case e
    when :true
      proc { k.resume(true) }
    when :nil
      proc { k.resume(nil) }
    when Symbol
      proc {
        if r[e].is_a?(Proc)
      proc { k.resume(e) }

Here evaluate_sexp is the entry point to the code. We first create a BottomCont that will just return the value. We then create an environment that includes simple values, a function (flux) that calls itself, and some procs that do different things. Finally evaluate is called, and then we repeatedly evaluate the thunk it returns. Since we know that the bottom continuation will return, we can actually invoke this part indefinitely. That is the actual trampolining part, right there.

The evaluate function will check if it’s an array we got, and in that case it will check the first entry and switch based on that, creating IfCont, CallCont, ContCont or NextCont based on the entry. If it’s a primitive value we do something different. As you can see we first check if the value is one of a few special ones, and then if it’s a symbol we look it up in the environment. If the value from the environment is a proc we invoke it with the current continuation, which means the proc can do funky stuff with it. The common thing for all the branches is that they wrap everything they do in a thunk, and inside that thunk call resume on the continuation with the value provided.

Finally we can try it out a bit:

p evaluate_sexp("123".parse_sexp.first) # 123
p evaluate_sexp("bar".parse_sexp.first) # 33
p evaluate_sexp("nil".parse_sexp.first) # nil

p evaluate_sexp("(if quux 13 (if true (if nil 444 555)))".parse_sexp.first) # 555
p evaluate_sexp("(if quux 13 (if true (if nil 444 haha)))".parse_sexp.first)

Here you can see that simple things work as expected.

What about calling the flux function, that will invoke itself?

p evaluate_sexp("(call flux)".parse_sexp.first)

This will actually loop endlessly. In effect, when we add trampolining to a CPS, we in effect get a stack less interpreter, in such a way that we get tail call recursion for free.

Finally, what about the actual continuation stuff? Another way of creating an eternal loop is to do something like this:

p evaluate_sexp("(prog2 save_cont (prog2 print (continue saved 33333)))".parse_sexp.first)

This piece of interesting code will actually loop forever. How? Well, first the prog2 will run the proc in save_cont. This will save the current continuation, and then return true from the proc. Then the next prog2 will be entered, running the print proc. Finally, the final part will be evaluating the continue form, which will take the continuation in saved, invoke that with the value 33333. This will in effect jump back to the first prog2, return 33333 from the call to save_cont and go into the next prog2 again. Looping…

If you use an if statement instead, and return nil from the inner call to the continuation, and add some printing to the IfCont#resume, you can see that that point will only be invoked twice:

p evaluate_sexp("(if save_cont (prog2 print (continue saved nil)) 321)".parse_sexp.first)

This will generate:

[:running, :if, :statement]
[:calling, :continue, :saved]
[:running, :if, :statement]

Here it’s obvious that the if statement runs twice, and that the second time the evaluation turns into false, which makes the final continuation return 321

I hope this little excursion into CPS land was interesting for someone. It’s a quite useful technique to know about, once you wrap your head around it.

In Joy and Sorrow with Continuations

Continuations is one of those topics that tend to crop up now and again. This is not strange, of course, since they happen to be one of the more powerful features of certain languages, but also is one of the most confusing one. I would like to stick my head out and say that continuations are probably up there besides real macros in power. The reason for this is that you can implement so many language features in terms of them.

Since there still seem to be some confusion about them, I’ll write my piece on the. Not just for you readers of course, but more importantly for myself. I intend to get a good grip on continuations in Ruby by writing this (and this is incidentally one of the best ways to learn about something confusing; try to write about).

First of all, exactly what is a continuation? Basically, at every point in the evaluation of an expression, there will be one or more continuations lurking. For example, if we take the very simple expression foo = 13 * (10 – 7). In this place there is 4 interesting continuations waiting. (There are actually 8 of them all in all, but only 4 interesting.) We start by looking at the expression 10 – 7. If we look at the rest of the expression like this: foo = 13 * [] where the square brackets is the place where the result of the expression 10 – 7 will go. What’s actually happening is that those square brackets is the continuation of the complete expression. The result of evaluating 10 – 7 will be injected into the rest of the expression, and that is what the continuation is.

Until now, I have spoken about continuations as a concept. Those of you who know the Ruby interpreter knows that it isn’t coded in continuation-passing style. But it could be, and it doesn’t really matter, since we still have a way to get at the current continuation. So, how should a continuation be represented, though? The way most languages choose to do it, a continuation is nothing but an anonymous closure, which takes one parameter, which is the result to return to the evaluation. In the example above, if we inject the callcc-primitive into the mix, we will have code that looks like this:

foo = 13 * callcc {|c| c.call(10-7) }

His doesn’t really look that spectacular, of course. The above code will have exactly the same effect as the first example, namely binding the variable ‘foo’ with the value 39.

If you want to, you can look at every computation like this. It sometimes helps to imagine that you just wring the evaluation inside out.

So. What can you do with them? Mostly anything, actually. Many parts of Scheme is implemented in CPS (continuation passing style). But for a few concrete things that can be implemented easily: exceptions, throw/catches, breaks, returns, coroutines, generators and much more. As an example, we can implement a return like this:

 def val
callcc do |ret|
1000.times do |v|
if v == 13
bar = val
puts bar

What happens here is exactly the same result as if we had used the keyword return. Most of the other flow control primitives can be implemented this way too.

What has made continuations trendy lately is something called continuation web servers. The idea is to make the statelessness of the web totally transparent by hiding the client round trips inside methods, and these methods save the current continuation, and then breaks of evaluation. When the result from the server arrives, the continuation will be looked up from some session storage, and then restarted again, where it was. Basically, this allows web applications to work more or less exactly the same as a console application. This is very powerful, but as I hope this small post have shown, continuations have much more to give.