ImperialViolet

Control flow with continuations (03 Apr 2006)

I've been hacking about with an interpreter for a little language I'm playing with. The end goals (as ever) as suitably vast, but for the moment I'm writing the dumbest interpreter possible. Here's a little snippet which actually runs:

var if = { #test x y# (ifte test x y) }

var cc = { return return }

var while = { #test body#
  var k = cc
  if (test) {
    body return
    k k
  }
}

while { continue 1 } { #break# print }

Here are the rules:

  • { starts a lambda, the arguments are named in between the # symbols
  • The continuation for the current function is called continue for anonymous lambdas and return for named lambdas
  • Symbols a b c are interpreted as calling a with b and c as arguments.
  • ifte returns its second argument if its first argument is true, other it returns its third argument

And the explanation:

if is a simple wrapper around ifte which passed its arguments to it and calls the result. So you pass a value and two callables and one of the callables is run.

cc returns its own return continuation. In Scheme it would look like this:

(lambda (cc) (call/cc (lambda (k) (k k))))

Let's build the while loop up from parts. First, consider a function which is an infinite loop:

var loop = {
  var k = cc
  k k
}

k is the continuation of cc, so if we call it upon itself, cc returns again and returns the same value: k

Now we all a test callable. Each time round the loop we call the test to see if we should continue:

var loop-while = { #test#
  var k = cc
  if (test) {
    k k
  }
}

Then it's just a case of adding a body argument and calling it every time. The body gets a single argument - the return continuation of the while function. If the body calls this it acts the same as a break in a C-like language.