What is lazy evaluation

In programming language theory, lazy evaluation, or call-by-need is an evaluation strategy which delays the evaluation of an expression until its value is needed (non-strict evaluation) and which also avoids repeated evaluations (sharing).

— Wikipedia

Simply put, lazy evaluation is to put some part of the program into a compute-on-demand mode. The opposite mode to lazy evaluation is called eager evaluation, in which the computation is always performed, regardless whether the result is demanded or not.

A simple example in Python is the range() function. You probably already know that range(x) gives a collection of integers ranging from 0 to x-1. In Python 2, range(x) will generate a list in memory to store the integers and return it to you. There is also an xrange() function, which does the similar thing as range(), except that it returns an xrange object instead of list. See the listing below:

The difference between aa and bb is that aa is an eagerly evaluated list, and by the time you call it to see its value, all elements in the list are already there. In this toy example its size is 10, no big deal. But if for some reason you need to use such a thing to do a 10M for loop (like for i in range(10**7):), you will be creating a big list containing 10M integers, that is starting to stress the RAM.

On the contrary, bb is a lazily evaluated generator. When you call it in the interpreter, no element gets created and returned, it tells you that bb is xrange(10). Elements only get created when you access them, like:

for i in bb:
    print(i)

Therefore, xrange(10) has the same memory footprint as xrange(10**7). Besides saving memory usage, it often makes your program run faster when used with a loop, because it doesn’t need to create the full collection before going into the 1st iteration of the loop.

In Python 3, the xrange() function is removed, instead range() becomes a lazily evaluated generator.

Lazy evaluation allows one to use infinite series in a programming language. Recently I have been learning the Clojure language. In Clojure, most of its sequence types are lazy, and the most frequently used sequence functions, including map, filter and reduce all return lazy sequences. For instance, (iterate inc 0) creates an infinite integer sequence, but it won’t blow up your computer, because nothing gets evaluated just yet, since it is a lazy sequence. New values will be created when you need them, like (take 10 (iterate inc 0)), which will take the first 10 elements from the infinite sequence.

In Python we can do the similar thing, by creating a generator:

The unconditional while loop (while True:) tells that this thing is going to run forever. In each iteration, it yields out an output. For the 1st iteration, the output is the given starting number start. After yielding out start, the function returns back the control flow to the calling stack. Then next time the generator is asked for a return, execution resumes from Line 4 (start+=1), so it increments the start value by 1, and enters into the next iteration, in which the next number is yielded. If you use such a thing like this:

for i in infIntegers(0):
    print(i)

It will print out all the integers, starting from 0, indefinitely.

What is memoization

I sometimes confuse lazy evaluation with memoization, because they are often used together. But there are some differences.

In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

— wikipedia

In the simplest form, you write your program to cache some results that you don’t want it to re-compute again. For computations that are deterministic, one can use the input argument as the key to a cache where the results are stored. The next time the results are needed, you provide the cache with the key and it returns the corresponding values, bypassing the computation process. Therefore the same key (input) always corresponds to the same result. This can’t be done with non-deterministic computations – you certainly don’t want a random number generator to repeatedly generate the same number.

A simple cache can be created using dictionary in Python. Here is one:

The fib(n) function computes the nth Fibonacci number. And fibCache() is the version using a cache, which is a dictionary. Some computation time comparison:

The difference is HUGE. To help you memoize a function, Python provides a decorator that simplifies the process even more (note that the lru_cache decorator is only available since Python version 3.2):

Now compare the decorated fib() with our fibCache():

Therefore you achieve the same level of performance boost without having to modify any of the inner workings of the function yourself. What a bonus.

Combine lazy evaluation with memoization

The above functions are all returning the nth Fibonacci number. Now let’s try combining lazy evaluation and memoization to create a new function that keeps on producing the next Fibonacci number from a given start point. Here is my implementation:

And here is the code snippet that keeps on getting a new Fibonacci number, starting from the 5th one, until the number is greater than 10^10:

Note that at Line 2, we created a generator specifying the starting number f_gen = fibGen(5). Line 3 primes the generator by calling the next() function on the generator. What it does is telling the generator to run its inner lines till the 1st yield, in this case, these 3 lines are run:

And it stops, and returns the control back to the main script.

The next call of next(f_gen) happens at Line 6 in the while True: loop, this will resume the execution of the generator, letting it enter its own while True: loop, and yield out the 1st result, which would be the 5th Fibonacci number it computed during the previous call of next(f_gen).

After yielding the result out, the generator stops and returns back the control again. The yielded value (number 55) is assigned to the variable new, which gets printed out at Line 7. Since the new number is smaller than 10^10, the loop continues. In the next call of next(f_gen), execution inside the generator starts from the line start+=1, and executes these following lines in sequence:

Then the generator hands back the control again, and execution moves on in the outer while loop. This same process repeats from then on, until a newly yielded Fibonacci number exceeds the upper bound and the while loop terminates. Below is the output:

Conclusion

In the above example, we used memoization to cache the computed results to help speed up the computation of Fibonacci numbers, and lazy evaluation to create a generator that outputs new Fibonacci numbers indefinitely.

In-memory caching can be quite helpful in many situations. For instance in GUI applications, responsiveness is one of the key ingredients in the delivery of a pleasant user experiences. Sometimes your graphical interface thread may have to wait for some computations to finish before it can display the outputs to the user. If such computations take too long (maybe longer than 1 or 2 seconds), you may consider caching the computed results (memoization) and only doing new computations when new data are demanded, or existing data need update (lazy evaluation). Then, the next time the user clicks into the same interface, the contents can be delivered from the cache and in a much faster speed.

In-memory caching is suitable for relatively small sized data. Sometimes, the computed results may be too large to fit into the RAM, and the time required to redo the computation is significantly longer than the time needed to read them from disk, then one may consider caching the results to disk as the memoization method. In a future post I’ll share some functions to cache the intermediate NetCDF data to disk, and load them in if re-computation can be bypassed.