12

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?

Improve this question

3 Answers 3

Reset to default
18

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.

Improve this answer
14
  • 2
    +1: Side-effect free programming is very, very easy to optimize.
    – S.Lott
    Apr 26, 2011 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, 2011 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, 2011 at 19:05
  • @Matthieu good point
    – alternative
    Apr 26, 2011 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, 2011 at 10:52
7

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.

Improve this answer
6
  • 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, 2011 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, 2011 at 16:32
  • 6
    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, 2011 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, 2011 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, 2012 at 16:54
2

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.

Improve this answer
7
  • 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, 2011 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, 2011 at 18:51
  • @jimwise Referential transparency is a very large difference.
    – alternative
    Apr 27, 2011 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, 2011 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, 2011 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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