On 2010-05-17, at 4:44 PM, Maxime Chevalier-Boisvert wrote:
The history of T article (http://www.paulgraham.com/thist.html) has some interesting things to say about intermediate representations, and SSA vs CPS in particular. Olin Shivers thinks that CPS representation is better than ANF (A-normal form). He also says that SSA is a rediscovery of CPS representation, under a different notation.
Are you suggesting we use CPS for Tachyon?
No.
I don't think that the SSA formalism having been discovered/invented later than CPS really disqualifies CPS in any way. It has been said that CPS and SSA are (more or less) equivalent. However, I still think CPS is less practical than SSA for imperative languages, and that JavaScript is more like Java, Python or Ruby than it is like Scheme. SSA has the benefit of being more human-readable than CPS too ;)
CPS is just as easy as ANF, as long as you don't indent every continuation. I.e.:
(add x y (lambda (r1) (sub r1 z (lambda (r2) ...
=>
(add x y (lambda (r1) (sub r1 z (lambda (r2) ...
which is just
r1 <= (add x y) r2 <= (sub r1 z) ...
I highly recommend you all read it.
I read it and found the following quote interesting:
"Richard Kelsey took his front end, which was a very aggressive CPS-based optimiser, and extended it all the way down to the ground to produce a complete, second compiler, which he called "TC" for the "Transformational Compiler." His approach was simply to keep transforming the program from one simple, CPS, lambda language to an even simpler one, until the language was so simple it only had 16 variables... r1 through r15, at which time you could just kill the lambdas and call it assembler"
Yes, I've used this technique in one of my compiler classes. The AST is transformed in several passes, and in the end, there is a direct mapping between the variables in the AST and machine registers.
This is similar to what I was suggesting for our IR. Have the front-end produce a CFG with SSA, then analyze, transform and optimize it all the way until we have assembler inside a CFG. I would ideally like for our IR/analysis/optimizations to fit within a model that is as unified as possible. This will make the compiler simpler to implement and extend.
Marc