Hacker News Reader

Comment by mwcampbell | Hacker News Reader

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).

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.

View on HN

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 ... and the particular mix simply doesn't appeal to me personally.

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.

>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.

> 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.

I would like to know why you think that. The same predominant factor, complicated interactions, prevents easy reasoning in both cases.

I don't agree that functional programming fails in those cases.

What kind of code do you write? I write games (and, recently, UI-heavy interactive apps that talk to servers).

Even the most strident FP advocates I know who are real game developers say that they wouldn't even consider using a strictly functional language for game development. IO-heavy apps in general seem like they're not a good use of functional languages.

Different programming paradigms suit different problem domains. It's not complicated interactions that would make it harder to understand for a human; it's that when you try to use a language for something that it isn't well suited for, it can be hard to figure out what the program does or how it works.

The objective isn't to write the most clever code, or even the code that's easiest to reason about, but the code that works and is easy to understand.

> 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.

It's easier to reason about for the developers who are writing the compiler transforms, ie. humans.

Agreed--I think functional programming comes a lot closer (or at least it can, in theory) to expressing programmer intentions. The compiler doesn't have to deal with side effects and all of their hairy consequences (escape analysis, aliasing, inferring dependencies, ...).

> 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

> 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.

> 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?

Crashing would be a side-effect. However your idea is correct. Consider instead:

    [True, SpinForever()]

You can consider any "variable" in Haskell to have a value of the type of that variable or the bottom value. The bottom value is tech-speak for no-value at all, since it means that the program has gone into a infinite-loop trying to produce the value.

Eagerness would fix this since, such a program as above would always cause a infinite-loop, and thus the program would no longer be a useful construction. While with lazy evaluation it only spins if you try to evaluate any more than the first element in the list.

Of course you could also fix this by going with total programming which basically removes the implicit bottom-value from the language. Which is a nice concept. Though then you need to explicitly declare you infinite data from you finite data (think a network socket, compared with string). And you lose Turing-completeness (but who needs that anyway :) )

Fair enough. Though as later comments point out, constructing a 1tb object is probably a better failure case for functional languages. It would also be fairly easy to avoid if the True on the lhs could be evaluated quickly so you could abort the second calculation.

That kind of code is only valid in strict languages because of short circuiting, is functionally equivalent to lazyness in this respect. If you tried to automatically parallelize C by speculatively evaluating both sides you would have exactly the same problem.

Lazy languages may make this kind of code easier to write, but the problem is actually that of non-deterministic calculations, and would be a problem anywhere.

> 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.

Consider

> True || construct_a_1TB_object()

Unless you have infinite computation and memory, there are always visible side-effects, no matter how functional your language is.

If the 1TB object is constructed atomically, it has to wait, yes - but really, that's the case in eager languages too if you want the same final semantics.

If the 1TB object can in any way be constructed a bit at a time, then in principle you can get some work done in constructing it and back that out if you wind up not needing it.

Would Standard ML be a suitable language for the kind of research you describe?

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.

But these kinds of languages do exist and it's reasonable to think about writing compilers for them and/or subsets.

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).

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) looks like what I imagined the phrase meant.

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.

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....

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.

I always considered CPS and SSA to be duals. (Just like FST and Lambda-calculus are duals)

What do you mean by FST?

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).

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.)

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.

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

Reply on news.ycombinator.com