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?

Michael K
  • 15,539
  • 9
  • 61
  • 93
Gulshan
  • 9,402
  • 10
  • 58
  • 89

3 Answers3

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.

alternative
  • 1,542
  • 13
  • 14
  • 2
    +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
  • Shouldn't any non-IO monad be able to be calculated ahead of time? After all they're all pure functions, but monads just hide the boilerplate. – Masse May 04 '11 at 06:57
  • 1
    @Masse Even the IO monad is pure. Its just that the result of "running" the IO monad is not. – alternative May 04 '11 at 10:52
  • I'm ignorant (but very curious!) about Haskell, but I understand that Haskell is relatively slow (compared to C, C++, etc)... why would a pure functional language with lots of optimization opportunity be slower than imperative language implementations? – weberc2 May 12 '15 at 17:57
  • @weberc2 Its not, it can reach C-like speeds. That being said, the C model matches more closely the actual hardware, which means that (more correctly, the asm model) it sets the absolute maximum but is hard to reach that maximum – alternative May 23 '15 at 17:43
  • @alternative what do you mean by "it can reach"? Is this the normal case? Or is it with optimized source code or some special edge case at which it happens to excel? – weberc2 May 23 '15 at 18:34
  • @weberc2 I mean that your viewpoint is naive and that Haskell is not slow relative to C in a meaningful way. – alternative May 27 '15 at 01:09
  • My question was perfectly reasonable. Languages like Python also claim that they can "reach C-like speeds", but of course this isn't the normal case. Your most recent response is much more substantive. – weberc2 May 27 '15 at 01:17
  • @weberc2 Except Python has implicit differences (in that it has to be at best JIT'd because it isn't compiled) while there isn't too much difference between say, a C vector and a Haskell MVector running in ST, and a Haskell Vector (pure) can reach MVector speeds through fusion, etc. Its the weird optimizations that are allowed by functional programming that lets it sort of approach the "imperative ceiling" to overcome some of the weaknesses of functional programming – alternative May 28 '15 at 04:10
  • Great. That's a great response to my original question. If still doesn't make my viewpoint naive; I'm just uninformed about Haskell, which is why I asked the question originally. Thanks for the informative response! :) – weberc2 May 28 '15 at 12:42
  • @weberc2 What I mean by that is that it is a common belief that Haskell is not on native-level speeds simply because it is "pure" and whatnot – alternative May 29 '15 at 02:07
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.

Alexander Battisti
  • 1,622
  • 11
  • 11
  • 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
  • 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 '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
  • because benchmarking programming languages is very [difficult](http://shootout.alioth.debian.org/dont-jump-to-conclusions.php). – Alexander Battisti May 16 '12 at 16:02
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.

jimwise
  • 7,433
  • 1
  • 30
  • 32
  • 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
  • @jimwise but they do return the same value, its the same state transformer function. Keep in mind you don't even need a monad to do pseudo-randomness, you would just have to manually keep track of the intermediate states in your code. Its fully functional. – alternative Apr 28 '11 at 15:15
  • 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](http://existentialtype.wordpress.com/2011/04/24/the-real-point-of-laziness/) on his blog about CMU's new functional-programming-first CS curriculum. – jimwise Apr 28 '11 at 16:28
  • @mathepic By the way, this is not an argument for or against Haskell's view of such externals; to my taste, they're a bridge too far, but Your Mileage May Vary. The important point here is that even viewed as pure functions, such externals do not lend themselves well to the same level of optimization which makes FP language compilers so effective. – jimwise Apr 28 '11 at 16:30