3 ms·
Warning: I am far from being knowledgeable about compilers. That being said... SSA is actually more appropriate for imperative languages. Compilers for functio
by catwell 14y ago
Warning: I am far from being knowledgeable about compilers. That being said...
SSA is actually more appropriate for imperative languages. Compilers for functional languages tend to use other intermediate representations such as CPS / ANF. They are "equivalent" though: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.34.3282&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.34....
- cwzwarich 14y agoIn practice, working with them can be quite different. In a lexically scoped representation (either ANF or CPS) you have to preserve lexical scoping after each transformation, which can be pretty annoying if you want to do optimizations in their full generality. With SSA, you have to preserve dominance, but you don't have to update the dominator tree (the equivalent of the information encoded in the lexical scoping of ANF / CPS) if you don't want to; you can simply recompute it. Of course, the advantage that ANF / CPS have is that they can naturally represent higher-order programs, but for first-order programs they don't really have any advantage over SSA.
- toolslive 14y agoI always considered CPS and SSA to be duals. (Just like FST and Lambda-calculus are duals)
- abecedarius 14y agoWhat do you mean by FST?
- catwell 14y agoIn that context it means Finite State Transducer. Basically it is a FSM (Finite State Machine) that generates an output depending on its input. I don't think you lose too much meaning of his sentence if you replace FST by Turing Machines (the more usual comparison to lambda-calculus).
- abecedarius 14y agoAh, thanks. I thought the comment had some precise dualities in mind, but I guess not? (There is such a correspondence for CPS and SSA, cf Appel's paper.)