An evaluator can make local initialization explicit.
A procedure-body transformation can allocate every internal name first, install each value with assignment, and preserve the remaining body so mutually recursive helpers share one local environment.
Why must an evaluator create all internal bindings before it installs any of the procedure values?
- Recognize the leading internal definitions in a procedure body
- Convert procedure-definition syntax into an explicit lambda value
- Allocate every local name with an unassigned marker before assignment
- Preserve the original non-definition body after the assignments
- Compare original and transformed programs on the same finite inputs
- Keep observed agreement separate from a proof about every program or implementation
The scan-out pass reads a procedure body as data. It takes the leading define forms, converts procedure-definition shorthand into lambda expressions, creates one let binding for every name with an explicit unassigned marker, and places a set! for every definition before the original remaining body. The names therefore exist together before any closure is applied, which gives mutually recursive helpers one shared local environment.
The second program executes both forms. classify-original uses internal definitions directly. classify-scanned writes the transformed let and set! structure explicitly. Both return the same parity observations for 7 and 8, and equal? reports true. That finite comparison checks this transformation and these inputs; it does not prove semantic equivalence for every Scheme program, reveal a hidden Lispex compiler pass, or specify every implementation’s intermediate representation.
(begin
(define body
'((define (even-step value)
(if (= value 0)
#t
(odd-step (- value 1))))
(define (odd-step value)
(if (= value 0)
#f
(even-step (- value 1))))
(list (even-step n) (odd-step n))))
(define (definition? expression)
(and (pair? expression)
(eq? (car expression) 'define)))
(define (take-definitions expressions)
(if (and (pair? expressions)
(definition? (car expressions)))
(cons (car expressions)
(take-definitions (cdr expressions)))
'()))
(define (drop-definitions expressions)
(if (and (pair? expressions)
(definition? (car expressions)))
(drop-definitions (cdr expressions))
expressions))
(define (definition-name definition)
(if (symbol? (cadr definition))
(cadr definition)
(car (cadr definition))))
(define (definition-value definition)
(if (symbol? (cadr definition))
(caddr definition)
(cons 'lambda
(cons (cdr (cadr definition))
(cddr definition)))))
(define (make-binding definition)
(list (definition-name definition)
(list 'quote '*unassigned*)))
(define (make-assignment definition)
(list 'set!
(definition-name definition)
(definition-value definition)))
(define (scan-out-defines expressions)
(let ((definitions (take-definitions expressions))
(remaining (drop-definitions expressions)))
(if (null? definitions)
expressions
(list
(cons 'let
(cons (map make-binding definitions)
(append (map make-assignment definitions)
remaining)))))))
(car (scan-out-defines body)))- Output
- —
- Value
- —
- Diagnostic
- —
The transformation program returns one let expression with even-step and odd-step bound to quoted *unassigned* markers, followed by two set! forms and the original list body. The comparison program returns (#t ((#f #t) (#t #f)) ((#f #t) (#t #f))).
In the transformation run, separate reading quoted source data from collecting leading definitions, constructing bindings, converting procedure definitions to lambda values, constructing assignments, and appending the remaining body. In the comparison run, find the one let environment, both set! operations, and the alternating closure calls. Agreement is reported only for the selected inputs.
Change the program before you read the hint.
Add a third internal helper that recognizes values divisible by three through three mutually recursive remainder procedures. Write both the original and explicitly scanned versions, then compare their results for 8 and 9.
Show one hint
Allocate all three names before the assignments. Each closure calls the next remainder procedure after subtracting one, and only the remainder-zero procedure returns true at zero.