A Nibble of Lazy Evaluation

Eager vs strict vs non-strict vs lazy - what does it all mean?

Nibble: a small piece of food bitten off. In computing: half a byte of information. Every nibble explains one computing science or software engineering idea in five minutes.

Every programming language needs to choose in which order to evaluate expressions. Almost all use strict evaluation: before evaluating an expression, all sub-expressions are evaluated first. For example, arguments to a function are evaluated before the function. Many people use eager evaluation as a synonym for strict evaluation.

A minority, most prominently Haskell, uses non-strict evaluation. Non-strict evaluation is defined by what it is not: any evaluation strategy that doesn't evaluate all sub-expressions first, or at all, is non-strict. Lazy evaluation is a particular strategy of non-strict evaluation.

Let's try to clear up the confusion with a nibble of lazy evaluation.

I envy koalas for their ability to be supremely comfortable in the most awkward of places. Photo by David Clode on Unsplash

Strict evaluation

Like the majority of languages, python uses strict evaluation for function applications:

def log(value):
    if log_level == INFO:
        print(value)

log(42 + 33)

First, the sum is calculated, then it's logged. While intuitive to understand, the example shows a potential downside of strict evaluation: if the argument ends up being unused, if log_level is WARN, then it's calculated needlessly.

A simple way to spot strict evaluation is to imagine what would happen if one sub-expression gets into an infinite loop. If the top-level expression never gets evaluated, then evaluation is strict.

Strict evaluation doesn't restrict in which order sub-expressions are evaluated, just that they're all evaluated before the top-level expression. It can be left to right, like in Python; right to left, like in OCaml; or left undefined, like in C.

Non-strict evaluation

Non-strict evaluation is not as unusual as it may appear at first - if...else... for example is non-strict.

Let's apply our trick to spot strict evaluation. The following Python program terminates even though the else branch loops forever:

if True:
    print("I am True")
else:
    while True:
        print("I never terminate")

The else branch is not evaluated at all, so if...else... is not strict in python.

Short-circuited boolean operations are also non-strict. The following or expression terminates.

True or infinite_loop()

Non-strict DIY

That's nice for built-ins, but if you want something done right...

We can simulate non-strict evaluation using thunks: functions without arguments. Thunks delay evaluation until needed.

def log(value_thunk):
    if log_level == INFO:
        print(value_thunk())

log(lambda: 42 + 33)

Thunks avoid unnecessary work - if the value to log is expensive to compute, the log function only evaluates it when logging is enabled.

Lazy evaluation

An annoying problem with thunks is that they are re-evaluated each time they are called.

def log(value_thunk):
    if log_level == INFO:
        print(value_thunk())
        send_to_log_aggregator(value_thunk())

To solve that, we can keep the thunk's result the first time it's evaluated, and re-use it. This evaluation strategy is called lazy evaluation. It combines two optimizations:

• It never performs unnecessary work, by delaying evaluation until needed.

• It never repeats work, by caching the first result.

There is a catch: if the thunk has side effects, such as writing to disk, it becomes hard to understand when or if the side effect occurs. For this reason, lazy evaluation assumes thunks have no side effects.

The functional programming language Haskell gets away with using lazy evaluation by default because it is pure: Haskell functions do not have side effects.

Strict languages like OCaml, F#, and C# support lazy evaluation using a lazy keyword or Lazy object.

Here's an illustrative implementation of a Lazy object in python:

class Lazy:
    def __init__(self, thunk):
        self._thunk = thunk
        self._is_cached = False
        self._value = None

    @property
    def value(self):
        if not self._is_cached:
            self._value = self._thunk()
            self._is_cached = True
        return self._value

Why lazy evaluation matters

Strict evaluation is more common because it's easier to understand, and is more straightforward to debug. That said, non-strict evaluation is indispensable in some situations.

Doug McIlroy's Power Serious illustrates this beautifully: a complete, 10-line implementation of infinite power series in Haskell.

Here's one line from it:

series f = f : repeat 0

In Haskell, one of the fundamental data structures is a lazy list. The function series creates such a list. The first element of the list is the number f, and the rest are zeroes. The list constructor : prepends a list with one element. The standard function repeat s creates an infinite list of s.

Concretely, series 13 represents the infinite list [13, 0, 0, 0,...]. But since it's lazy, the elements are only calculated when needed. One way to ask for elements is to use the function take n, which takes n elements from the front of a list. In other words, take 4 (series 13) yields [13, 0, 0, 0].

At this point, you may think that lazy lists are just iterators. Like lazy lists, iterators are computed on demand and can be used to represent infinite data structures. Here's series as a python generator:

def series(f: int) -> Iterable[int]:
    yield f
    while True:
        yield 0

The difference is that lazy lists cache elements of the list as they are evaluated. A program like:

myList = series 10 --list thunk is created
some = take 5 myList --eval first 5 elements
somemore = take 20 myList --eval 15 more elements

evaluates only 20 values in total. Iterators sometimes can't be reset, and if they can the whole computation is redone from scratch. Not so with lazy lists!

Back to Power Serious. Doug McIlroy uses lazy lists to represent the coefficients of an infinite power series. In other words, the list [1, 2, 3, 4, 0, ...] represents the power series 1 + 2𝑥 + 3𝑥² + 4𝑥³ + ...

Here's addition of two power series:

 (f:ft) + (g:gt) = f+g : ft+gt

Haskell's syntax is terse. In this one line both the : and + symbols are overloaded. The : symbol on the left of the equals sign means list deconstruction. On the right, it means list construction. Here's an image that color-codes the different meanings of each symbol to clarify:

Hold on - a recursive definition without a base case? That's only possible thanks to lazy evaluation. When the first element of a sum of two series is needed, the expression f+g in turn needs f and g, which triggers evaluation of the first elements of the left and right list via the lazy pattern matches (f:ft) and (g:gt). Further evaluation of ft+gt is delayed until more elements are needed. This process repeats when a second element is asked for, and so on.

Lazy infinite lists simplify everything: no need to check when the list ends because it doesn't, and no recursive base case is needed because we only recurse when needed.

Recap

This nibble discussed a bunch of terms.

I divided evaluation strategies into two categories: strict and non-strict.

In strict evaluation, all of an expression's sub-expressions are evaluated first. Non-strict evaluation encompasses all strategies that do anything else, including not evaluating some arguments at all.

Strict evaluation is sometimes called eager evaluation, which sounds like it's the counterpart of lazy evaluation. However, lazy evaluation is just one of many possible non-strict strategies. Lazy evaluation stands out because it additionally caches results, but that's only possible if the expressions don't have side effects.

Finally, strict and non-strict evaluation is commonly used together in a single programming language, and even in the same expression. Hence the intersection in the image. An example is if...else...: evaluation of the condition is strict, but evaluation of the two clauses is non-strict.