Isn't functional paradigm too divergent with underlying hardware to be generally efficient?

Question

Inspired by a question from SO: https://stackoverflow.com/questions/6623391/how-to-gain-control-of-a-5gb-heap-in-haskell

It can be a long debate about FP's numerous advantages and disadvantages, but for now, I'd like to narrow the scope to principal efficiency of FP on modern hardware.

Thesis:

Functional paradigm implies immutability and statelessness (?), but the hardware we run functional programs on are stateful finite automata. Translation of 'pure functional' program to a 'stateful hardware' representation leaves little control to programmer, brings overhead (?) and limits the use of hardware capabilities (?).

Am I right or wrong in the questioned statements?

Can it be proven that FP does / doesn't imply principal performance penalties on modern general-purpose computer architecture?

EDIT: As I've already stated in response to some comments, the question isn't about implementation performance and details. It is about presence or absence of principal overhead, which running FP on stateful automata may bring.

Answer 1

There is a huge misunderstanding in immutability.

The immutability is a feature of the semantics, but it does not imply immutability in implementation.

A simple example is the implementation of laziness.

When computations are lazy, the result of an expression is conceptually a value, but the underlying implementation is a thunk that contains the arguments to be evaluated and a function to create the value, as well as a slot to store the value in.

The first time you will ask (in the language) for the value, the computation will actually be performed, its result evaluated, and the value given back to you (or a handle).

This is transparent in the language semantics, and all you know is that this variable has been bound to a value (or a future value) and that once it's done you cannot change the value that will be returned. The underlying memory representation will change, but you won't know about it.

The same semantic/implementation difference exist in about any language, and is in fact at the heart of optimization. Whatever the language, the semantics guarantee some things, but leave others unspecified to leave room for optimization.

Now, it is true that practically functional languages are not as fast as C++, for example. However, Go (which is quite the hype still) is slower than Haskell or Lisp, and so is C# Mono (source).

When you see how unreliable C++ or C can be to get you those performances, you might wish to let go a bit.

When you realize that Haskell is growing fast today, and there is still much room for optimization in its compiler/runtime (GHC just switched recently to LLVM for example, Microsoft Research is actively funding the runtime improvements), you might be willing to bet that it's going to improve soon.

Fun: A Play on Regular Expressions or how a Haskell team created a regular expression matcher that outperforms re2, the C library from Google, in a number of scenarios.

Answer 2

Functional paradigm is useful to split up thing in a narrow scope. This is a really good thing considering how computer evolve.

Multicore CPU have big problems dealing with shared resources and synchronization cost are really exepensive. Functional paradigm allows a natural way to express programs that doesn't have thoses issues. This is really good for parallelism.

In addition, we are using servers farms more and more with SaaS and cloud computing. Thus, the same application has to run on several machines. In this position, synchronization costs are even more costly. Google has done some work and publish some research papers about functionnal programming and algorithm you can write in. This is a key thing for them because they have a scallability issue.

Moreover, you can easily do a stack in the heap of the computer, and even a non continuous one using linked lists. This is aloready done to generate stack trace in many programmation languages. So this is not an issue.

OK, functionnal programming implies some limitations. But it also brings natural way to express problematics we have in modern computering, that are extremely hard to handle in paradigms wa are used to. Scalability is one of them, and it's becoming a real deal.

Everyone that already deal with a complex parallel system know what I'm talking about.

So I would nuance the answer. Yes, functional has issue with modern hardware, but plain old programming has some too. Like always, you'll find advantages and drawbacks. The point is to know what they are so you can make the apropriate choice when you have to.

Answer 3

I don't really have an answer, as I don't know the current state or even how difficult it would be, but just because the compiler would ensure those things from the input, doesn't necessarily mean that the output would have them. In theory, a sufficiently smart compiler could by pass all these problems, but in practice, it probably will always exist.

However, another way to look at it is to look at the history of the Lisp machine. If I recall correctly, they were originally designed to over come the same problems Lisp had with it's difference from the machines at the time. Development of these machines eventually stopped, as desktop became fast enough to make the inefficiencies cheaper to live with than to support another machine.

Generally, except for the most performance critical application, FP languages are still fast enough. Choices any higher level language, you will be willing to lower the priority on fine tune control and performance for safer, easier, more maintainable, or some other priority.

End in the end, programming is all about trade offs, so one just needs to choose what matters more for the project on hand.

Answer 4

It's true that the functional paradigm implies immutability and statelessness, but we don't have any completely pure programming languages. Even the purest, Haskell, allows side effects.

That said, to answer your question about efficiency, I've used both Haskell and Clojure, and haven't noticed any performance issues with either.