In case anyone is wondering, "when would I EVER use this (in hand-written code)?", it's a trick that makes DSL (domain specific language) and small language implementation much easier. A great reference for this is Peter Norvig's Paradigms of Artificial Intelligence Programming, when he implements a subset of Prolog and bolsters the functionality using CPS[1].<p>The second, although more
obscure, is that you can use it in languages that do not have "non-local exits" to terminate a deeply nested computation early or return to an earlier point in the call stack. For example, Clojure does not have nonlocal exits, as only the final form of the function is returned. However, using CPS, you can terminate the expression early and return to the original caller without executing the rest of the function. You probably only want to use this in specialized cases though or it may upset your team, they are tricky to debug.<p>Lastly and probably most controversially, you can make an extensible "if" statement using CPS if you are in a dynamic language and you have no other tools to do so. Admittedly I do sometimes use this in ClojureScript. This allows you to write "append only" code without continually growing the "cond". Again, most teams don't like this, so it depends on the circumstances, but might be
nice to have in your back pocket if you need it.<p>[1]: <a href="https://github.com/norvig/paip-lisp/blob/main/docs/chapter12.md#compiling-logic-programs">https://github.com/norvig/paip-lisp/blob/main/docs/chapter12...</a>
There is actually a way to produce CPS without lots of administrative redexes, which uses the same main trick that "higher-order transform" utilizes: tracking the whether the expression being transformed is in tail context or general context, and translating accordingly — but without using meta-continuations because boy are those mind-boggling.<p>Instead, the normal loops are used, and the subresults are accumulated in some builder structure which is then finalized to produce a complete tree of a CPS expression. The main trick is to figure out just <i>what</i> this builder structure should be, and it turns out it's a tree zipper of sorts!<p>The margins of this comment are not big enough to sketch the whole thing but it's actually not as formidable as it sounds ("tree zipper", wooooh): it's mostly just a stack of tree-building instructions which can be easily extended/completed. An alternative would be to have a <i>mutable</i> CPS expression as the result, and keep appending things into it, but it requires lots of tree traversal and lot of care to not accidentally leave the thing in not quite constructed state which is way too easy in my experience.<p>I think I'll make and publish a gist with it when I get home because I don't believe I've ever seen it done this way anywhere.
> If you don’t want to do any of this trampoline stuff, you can also do the One Big Switch approach which stuffs each of the funs and conts into a case in a massive switch statement. Calls become gotos.<p>Just wanted to add that this is very similar to how async/await JavaScript code was compiled for runtimes that didn't support generators back in the day: <a href="http://facebook.github.io/regenerator/" rel="nofollow">http://facebook.github.io/regenerator/</a>
CPS is a cool technique, and makes advanced constructs like call/cc trivial to implement. Using CPS techniques in code can feel like magic.<p>But CPS isn't really the state of the art for functional compilers anymore. It's complex for a human to read and hard to optimize. Something like A-normal form is much easier to work with for a compiler intermediate representation<p><a href="https://en.wikipedia.org/wiki/A-normal_form" rel="nofollow">https://en.wikipedia.org/wiki/A-normal_form</a>
The author references [scrapscript](<a href="https://scrapscript.org/" rel="nofollow">https://scrapscript.org/</a>), hopefully we'll hear more about it.