Why compiling with continuations is wrong(-ish)

There are two axes to plot programming languages, eager/lazy and strict/permissive. Eager/lazy are two evaluation models, strict/permissive determines how much a language sticks to the chosen model.

Most languages are very eager, usually except for short-circuited boolean operators, and reasonably strict, the order of evaluation is mostly known. Non-strictness is often exploited by compiler writers to reorder expressions for performance; i.e., one might not know precisely in what order '2*x+3*y' is evaluated but it will be fast.

Lazy languages like Haskell and Clean, are mostly lazy and permissive, entire program fragments might be reordered or made eager due to purity. All for performance reasons.

Order of evaluation is of course important, all programmers need to deal with it - albeit less in pure languages. Compiler writers need to deal with it too, a popular manner of writing a Scheme compiler is to transform to continuation passing style since that will make the order of evaluation explicit but also allows for control flow operators.

Let's dive into that a bit with a small snippet of code.

pyth x y = sqrt (add (pow2 x) (pow2 y))

After transformation to continuation passing style, one ends up with:

pyth' x y cont = pow2' x (\x2 -> pow2' y (\y2 -> add' x2 y2 

                                 (\anb -> sqrt' anb cont)))

This transformation is of course global, all functions get a continuation object as an extra argument, and all functions are defined as complex expressions that pass along continuations. It's also a pretty bad manner of writing a program if it weren't for that this style serves well as an intermediate representation for compilation to a backend since it makes order of evaluation and temporary values explicit. Fantastic, done!

The Egel interpreter internally also uses an intermediate representation prior to outputting to bytecode. Let's look at that.

pyth x y =

    let y2 = pow2 y in

    let x2 = pow2 x in

    let anb = add x2 y2 in sqrt anb

The intermediate representation hoists reducible expressions, redexes, and reducible expressions only, out of the term and binds the results, often called reduxes. And similar to the continuation passing style or administrative normal form, makes the order of evaluation and use of temporary values explicit.

But only redexes -i.e. work- are hoisted out. And control flow is nice, but it was, and it will always be, mostly about communicating clearly to your backend what work needs to be done - in what order is the detail.

And that's where I think continuation passing style, or administrative normal form, went wrong-ish as a backend solution for rewriters; they are answers that will function but also the almost correct but strangely wrong answers to a trivial question: what work needs to be done. And instead of answering that they concentrated on the order or got the work statement wrong. No wonder that naive continuation passing style will state too much to be done. Meanwhile, this intermediate representation also gives a precise answer to what functions consume constant stack space and can be optimized further, i.e., those are the functions that rewrite to exactly one redex.

TL;DR: When developing a rewriter it becomes important what work needs to be done in what order. And hoisting out redexes makes that clear, whereas continuation passing style and administrative normal form give almost correct but wonkish answers.