News for hackers. Stuff that matters.
Re:How to compile with continuations by larsberg on Thursday January 30, 2014 @11:07AM (#7151363)
For those who are curious why CPS is such a great compiler representation for implementing optimizations, it's because the passes require less analysis complexity. You only have to handle the "call" portion and don't have to worry separately about "return" points (though you've really just converted returns into a call to a new function!).

It sounds trivial, but in practice it dramatically reduces the size of not only optimization passes such as inlining, but it makes analyses that drive optimizations simpler as well (e.g., control-flow analysis). For an example from my experience (Manticore - http://manticore.cs.uchicago.edu/), my pretty coarse CFA analysis on our direct-style IR is about 750 lines of SML code whereas an optimized CFA with three different variants and extra support for environment analysis is only 700 lines of SML.

Re:How to compile with continuations by Flow on Thursday January 30, 2014 @02:56PM (#7152954)
Interesting, do you mean that one can use CPS transforms instead of SSA? I've never written a non-trivial code generator, so please excuse me if the question seem dumb.
Re:How to compile with continuations by lmkg on Thursday January 30, 2014 @03:21PM (#7153106)
SSA and CPS are actually the same thing, in some fashion. I'm not 100% up to speed on the details myself, but as I understand it, CPS is the functional-language form and SSA is the imperative-language form.
Re:How to compile with continuations by larsberg on Thursday January 30, 2014 @05:21PM (#7153735)
The basic result is that if you just CPS-convert a language without first-class continuations (so, no call-CC), all of that is interchangeable with SSA and any optimization written against one IR can be rewritten fairly mindlessly against the other IR.

If you allow first-class continuations in user programs, though, all bets are off and CPS is more expressive.

Richard Kelsey wrote the paper that talks about how to convert between CPS and SSA forms, along with the first-class continuation limitation mentioned above:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.67...

Re:How to compile with continuations by takeoutweight on Thursday January 30, 2014 @04:36PM (#7153499)
A good reference is Andrew Appel's "SSA is functional programming"[1] which discusses the similarities. There are practical differences between SSA, ANF, and CPS, but the similarity at a high level is quite strong.

[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.3...