I was reading the book "Functional Programming for the Real World". It started with comparison between imperative and functional programming languages. And it stated how 'values' and 'expressions' in functional programming is different from 'variables' and 'functions' of imperative programming. From the discussion I sort of developed an idea that -

Functional programming languages have more opportunity to do compile time optimization than their imperative counterparts.

Is it true?


Functional programming languages do much more compile time optimization. One of the reasons is purity - concurrency is trivial because there is no state. So the compiler can take two branches and concurrencize them easily without changing the behavior of the program.

At the same time, anything that can be calculated without state (ie anything non-monadic in haskell) can be calculated ahead-of-time by the compiler, but such calculations could be expensive and thus are probably only done partially.

Additionally, anything that isn't needed computationally can be completely optimzied out of the program.

  • 1
    +1: Side-effect free programming is very, very easy to optimize. – S.Lott Apr 26 '11 at 14:47
  • @mathepic: actually the parallelization (in Haskell) occurs at both compile-time and run-time. Compile-time decides whether or not it's worth creating a shard (thread seed) and run-time processes shards as it can, depending on the number of threads you specified. If you only specify a single thread, the shards get created, but they are processed one after the other. – Matthieu M. Apr 26 '11 at 18:57
  • 2
    @mathepic: another use of purity --> laziness and the absence of computation. If you can prove that the value is not needed, then strip off the computation entirely. If it may be needed, use a lazy thunk. If you know it'll be needed, compute it straight ahead (to avoid the lazy overhead). Purity is (just) amazing :) – Matthieu M. Apr 26 '11 at 19:05
  • @Matthieu good point – alternative Apr 26 '11 at 19:16
  • 1
    @Masse Even the IO monad is pure. Its just that the result of "running" the IO monad is not. – alternative May 4 '11 at 10:52

That there are in principle more compile time optimization possibilities for functional languages than for their imperative counterparts is probably true.

More interesting though is, if they are actually implemented in current compilers and how relevant these optimizations are in practice (i.e. final performance of idiomatic 'real life(TM)' code in a production environment, with a priori predictable compiler settings).

e.g. the Haskell submissions for the infamous Computer Language Benchmarks Game (bad as it might be - but it is not like that there is - at the moment - anything significantly better out there) give the impression that a significant amount of time has been spend on manual optimizations, which confronted with the claim about "possible compiler optimizations due to insert some property about FP languages here" makes it look like the optimizations are (currently at least) more of a theoretical possibility than a relevant reality.

I would be glad though to be proven wrong on this point.

  • 1
    The reason for the manual optimizations in Haskell have more to do with the fact that certain "straightforward" operations are somewhat time consuming (from a complexity perspective) in Haskell. For example, say you want to get the last element of a list. In Java, that's a pretty simple operation; in Haskell, the naïve approach requires that you walk the entire list until you come to the end (due to the lazy nature of lists), making it an O(n) operation. That's (partly) where manual optimizations come in. – mipadi Apr 26 '11 at 15:16
  • 2
    I am sure that there are valid reasons for Haskell's hand rolled optimizations, but they being necessary for "straightforward" operations gives the impressions that the greater opportunities for optimizing code are (currently) only relevant in theory. – Alexander Battisti Apr 26 '11 at 16:32
  • 5
    It's more the difference between optimizing algorithms, and optimizing generated code. Take a C example: if I'm writing a search algorithm, I can write a naïve algorithm that simply walks through a list, or I can use binary search. In both cases, the compiler will optimize my code, but it won't turn a naïve search algorithm into a binary search. A lot of the manual optimizations in Haskell code have more to do with optimizing the algorithms themselves, rather than optimizing the generated code. – mipadi Apr 26 '11 at 17:11
  • 2
    @mipadi, but it seems that the straightforward version of Haskell algorithm isn't as good as the straightforward version of other languages' algorithms. (I suspect due to mismatch between the functional model and computer architecture) Even if its good at generating code, its not enough to overcome this problem. – Winston Ewert Apr 28 '11 at 17:17
  • >>bad as it might be<< -- Do you know whether it's bad or not? What do you even mean by suggesting it's "bad"? Please be specific. – igouy May 15 '12 at 16:54

In functional style, the flow of values through a program is very, very visible (to both the compiler and the programmer). This gives the compiler a lot of leeway to decide where to store values, how long to keep them around, and so on.

In an imperative language, the compiler promises the programmer a model where most variables correspond to actual locations in memory which stay around for a defined lifetime. Potentially, any statement may read from (or write to!) any of these locations, so the compiler can only replace memory locations with register allocation, merge two variables into a single storage location, or perform similar optimizations after performing a painstaking analysis of where else in the program that variable may be referenced.

Now, there are two caveats:

  • The programming language community has spent (wasted?) a lot of effort over the last fifty years on developing clever ways to do this analysis. There are well-known tricks like register-coloring and so forth to get some of the easier cases done most of the time; but this makes for big, slow compilers, and a constant tradeoff of complexity of compilation for quality of resulting code
  • At the same time, most functional programming languages are not purely functional either; a lot of the things programs actually need to do, like respond to I/O are inherently non-functional, so no compiler can be completely free of these tricks, and no language avoids them entirely -- even Haskell, which is a bit too pure for my taste (Your Mileage May Vary) can only control and wall-off the non-functional parts of your code, not avoid them altogether.

But to answer the general question, yes, a functional paradigm gives the compiler a lot of freedom to optimize that it does not have in an imperative setting.

  • Everything in Haskell is functional, its just that your main is a state transforming function rather than something that uses the state itself. – alternative Apr 26 '11 at 19:17
  • Yes and no -- conceptually, it's quite correct to say that a Haskell program is a pure function over the user's interactions with that program (and the state of the system's random number generator, and the latency of the network today, and any other inherently non-functional inputs the program responds to), but in practice it's a distinction without a difference. – jimwise Apr 27 '11 at 18:51
  • @jimwise Referential transparency is a very large difference. – alternative Apr 27 '11 at 18:59
  • Except that you don't really have it, at least for the purpose discussed here. The point of operations like IO, or random number generation, is that they should return a different value each time they're invoked with the same inputs, and this inherently limits reasoning about them functionally, for either the programmer or the compiler. – jimwise Apr 28 '11 at 15:10
  • 1
    @mathepic Yes, of course you can conceptually view randomness or user input (or network latency, or system load) as an infinite stream or a function from state to state, but it's not a view which lends itself to useful reasoning about program behavior by you or your compiler -- Bob Harper covers this ground well in a recent post on his blog about CMU's new functional-programming-first CS curriculum. – jimwise Apr 28 '11 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.