Programblings

Rambling about programming and life as a programmer

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 programblings.com. 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.

Advertisements

10 Responses to “An epiphany about Functional Programming and Lazy Evaluation”

  1. John Nowak said

    “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.”

    What does lazy evaluation have to do with this?

  2. Warren W said

    As John Nowak says, you don’t need Lazy Evaluation for the compiler to determine when instructions are independent and thus paralizable, this isn’t really an advantage of Lazy evaluation. Besides, parallelization at this level is too low level to be of much use, the overhead outweighs the benefit.

    Also, I think you need to look in more detail about automatic memory manage. The speed increase they gained was probably due to a copy on garbage collect behavior. Whenever the garbage collector is run, it likely automatically restructures the allocated memory so that its contiguous. Once this is the case, memory allocation just requires a few pointer arithmetic operations. In manual memory languages, since you cannot ‘defrag’ the active memory like this, you must maintain dirty/clean lists of memory, and every memory allocation is a search.

    The speed increase for the memory managed version is amortized by the general slowdown of whatever garbage collection algorithm that is in use. Even still, automatic memory management is something I think nearly everyone should use and enjoy.

    To round out this comment, one real benefit of lazy evaluation, is in the building of infinite streams. If you can describe a value as some formula of previous values, then it naturally fits into a list comprehension. For example, you could define fibiconni’s numbers (0,1,1,2,3,5…) as a array and access any member of it (element 0 to element 6×10^66) — the program will only compute as much as you actually use. This frees the programmer from some explicit bookkeeping.

  3. Cale Gibbard said

    This is perhaps being overly picky, but what you are talking about is not so much lazy evaluation, but non-strict semantics. Non-strict semantics are what allow for a multitude of potential evaluation orders, and basically amount to saying that if there’s a way for the evaluation to finish (under some order of reduction), then the result is what the result must be. It is possible to show that (in a pure language) any two evaluation orders which both produce a result must produce the same result.

    Lazy evaluation implies a particular evaluation order (outermost-first, rather than strict-evaluation’s innermost-first), along with the technique of sharing the computation of expressions which came from a function parameter being duplicated in the function’s body. Lazy evaluation is an implementation of non-strict semantics — it’s possible to show that if some order of evaluation terminates and produces a result, then lazy evaluation will also terminate and produce the same thing.

    However, that aside, even just lazy evaluation really does have a big impact on the way in which you can program. Because results are only produced if demanded, it becomes possible to define larger structures than you might need in your specific case (which is often easier than explicitly restricting your computation), and then have the remaining part of the computation only use what it needs. This allows you to decompose problems in new ways that you couldn’t before, and get better code reuse.

    Non-strict semantics, without the guarantee of lazy evaluation, allows compiler writers additional freedom to do things like parallelise (though this is really hard to accomplish automatically — programmer annotations help a lot) or apply other evaluation strategies like strict evaluation automatically in places where it’s verifiably safe to do so.

  4. Joseph Huang said

    Shared thunks required by lazy evaluation make automatic parallelization harder. For a language already offering automatic parallelization, see

    http://www.cs.mu.oz.au/research/mercury/information/papers.html#wangp-hons

  5. DRMacIver said

    The implicit parallelism thing is mostly a myth. Especially in Haskell, the opportunities for it are few and far between, and the compiler doesn’t really take advantage of them anyway.

    Which isn’t to say that I disagree with you (although I think we have a long way to go before the ability of the compiler to optimise pure lazy code is as good as the state of the art of garbage collection these days). It’s just that the specific example is wrong.

  6. Laurie Cheers said

    Lazy evaluation has everything to do with this. In a sequential program, you say “Do this, then this, then this”. This is inherently a single-core process.

    In a lazy evaluated program, you say “We need these pieces of information”. You don’t specify the order in which they get worked out, so the compiler is free to process them in any order, or split the calculations across many cores, .

  7. novhard said

    i like about programming too ..
    visit me at novhard.wordpress.com

  8. webmat said

    Thanks all for your comments. I am in fact probably mixing the concepts a bit, yes. Mea culpa :-)
    After reading your comments, I realize I should probably have said that “functional programming language’s non-strict semantics are to the detailed…” (thanks Cale). And yes, lazy evaluation is just one of the way to take advandage of the non-strict semantics.
    Keep in mind one of the opening sentences of the article, however:
    “Altough I haven’t had the chance yet to program with a functional programming language” ;-)

  9. webmat said

    For those who liked the article’s comments, you can also look at the comments on reddit. There’s interesting content there too.

  10. There’s also a certain sense in which lazy evaluation not only performs calculations “if and when they’re needed”, but that it does them “all at once”. When you dig into the semantics of functional programming, all you’re doing is building one big function to calculate, rather than stringing together a bunch of little commands to do one after another. This makes it (IMHO) a good candidate for a programming style suitable for quantum computation… once we actually have quantum computers.

Sorry, the comment form is closed at this time.

 
%d bloggers like this: