Execution Notes: Eager vs Lazy Evaluation in Python

This book mirrors pure lambda-calculus encodings in Python. One crucial difference is evaluation strategy.

Remark (Why IF_THUNK)

With Church booleans under normal-order (call-by-name style) reduction, IF evaluates only the selected branch. Python evaluates arguments eagerly, so both branches are computed before IF gets control. That breaks recursive definitions like factorial and modulo because the recursive branch is evaluated even when the base case holds.

We fix this by passing thunks (zero-argument functions) and forcing only the selected branch:

IF_THUNK = lambda b: (lambda t: (lambda f: b(t)(f)()))

result = IF_THUNK(condition)(lambda: base_case)(lambda: recursive_case)

Example

Here is the factorial definition from the recursion chapter, written to be safe under eager evaluation:

FACT = Z(
    lambda f: (
        lambda n: IF_THUNK(is_zero(n))(
            lambda: one
        )(
            lambda: mul(n)(f(pred(n)))
        )
    )
)

Exercise

Rewrite a recursive Church-encoded pow using IF_THUNK. Then compare it to the same definition written with Python’s native if.