7 ms·

I find it somewhat ironic that most mainstream compilers now transform imperative code into a functional language in order to reason about the code.

by willtim 11y ago

richardwhiuk 11y ago
It's not a functional language...
- willtim 11y ago
  There is no rigorous definition of functional programming. But SSA is trying to achieve similar goals. Google the paper "SSA is functional programming" by Andrew Appel if you want to know more.
profquail 11y ago
I wonder if it'd make more sense for the go compiler developers to use ANF (A-normal form [0]) instead of SSA? ANF is less well-known outside of language research but seems like it'd be a better fit given the design of golang. [0]: https://en.wikipedia.org/wiki/A-normal_form https://en.wikipedia.org/wiki/A-normal_form
- tonfa 11y ago
  Doesn't seem easy to translate to it from an imperative language, the wiki page says it's used in functional compilers. Are there examples of ANF used for imperative languages? SSA is fairly well studied, there are many algorithms to transform an IR into SSA and also lots of algorithms for optimizing programs in SSA form.
  - willtim 11y ago
    This paper discusses going from SSA to ANF: http://tinyurl.com/j25xy5t http://tinyurl.com/j25xy5t
  - profquail 11y ago
    ANF is mostly used in functional compilers, but there are plenty of functional languages which aren't purely functional (e.g., Scheme, SML, OCaml) -- which is why I'm wondering if it could be adapted for a more imperative language like go.
- Joof 11y ago
  SSA is extremely well studied and algorithms for it are fast.
Joof 11y ago
Its not that ironic. SSA has the property that it's interference graphs are chordal and thus can be colored (an NP problem) in polynomial time. Aka, we can do optimal register allocation really fast. Among other benefits. It doesn't matter how it's structured, just that it's faster.
- willtim 11y ago
  That's just one advantage of many. Without SSA, you can't even constant fold without doing dataflow analysis. So I would say the structure is very important, that's why everyone is using it now.
geodel 11y ago
Well many functional programing languages have compilers/VM written in C/C++. So it is not ironic but simply use what works for now.
- willtim 11y ago
  C/C++ is not a good choice for writing a compiler. I do not know of any modern functional language compiler that is written in C/C++. But what does this have to do with SSA?
  - geodel 11y ago
    You are right. Sorry for the noise.
- catnaroek 11y ago
  What is typically implemented in C and C++ is runtime systems, not compilers.
  - pjmlp 11y ago
    And that is only as a matter of convenience, as many of those runtimes could be bootstraped as well.
chubot 11y ago
And then your CPU does it again! After all that work, your compiler outputs a totally ordered stream of instructions; then the CPU tries to figure out data dependencies in hardware and execute instructions out of order and in parallel. It seems as though C-like imperative languages and x86 are baked in forever... but the world is actually parallel.
- willtim 11y ago
  Excellent point!
- marssaxman 11y ago
  I've recently been thinking that we are looking at a situation analogous to the one Ben Franklin was in when he identified the two types of electrical charge as "positive" or "negative" pressure in the "electrical fluid" - he took a guess, which happened to be wrong, and ever since we have been stuck describing a surplus of electrons as "negative" and a deficit as "positive". This is no obstacle for the experienced but will remain an eternal hangup for beginners. By analogy, of course, I am suggesting that the Church model of computation might have served us better as a foundation than the Turing model has done, since it seems that everything's turning up lambdas as the technology S-curve for silicon computers continues to flatten out.
  - masak 11y ago
    Or maybe we needed to scale to some point with the Turing model for the Church model to assert itself and prove its merits in comparison. It's a bit more thrilling to think of it that way, as a matter of scale. When space and time resources are scarce, thinking of the computer as a big piece of RAM that we mutate in-place makes the most sense. As we push upwards and outwards into enough resources and a bigger need for parallelism, it suddenly makes more sense to switch perspectives and reason in terms of binding and substitution.
    - marssaxman 11y ago
      That certainly makes sense. I'm just looking ahead over the next couple of centuries and imagining generations of young programmers stumbling over all these ancient vestiges of mutable state and synchronous, batch-driven control flow which will probably still be littered around the roots of our computing systems long after the dominant paradigm has shifted. You can see the same pattern with IO models. We have programming languages descended from 50s-era concepts of computing in which the program drives the machine, but that just isn't true at all. A computer is a passive machine, not an active one: it reacts when you poke it with an interrupt, until it reaches a steady state and settles down again. Operating systems go to a great deal of trouble to simulate the kind of top-down flow control environment our imperative tradition wants to think it is operating in, but in order to get any real performance out of these systems, we all end up building asynchronous, reactive layers on top of the simulated batch-job anyway. We'd all be better off if we flipped the paradigm, imagining the process of building a program not in terms of writing instructions for the computer to perform, but in terms of creating a structure which will react appropriately in response to whichever events may be brought to its attention. Instead, we'll probably still be starting young programmers out with for-loops counting from 1 to 10 and printing the result on an imaginary console for decades to come, even though none of that is even remotely relevant to what's actually happening anymore, and once they've crossed that hurdle they'll promptly begin unlearning all that stuff in order to start getting real work done. On an unrelated note, I spent a while last fall/winter playing around with the idea of a very low level functional language - could we use these techniques in memory-constrained environments too? I didn't find the model I was looking for, but I think it's probably out there, and it would be very interesting to develop a functional/type-safe/immutable language suitable for microcontroller programming, with no garbage collection or implicit allocation. It may be that the Turing model is a better fit for computing in the small, but I suspect that we may find dataflow and functional composition to be useful at all scales. That way of looking at the world has some profound philosophical strength, after all - "you cannot step twice into the same river" and all that.
munificent 11y ago
I wouldn't describe SSA as "a functional language". It was originally designed as an IR for imperative languages, not functional ones. (The functional folks prefer CPS, which really is a functional language.) I think one could read too much into the "single-assignment" part of SSA. Sure, functional languages don't tend to rebind variables either, but that's really all SSA has in common with them. I'm familiar with Appel's "SSA is a functional language" article, but the vibe I got was more than he was trying to build some bridges between the SSA and CPS camps to try to get some cross-pollination going and knowldge sharing between them. I think he could have just as easily called it "CPS is an imperative language", but my hunch is the FP folks are more persnickety and wouldn't have swallowed that as easily as imperative folks would accept the other title.
- willtim 11y ago
  Like Appel, I wasn't entirely serious about it being a "functional language", but I think the point still stands, it is a major step towards a more mathematical program representation ("variables" instead of "assignables"). And just like "functional programming", the primary goal is ease of reasoning. CPS is typically used to handle imperative control structures by impure functional programming languages, so it should indeed be of interest to imperative compiler authors.
- willtim 11y ago
  The paper "A Correspondence between Continuation Passing Style and Static Single Assignment" by Kelsey, suggests SSA has a lot more in common with functional programming than you seem to believe it has.

I find it somewhat ironic that most mainstream compilers now transform imperative code into a functional language in order to reason about the code.

by willtim 11y ago

I find it somewhat ironic that most mainstream compilers now transform imperative code into a functional language in order to reason about the code.

richardwhiuk 11y ago

It's not a functional language...

willtim 11y ago
There is no rigorous definition of functional programming. But SSA is trying to achieve similar goals. Google the paper "SSA is functional programming" by Andrew Appel if you want to know more.

profquail 11y ago

I wonder if it'd make more sense for the go compiler developers to use ANF (A-normal form [0]) instead of SSA? ANF is less well-known outside of language research but seems like it'd be a better fit given the design of golang. [0]: https://en.wikipedia.org/wiki/A-normal_form https://en.wikipedia.org/wiki/A-normal_form

tonfa 11y ago
Doesn't seem easy to translate to it from an imperative language, the wiki page says it's used in functional compilers. Are there examples of ANF used for imperative languages? SSA is fairly well studied, there are many algorithms to transform an IR into SSA and also lots of algorithms for optimizing programs in SSA form.
- willtim 11y ago
  This paper discusses going from SSA to ANF: http://tinyurl.com/j25xy5t http://tinyurl.com/j25xy5t
- profquail 11y ago
  ANF is mostly used in functional compilers, but there are plenty of functional languages which aren't purely functional (e.g., Scheme, SML, OCaml) -- which is why I'm wondering if it could be adapted for a more imperative language like go.
Joof 11y ago
SSA is extremely well studied and algorithms for it are fast.

Joof 11y ago

Its not that ironic. SSA has the property that it's interference graphs are chordal and thus can be colored (an NP problem) in polynomial time. Aka, we can do optimal register allocation really fast. Among other benefits. It doesn't matter how it's structured, just that it's faster.

willtim 11y ago
That's just one advantage of many. Without SSA, you can't even constant fold without doing dataflow analysis. So I would say the structure is very important, that's why everyone is using it now.

geodel 11y ago

Well many functional programing languages have compilers/VM written in C/C++. So it is not ironic but simply use what works for now.

willtim 11y ago
C/C++ is not a good choice for writing a compiler. I do not know of any modern functional language compiler that is written in C/C++. But what does this have to do with SSA?
- geodel 11y ago
  You are right. Sorry for the noise.
catnaroek 11y ago
What is typically implemented in C and C++ is runtime systems, not compilers.
- pjmlp 11y ago
  And that is only as a matter of convenience, as many of those runtimes could be bootstraped as well.

chubot 11y ago

And then your CPU does it again! After all that work, your compiler outputs a totally ordered stream of instructions; then the CPU tries to figure out data dependencies in hardware and execute instructions out of order and in parallel. It seems as though C-like imperative languages and x86 are baked in forever... but the world is actually parallel.

willtim 11y ago
Excellent point!
marssaxman 11y ago
I've recently been thinking that we are looking at a situation analogous to the one Ben Franklin was in when he identified the two types of electrical charge as "positive" or "negative" pressure in the "electrical fluid" - he took a guess, which happened to be wrong, and ever since we have been stuck describing a surplus of electrons as "negative" and a deficit as "positive". This is no obstacle for the experienced but will remain an eternal hangup for beginners. By analogy, of course, I am suggesting that the Church model of computation might have served us better as a foundation than the Turing model has done, since it seems that everything's turning up lambdas as the technology S-curve for silicon computers continues to flatten out.
- masak 11y ago
  Or maybe we needed to scale to some point with the Turing model for the Church model to assert itself and prove its merits in comparison. It's a bit more thrilling to think of it that way, as a matter of scale. When space and time resources are scarce, thinking of the computer as a big piece of RAM that we mutate in-place makes the most sense. As we push upwards and outwards into enough resources and a bigger need for parallelism, it suddenly makes more sense to switch perspectives and reason in terms of binding and substitution.
  - marssaxman 11y ago
    That certainly makes sense. I'm just looking ahead over the next couple of centuries and imagining generations of young programmers stumbling over all these ancient vestiges of mutable state and synchronous, batch-driven control flow which will probably still be littered around the roots of our computing systems long after the dominant paradigm has shifted. You can see the same pattern with IO models. We have programming languages descended from 50s-era concepts of computing in which the program drives the machine, but that just isn't true at all. A computer is a passive machine, not an active one: it reacts when you poke it with an interrupt, until it reaches a steady state and settles down again. Operating systems go to a great deal of trouble to simulate the kind of top-down flow control environment our imperative tradition wants to think it is operating in, but in order to get any real performance out of these systems, we all end up building asynchronous, reactive layers on top of the simulated batch-job anyway. We'd all be better off if we flipped the paradigm, imagining the process of building a program not in terms of writing instructions for the computer to perform, but in terms of creating a structure which will react appropriately in response to whichever events may be brought to its attention. Instead, we'll probably still be starting young programmers out with for-loops counting from 1 to 10 and printing the result on an imaginary console for decades to come, even though none of that is even remotely relevant to what's actually happening anymore, and once they've crossed that hurdle they'll promptly begin unlearning all that stuff in order to start getting real work done. On an unrelated note, I spent a while last fall/winter playing around with the idea of a very low level functional language - could we use these techniques in memory-constrained environments too? I didn't find the model I was looking for, but I think it's probably out there, and it would be very interesting to develop a functional/type-safe/immutable language suitable for microcontroller programming, with no garbage collection or implicit allocation. It may be that the Turing model is a better fit for computing in the small, but I suspect that we may find dataflow and functional composition to be useful at all scales. That way of looking at the world has some profound philosophical strength, after all - "you cannot step twice into the same river" and all that.

munificent 11y ago

I wouldn't describe SSA as "a functional language". It was originally designed as an IR for imperative languages, not functional ones. (The functional folks prefer CPS, which really is a functional language.) I think one could read too much into the "single-assignment" part of SSA. Sure, functional languages don't tend to rebind variables either, but that's really all SSA has in common with them. I'm familiar with Appel's "SSA is a functional language" article, but the vibe I got was more than he was trying to build some bridges between the SSA and CPS camps to try to get some cross-pollination going and knowldge sharing between them. I think he could have just as easily called it "CPS is an imperative language", but my hunch is the FP folks are more persnickety and wouldn't have swallowed that as easily as imperative folks would accept the other title.

willtim 11y ago
Like Appel, I wasn't entirely serious about it being a "functional language", but I think the point still stands, it is a major step towards a more mathematical program representation ("variables" instead of "assignables"). And just like "functional programming", the primary goal is ease of reasoning. CPS is typically used to handle imperative control structures by impure functional programming languages, so it should indeed be of interest to imperative compiler authors.
willtim 11y ago
The paper "A Correspondence between Continuation Passing Style and Static Single Assignment" by Kelsey, suggests SSA has a lot more in common with functional programming than you seem to believe it has.