Read the syntax. Carry the context. Resume the saved alternative.
Use fourteen canonical lesson programs to reconnect expression data, environments, control, analyzed execution, derived syntax, delayed values, alternatives, pattern frames, rule search, logic limits, internal-definition transformation, a finite eval/apply driver, and an amb evaluator whose failure continuation resumes saved choices.
Can you explain which evaluator component chooses meaning, which transformation prepares source data, which environment persists, and which continuation controls the next nondeterministic alternative?
- Interpret a quoted expression tree as data
- Bind the same symbol differently in different environments
- Evaluate only the selected branch of a special form
- Analyze expression structure once and reuse an execution plan
- Transform let into an existing lambda application rule
- Force an explicit thunk once and memoize its value
- Retain every successful finite alternative
- Extend a frame only with consistent pattern bindings
- Carry frames through a finite sequence of rule goals
- Report recursive search as complete or truncated with a visible frontier
- Distinguish failed lookup from negation and declarative relation from operational search
- Allocate internal names before assignments install mutually recursive procedure values
- Run quoted top-level forms through eval/apply while definitions persist in one global environment
- Thread success and failure continuations so require can resume an earlier amb choice
The first five programs treat programs as data. Environment lookup, special-form control, analysis, and derived syntax each change how that data is interpreted or transformed.
Thunks and nondeterministic alternatives expose control choices as explicit values. Pattern matching and finite queries carry frames that record only consistent bindings from one goal to the next.
Recursive rules add a frontier and work budget so a cyclic or incomplete search cannot masquerade as a complete result. The logic-limits program separately distinguishes a failed lookup from a proven negation.
The internal-definition program scans leading definitions into explicit unassigned bindings and assignments, then compares the original and transformed forms on finite inputs.
The finite evaluator driver dispatches syntax, evaluates applications, mutates one global frame across forms, preserves lexical closure environments, and reports whether a top-level form budget completed the batch. That budget does not count recursive work inside a form.
The amb evaluator changes the control protocol itself. Every success carries the failure continuation for the next available choice; require invokes that continuation when a constraint fails, and all-values repeatedly resumes it until the finite search is exhausted or an explicit solution limit is reached.
(begin
(define (evaluate expression)
(if (number? expression)
expression
(let ((operator (car expression))
(left (cadr expression))
(right (caddr expression)))
(cond ((eq? operator '+)
(+ (evaluate left) (evaluate right)))
((eq? operator '-)
(- (evaluate left) (evaluate right)))
((eq? operator '*)
(* (evaluate left) (evaluate right)))))))
(evaluate '(+ (* 3 4) (- 10 2))))- Output
- —
- Value
- —
- Diagnostic
- —
Each program returns the first expected observation from its corresponding Chapter 4 lesson. The finite driver returns (complete ((defined square) (defined make-adder) (defined add-five) (defined base) 49 12 (assigned base) 81 6) 0). The amb evaluator returns (complete ((1 4) (2 3))) for the constrained pair search.
Follow expression traversal, environment lookup, branch selection, analysis construction, let transformation, thunk state, frame extension, goal sequencing, frontier expansion, failed fact scans, definition collection, global-frame mutation, compound-procedure application, closure capture, top-level budget decrease, amb choice installation, require failure, and the continuation that resumes a later argument choice. These bounded runs do not establish fairness or completeness for infinite search spaces.
Fourteen checks for evaluators, transformations, rules, and continuations
What must an evaluator do to turn expression data into a value?
Answer Numbers evaluate directly. A compound expression asks evaluate to interpret both nested operands before combining their values. The evaluator follows the expression tree one node at a time.
Why can the same expression produce a different value in another environment?
Answer evaluate does not attach one permanent meaning to x or y. It receives an environment with the expression, so the same expression tree can be reused with different bindings.
What would go wrong if an evaluator evaluated both branches of if?
Answer In the first example the alternative divides by zero. The program still returns 60 because the true predicate selects the addition branch and the invalid alternative remains expression data.
Which work can be done before the expression receives an environment?
Answer The resulting plan accepts an environment. Running it only looks up variables, runs the stored operand plans, and applies the already selected operator. One analyzed plan can therefore serve many environments.
What must remain unchanged when let is rewritten as a lambda application?
Answer The evaluator does not need a second implementation of local binding. Its let case rewrites the expression and sends the result back through the ordinary lambda and application cases in the same environment.
Which representation changes make call-by-need visible inside an evaluator?
Answer force-it inspects the tag. On the first demand it calls the stored computation, changes the tag to evaluated-thunk, discards the computation, and stores the value. Later demands select the cached slot and perform no computation again. This exposes the representation change that a lazy evaluator normally hides behind argument handling.
What changes when evaluation keeps the remaining alternatives after one success?
Answer The second program makes two choice positions explicit. scan-y tests every y for one x, and scan-x repeats that work for every x. Returning all pairs whose squared components sum to 25 exposes a finite nondeterministic search as ordinary list-producing control.
How can a matcher carry partial knowledge while it walks two data structures?
Answer A later occurrence looks up the existing binding before extending anything. Equal data preserves the frame; conflicting data returns failed, which every remaining recursive step propagates. This is one-way matching with variables in the pattern, not full bidirectional unification or database search.
How does a rule preserve the middle binding needed by its next goal?
Answer The second program binds grand from the rule head, then solve-goals processes the two parent goals in order. The first goal produces middle values ben and dia. Each frame becomes input to the second goal, which finds cy and eli. This deliberately narrow evaluator supports parent goals in one finite rule body. It does not implement variable renaming, negation, recursive rules, duplicate removal, or general unification.
How can recursive rule expansion terminate honestly when the data may contain a cycle?
Answer The second program uses a three-person cycle. Expanding ada reaches ben, ben reaches cy, and cy reaches ada again. The evaluator spends exactly one work unit per removed frontier item and returns truncated with the remaining frontier when the budget reaches zero. It does not silently present the repeated prefix as the complete ancestor relation. This narrow breadth-first model does not implement general unification, variable renaming, duplicate removal, negation, fairness, or a complete logic-programming engine.
Which conclusions come from the logical relation, and which come from the particular database and search procedure?
Answer The second program gives married a symmetric operational rule: when a direct fact is absent, swap the arguments and search again. This proves (married mickey minnie) after one swap because the reverse fact exists. The same rule alternates forever for an unrelated pair unless the evaluator detects repetition or spends a visible work budget. The logical statement may be symmetric, but the direction and control of the rule still determine the behavior of this executable search.
Why must an evaluator create all internal bindings before it installs any of the procedure values?
Answer 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.
What turns a collection of evaluator procedures into a program that can run a sequence of user forms?
Answer run-program is the driver. It receives quoted top-level forms, one explicit global environment, and a form budget. Every completed form contributes one transcript value while definitions and assignments remain visible to later forms. The full run defines square, make-adder, add-five, and base; add-five keeps the local x value 5 even after the global base changes. The second run stops after five forms and reports four forms still pending. This form budget does not bound recursion or work inside a single form; the packaged browser runtime still supplies the lower-level execution limits.
How can an evaluator turn failure from a terminal error into a request to resume an earlier choice point?
Answer require evaluates its predicate in the same continuation system. A true predicate succeeds with ok; a false predicate invokes the next predicate alternative, which ultimately returns to the most recent amb choice. all-values repeatedly calls the next alternative supplied by each success. The first run exhausts the finite search and reports complete. The second deliberately stops after four solutions and reports truncated. This slice does not implement reversible set!, permanent-set!, random choice order, duplicate suppression, or fairness for infinite search spaces.