The essence of functional languages is that names are created by lambdas, labmdas are first class, and names might not alias themselves (within the same scope, two references to X may be referencing two instances of X that have different values).
The essence of SSA is that names must-alias themselves (X referenced twice in the same scope will definitely give the same value).
There are lots of other interesting differences.
But perhaps the most important difference is just that when folks implement SSA, or CPS, or ANF, they end up with things that look radically different with little opportunity for skills transfer (if you're an SSA compiler hacker then you'll feel like a fish out of water in a CPS compiler).
Folks like to write these "cute" papers that say things that sound nice but aren't really true.
https://gist.github.com/pizlonator/cf1e72b8600b1437dda8153ea...
But even if you used block arguments, it's so very different from a lambda. Lambdas allow dynamic creation of variables, while SSA doesn't. Therefore, in SSA, variables must-alias themselves, while in the lambda calculus they don't. If you think that a block that takes arguments is the same as a lambda because you're willing to ignore such huge differences, then what's the limiting principle that would make you say that two languages really are different from one another?
Remember, all Turing complete languages are "conceptually the same" in the sense that you can compile them to one another
Then you don't understand Phi/Upsilon
When people say equivalent, it is usually not in the mathematical sense, which would be meaningless here because all forms are turing complete anyway.
Take equivalent as--similarity that helps you understand A given you know B, and perhaps some of the wisdom from B translates to A.
You're just overindexing on the fact that block "arguments" are called "arguments". In SSA with block arguments, you can pass data to a block without passing it as an argument. The arguments are just a way of expressing Phis.
And in Phi/Upsilon, this is valid:
MyBlock:
X = Whatever(...)
Upsilon(X, ^Y)
Y = Phi()
These things just aren't the same at all. Saying that they are the same just shows that you don't get it.
> When people say equivalent, it is usually not in the mathematical sense, which would be meaningless here because all forms are turing complete anyway.
But they're not equivalent even in a mathematical sense.
> Take equivalent as--similarity that helps you understand A given you know B, and perhaps some of the wisdom from B translates to A.
If you want to understand these things, then focus on how they are so very different rather than brain damaging yourself into thinking they are similar
But that's what it is. Briefly stated, your "upsilon" is just picking the 'actual' argument for the 'formal' parameter in a matching "phi". That's exactly what a function call does, and this holds even though you've intentionally decoupled the "upsilon" and "phi" nodes from any control-flow "jump" construct.
> Note how I'm using an upsilon to set the shadow variable of a Phi that's in the same block. You can't do that with block arguments.
Classically, the phi node would sit at the top of a block anyway, and this arrangement helps significantly in computing dominator set properties, renaming and use-def chains etc. etc. Giving up that property makes everything more awkward, including proofs of correctness for transformations, minimality, etc.
By that argument, every store instruction is an "argument". And basic block arguments and lambda calculus are equivalent to people storing and loading to memory willy nilly.
As I said before, these equivalence claims are so nonsensical because if you take the arguments to their limits, you end up with all languages being equivalent to one another
> Classically, the phi node would sit at the top of a block anyway, and this arrangement helps significantly in computing dominator set properties, renaming and use-def chains etc. etc. Giving up that property makes everything more awkward, including proofs of correctness for transformations, minimality, etc.
All of those things that Phi-at-top-of-blocks works with also work in the Phi/Upsilon world
It had an immutable IR and literally every one of the dozens of passes made basically an entire copy of it. Needless to say, that was slow and memory hungry. It was difficult to follow the transformation passes unless well-versed in CPS.
We replaced that with a clone of the C1 compiler, C1X, which was basically just a Java rewrite. C1X supposedly still exists in MaxineVM, but has been superceded by the Graal compiler in Truffle/Graal, which is a hybrid CFG/sea-of-nodes style compiler based on SSA.
Yeah, this is what CPS is really all about. It's not like SSA at all.
Also, it's just a dumb way to write a compiler, and so nobody does that to themselves anymore, now that SSA is widely known.
The goofy "hot" takes about how CPS and SSA are the same are usually written by CPS apologists who want to make the rest of us believe that their work on CPS is somehow relevant when it really isn't
That's certainly true of "every one of the dozens of passes made basically an entire copy of it" - that's just a choice of how to implement it, which is an obvious choice if one is coming at it from a functional angle.
These kinds of approaches aren't always as inefficient as one might naively imagine, because there are usually tradeoffs involved - look at Haskell for example, which is capable of producing very performant code despite being largely purely functional. Often, the performance is gained because of the purely functional source code allowing for optimizations during compilation, like stream fusion and so on.
edit: actually even discussed on here
CPS is formally equivalent to SSA, is it not? What are advantages of using CPS o... | Hacker News https://share.google/PkSUW97GIknkag7WY
CPS is usually higher order and SSA usually first order. As in the continuation you're passing in CPS is probably a closure with some state attached. In SSA you'd have expanded that to pass a function and some explicit state argument, making the allocation explicit.
I think the big thing in favour of CPS was it came first but I could be wrong about that. The lambda people came up with CPS and the imperative people came up with SSA. A while later Appel pointed out that they're views on very similar things. https://www.cs.princeton.edu/~appel/papers/ssafun.pdf is worth reading if you haven't seen it yet.
CPS compilers have to do a lot of work to get rid of pessimization due to unnecessary closures. Inlining, contification, and lambda lifting are some of the things they have to do. IIUC SSA compilers don't have to do that, which is their main advantage (i.e., they are naturally faster).
The llvm tutorials I played with (admittedly a long time ago) made it seem like "just allocate everything and trust mem2reg" basically abstracted SSA pretty completely from a user pov.
This naturally leads to the question "what is a functional language?" I've written my thoughts on what FP is at [1]. I argue that FP is about local reasoning and composition. The former is most relevant here: local reasoning means it's easy to reason about code. This is exactly why SSA is used in compiler: it makes it easy for the compiler to reason about code and therefore which optimizations are valid. This is the same argument given in these comments: https://news.ycombinator.com/item?id=45674568 and https://news.ycombinator.com/item?id=45678483