A Nibble of Lazy Evaluation
Tags: lazyevaluation, haskell, python
Published: 2022-11-14 21:16:36

---
title: A Nibble of Lazy Evaluation
published: true
date: 2022-11-13 18:47:19 UTC
tags: lazyevaluation,haskell,python
canonical_url: https://getcode.substack.com/p/a-nibble-of-lazy-evaluation
---

_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.


![koala on bough](https://images.unsplash.com/photo-1504578957268-924fac546438?crop=entropy&cs=tinysrgb&fit=max&fm=jpg&ixid=MnwzMDAzMzh8MHwxfHNlYXJjaHw4fHxsYXp5fGVufDB8fHx8MTY2ODI5MjkzOA&ixlib=rb-4.0.3&q=80&w=1080 "koala on bough")
_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:

```python
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:

```python
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.

```python
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](https://www.wikiwand.com/en/Thunk)_: functions without arguments. Thunks delay evaluation until needed.

```python
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.

```python
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:

```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](https://www.cs.dartmouth.edu/~doug/powser.html) illustrates this beautifully: a complete, 10-line implementation of infinite power series in Haskell.

Here's one line from it:

```haskell
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:

```python
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:

```haskell
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:

```haskell
 (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:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/u7yrd1j0zvooiujkcspl.png)

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.

![a venn diagram showing strict, non strict and lazy evaluation](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/985rwm3kanymtc30o430.png)

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.

Thanks for reading! I intend to write one nibble every month. For more, [subscribe to my newletter](https://getcode.substack.com/subscribe?) and [follow me on Twitter](https://twitter.com/kurt2001)