11 ms·

EDIT: Expanded my question about Mike's opinion of FP. This perspective from a compiler developer lends credence to Stanislav Datskovskiy's rants about the imp

EDIT: Expanded my question about Mike's opinion of FP. This perspective from a compiler developer lends credence to Stanislav Datskovskiy's rants about the importance of the underlying CPU architecture. Stanislav has done some work on a new dataflow-based CPU architecture (http://www.loper-os.org/?p=846 http://www.loper-os.org/?p=846). I wonder why Mike considers the usual blend of concepts provided by FP languages to not be worthwhile. After all, FP languages that don't allow reassignment of variables are in SSA form already, unless I misunderstand what SSA form is.

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 ago
  In 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 ago
  I always considered CPS and SSA to be duals. (Just like FST and Lambda-calculus are duals)
  - abecedarius 14y ago
    What do you mean by FST?
    - catwell 14y ago
      In 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 ago
        Ah, 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.)
mikemike 14y ago
Converting to SSA form is comparatively easy. The interesting question is how pure a particular SSA variant actually is (hint: almost none are in practice). Just the fact that a language is closer to SSA form doesn't make it interesting. If a compiler is able to turn pretty much every source language into SSA, then why should I bother to do part of its work by hand? Much more relevant is how easy it is to express my intentions as a programmer and how much of that ends up helping the compiler and the CPU to execute the code faster. I really don't want this to turn into a flame-war about the merits of functional programming. The Wikipedia article has a nice list of the typical concepts: http://en.wikipedia.org/wiki/Functional_programming#Concepts http://en.wikipedia.org/wiki/Functional_programming#Concepts ... and the particular mix simply doesn't appeal to me personally.
- DanWaterworth 14y ago
  It's interesting that you say that you are doing the compiler's work when you program functionally. Imperative compilers have three steps: they compile from an imperative language to SSA (which is almost functional), they then optimizes the SSA and then convert back to an imperative language. The reason that they convert the program into SSA is because it is much easier to reason about the program in that form. My take is that imperative compilers are an admission that functional programs are easier to reason about.
  - SomeCallMeTim 14y ago
    >My take is that imperative compilers are an admission that functional programs are easier to reason about. If you're implying that "easier to reason about" for a compiler is equivalent to "easier to reason about" for humans, I think that's a fallacy. Where functional programming fails is in performing tasks that are predominantly imperative; say, anything involving real-time behavior, like games or animation. And by "fails" I mean that an imperative language is easier for humans to follow when it maps more directly to the problem at hand.
    - DanWaterworth 14y ago
yvdriess 14y ago
> I wonder why Mike considers the usual blend of concepts provided by FP languages to not be worthwhile. As the FP community has consolidated around Haskell, this usually refers to the Haskell feature set: Graph reduction, lazy semantics. Graph reduction is extremely imperative (see: spineless stackless g-machine), which makes it map well on a Von Neumann processor, but limits the amount of exploitable parallelism. Relying on lazy semantics also wrecks parallelism, because some evaluation branches cannot be visited ahead of time, without changing the program's semantics. A functional language using eager semantics and string-reduction execution would map much better on, say, a parallel dataflow processor. Research in this direction got buried as parallel research money evaporated in the early 90's
- mwcampbell 14y ago
  Would Standard ML be a suitable language for the kind of research you describe?
  - yvdriess 14y ago
    Very likely. At the very least a subset or with some additions, I-structures come to mind. If you're interested, someone already did some legwork on this, using an eager version of Haskell: [1] S. Aditya, Arvind, J.-W. Maessen, L. Augustsson, and R. S. Nikhil, “Semantics of pH: A parallel dialect of Haskell,” presented at the FPCA 95, 1995, pp. 35–49.
- radm 14y ago
  But these kinds of languages do exist and it's reasonable to think about writing compilers for them and/or subsets.
  - yvdriess 14y ago
    I haven't heard of any recent string reduction languages. The last I heard about it was in Kent Dybvig 'Three Scheme Implementations' thesis, where he used it to map Scheme on a dataflow-like FP architecture (IIRC).
riffraff 14y ago
I may be wrong, but doesn't SSA imply the usage of the strange PHI thingy? I think it's a relatively simple transformation from a FP language without reassignment but I believe it's one significant difference at the surface level.
- seabee 14y ago
  Doesn't an FP language without reassignment imply the existence of a function like phi to perform nontrivial control flow?

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 ago
In 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 ago
I always considered CPS and SSA to be duals. (Just like FST and Lambda-calculus are duals)
- abecedarius 14y ago
  What do you mean by FST?
  - catwell 14y ago
    In 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 ago
      Ah, 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.)

mikemike 14y ago

Converting to SSA form is comparatively easy. The interesting question is how pure a particular SSA variant actually is (hint: almost none are in practice). Just the fact that a language is closer to SSA form doesn't make it interesting. If a compiler is able to turn pretty much every source language into SSA, then why should I bother to do part of its work by hand? Much more relevant is how easy it is to express my intentions as a programmer and how much of that ends up helping the compiler and the CPU to execute the code faster. I really don't want this to turn into a flame-war about the merits of functional programming. The Wikipedia article has a nice list of the typical concepts: http://en.wikipedia.org/wiki/Functional_programming#Concepts http://en.wikipedia.org/wiki/Functional_programming#Concepts ... and the particular mix simply doesn't appeal to me personally.

DanWaterworth 14y ago
It's interesting that you say that you are doing the compiler's work when you program functionally. Imperative compilers have three steps: they compile from an imperative language to SSA (which is almost functional), they then optimizes the SSA and then convert back to an imperative language. The reason that they convert the program into SSA is because it is much easier to reason about the program in that form. My take is that imperative compilers are an admission that functional programs are easier to reason about.
- SomeCallMeTim 14y ago
  >My take is that imperative compilers are an admission that functional programs are easier to reason about. If you're implying that "easier to reason about" for a compiler is equivalent to "easier to reason about" for humans, I think that's a fallacy. Where functional programming fails is in performing tasks that are predominantly imperative; say, anything involving real-time behavior, like games or animation. And by "fails" I mean that an imperative language is easier for humans to follow when it maps more directly to the problem at hand.
  - DanWaterworth 14y ago

yvdriess 14y ago

> I wonder why Mike considers the usual blend of concepts provided by FP languages to not be worthwhile. As the FP community has consolidated around Haskell, this usually refers to the Haskell feature set: Graph reduction, lazy semantics. Graph reduction is extremely imperative (see: spineless stackless g-machine), which makes it map well on a Von Neumann processor, but limits the amount of exploitable parallelism. Relying on lazy semantics also wrecks parallelism, because some evaluation branches cannot be visited ahead of time, without changing the program's semantics. A functional language using eager semantics and string-reduction execution would map much better on, say, a parallel dataflow processor. Research in this direction got buried as parallel research money evaporated in the early 90's

mwcampbell 14y ago
Would Standard ML be a suitable language for the kind of research you describe?
- yvdriess 14y ago
  Very likely. At the very least a subset or with some additions, I-structures come to mind. If you're interested, someone already did some legwork on this, using an eager version of Haskell: [1] S. Aditya, Arvind, J.-W. Maessen, L. Augustsson, and R. S. Nikhil, “Semantics of pH: A parallel dialect of Haskell,” presented at the FPCA 95, 1995, pp. 35–49.
radm 14y ago
But these kinds of languages do exist and it's reasonable to think about writing compilers for them and/or subsets.
- yvdriess 14y ago
  I haven't heard of any recent string reduction languages. The last I heard about it was in Kent Dybvig 'Three Scheme Implementations' thesis, where he used it to map Scheme on a dataflow-like FP architecture (IIRC).

riffraff 14y ago

I may be wrong, but doesn't SSA imply the usage of the strange PHI thingy? I think it's a relatively simple transformation from a FP language without reassignment but I believe it's one significant difference at the surface level.

seabee 14y ago
Doesn't an FP language without reassignment imply the existence of a function like phi to perform nontrivial control flow?