Abstraction and HOF Lab

Build a small numerical methods library in both Scheme and Python. Use it as a scaffold to practice procedural abstraction, data abstraction, higher-order functions, and closures -- all together, on the same code.

Retrieval Prompts

Answer closed-book before starting:

1. What goes into a "contract" for a procedural abstraction?
2. What fields does a closure carry with it, and why?
3. Write the types of map, filter, reduce, and compose.
4. When is a returned procedure the right move, and not a passed one?

Target Library

Implement these operations. Each of them is built in SICP §1.3, which you should only open if stuck.

Name	Signature	Meaning
sum(term, a, next, b)	summation of a sequence	Σ term(i) for i = a, next(a), next(next(a)) …, ≤ b
product(term, a, next, b)	product of a sequence	same, with * and initial 1
accumulate(combine, id, term, a, next, b)	generalize sum and product
integral(f, a, b, dx)	numerical integration	Simpson or midpoint
fixed-point(f, x0)	iterate f until `	x - f(x)
average-damp(f)	returns (λx. (x + f(x))/2)
deriv(f, dx)	returns the derivative of f
newton(f, guess)	fixed-point of x − f(x) / deriv(f)(x)

Two things to notice:

• accumulate should fully subsume sum and product by being called with the right combine and id.
• average-damp, deriv, newton all return procedures. They must be implemented as closures.

Workflow

1. In Scheme, implement each operation. Keep procedures small; every one has a contract in a comment.
2. Port the entire library to Python. Use lambda or nested def freely. Closures should look nearly identical.
3. Write at least three callers of the library:
   • sum-of-cubes 1..10
   • integral of cube over [0, 1] (should approach 1/4)
   • square root via newton, compared to the host language's sqrt
4. Extract a pressure table in a README.md that lists, for each piece of the library, which abstraction move it demonstrates (procedural? data? HOF? closure?).

Compare and Distinguish

• sum vs accumulate. Which should be the primitive, and which should be a one-liner in terms of the other?
• deriv with closures vs deriv taking an extra dx every call. What does the closure version buy you? What does it cost?
• newton in Scheme vs in C. Sketch how you would write newton in C. Which parts become harder? Which become impossible without closures?

Common Mistake Check

Identify the error in each of these patterns (do NOT write correct code yet -- explain the bug):

1. newton is implemented as a loop that mutates x, then returns x. Why is this a smell in a library that wants to be composable?
2. average-damp is implemented as average-damp(f, x) -- taking x as an extra argument instead of returning a procedure.
3. integral hard-codes dx = 0.001 deep inside its body.
4. fixed-point uses set! inside a loop over a mutable binding captured by a closure; two callers of the same library share a cached guess.

Extension: Abstract Data Types

Add a Point, Vector, and Matrix ADT to the library. Design the constructors and selectors first; forbid callers from touching the representation.

• Implement in Scheme using cons/list, with clearly-labeled constructors and selectors.
• Re-implement in Python using a namedtuple or a @dataclass(frozen=True). Hide fields that should not be read by clients.
• Write one vector operation (dot-product) using only selectors. Change the representation (e.g. swap internal order) and confirm dot-product does not change.

Evidence Check

This lab is complete only if:

• Both Scheme and Python implementations exist and pass the same acceptance tests.
• accumulate is the primitive; sum and product are one-liners on top.
• average-damp, deriv, newton are closures that return procedures.
• The Point/Vector/Matrix ADT can swap representations without touching callers.
• The README has the pressure table described above.
• You can explain, in one sentence per operation, which abstraction move justifies its shape.