Compiling with Continuations, Continued (2007) [pdf] | Hacker News Reader

Compiling with Continuations, Continued (2007) [pdf]

research.microsoft.com

47 pointschicken_lady8 comments

CPS is formally equivalent to SSA, is it not? What are advantages of using CPS over SSA?

It's not equivalent, but share some aspects. CPS straight forward semantics, but a semantic for SSA must carry path history along as phi-nodes have no local meaning (you must know where you came from).

I never really understood the big deal about SSA as it's just a really weak version of models from the functional world. (Disclaimer: I've worked on both sides of the fence).

Some discussion of the relative strengths and weaknesses here, with references: http://wingolog.org/archives/2011/07/12/static-single-assign...

(Including to the paper here, incidentally.)

The last paragraph of the paper briefly touches on that:

This paper would not be complete without a mention of Static Single Assignment form (SSA), the currently fashionable intermediate representation for imperative languages. As is well known, SSA is in some sense equivalent to CPS (Kelsey 1995) and to ANF (Appel 1998). Its focus is intra-procedural optimization (as with ANF, it’s necessary to renormalize when inlining functions, in contrast to CPS) and there is a large body of work on such optimizations. Future work is to transfer SSA-based optimizations to CPS. We conjecture that CPS is a good fit for both functional and imperative paradigms.

See http://mlton.org/pipermail/mlton/2003-January/023054.html for an in-depth comparison from a compiler hacker experienced with both styles of IR.

A summary is that there is no advantage to CPS, since it is SSA with a scope nesting requirement that gets in the way of some beneficial transformations.

This is an area where the compiler and programming language communities often seem to be talking past each other. In the post you linked, Weeks is talking about CPS and SSA as the datastructures manipulated by optimization algorithms. CPS is interesting primarily as a language in the formal sense of assigning semantics to programs. Whether you choose to represent those programs naively as a tree structure or with an efficient graph representation as in SSA, you're still using CPS.

This paper is really good because, unlike a lot of compiler literature, it treats both semantics and term representation.

Although I take your point about CPS in other disciplines, TFA advocates compiling with continuations. A criticism of its suitability for compilation would seem to be relevant.

Sure, and Weeks is totally correct regarding tree vs. flat representations, but I think identifying CPS with the former and SSA with the latter is misleading. The scoping discipline (respectively, dominator tree) is part of the language whether you represent it as subtrees or leave it implicit.

It would be more accurate to say that SSA is a particularly efficient data structure for representing a subset of CPS terms.

Reply on news.ycombinator.com