Compiler Design
Non-Imperative Programming Languages
Non-Imperative Programming Languages
Non-imperative paradigms (Functional, Logic, Declarative) present unique compilation challenges compared to traditional procedural languages.
- Higher-order functions & Closures: Functions can return functions. Closures must capture their lexical environment, compiled via closure conversion into a function + environment record.
- Tail Call Optimization: Recursive tail calls are optimized to reuse the current stack frame, reducing space complexity to O(1).
- Lazy Evaluation: Expressions are evaluated only when needed, implemented via thunks (deferred computation records).
- Execution model is search-based (unification + backtracking).
- Compiled using the WAM (Warren Abstract Machine).
- Backtracking is implemented via choice points (saving and restoring state).
- You describe WHAT to compute, not HOW.
- The compiler (or query engine) translates the query to an execution plan using query optimization.
- Optimizations include join ordering and index selection.