Rambling about programming and life as a programmer

Archive for August, 2007

An epiphany about Functional Programming and Lazy Evaluation

Posted by webmat on August 12, 2007

Update 2: This article has has a new home on Go to the article.
Comments are closed here but still open there :-) 

(Update: be sure to read the comments, as the language used in my article was not entirely exact, in functional programming legalese ;-) Many readers helped to clarify things a bit.)

I had a mini-epiphany recently. Altough I haven’t had the chance yet to program with a functional programming language, it’s a subject I’ve had my eye on for a while. My ear perks up when I hear about Erlang, Haskell, F# or Scala, 4 functional programming languages.

Recently I’ve been dipping in the intricacies of memory management, at work, in .Net. This was in the context of the Dispose pattern (I have a post in the making about the subject). Both subjects are not directly related, but I found a parallel that might help to explain lazy evaluation to programmers used to more traditional programming languages.

I won’t go in depth in the subject or define the concepts precisely here. I might however revisit what follows when I’ve had time to actually get more experience with an FP language. So here was my revelation:

When specifying a computation in a programming language, lazy evaluation is to the detailed, manual sequencing of operations what garbage collection and automatic memory management is to the detailed, manual management of memory.

In other words, with advanced virtual machines such as Java’s or .Net’s, by allowing the VM to manage the memory, we more or less get the advantage of having world-class computer scientists optimize the management of the memory we use. The programmer declares what he needs in term of memory, instead of specifying precisely how he needs it (stack vs heap, who’s responsible of freeing the memory, etc.) The amount of control over the precise performance is lessened to a certain extent, but the resulting performance gains can often be quite stunning. For example, I read recently that Java’s allocation of memory on the heap requires around 10 processor operations instead of 60 to 100, for the best C++ compilers. See Brian Goetz’ excellent article on IBM’s website.

In the same manner, with a functional programming language’s lazy evaluation, optimizations can be made without the programmer needing to state them explicitly. The interpreter can decide when to execute the code, namely if and when its outcome is needed, and not before that.

Since the precise order of execution is not guaranteed, the bits of computing specified by the programmer in an FP can be optimized in other ways, too. For example, if the VM sees that a given instructions in the code is not dependent on the outcome of the previous instruction, it can execute them both simultaneously, if there are more than one cores available. It’s managed automagically by the interpreter, no threading headache necessary. Conversely, the programmer can specify the ordering of instructions only when necessary (e.g. when interacting with an outside system).

This is why FPs are often mentioned in the current debate surrounding the looming concurrency challenge. This kind of optimization is also being done by Java and .Net’s VMs, but to a much lesser extent, because of deep differences between imperative (Java, C++, C#) and functional programming languages.

Posted in programming | Tagged: , | 10 Comments »