Home > Articles > Programming

  • Print
  • + Share This
Like this article? We recommend Provability


This is also related to performance. Compiler optimizations work by transforming the code that the programmer has written into something that has identical (observable) semantics but a different implementation. A trivial example is common subexpression elimination. For example, if you write:

int a = b+c;
int d = a+b+c;

The compiler will see that you are adding b and c together twice, so it can rewrite this as:

int a = b+c;
int d = a+a;

It can then see that a+a is the same as a+a. In binary, this is a left shift by one, which may (depending on the architecture) be faster than an addition, so it may rewrite it as:

int a = b+c;
int d = a<<1;

None of these change the program’s semantics, but they reduce the amount of work that the computer needs to do. Being able to do these transforms relies on being able to prove things about the source program. Imagine if this example had been C++ instead of C. Now all of these operators could be overloaded, so they could really be function calls. The compiler would have to prove that the + operator in b did not have side effects before it could do the first transform. This is hard in the general case, but is trivial with a functional language.

One of the problems that functional languages have had traditionally is that this advantage is largely theoretical. A bad C compiler will generate much better code than a bad Haskell compiler because, although the Haskell compiler has more information to work with, it needs to do more complex optimization to get to the same base level.

Now, however, C compilers are long past the point where they have done the trivial things that give good performance and now need to do things like type-based alias analysis to squeeze the last bits of performance out of the language. In contrast, Haskell compilers that give performance within a factor of 2 or so to modern C compilers are still ignoring a large number of potential optimization opportunities.

This means that if you write C now, a compiler in the future may make it 50 percent faster, if you're really lucky. If you write Haskell now, a future compiler is likely to make it 500 percent faster, possibly even more if you take into account implicit concurrency.

  • + Share This
  • 🔖 Save To Your Account