Substitution explains an application by rewriting its body.
Substitution replaces each parameter with its argument expression or value. Applicative order and normal order reach the same answer with different work.
What does substitution reveal about procedure application, and what changes when arguments are evaluated before or after they are inserted into the body?
- Represent a procedure body and application as quoted expression data
- Replace a parameter consistently throughout a body
- Separate applicative-order argument evaluation from normal-order expansion
- Observe repeated argument work in an explicit normal-order model
- Keep an explanatory substitution model distinct from runtime environment internals
- Recognize that mutation and object identity require a richer model than naive substitution
The first program does not ask Lispex to switch evaluation strategies. It treats the call (square (+ 2 3)) and the body (* x x) as quoted data, then constructs two textbook reduction paths. The applicative path evaluates (+ 2 3) first, substitutes the value 5, and reduces (* 5 5). The normal path substitutes the unevaluated operand expression first, producing (* (+ 2 3) (+ 2 3)), and only then reduces both copies.
The second program makes the work difference observable with an argument procedure that increments a counter. The ordinary Lispex call (square (argument)) evaluates the argument once before applying square. The explicit normal-model schedule calls argument twice because the body uses x twice. Both schedules return 25, but their call counts differ. The comparison records two explicitly written finite schedules and their exact call counts.
- Output
- —
- Value
- —
- Diagnostic
- —
The reduction program returns ((applicative (square (+ 2 3)) (square 5) (* 5 5) 25) (normal (square (+ 2 3)) (* (+ 2 3) (+ 2 3)) (* 5 5) 25)). The schedule program returns ((applicative 25 1) (normal-model 25 2)).
In the first run, follow substitute through both occurrences of x and compare replacement by the value 5 with replacement by the expression (+ 2 3). In the second, locate one argument application inside the ordinary procedure call and two argument applications in the explicitly written normal-model multiplication. The runtime trace records the code that was actually run; the quoted reduction lists are explanatory data rather than hidden evaluator frames.
Change the program and compare the result.
Use the body (+ (* x x) y), substitute x with (+ 1 2) and y with 4, and construct both an applicative path and a normal-order path as data. Predict how many copies of (+ 1 2) appear before reduction.
Show hint
Substitute one parameter at a time. Because x occurs twice, the normal-order body contains two copies of its operand expression; y occurs once.