from Hacker News

Into CPS, Never to Return

by g0xA52A2A on 12/25/24, 7:43 PM with 57 comments

• by upghost on 12/25/24, 8:41 PM

  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].

  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.

  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.

  [1]: https://github.com/norvig/paip-lisp/blob/main/docs/chapter12...

• by Joker_vD on 12/26/24, 2:34 PM

  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.

  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 what this builder structure should be, and it turns out it's a tree zipper of sorts!

  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 mutable 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.

  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.

• by purplesyringa on 12/26/24, 5:37 AM

  > 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.

  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: http://facebook.github.io/regenerator/

• by assbuttbuttass on 12/25/24, 9:22 PM

  CPS is a cool technique, and makes advanced constructs like call/cc trivial to implement. Using CPS techniques in code can feel like magic.

  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

  https://en.wikipedia.org/wiki/A-normal_form

• by childintime on 12/25/24, 9:56 PM

  The author references [scrapscript](https://scrapscript.org/), hopefully we'll hear more about it.

• by _zoltan_ on 12/25/24, 9:07 PM

  I thought I'm going to read a piece about US's Child Protective Services, and clicked. Was a letdown :-)

• by fovc on 12/26/24, 12:00 AM

  It’s also useful in typed languages to introduce an existentially quantified type

• by yapyap on 12/26/24, 3:41 AM

  not gonna lie this title made me think this was gonna be some child protective services horror story or something