The Paradigm Divide

Most of this course has focused on compiling imperative languages (C, C++, Java) — languages where the programmer describes how to compute using sequences of statements, mutable variables, and explicit control flow.

Functional languages (Haskell, ML, Lisp/Scheme, Erlang) and logic languages (Prolog, Datalog) describe what the result should be, leaving the compiler to determine how to compute it. This fundamentally changes how the compiler works:

The compiler for a non-imperative language cannot reuse the straightforward techniques from imperative compilation. Instead, it needs fundamentally different intermediate representations and transformations.

First-Class and Higher-Order Functions

In functional languages, functions are first-class values — they can be passed as arguments, returned from other functions, and stored in data structures:

1-- A function that takes another function as an argument
2applyTwice :: (Int -> Int) -> Int -> Int
3applyTwice f x = f (f x)
4
5-- A function that returns a new function
6adder :: Int -> (Int -> Int)
7adder x = \y -> x + y     -- This creates a closure!

The critical challenge is that functions may capture variables from their enclosing scope — these are closures.

Example:

1let a = 5 in
2let f = \x -> x + a in    -- f captures 'a' from the environment
3f 3                       -- evaluates to 8

The compiler must ensure that a remains alive and accessible after the scope where it was defined has exited. This is impossible on a simple stack — the solution is closure conversion.

Lazy Evaluation and Thunks

In eager evaluation (call-by-value), arguments are fully evaluated before the function is called. In lazy evaluation (call-by-need), arguments are evaluated only when their value is first needed, and the result is memoized (cached) so subsequent uses don't re-evaluate.

Haskell uses lazy evaluation by default. This is a radical departure from imperative languages and requires a fundamentally different execution model.

The mechanism: thunks.

A thunk is a heap-allocated object representing a suspended computation. When the compiler encounters a lazy expression, it generates code that creates a thunk instead of evaluating immediately:

1-- Haskell: this creates a thunk, does NOT compute 1+2 immediately
2let x = 1 + 2 in
3-- x is a thunk: { code: () -> 1+2, result: unevaluated }
4
5-- When x is first used (e.g., in print x):
6-- 1. Check if thunk is already evaluated
7-- 2. If not, run the code, store result in the thunk
8-- 3. Return the stored result
9-- 4. All future uses of x return the cached result

Compilation implications:

• Every expression becomes a heap-allocated thunk (memory overhead)
• Every value access requires a check-and-possibly-evaluate (time overhead)
• The compiler performs strictness analysis to detect when an argument will definitely be needed — in those cases, it can safely use eager evaluation and skip the thunk entirely. This optimization is critical for performance.

Tail-Call Optimization (TCO)

Functional languages use recursion as the primary looping construct (no for or while loops in pure Haskell). A naive recursive function would consume stack space proportional to the recursion depth — for a loop that runs a million times, this would overflow the stack.

Tail-call optimization solves this. When a function's last action is to call another function (or itself), the compiler reuses the current stack frame instead of creating a new one:

1-- Tail-recursive factorial: the recursive call is the LAST operation
2factorial :: Int -> Int -> Int
3factorial 0 acc = acc
4factorial n acc = factorial (n - 1) (n * acc)   -- Tail call!

Without TCO:

factorial(5, 1)
  factorial(4, 5)
    factorial(3, 20)
      factorial(2, 60)
        factorial(1, 120)
          factorial(0, 120) → 120

Stack depth: O(n) — each call adds a new frame.

With TCO:

factorial(5, 1)  →  overwrite frame with (4, 5)
factorial(4, 5)  →  overwrite frame with (3, 20)
factorial(3, 20)  →  overwrite frame with (2, 60)
...
factorial(0, 120)  →  120

Stack depth: O(1) — the same frame is reused.

How the compiler implements TCO:

1; Instead of:
2;   CALL factorial    ; pushes return address, creates new frame
3;   RET
4
5; The compiler generates:
6;   MOV [SP], new_n   ; overwrite current frame's n parameter
7;   MOV [SP+8], new_acc ; overwrite current frame's acc parameter
8;   JMP factorial     ; jump to start of function (no call/ret!)

The JMP instead of CALL is the key — it doesn't push a return address, so when the "recursion" finishes, it returns directly to the original caller.

Why TCO matters: Without it, functional programs would be impractical for any significant computation. TCO makes recursion as efficient as a while loop. This is why Haskell, Scheme, and Erlang guarantee TCO in their language specification.

The Warren Abstract Machine (WAM) — A Brief Overview

The Warren Abstract Machine is the standard compilation target for Prolog, invented by David H.D. Warren in 1983. Understanding its architecture explains how logic programs execute:

WAM memory areas:

1. Global stack (heap): Stores compound terms (structures like f(a, b))
2. Local stack: Stores choice points (for backtracking) and environment frames
3. Trail: Records variable bindings that must be undone on backtracking

WAM registers:

• A1, A2, ...: Argument registers (pass arguments to predicates)
• X1, X2, ...: Temporary variable registers
• P: Program counter (points to current instruction)
• S: Structure pointer (for unification)

Compiling a Prolog clause:

1ancestor(X, Y) :- parent(X, Y).
2ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

The compiler generates WAM instructions:

1. Try / Retry / Trust instructions to manage the choice point stack for the three clauses
2. Unify instructions that perform unification of arguments
3. Call instructions that invoke sub-predicates
4. Proceed instruction for the last call (tail-call optimization in Prolog!)

The key insight: Prolog compilation is fundamentally about compiling unification and backtracking into efficient machine code, rather than compiling statement sequences like an imperative compiler.