Compilation of Non-Imperative Programming Languages
1. Landscape
Non-imperative = no explicit mutable state/sequence: functional (ML, Haskell), logic (Prolog), dataflow/GPU. Compiler maps high-level semantics to imperative machine via closures, unification, lazy graphs.
2. Functional Languages
| Feature | Compile strategy |
|---|---|
| First-class fns/closures | closure record {code ptr, env}; lambda lifting |
| Currying/partial app | return new closure capturing args |
| Lazy eval | thunk {code, memoized value}; force on demand |
| GC | essential (rapid alloc); tagless/precise via type maps |
| Tail calls | reuse frame (must for recursion) |
| Pattern match | decision tree / jump table |
Example: map f [1,2] → loop applying closure f (env ptr passed), result list heap-allocated.
3. Logic Languages (Prolog)
- Unification (match + bind vars) compiled to WAM (Warren machine) ops: get/unify, trail for backtracking.
- Backtracking: choice points saved; fail → restore + try next clause.
- Indexing on first arg avoids trying all clauses.
4. Other Models
Dataflow/array (NumPy, shaders): fuse elementwise ops, tile for cache/GPU, auto-parallelize pure loops (no dependences by construction).
5. Exam Points
- Closure + thunk compilation — 5-7 marks, very frequent.
- WAM/unification/backtracking sketch — 5 marks, frequent.
- Functional vs imperative compile differences — 3-5 marks, frequent.