Keep the result. Reconstruct the process.
Use eleven small programs to reconnect the chapter’s twelve ideas. Predict first, run second, then explain what the visible execution adds to the final value.
Can you explain what a program returns, how its process grows or shrinks, and when a procedure value constructs behavior for a later application?
- Read an operator and its operands as one combination
- Explain which environment supplies a procedure parameter
- Contrast recursive and iterative process shapes
- Follow a procedure passed as an argument
- Build a new transformation by returning and composing procedures
- Preserve an invariant while reducing a problem
- Refine a numerical guess through a fixed iterative process
- Accumulate a finite continued fraction from its final term
- Search for a fixed point by feeding each transformed value into the next step
- Reduce an exponent while preserving a product invariant
- Reduce modular powers and limit a fixed-base Fermat conclusion
- Compare tree-recursive call growth with linear iterative state transitions
Run the two factorial programs with the same input. Their value agrees, but one carries a complete fixed-size state while the other leaves multiplications pending until smaller calls return.
Then run the higher-order sum. The evaluator receives term and next as ordinary procedure values and applies them at each step. In the returned-procedure example, compose and repeated first build transformations and only later apply them; reversing composition order changes the result.
Euclid’s algorithm turns every remainder pair into a smaller problem with the same greatest common divisor. The square-root program refines one guess repeatedly. The continued-fraction program carries a completed suffix from the final term toward the first. The fixed-point program passes one transformation as a value and feeds each output back as the next guess.
Fast exponentiation preserves product times base to the exponent. The modular program reduces after each square or multiplication and shows why one passing base-2 congruence is not a primality proof.
Finally compare the Fibonacci call tree with iterative state. fib 8 returns only 21, but the instrumented tree reports 67 applications and depth 8. The iterative process reaches the same value in eight transitions with a fixed number of state fields.
(letrec ((factorial
(lambda (n product)
(if (= n 0)
product
(factorial (- n 1) (* n product))))))
(factorial 8 1))- Output
- —
- Value
- —
- Diagnostic
- —
The two factorial programs return 40320. The higher-order sum returns 55. The returned-procedure composition returns (49 37 15). Euclid’s algorithm returns 2. The square-root program returns (1.414213562373095 1.9999999999999996). The continued fraction returns 0.6179775280898876. The fixed-point transformation returns 1.6180257510729614. Fast exponentiation returns 1594323. The base-2 Fermat checks return (#t #f #t). The Fibonacci measurement returns (21 67 8).
Compare factorial calls and multiplications, locate term and next in the sum, separate returned-procedure construction from later application, follow Euclid’s decreasing remainder pairs, trace each quotient and average in the square-root refinements, watch the continued fraction accumulate, follow transformed fixed-point guesses, distinguish even and odd exponent reductions, locate each remainder reduction in the fixed-base checks, then find repeated Fibonacci calls along the two recursive branches. These bounded traces describe only the selected runs and may themselves be truncated at the event limit.
Eleven short checks for your own explanation
Why can equal results come from different processes?
Answer A value records the answer, while the order and state of pending work determine the process that produces it.
What makes sum a higher-order procedure?
Answer It accepts term and next as procedure values and applies them while traversing the interval.
When does a procedure returned by compose actually use its captured f and g?
Answer compose constructs and returns the new procedure first. The captured procedures run only when that returned procedure later receives an x argument.
What remains unchanged while Euclid’s arguments shrink?
Answer The set of common divisors, and therefore the greatest common divisor, is the same for each successive argument pair.
Why does the square-root process carry only one guess forward?
Answer The improvement rule can compute the next guess entirely from the current guess and the unchanged target.
What does a bounded trace not establish?
Answer It does not prove behavior for every input and does not create authentication, evidence, or authority.
Why does the iterative continued fraction begin at the final term?
Answer Each outer fraction layer needs the already computed suffix below it, so carrying that suffix from k toward 1 makes the current result complete at every call.
What makes the fixed-point program’s stopping rule explicit?
Answer The remaining count is part of every call’s state, and reaching zero returns the current guess without relying on a hidden tolerance.
Why can an even exponent be halved after the base is squared?
Answer The squared base raised to half the exponent equals the original base raised to the even exponent, so the product invariant is unchanged.
Why does the passing result for 561 not prove that 561 is prime?
Answer The program checks one base-2 congruence only, and composite 561 satisfies it. Passing that equality does not exclude all composite candidates.
Why do recursive Fibonacci calls grow much faster than iterative steps?
Answer Each non-base recursive call creates two overlapping subproblems, while the iterative process advances one fixed-size state exactly once per index.