Evaluation strategies, laziness and continuations

Lesson 5 showed that the order in which redexes are reduced can decide whether a computation finishes at all. Real languages must fix an order, and they must decide how arguments are passed to functions: as values, as references, or as unevaluated expressions. These choices affect performance, what programs can express and how easy programs are to reason about. This lesson compares the main evaluation strategies, implements lazy evaluation with thunks, and introduces continuations, the idea that 'the rest of the computation' can itself be a value. Continuations explain exceptions, generators, async functions and tail calls in one framework.

CMPUT-274 used generators and async functions as tools and mentioned laziness briefly. Here we implement the mechanisms ourselves, so that you can see exactly what a thunk, a continuation or a trampoline does.

Strict and non-strict evaluation

A function is strict in an argument if it always needs that argument's value. A language is strict, or eager, if it evaluates every argument before calling a function; this is call-by-value, the applicative order of lesson 5. C, Java, Python, Rust, OCaml and JavaScript are strict. A non-strict language passes arguments unevaluated and evaluates them only when, and if, they are needed. Call-by-name re-evaluates the argument expression every time the parameter is used, as ALGOL 60 did. Call-by-need evaluates it at most once and remembers the result; this is lazy evaluation, the strategy of Haskell.

The implementation device for non-strict evaluation is the thunk: a small record holding an unevaluated expression together with the environment needed to evaluate it. Forcing a thunk evaluates the expression. Under call-by-name a thunk is forced afresh each time; under call-by-need it caches its value after the first force. The interpreter below runs the same programs under all three strategies and counts how many times an expensive argument is evaluated.

# One interpreter, three parameter-passing strategies.  We count how many times each
# argument expression is actually evaluated.
#   e ::= n | x | ("+", e, e) | ("*", e, e) | ("if0", e, e, e) | ("fun", x, e) | ("app", e, e) | ("expensive", e)
class Thunk:
    def __init__(self, expr, env, memo):
        self.expr, self.env, self.memo, self.done, self.value = expr, env, memo, False, None
    def force(self, mode):
        if self.memo and self.done: return self.value          # call-by-need: reuse
        v = ev(self.expr, self.env, mode)
        if self.memo: self.done, self.value = True, v
        return v

COUNT = {"expensive": 0}
def ev(e, env, mode):
    if isinstance(e, int): return e
    if isinstance(e, str):
        v = env[e]
        return v.force(mode) if isinstance(v, Thunk) else v
    t = e[0]
    if t == "+": return ev(e[1], env, mode) + ev(e[2], env, mode)
    if t == "*": return ev(e[1], env, mode) * ev(e[2], env, mode)
    if t == "if0": return ev(e[2], env, mode) if ev(e[1], env, mode) == 0 else ev(e[3], env, mode)
    if t == "expensive":
        COUNT["expensive"] += 1; return ev(e[1], env, mode)
    if t == "fun": return ("closure", e[1], e[2], env)
    if t == "app":
        _, x, body, cenv = ev(e[1], env, mode)
        if mode == "value": arg = ev(e[2], env, mode)                 # evaluate now
        else: arg = Thunk(e[2], env, memo=(mode == "need"))           # delay
        return ev(body, {**cenv, x: arg}, mode)

square = ("fun", "x", ("*", "x", "x"))
ignore = ("fun", "x", 42)
arg = ("expensive", ("+", 3, 4))
for name, prog in (("square (expensive 7)", ("app", square, arg)), ("ignore (expensive 7)", ("app", ignore, arg))):
    for mode in ("value", "name", "need"):
        COUNT["expensive"] = 0
        result = ev(prog, {}, mode)
        print(f"{name:22} call-by-{mode:5}: result {result:3}, argument evaluated {COUNT['expensive']} time(s)")

square (expensive 7)   call-by-value: result  49, argument evaluated 1 time(s)
square (expensive 7)   call-by-name : result  49, argument evaluated 2 time(s)
square (expensive 7)   call-by-need : result  49, argument evaluated 1 time(s)
ignore (expensive 7)   call-by-value: result  42, argument evaluated 1 time(s)
ignore (expensive 7)   call-by-name : result  42, argument evaluated 0 time(s)
ignore (expensive 7)   call-by-need : result  42, argument evaluated 0 time(s)

The results summarize the trade-off. For square, which uses its argument twice, call-by-name evaluates the argument twice; call-by-value and call-by-need evaluate it once. For ignore, which never uses its argument, call-by-value wastes an evaluation that the non-strict strategies skip. Call-by-need gets the best of both, at the cost of allocating and checking thunks, and of making it harder to predict when side effects happen. That last point is why lazy languages such as Haskell keep side effects out of ordinary expressions altogether.

Parameter passing in mainstream languages

Two more modes concern what the parameter refers to rather than when it is evaluated. With call-by-reference the parameter is an alias for the caller's variable, so assigning to it changes the caller's variable, as with C++ reference parameters. C has only call-by-value, so programs pass pointers when a function must change the caller's data. Java, Python and JavaScript are often described confusingly. All three are call-by-value, but for objects the value passed is a reference to the object. Reassigning the parameter has no effect on the caller, while mutating the shared object does. The phrase 'call-by-sharing', coined by Barbara Liskov for the CLU language, describes this exactly.

#include <stdio.h>

void by_value(int x)    { x = x + 1; }        /* changes a copy */
void by_pointer(int *p) { *p = *p + 1; }      /* C has no references; pass an address */

int main(void) {
    int n = 10;
    by_value(n);
    printf("after by_value:   n = %d\n", n);
    by_pointer(&n);
    printf("after by_pointer: n = %d\n", n);
    return 0;
}

$ gcc -Wall toy.c -o toy
$ ./toy
after by_value:   n = 10
after by_pointer: n = 11

import java.util.ArrayList;
import java.util.List;

public class Passing {
    static void reassign(List<Integer> xs) { xs = new ArrayList<>(); xs.add(99); }
    static void mutate(List<Integer> xs)   { xs.add(99); }

    public static void main(String[] args) {
        List<Integer> a = new ArrayList<>(List.of(1, 2));
        reassign(a);
        System.out.println("after reassign: " + a);   // the caller's variable is untouched
        mutate(a);
        System.out.println("after mutate:   " + a);   // but the shared object changed
    }
}

after reassign: [1, 2]
after mutate:   [1, 2, 99]

ALGOL 60's call-by-name allowed a famous trick, Jensen's device, in which a summation procedure is passed both an index variable and an expression mentioning it, so that each re-evaluation of the expression sees the updated index. It is elegant and confusing in equal measure, and it is one reason later languages abandoned call-by-name as a default. Scala keeps it as an option: a parameter declared as => T is passed by name, which lets library authors write functions that behave like new control structures.

Laziness in practice

Lazy evaluation makes infinite data structures possible. In Haskell, the list of all natural numbers or all primes is an ordinary value; only the part the program inspects is ever computed. It also lets programs be written as compositions of simple stages without worrying about wasted work. Python reaches for the same benefits with generators and the itertools module, which produce values one at a time on demand. Even strict languages contain small pieces of laziness: the && and || operators, conditional expressions and Python's and/or evaluate their second operand only if needed, which is why they cannot be written as ordinary functions in a strict language.

# Lazy evaluation with generators: an infinite stream of primes, computed only on demand.
from itertools import count, islice, takewhile

def primes():
    """An unbounded sieve: keep a dict of the next composite for each prime found."""
    composites = {}
    for n in count(2):
        if n not in composites:
            yield n                       # n is prime; first composite to cross off is n*n
            composites[n * n] = [n]
        else:
            for p in composites.pop(n):
                composites.setdefault(n + p, []).append(p)

print("first 15 primes:", list(islice(primes(), 15)))
print("primes below 60:", list(takewhile(lambda p: p < 60, primes())))

# Laziness lets us define a stream in terms of itself.
def fibs():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b
print("first 12 Fibonacci numbers:", list(islice(fibs(), 12)))

# Short-circuit operators are a built-in form of laziness.
def noisy(v):
    print(f"  evaluated {v}")
    return v
print("False and noisy(True):", False and noisy(True))
print("True or noisy(False):", True or noisy(False))

first 15 primes: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
primes below 60: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
first 12 Fibonacci numbers: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
False and noisy(True): False
True or noisy(False): True

Laziness has costs. Thunks use memory, and a long chain of unevaluated additions can consume far more memory than the final number would, a problem Haskell programmers call a space leak. The time at which a computation happens becomes hard to predict, which complicates performance tuning and makes side effects dangerous. Haskell therefore provides strictness annotations and functions such as seq and foldl' that force evaluation, and its compiler performs strictness analysis to evaluate eagerly whenever it can prove the result will be needed anyway.

Continuations

At any point during evaluation, there is a 'rest of the computation': what will be done with the value currently being computed. A continuation is that rest of the computation, made explicit as a function. In continuation-passing style (CPS), every function takes an extra argument k, its continuation, and instead of returning a result it calls k with the result. A CPS program never returns in the ordinary sense; every call is a tail call. Compilers for Scheme, ML and Kotlin's coroutines translate programs into CPS or something close to it, because it makes control flow explicit and easy to manipulate.

# Continuation-passing style: every function takes an extra argument k, "what to do next".
import sys

def fact_direct(n):
    return 1 if n == 0 else n * fact_direct(n - 1)

def fact_cps(n, k):
    if n == 0:
        return k(1)
    return fact_cps(n - 1, lambda r: k(n * r))      # the pending multiplication moves into k

print("direct fact 10 =", fact_direct(10))
print("CPS fact 10    =", fact_cps(10, lambda r: r))

# Every call in CPS is a tail call, but CPython does not eliminate tail calls,
# so deep recursion still overflows.  A trampoline returns thunks instead of calling.
def fact_tramp(n, k):
    if n == 0:
        return lambda: k(1)
    return lambda: fact_tramp(n - 1, lambda r: lambda: k(n * r))

def run(thunk):
    while callable(thunk):
        thunk = thunk()
    return thunk

sys.setrecursionlimit(1000)
try:
    fact_direct(5000)
except RecursionError:
    print("direct fact 5000: RecursionError (stack depth limit)")
bits = run(fact_tramp(5000, lambda r: r)).bit_length()
print(f"trampolined CPS fact 5000: a {bits}-bit integer, no stack overflow")

direct fact 10 = 3628800
CPS fact 10    = 3628800
direct fact 5000: RecursionError (stack depth limit)
trampolined CPS fact 5000: a 54233-bit integer, no stack overflow

A tail call is a call that is the last thing a function does. Languages that guarantee tail-call elimination, such as Scheme, run such calls without growing the stack, so loops can be written as recursion. CPython deliberately does not eliminate tail calls, partly to keep full stack traces for debugging, which is why the trampoline above returns thunks to a driver loop instead of calling directly. JavaScript's specification required proper tail calls in 2015, but only Safari's engine implemented them; the others declined, a reminder that a feature in a standard is not the same as a feature in use.

Control operators built from continuations

Once continuations are explicit, many control features become ordinary functions. An exception or early exit simply ignores the current continuation and calls an outer one instead. A generator saves its continuation when it yields and resumes it on the next request. Async and await save the continuation of an awaiting function and resume it when the awaited result arrives. Scheme exposes continuations directly with call/cc (call-with-current-continuation), which captures the current continuation as a first-class value; Racket, Ruby and Standard ML of New Jersey offer variants. The interpreter below adds an escape construct to a CPS interpreter in a single line.

# A CPS interpreter makes control operators easy.  Here "escape" aborts the whole
# computation with a value, the way an exception or an early return would.
def ev(e, env, k, top):
    if isinstance(e, int): return k(e)
    if isinstance(e, str): return k(env[e])
    t = e[0]
    if t in ("+", "*"):
        return ev(e[1], env, lambda a: ev(e[2], env, lambda b: k(a + b if t == "+" else a * b), top), top)
    if t == "if0":
        return ev(e[1], env, lambda c: ev(e[2] if c == 0 else e[3], env, k, top), top)
    if t == "escape":
        return ev(e[1], env, top, top)            # ignore k: jump straight to the top continuation
    if t == "let":
        return ev(e[2], env, lambda v: ev(e[3], {**env, e[1]: v}, k, top), top)

done = lambda v: ("finished", v)
aborted = lambda v: ("escaped", v)
# product of a list, escaping with 0 as soon as a zero is seen
def product(xs):
    e = 1
    for i, _ in enumerate(xs):
        e = ("*", ("if0", f"x{i}", ("escape", 0), f"x{i}"), e)
    env = {f"x{i}": v for i, v in enumerate(xs)}
    return ev(e, env, done, aborted)

print(product([3, 4, 5]))
print(product([3, 0, 5]))

('finished', 60)
('escaped', 0)

Continuations also give a precise account of the difference between statements such as return, break and continue: each one transfers control to a particular continuation saved at a particular point. Lesson 3's small-step semantics can be extended with such operators, and compilers lower all of them to jumps in the end.

Worked examples