5 ms·

> 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, t

> 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).
  - radm 14y ago
    I don't have a formal definition of a string reduction language, so maybe I'm mis-generalizing. That said, J's parser (http://www.jsoftware.com/help/dictionary/dicte.htm http://www.jsoftware.com/help/dictionary/dicte.htm) looks like what I imagined the phrase meant.
    - yvdriess 14y ago
      p. 127 of www.cs.indiana.edu/~dyb/papers/3imp.pdf gives a pretty good overview, including a ton of references. Roughly, graph reduction execution represents an expression as a node, with an edge to nodes of subexpressions. A value of a node is obtained by walking through it's children, setting the value of each node as the recursion winds down. String reduction simply modifies the expression itself. This does not eliminate common subexpressions (a() * a() will reduce a() twice), which is why graph reduction is favoured. In a parallel world, you often don't care about the extra work if it reduces the number of synchronisation.
triplepoint217 14y ago
> Relying on lazy semantics also wrecks parallelism, because some evaluation branches cannot be visited ahead of time, without changing the program's semantics. For a pure functional language, like Haskell, speculatively evaluating pieces of it in parallel shouldn't hurt anything (since they are guaranteed not to have side effects). It is my understanding that the lazy semantics of Haskell mostly mean that you shouldn't be making any assumptions about the order of evaluation which would seem to be useful from an optimization perspective. I am still new to FP and Haskell, so please correct me if I am misinterpreting things.
- yvdriess 14y ago
  > It is my understanding that the lazy semantics of Haskell mostly mean that you shouldn't be making any assumptions about the order of evaluation which would seem to be useful from an optimization perspective. A crudely example, to impart some intuition: True || this_crashes(); Imagine the above reliance on lazy semantics, but then for Haskell memory management or constructs such as infinite lists. The semantics of your program rely on the fact that some branches of your AST/program are not visited, due to lazy semantics. A FP with eager evaluation semantics can be free to evaluate every branch of the program, throwing away what isn't used. Lazy evaluation means a runtime cannot be as aggressive, introducing a number of logical sequence points. NB. A Haskell colleague lets me know that it is considered good style in Haskell these days to program as if it was eagerly evaluated. There is talk of limiting or doing away with it in Haskell Prime. Can anyone confirm/deny this?
  - zwegner 14y ago
    > True || this_crashes(); That's not functional though--this_crashes() has side effects. I'm far from a Haskell expert, but I guess in practice you'd be returning some error type from that function, and it didn't matter whether it's evaluated or not, since True || arbitrary_expression will always just be True. Laziness, AFAIK, only complicates compilation due to making it hard to reason about memory/performance, and for having branches all over to see if expressions have been evaluated yet.

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).
- radm 14y ago
  I don't have a formal definition of a string reduction language, so maybe I'm mis-generalizing. That said, J's parser (http://www.jsoftware.com/help/dictionary/dicte.htm http://www.jsoftware.com/help/dictionary/dicte.htm) looks like what I imagined the phrase meant.
  - yvdriess 14y ago
    p. 127 of www.cs.indiana.edu/~dyb/papers/3imp.pdf gives a pretty good overview, including a ton of references. Roughly, graph reduction execution represents an expression as a node, with an edge to nodes of subexpressions. A value of a node is obtained by walking through it's children, setting the value of each node as the recursion winds down. String reduction simply modifies the expression itself. This does not eliminate common subexpressions (a() * a() will reduce a() twice), which is why graph reduction is favoured. In a parallel world, you often don't care about the extra work if it reduces the number of synchronisation.

triplepoint217 14y ago

> Relying on lazy semantics also wrecks parallelism, because some evaluation branches cannot be visited ahead of time, without changing the program's semantics. For a pure functional language, like Haskell, speculatively evaluating pieces of it in parallel shouldn't hurt anything (since they are guaranteed not to have side effects). It is my understanding that the lazy semantics of Haskell mostly mean that you shouldn't be making any assumptions about the order of evaluation which would seem to be useful from an optimization perspective. I am still new to FP and Haskell, so please correct me if I am misinterpreting things.

yvdriess 14y ago
> It is my understanding that the lazy semantics of Haskell mostly mean that you shouldn't be making any assumptions about the order of evaluation which would seem to be useful from an optimization perspective. A crudely example, to impart some intuition: True || this_crashes(); Imagine the above reliance on lazy semantics, but then for Haskell memory management or constructs such as infinite lists. The semantics of your program rely on the fact that some branches of your AST/program are not visited, due to lazy semantics. A FP with eager evaluation semantics can be free to evaluate every branch of the program, throwing away what isn't used. Lazy evaluation means a runtime cannot be as aggressive, introducing a number of logical sequence points. NB. A Haskell colleague lets me know that it is considered good style in Haskell these days to program as if it was eagerly evaluated. There is talk of limiting or doing away with it in Haskell Prime. Can anyone confirm/deny this?
- zwegner 14y ago
  > True || this_crashes(); That's not functional though--this_crashes() has side effects. I'm far from a Haskell expert, but I guess in practice you'd be returning some error type from that function, and it didn't matter whether it's evaluated or not, since True || arbitrary_expression will always just be True. Laziness, AFAIK, only complicates compilation due to making it hard to reason about memory/performance, and for having branches all over to see if expressions have been evaluated yet.