4 ms·

No they're not. The essence of functional languages is that names are created by lambdas, labmdas are first class, and names might not alias themselves (within

No they're not. 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.

zozbot234 1y ago
The whole ad-hoc mechanism of phi-nodes in SSA can be replaced by local blocks with parameters. A block that can take parameters is not that different conceptually from a lambda.
- pizlonator 1y ago
  Local blocks with parameters is the gross way to do it. The right way to do it is Phi/Upsilon form. https://gist.github.com/pizlonator/cf1e72b8600b1437dda8153ea3fdb963 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
  - JonChesterfield 1y ago
    Phi/Upsilon is even more obviously equivalent to blocks with parameters than phi nodes were. It's storing to a "shadow variable" that you "load from" in the phi, i.e. it's exactly the same "store to ABI specified location in caller, load from it in callee" as a function call.
    - pizlonator 1y ago
      > Phi/Upsilon is even more obviously equivalent to blocks with parameters than phi nodes were Then you don't understand Phi/Upsilon
      - fooker 1y ago
        It does seem to rhyme with how function calls work under the hood. 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.
        pizlonator 1y ago
        > It does seem to rhyme with how function calls work under the hood. 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() 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. 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
  - titzer 1y ago
    In CS-411 we teach both SSA and parameterized blocks, with more emphasis on SSA. IMHO the main advantage is that phis are connected to their "call" sites and argument values. Blocks aren't first class, there's no need to decouple the names of their inputs from the actual inputs. SSA makes those dataflow connections explicit, which is obviously superior.
titzer 1y ago
I've never been more confused than working on Maxine VM's CPS optimizing compiler.
- antonvs 1y ago
  I've never actually looked at that compiler, so can't comment on it, but have you read Appel's "Compiling with Continuations"? It motivates and explains the process very clearly. Add ANF into the mix and it's a very straightforward, well-defined system - much more so than SSA.
  - titzer 1y ago
    The author of that compiler used that book as a reference in developing it; that book was open on his desk daily. 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.
    - pizlonator 1y ago
      > It had an immutable IR and literally every one of the dozens of passes made basically an entire copy of it. 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
      - antonvs 1y ago
        As I pointed out in another comment, the equivalence is really just about the fact that SSA, CPS, and ANF all name each intermediate value once and avoid mutation. The rest is implementation details. 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.

zozbot234 1y ago

The whole ad-hoc mechanism of phi-nodes in SSA can be replaced by local blocks with parameters. A block that can take parameters is not that different conceptually from a lambda.

pizlonator 1y ago
Local blocks with parameters is the gross way to do it. The right way to do it is Phi/Upsilon form. https://gist.github.com/pizlonator/cf1e72b8600b1437dda8153ea3fdb963 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
- JonChesterfield 1y ago
  Phi/Upsilon is even more obviously equivalent to blocks with parameters than phi nodes were. It's storing to a "shadow variable" that you "load from" in the phi, i.e. it's exactly the same "store to ABI specified location in caller, load from it in callee" as a function call.
  - pizlonator 1y ago
    > Phi/Upsilon is even more obviously equivalent to blocks with parameters than phi nodes were Then you don't understand Phi/Upsilon
    - fooker 1y ago
      It does seem to rhyme with how function calls work under the hood. 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.
      - pizlonator 1y ago
        > It does seem to rhyme with how function calls work under the hood. 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() 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. 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
- titzer 1y ago
  In CS-411 we teach both SSA and parameterized blocks, with more emphasis on SSA. IMHO the main advantage is that phis are connected to their "call" sites and argument values. Blocks aren't first class, there's no need to decouple the names of their inputs from the actual inputs. SSA makes those dataflow connections explicit, which is obviously superior.

titzer 1y ago

I've never been more confused than working on Maxine VM's CPS optimizing compiler.

antonvs 1y ago
I've never actually looked at that compiler, so can't comment on it, but have you read Appel's "Compiling with Continuations"? It motivates and explains the process very clearly. Add ANF into the mix and it's a very straightforward, well-defined system - much more so than SSA.
- titzer 1y ago
  The author of that compiler used that book as a reference in developing it; that book was open on his desk daily. 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.
  - pizlonator 1y ago
    > It had an immutable IR and literally every one of the dozens of passes made basically an entire copy of it. 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
    - antonvs 1y ago
      As I pointed out in another comment, the equivalence is really just about the fact that SSA, CPS, and ANF all name each intermediate value once and avoid mutation. The rest is implementation details. 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.