Archive for the ‘Lazy Evaluation’ Category

My New Mantra: Modularity is the Key to Successful Programming

March 8, 2013

Modularity is the key to successful programming. [John Hughes]

Lazy evaluation is perhaps the most powerful tool for modularization in the functional programmer’s repertoire. Consider …

Most functional programming languages have a function called “repeat” which generates an infinite list; its argument is used as the value of the list. For example, this generates an infinite list of 3:

        repeat 3        returns [3, 3, 3, …]

Also provided by most functional programming languages is a function called “take” which has two arguments, an integer N and a list. The function “take” returns the first N values of the list.

“take” can be composed with “repeat” to obtain a pruned list of values. The following returns the first 5 values of an infinite list:

        take 5 . repeat

Function composition is denoted by the dot ( . )

Applying that composed function to 3 results in a list of five 3’s:

        (take 5 . repeat) 3        returns [3, 3, 3, 3, 3]

It is lazy evaluation that allows us to modularize the pruning problem in this way. The “repeat” function is evaluated lazily – only as many values as requested are generated. So lazy evaluation is very efficient. Without lazy evaluation we would have to fold these two functions together into one function which only constructs the first five values.

Here’s another example. We can define the set of even numbers by enumerating all positive numbers [1..] and multiplying each by 2:

        evens = [x * 2 | x <- [1..]]

That is, of course, an infinite list. However, lazy evaluation will compute only as many as needed. Let’s take the first 5 evens:

        take 5 evens        returns [2, 4, 6, 8, 10]

One more example. The example comes from the field of Artificial Intelligence. A decision tree is generated. It could be a decision tree for medical diagnosis or a decision tree for chess moves or a decision tree for something else. The decision tree is potentially infinite. Without lazy evaluation, processing may never terminate. Rather than exploring a potentially infinite space we prune the tree to a depth of, say, 5 levels:

        prune 5 . decisiontree

decisiontree is a function that generates the tree. prune 5 chops off any levels of the tree beyond 5 levels deep. We can make improvements by tinkering with each part. Without lazy evaluation we would have to fold these two functions into one function which only constructed the first five levels of the tree. That is a significant reduction in modularity.

Lesson Learned: Want to have successful software? Then you need to learn how to take advantage of the enhanced modularity that lazy evaluation provides. And, of course, you need to use a programming language that supports lazy evaluation.