Hazards of continuation-passing
So I've been working on converting the Links interpreter to continuation-passing style. It's pretty straightforward but there are some subtleties and it's easy to make a mistake, so I've been writing up little tests and trying those.
The Links interpreter has 30 distinct kinds of expressions, and the old interpret function has an evaluation case for each one. I asked myself how many kinds of continuations we'd need, each with its own handler, and how small I could make that set.
I had the insight (and I think this might have been noted in Definitional Interpreters or someplace) that you need one kind of continuation record for each method of evaluating subexpressions. For example, evaluating binary operators entails evaluating the left operand and the right operand, independently. We only need one kind of continuation record for all binary operators, and the apply_continuation routine basically handles them all the same way. We still need to switch on the specific operation, of course, but we can plug-and-play as many particular binary operators as we want just by writing the code that combines the evaluated sub-expressions.
Let expressions have only two subexpressions (not counting the identifier, which isn't evaluated) but they are different from binary operators, because the subexpressions are not independent. You have to evaluate one of them, then bind an identifier for the evaluation of the other. So Let expressions call for their own kind of continuation record.
List comprehensions require another distinct kind of continuation record, because you have do an unknown number of sub-evaluations. Altogether I have just 12 different continuation records, and I suspect that could be trimmed a bit with some more clever thinking.
For the edification of anyone else out there who's doing a CPS transformation on some code, the most common error is to forget to apply the continuation when you've got a final result. It's easy to write x + y when you mean apply_continuation cont (x + y). To guard against this, I made test cases that don't just test a given operation, they test it in context, to make sure that the operation correctly passes off its result to the surrounding code.