Sample CPS transformations

The samples below will parse, transform to CPS and generate JavaScript. You can see how our λanguage compiles to proper JavaScript in continuation-passing style. Indentation of the output is done with UglifyJS (if you look at the page source you'll find that these samples are actually generated by your browser). The code to do this looks like this:

var ast = parse(TokenStream(InputStream(code)));
var cps = to_cps(ast, function(x){ return x });
var out = make_js(cps);

// get beautified output:
out = UglifyJS.parse(out).print_to_string({ beautify: true });

The “toplevel continuation” that we pass to to_cps just returns whatever AST node it gets.

You'll notice in the samples below that the return keyword is meaningless, just as it was in our CPS evaluator. Functions don't return, instead they call the continuation with the result.

Function calls

You can see how each function call injects as first argument a continuation that wraps the rest of the program.

a = foo(10);

→

a = foo(bar(10));

Might be counter-intuitive the fact that bar is obviously called first in the output, while in the source foo appears first. But it's correct. CPS means turning your code inside-out and that's what you do when you're doing asynchronous programming by hand.

→

a = foo(10) + bar(20);

→

Sequences (prog)

a = foo();
b = bar();
c = baz();

Remember, the whole program is parsed into a "prog" node, so this really exemplifies sequences. This one looks okay.

→

foo();
bar();
baz();

However, this one pointlessly repeats the β_R_n variables. To fix this in cps_prog we need to discard the first expression when it has no side effects.

→

Conditionals

Notice how the following two if samples compile exactly the same. This is interesting and it signals a problem.

if foo() then a = 1 else a = 2;

→

a = if foo() then 1 else 2;

→

Here's what we get for consecutive if-s:

a = if foo() then 1 else 2;
b = if bar() then 3 else 4;
c = if baz() then 5 else 6;

The output is technically correct, but the continuation of each if is repeated on both branches, resulting in an explosion of code in the output. Each if multiplies the rest of the code by 2, therefore you can count two a = 1/2, four b = 3/4 and eight c = 5/6 in the output!

→

Functions (lambda)

add = λ(a, b) a + b;

→

dup = λ(x) add(x, x);

You can notice here the lack of tail call optimization. The last (well, only, in our sample) thing that dup does is to call another function (add). That call is said to be in “tail position” because nothing follows after it.

→

Still, the resulted code passes to add a full continuation whose only purpose is to call the original continuation that dup had with the result — β_K(β_R). That whole function could be just replaced with β_K:

dup = function(β_K_1, x) {
  return add(β_K_1, x, x);
};

This is an important and simple optimization that we should do.

Let blocks

let (a = foo(), b = bar(a)) {
  print(a + b);
}

We can notice that the way we currently handle "let" nodes is highly inefficient.

→

The `fib` function

Just to show a sample of a little more meaningful program:

fib = λ(n) {
  if n < 2 then n
  else
    fib(n - 1) +
    fib(n - 2);
};
print(fib(20));

→

Conclusions

So we still have a few issues to fix in order to get a decent language. On top of that, we're back to square one in terms of recursion limit — but the fix is quite easy and we'll use the same infrastructure we built for the CPS evaluator: Execute, Continuation and GUARD. We'll fix a bunch of the issues in the next section directly in the CPS transformer and JS code generator.