Module Quiz

Complete this quiz after finishing all concept and practice pages. The quiz includes 15 current-module questions (with at least 2 on evaluation-model tracing and 1 on closure/scope behavior), 5 interleaved questions from S1/S3/earlier S4 modules, and a 4-tier remediation rubric.

Current Module Questions

Question 1: Procedural vs Data Abstraction

A teammate says "A Set class with add, contains, remove is procedural abstraction." Is this accurate?

Answer: It is both. The methods are procedural abstractions (names hiding bodies). The set of values plus the operations together is a data abstraction (an ADT). The distinction is: procedural abstraction hides how a computation is done; data abstraction hides how data is represented. A well-built Set class does both.

Question 2: Abstraction Barrier Leak

You see customer.account._balance -= amount in application code. What is wrong with this, and what is the fix?

Answer: It bypasses the account's abstraction barrier -- clients should go through a withdraw(amount) operation. The leak means (a) invariants like "balance ≥ 0" cannot be enforced, (b) the representation of _balance cannot be changed without editing every client. Fix: make _balance inaccessible (or clearly name-mangled in Python, static in C, private in Java), and require all mutation through domain operations.

Question 3: Stratified Design

Give one sign that a system is not stratified, and one sign it has too many layers.

Answer: Not stratified: a low-level module imports a high-level one (upward dependency). Too many layers: three adjacent layers whose interfaces differ only in naming, none of which adds a new vocabulary -- often a sign of ceremonial architecture without purpose.

Question 4: Higher-Order vs Callback

What distinguishes a higher-order function from a plain "takes a callback" API?

Answer: A HOF is first-class in both directions -- it may return procedures, not just accept them, and may store them in data structures. Most callback APIs only flow in one direction (accept). Crucially, many HOFs (e.g. make-adder, memoize) have no natural reading as callbacks at all.

Question 5: Closure / Scope Behavior (required)

Given this Scheme program, what does the final expression evaluate to, and why?

(define n 5)
(define (make-proc) (lambda () n))
(define p (make-proc))
(let ((n 99)) (p))

Answer: 5. Scheme uses lexical scope. When make-proc is called, the inner lambda captures the environment that exists at its definition -- the one where n is 5. The let creates a new frame with n = 99, but that frame is the caller's environment, not the one captured by p. Variable lookup in p walks the chain from its definition, not from its call site. This is also the canonical one-line demonstration of the difference between lexical and dynamic scope.

Question 6: map/filter/reduce Pipeline

Rewrite this Python loop as a single pipeline using map, filter, and reduce (with functools.reduce):

total = 0
for x in xs:
    if x > 0:
        total += x * x

Answer:

from functools import reduce
total = reduce(lambda a, b: a + b,
               map(lambda x: x * x, filter(lambda x: x > 0, xs)),
               0)

Note the initial value of 0 for reduce -- essential if xs can be empty.

Question 7: Evaluation Model Trace (required)

Trace (sum-of-squares (+ 1 2) (* 3 4)) in the substitution model, showing each reduction step, where (define (sum-of-squares x y) (+ (square x) (square y))) and (define (square x) (* x x)). Use applicative order.

Answer:

(sum-of-squares (+ 1 2) (* 3 4))
-> (sum-of-squares 3 12)
-> (+ (square 3) (square 12))
-> (+ (* 3 3) (* 12 12))
-> (+ 9 144)
-> 153

Applicative order evaluates (+ 1 2) and (* 3 4) first (both fully reduced to 3 and 12), then substitutes into sum-of-squares' body.

Question 8: Evaluation Model Trace (required)

In the environment model, describe what happens when (add5 10) is called, given:

(define (make-adder n) (lambda (x) (+ x n)))
(define add5 (make-adder 5))
(add5 10)

Answer:

1. At (define add5 (make-adder 5)): make-adder is called with n = 5. A new frame F1 is created, { n: 5 }, parent = GLOBAL. The lambda body is never evaluated; instead a procedure value is created whose environment pointer is F1. That procedure is bound to add5 in GLOBAL.
2. At (add5 10): add5 is resolved in GLOBAL to the procedure value from step 1. A new frame F2 is created, { x: 10 }, parent = F1 (the procedure's captured environment), not GLOBAL. The body (+ x n) is evaluated in F2: x -> 10 from F2, n -> 5 from F1 (via parent pointer). Result: 15.

Critically, F2's parent is the definition environment, not the caller's -- that is the mechanical definition of lexical scope.

Question 9: Applicative vs Normal Order

Why must if be a special form in an applicative-order language?

Answer: Because applicative order evaluates all operands before calling a procedure. If if were an ordinary function, both branches would be evaluated before the test -- meaning (if safe? 42 (/ 1 0)) would always divide by zero. if needs to inspect the test first and then evaluate only one branch. Normal-order (or lazy) languages do not need this special treatment.

Question 10: Tail Call vs Recursive Process

Classify each as tail or non-tail position, and justify in one phrase: (a) (if p (f x) (g x)) (b) (let ((v (f x))) v) (c) (+ 1 (f x)) (d) (begin (log x) (f x))

Answer:

• (a) tail: both branches of an if in tail position are themselves tail positions.
• (b) tail: v is the body, and (f x) is the result bound to v; equivalent to ((lambda (v) v) (f x)) whose application is in tail position. More precisely, (let ((v (f x))) v) reduces to (f x).
• (c) non-tail: + is still waiting to add 1 to whatever (f x) returns.
• (d) tail: (f x) is the last expression of begin; its value is the value of the whole begin.

Question 11: Interpreter Core

What are the two mutually-recursive procedures at the heart of any Scheme evaluator, and what does each do?

Answer:

• eval(exp, env): dispatches on the syntactic shape of exp. For a number, returns it. For a symbol, looks it up in env. For a special form (if, lambda, define), handles it explicitly. For an application (f a b), recursively evaluates operator and operands, then hands control to apply.
• apply(proc, args): dispatches on the kind of procedure. For a primitive, calls the host implementation. For a compound procedure (a closure), extends the procedure's defining environment with a new frame binding parameters to args, then calls eval on the body in that extended environment.

Question 12: Lexical Scope in an Interpreter

In Concept 11's Python evaluator, which single field of the Procedure representation makes scope lexical rather than dynamic?

Answer: The env field captured at procedure creation. When the procedure is later called, the new frame's parent is this captured env, not the caller's current env. If the evaluator instead extended the caller's env, the language would be dynamically scoped. That one line is the entire mechanical content of "lexical scope."

Question 13: Staging / Analysis

What speedup comes from separating analyze(exp) from the per-call evaluator (SICP §4.1.7), and why?

Answer: The evaluator no longer re-dispatches on syntax every time a piece of code runs. analyze does the dispatch once and returns a closure over the syntactic choices; the closure is invoked per call with only the env. Typical speedups on tree-walking Scheme evaluators are 5-20× on loops and recursive programs -- eliminated dispatch dominates. Bytecode and JIT add further layers.

Question 14: Cost of Mutation

Give one concrete correctness issue that appears the moment set! is introduced into a pure functional program.

Answer: Referential transparency is lost: the same expression, evaluated at different times, can produce different results. You can no longer replace an expression by its value (let ((y (f x))) (+ y y) vs (+ (f x) (f x)) may differ). This kills equational reasoning and makes memoization and parallel evaluation unsafe without extra machinery.

Question 15: Streams as Pure Time

Why is using a stream of (time -> balance) potentially cheaper than using a mutable balance variable for a ledger application?

Answer: The stream gives you history and identity without mutation: any past balance is still reachable (no information loss); the data is trivially safe to read concurrently; derived views (moving averages, alerts, audits) are pure functions over the stream; replay is free. The price is the delay overhead and the risk of space leaks if you hold the head. For ledger-shaped problems, the tradeoff is often favorable.

Interleaved Review Questions

Prior Module Question 1 (from S4M1: C Programming Fundamentals)

Why does C lack closures, and what is the closest idiomatic equivalent?

Answer: C procedures are not values that can carry an environment; local variables live on the stack and are destroyed when the caller returns. The idiomatic equivalent is a struct carrying captured state plus a function pointer that takes that struct as its first argument. This is "closures, by hand" -- the same shape, manually expressed.

Prior Module Question 2 (from S4M2: Memory, Pointers, Machine Representation)

A function returns a pointer to a local variable. Why is this undefined behavior, and how does this relate to the difference between C and Scheme for returning functions?

Answer: Local variables of a C function live in its stack frame; the frame is destroyed on return, so the pointer dangles. Scheme closures also want to "return something pointing into" their frame (the captured environment), but Scheme frames are allocated on the heap and kept alive as long as any closure references them. This is the concrete cost -- and payoff -- of first-class procedures.

Prior Module Question 3 (from S3M2: Refactoring Techniques)

How does "extract function" connect to procedural abstraction as described in this module?

Answer: Extract function is the refactoring mechanic that creates a procedural abstraction in existing code. The refactoring only pays off if the extracted function has a name that captures intent and a stable contract. Extracting a function named do_stuff gives you no abstraction; extracting one named is_tax_exempt_for_state does.

Prior Module Question 4 (from S1: Math Foundations)

Why is reduction via fold / reduce related to induction?

Answer: A fold over a list defines a value recursively over the list's structure: base case on the empty list (returning the identity) and inductive case (combining the head with the fold of the tail). This is exactly the shape of a structural-induction proof. Recognizing folds as "induction on lists" lets you prove correctness by induction on the list length.

Prior Module Question 5 (from S3M1: OOD Foundations & Code Smells)

How does a closure capturing state relate to encapsulation in OOP?

Answer: A closure with captured mutable state is a minimal object: the captured variables are its private fields, the procedure itself is its public method. SICP §3.1 is an OO tutorial in closure clothing. OOP's encapsulation adds syntactic machinery (classes, visibility modifiers), but the semantic core is the same: behavior bundled with hidden state.

Self-Assessment and Remediation

Mastery (90-100% correct)

• Advance to Module 5 completion. Apply the evaluation-model traces and interpreter in the semester project or exam. Revisit the interpreter kata periodically to keep it fast.

Proficient (75-89%)

• Review only the concept pages tied to missed questions. Rework at least one trace in Practice 2 and verify on paper. Redo Kata 3 (tiny interpreter) once.

Developing (60-74%)

• Rework Practice 2 (Evaluation Models Workshop) and Practice 3 (Interpreter Construction Clinic) in full. Most of the module's judgment lives in those two. Do not start Cluster 5 until the interpreter runs the acceptance tests.

Insufficient (<60%)

• Return to the concept sequence from Cluster 1 in order. Do each "Mini Drill" on paper. Rebuild the interpreter from scratch once. Do not attempt the module quiz again until all three clusters' mastery checks pass.