Module 5: Abstraction & Interpretation: Case Studies
These case studies connect SICP-style abstraction to real interpreters, DSLs, evaluators, and mutation costs.
Case Study 1: Tiny Lisp Interpreter As eval / apply
Scenario: A learner thinks interpreters are magic. A tiny Lisp shows that evaluation is an explicit recursive process over expressions and environments.
Source anchor: Peter Norvig's (How to Write a Lisp Interpreter in Python) provides a compact interpreter walkthrough that makes eval and apply concrete.
Module concepts: eval, apply, environment, expression, procedure.
Wrong Approach
"The language runtime just knows what code means."
Better Approach
Model evaluation:
self-evaluating:
numbers, strings
symbol:
lookup in environment
combination:
eval operator
eval operands
apply procedure
Tradeoff Table
| Choice | Gain | Cost |
|---|---|---|
| Treat interpreter as black box | Less conceptual overhead initially | Weak transfer to real evaluator design |
Trace eval/apply explicitly | Clear operational model | More recursion and environment detail |
Jump straight to host-language eval | Quick demo | Hides the core abstraction being taught |
Failure Mode
Learners can run examples but cannot explain why symbol lookup, recursion, or procedure application behaves the way it does.
Required Artifact
Write an eval/apply trace for (+ (* 2 3) 4).
Project / Capstone Connection
Use this tracing style for any DSL, rules engine, or interpreter-style component you design later.
Case Study 2: Environment Model Explains Closures
Scenario: A function returns another function that remembers a variable. The substitution model becomes awkward; the environment model explains it.
Source anchor: SICP's environment model and Norvig's lispy environment implementation anchor this case.
Module concepts: closure, lexical scope, environment frame, binding.
Wrong Approach
"The variable disappeared when the outer function returned."
Better Approach
Draw frames:
make_counter frame:
count -> 0
returned closure:
code + pointer to environment
Tradeoff Table
| Choice | Gain | Cost |
|---|---|---|
| Force substitution model everywhere | One simple story | Breaks down on closures and mutation |
| Use environment frames | Explains lexical scope directly | Requires graph-like reasoning |
| Memorize closure behavior by example | Fast recall for simple cases | Weak debugging model |
Failure Mode
A learner predicts that captured variables vanish after return and cannot reason about stateful closures or lexical scope bugs.
Required Artifact
Draw environment frames for a counter closure after three calls.
Project / Capstone Connection
Apply this model when you design callback-heavy code, templating evaluators, or scoped configuration languages.
Case Study 3: DSL Dispatcher For Build Rules
Scenario: A build tool has commands like compile, test, package, and deploy. The first implementation is a giant if/else.
Source anchor: Crafting Interpreters builds interpreters through scanning, parsing, representation, and execution, which grounds the move from string conditionals to a DSL model.
Module concepts: DSL, parser, AST, dispatcher, abstraction barrier.
Wrong Approach
Keep adding stringly typed conditionals.
Better Approach
Represent commands:
AST:
Task(name, dependencies, action)
Evaluator:
resolve dependencies
execute action
record result
Tradeoff Table
| Choice | Gain | Cost |
|---|---|---|
Giant if/else dispatcher | Fast first implementation | Hard to extend and validate |
| AST + evaluator | Clear abstraction barrier | Parser and representation work upfront |
| Full general-purpose scripting | Maximum flexibility | Much larger surface to secure and debug |
Failure Mode
Adding one new command duplicates parsing, validation, and dependency logic across branches until the tool becomes brittle.
Required Artifact
Design a tiny build-rule AST and evaluator pseudocode.
Project / Capstone Connection
Use this pattern when later projects need command dispatch, workflow engines, or structured configuration.
Case Study 4: Mutation Breaks Equational Reasoning
Scenario: Two calls to a function return different results because hidden state changes inside the function.
Source anchor: SICP's assignment and mutation chapters frame the cost of state and the environment model.
Module concepts: mutation, state, referential transparency, streams.
Wrong Approach
Assume a procedure call can always be replaced by its value.
Better Approach
Name the state:
pure function:
same input -> same output
stateful procedure:
depends on hidden environment
repair:
pass state explicitly or isolate mutation
Tradeoff Table
| Choice | Gain | Cost |
|---|---|---|
| Hidden mutable state | Convenient local updates | Harder reasoning and testing |
| Explicit state passing | Clear behavior | More plumbing in APIs |
| Isolated mutation boundary | Balance of clarity and practicality | Requires discipline at the boundary |
Failure Mode
Refactors or tests assume referential transparency, but hidden state changes make repeated calls diverge unexpectedly.
Required Artifact
Compare a pure and mutable accumulator with an environment trace.
Project / Capstone Connection
Use this lens when deciding where later systems or tooling projects should allow mutation versus preserve pure transformations.
Case Study 5: Normal-Order Saves Work, Or Repeats It
Scenario: A conditional-like function receives an expensive expression. Applicative order evaluates it even when unused; normal order delays it but may duplicate work.
Source anchor: SICP evaluation-order material and interpreter implementation make the distinction concrete.
Module concepts: applicative order, normal order, laziness, thunk, memoization.
Wrong Approach
"Evaluation order is an implementation detail."
Better Approach
Trace both:
applicative:
evaluate all arguments first
normal:
substitute/delay until needed
lazy with memoization:
delay once, cache result
Tradeoff Table
| Choice | Gain | Cost |
|---|---|---|
| Applicative order | Predictable eager execution | Wastes work on unused branches |
| Normal order | Can avoid unnecessary work | May repeat expensive evaluation |
| Lazy with memoization | Avoids repeated work after first force | Extra runtime machinery |
Failure Mode
An apparently harmless abstraction either evaluates an error-producing branch too early or recomputes an expensive thunk many times.
Required Artifact
Write an evaluation trace for an expression where normal order avoids an error or expensive computation.
Project / Capstone Connection
Use this distinction when later designs introduce deferred configuration, streaming pipelines, or cached computations.
Source Map
| Source | Use it for |
|---|---|
| Norvig: lis.py | tiny Lisp interpreter and environments |
| Crafting Interpreters | scanning/parsing/AST/evaluation path |
| SICP JS edition | evaluation, abstraction, mutation |
Completion Standard
- At least three artifacts are completed.
- At least one artifact traces eval/apply.
- At least one artifact draws environment frames.
- At least one artifact designs a tiny DSL or interpreter.