Call-by-Need vs. Explicit Memoization

Hello! Welcome to your fifth lesson in the module on Evaluation Strategies and Laziness.

Introduction

In our previous lesson, we explored how lazy evaluation enables the creation and use of infinite data structures. We saw how Haskell handles this natively and how Python can simulate it using generators. The core idea was "evaluate-on-demand."

Today, we will dissect the specific mechanism behind Haskell's laziness, known as call-by-need evaluation. Our goal is to:

Explain how call-by-need evaluation (in Haskell) provides implicit memoization, and contrast this with explicit memoization techniques in eager languages.

We will see that memoization—a powerful optimization technique you may know from algorithm design—is a natural, built-in consequence of Haskell's evaluation model. We'll then contrast this with the explicit approach required in a call-by-value language like Python.

1. From Call-by-Name to Call-by-Need

To understand Haskell's approach, it's useful to distinguish between two types of lazy evaluation:

1. Call-by-Name: An unevaluated expression (a "thunk") is passed as an argument to a function. This expression is re-evaluated every single time it is referenced within the function. This was used in early languages like Algol 60 but is generally inefficient.

2. Call-by-Need (or "Graph Reduction"): This is the strategy Haskell uses. Like call-by-name, an unevaluated thunk is passed as an argument. However, the first time the value is needed, the thunk is evaluated, and its result replaces the thunk in memory. Any subsequent reference to that argument uses the stored result directly, without re-computation.

This "evaluate once and update" behavior is the key. Call-by-need has memoization built into its very fabric.

Consider this simple Haskell code:

let x = 1 + 1
let y = x + x

Under call-by-need:

1. x is bound to a thunk representing the computation 1 + 1.
2. When y is evaluated, it needs the value of the first x. The thunk 1 + 1 is evaluated to 2. The memory location for x is updated with the value 2.
3. The expression for y now needs the second x. It looks up x and finds the already-computed value 2.
4. The final result is 2 + 2 = 4. The addition 1 + 1 was performed only once.

Under a pure call-by-name strategy, 1 + 1 would have been computed twice.

2. Implicit Memoization: The Haskell Way

This built-in memoization becomes incredibly powerful when combined with Haskell's support for lazy data structures. The classic example is generating Fibonacci numbers.

In our last lesson, you saw how to define an infinite list of Fibonacci numbers:

fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Let's trace what happens when we ask for an element from this list, for example fibs !! 3 (the 4th element, at index 3).

1. fibs is initially a thunk: 0 : 1 : <thunk for zipWith>.
2. To get index 3, the runtime needs to evaluate the list.
   • fibs !! 0 is 0.
   • fibs !! 1 is 1.
   • fibs !! 2 requires evaluating the thunk. zipWith (+) adds the first element of fibs (0) and the first element of tail fibs (1), producing 1. The list is now effectively 0 : 1 : 1 : <thunk>.
   • fibs !! 3 requires evaluating the next part of the thunk. zipWith (+) adds the second element of fibs (1) and the second element of tail fibs (the newly computed 1), producing 2.
3. The list in memory now looks like: 0 : 1 : 1 : 2 : <thunk>. The computed values are stored.
4. If you now ask for fibs !! 2, the runtime doesn't recompute anything. It just retrieves the stored value 1.

The list fibs acts as its own memoization table, and this behavior is an automatic consequence of call-by-need evaluation. The programmer simply stated the recursive definition of the sequence; the language took care of ensuring that each Fibonacci number is computed only once.

3. Explicit Memoization: The Python Way

Now, let's achieve the same result in Python, an eager, call-by-value language.

A naive recursive implementation is notoriously inefficient due to redundant computations:

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

# Calling fib(35) takes a very long time.

To optimize this, the programmer must explicitly implement memoization. A common way to do this is by using a dictionary as a cache.

memo_cache = {}

def fib_memo(n):
    # 1. Explicitly check if the result is already in the cache
    if n in memo_cache:
        return memo_cache[n]

    # 2. If not, compute it
    if n < 2:
        result = n
    else:
        result = fib_memo(n - 1) + fib_memo(n - 2)
    
    # 3. Explicitly store the result in the cache before returning
    memo_cache[n] = result
    return result

# Calling fib_memo(35) is now instantaneous.

This works, but it mixes the core logic of the Fibonacci algorithm with the caching logic. A cleaner, more idiomatic Python approach uses a decorator, which is a higher-order function that wraps another function to add functionality.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_lru(n):
    if n < 2:
        return n
    return fib_lru(n - 1) + fib_lru(n - 2)

# fib_lru(35) is also instantaneous.

Here, the @lru_cache decorator abstracts away the caching mechanism, but the programmer still has to make the conscious decision to apply it. The memoization is not a feature of the language's evaluation model itself.

4. Contrasting the Philosophies

The video below discusses the semantic differences between strict and lazy evaluation and explores what it would mean for a strict language to "opt-in" to laziness. This provides a great high-level perspective on the contrast we've just examined.

The video's discussion of delay(expression) and force(expression) where the result is cached is a perfect analogy for what Python's @lru_cache provides.

• The first call to fib_lru(n) is like force, which triggers the computation and caches the result.
• Subsequent calls with the same n retrieve the cached value.

This brings us to a clear summary of the two approaches.

Feature	Haskell (Call-by-Need)	Python (Call-by-Value)
Mechanism	Implicit memoization via graph reduction. Part of the core evaluation strategy.	Explicit memoization via programmer-managed data structures (e.g., a dictionary).
Implementation	Automatic and transparent. Any shared expression is memoized by default.	Manual. The programmer must decide what to memoize and apply a technique (e.g., a decorator).
Syntax	No special syntax required. It's just how the language works.	Requires explicit code, such as the @lru_cache decorator or manual cache handling.
Scope	Pervasive. Applies to any value bound with let or where and shared.	Localized. Applies only to the specific functions the programmer chooses to wrap.
Mindset	"Define relationships between values; the runtime will compute them efficiently."	"Define a sequence of computational steps; apply optimizations like caching where needed."

Conclusion

Today we've uncovered one of the most elegant and powerful consequences of Haskell's lazy evaluation model.

Key Takeaways:

• Call-by-need is Haskell's evaluation strategy. It evaluates an expression the first time it's needed and caches the result, replacing the original computation (thunk).
• This provides implicit memoization as a fundamental feature of the language, ensuring that any shared expression is never computed more than once.
• Eager languages like Python follow a call-by-value strategy and require explicit memoization, where the programmer is responsible for implementing and applying caching logic, often using decorators like functools.lru_cache.
• This contrast highlights a core design trade-off: Haskell's model offers powerful, automatic optimization at the cost of a more complex mental model of evaluation, while Python's model is more direct but requires manual optimization.

Preview of the Next Lesson:

We've just seen a major performance benefit of lazy evaluation. However, there are no free lunches in language design. The "evaluate-on-demand" and "cache-everything" nature of call-by-need can have significant memory implications. In our final lesson of this module, we will explore the other side of the coin by addressing the learning outcome: "Identify performance trade-offs of evaluation strategies, such as space leaks in lazy languages and redundant computation in eager ones."