3 ms·
CPS is a tool in the box of language theorists and compiler authors (although I don't know if any non-prototype actually uses CPS). IIRC it is mostly a convenie
by choeger 6y ago
CPS is a tool in the box of language theorists and compiler authors (although I don't know if any non-prototype actually uses CPS). IIRC it is mostly a convenient alternative to SSA. So yes, a compiler can transform your code into CPS to make some other passes simpler.
Just an example from my own research: Say your program has the form of a long prelude followed by a tight loop. The loop cannot easily be changed, but the prelude can (think of languages like prolog, the prelude sets up the model, the loop solves it). At some point during the prelude you want to say: "For now, do this, but if x happens inside the loop, come back here, do that and then go back into the loop!" (e.g., your solver found a solution and you want to add/remove/change predicates). This is conveniently expressed as taking a continuation and passing it into the loop, which continues it when necessary.
- fivhjvf 6y agoTragically, this blog post is not using the words "continuation passing style" to refer to CPS. If you read it you will see that the author is talking about a "style" of code which involves passing multiple lambdas to a function. Why he thinks it is a good idea to refer to this idiom as "continuation passing style" is anybody's guess. It is not CPS. His usage is confusing and to me it seems most likely that he just wants to be seen using a fancy ten-dollar technical term with the ring of prestige. Basically, the kind of blog post that wastes the time of unsuspecting readers.
- tonyg 6y agoYou are mistaken. This is exactly continuation passing style. The two arguments `if-found` and `if-not-found` are continuations of `lookup`. Note that their invocations are in tail position within lookup.
- Darmani 6y agoSML/NJ uses CPS.
- Blikkentrekker 6y agoAnd it's noteably slow due to it; c.p.s. made sense at that time, but modern hardware takes advantage of the existence of a stack much more aggressively. Chicken Scheme also uses it with a novel approach that allows the C stack to become the garbage collector which is still relatively fast as far as I heard.
- samus 6y agoActually, programs in SSA form are a subset of programs in CPS [0] [0] "A correspondence between continuation passing style and static single assignment form" https://www.cs.purdue.edu/homes/suresh/502-Fall2008/papers/kelsey-ssa-cps.pdf https://www.cs.purdue.edu/homes/suresh/502-Fall2008/papers/k...