Normal-order evaluation delays arguments until needed. Thunks wrap unevaluated expressions with their environments. Memoization ensures each thunk is forced at most once.
Normal order vs applicative order
Applicative order evaluates arguments before applying the procedure. Normal order passes arguments unevaluated and only forces them when actually needed. The results agree for pure functions, but diverge when evaluation has side effects or non-termination.
Scheme
; Applicative vs normal order โ the difference matters; when an argument would diverge.; In applicative order, (test 0 (/ 1 0)) would error; because (/ 1 0) is evaluated before test is called.; In normal order, the second argument is never used.
(define (try a b)
(if (= a 0) 1 b))
; Applicative order: both args evaluated; (try 0 (/ 1 0)) => ERROR in standard Scheme; But with short-circuit tricks we can simulate normal order:
(define (try-lazy a b-thunk)
(if (= a 0) 1 (b-thunk)))
(display "try-lazy(0, <error>): ")
(display (try-lazy 0 (lambda () (/ 10))))
(newline)
; => 1 (the thunk is never called); When a != 0, the thunk IS forced:
(display "try-lazy(1, <42>): ")
(display (try-lazy 1 (lambda () 42)))
; => 42
Python
# Normal vs applicative order in Pythondef try_eager(a, b):
"""Applicative: b is always evaluated"""return1if a == 0else b
# try_eager(0, 1/0) # ZeroDivisionError!def try_lazy(a, b_thunk):
"""Normal order: b is a thunk, called only if needed"""return1if a == 0else b_thunk()
print(f"try_lazy(0, <error>): {try_lazy(0, lambda: 1/0)}") # 1print(f"try_lazy(1, <42>): {try_lazy(1, lambda: 42)}") # 42
An interpreter with lazy evaluation
To make evaluation lazy, we change apply: instead of evaluating arguments, we wrap them as thunks. A thunk is a pair of (expression, environment) — everything needed to evaluate the expression later. When a value is actually needed, we force the thunk.
Without memoization, forcing the same thunk twice evaluates the expression twice. A memoized thunk caches its result after the first force. This is the difference between call-by-name (no memo) and call-by-need (with memo). Haskell uses call-by-need throughout.
With lazy evaluation built into the interpreter, streams become ordinary lists. cons delays its second argument automatically. No special cons-stream or delay/force needed — the language itself is lazy. This unifies lists and streams.
Scheme
; Streams via explicit laziness (delay/force).; In a lazy evaluator, these would be implicit.
(define-syntax my-delay
(syntax-rules ()
((my-delay expr) (lambda () expr))))
(define (my-force thunk) (thunk))
(define (stream-cons x delayed-y)
(cons x delayed-y))
(define (stream-car s) (car s))
(define (stream-cdr s) (my-force (cdr s)))
; Infinite stream of integers from n
(define (integers-from n)
(stream-cons n (my-delay (integers-from (+ n 1)))))
(define nats (integers-from 1))
; Take first k elements
(define (stream-take s k)
(if (= k 0) '()
(cons (stream-car s)
(stream-take (stream-cdr s) (- k 1)))))
(display "First 10 naturals: ")
(display (stream-take nats 10))
(newline)
; Lazy filter
(define (stream-filter pred s)
(cond ((pred (stream-car s))
(stream-cons (stream-car s)
(my-delay (stream-filter pred (stream-cdr s)))))
(else (stream-filter pred (stream-cdr s)))))
(define evens (stream-filter even? nats))
(display "First 8 evens: ")
(display (stream-take evens 8))
Python
# Lazy lists via generators in Pythondef integers_from(n):
whileTrue:
yield n
n += 1def take(stream, k):
result = []
for x in stream:
iflen(result) >= k:
break
result.append(x)
return result
nats = integers_from(1)
print(f"First 10 naturals: {take(nats, 10)}")
def lazy_filter(pred, stream):
for x in stream:
if pred(x):
yield x
evens = lazy_filter(lambda x: x % 2 == 0, integers_from(1))
print(f"First 8 evens: {take(evens, 8)}")
Lazy evaluation and control flow
In a lazy language, if doesn't need to be a special form — it can be an ordinary procedure, since arguments aren't evaluated until needed. User-defined control structures become possible. This is why Haskell can define if-then-else as a regular function.
Scheme
; In a lazy language, if could be a regular procedure.; We simulate this with thunks (lambdas).
(define (lazy-if condition then-thunk else-thunk)
(if condition (then-thunk) (else-thunk)))
; Works correctly โ only the chosen branch runs
(display "lazy-if true: ")
(display (lazy-if #t
(lambda () "yes")
(lambda () (/ 10)))) ; never evaluated!
(newline)
(display "lazy-if false: ")
(display (lazy-if #f
(lambda () (/ 10)) ; never evaluated!
(lambda () "no")))
(newline)
; Custom control: unless
(define (unless condition then-thunk else-thunk)
(lazy-if (not condition) then-thunk else-thunk))
(display "unless false: ")
(display (unless #f
(lambda () "ran the body")
(lambda () "skipped")))
Python
# Lazy if as a regular function in Pythondef lazy_if(condition, then_thunk, else_thunk):
return then_thunk() if condition else else_thunk()
print(f"lazy_if True: {lazy_if(True, lambda: 'yes', lambda: 1/0)}")
print(f"lazy_if False: {lazy_if(False, lambda: 1/0, lambda: 'no')}")
def unless(condition, then_thunk, else_thunk):
return lazy_if(not condition, then_thunk, else_thunk)
print(f"unless False: {unless(False, lambda: 'ran the body', lambda: 'skipped')}")
Python is strictly applicative-order, so laziness must be encoded explicitly via lambda wrappers or generators. Scheme's delay/force are macros that do the wrapping automatically. In a fully lazy evaluator (like Haskell), neither is needed — all arguments are thunks by default. The Python generator protocol (yield) provides a natural translation for streams but not for general lazy arguments.
Thunk