Keep every successful choice instead of committing early.
An evaluator can treat alternatives as data, test each resulting value, and return the complete finite set of successes rather than one selected branch.
What changes when evaluation keeps the remaining alternatives after one success?
- Represent a finite search space as an explicit choice list
- Evaluate each alternative before applying its requirement
- Retain every value that satisfies the predicate
- Enumerate combinations without hiding the search order
The first search receives quoted expression trees. evaluate interprets one tree at a time, while search applies acceptable? to the resulting value and keeps scanning after both failure and success. No early commitment discards the remaining alternatives.
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.
(begin
(define (evaluate expression)
(if (number? expression)
expression
(let ((operator (car expression))
(left (evaluate (cadr expression)))
(right (evaluate (caddr expression))))
(cond ((eq? operator '+) (+ left right))
((eq? operator '*) (* left right))))))
(define (search alternatives acceptable?)
(if (null? alternatives)
'()
(let ((value (evaluate (car alternatives))))
(if (acceptable? value)
(cons value (search (cdr alternatives) acceptable?))
(search (cdr alternatives) acceptable?)))))
(search '((+ 1 2) (* 2 3) (+ 4 5) (* 4 4)) odd?))- Output
- —
- Value
- —
- Diagnostic
- —
The first program returns (3 9). The second returns ((3 4) (4 3)).
In the first run, follow evaluate before each predicate decision and confirm that success still recurses over the remaining alternatives. In the second run, follow the nested choice order from (1 1) through (4 4) and locate both accepted pairs.
Change the program before you read the hint.
Change the first predicate to even? and predict every retained value in the original alternative order.
Show one hint
Evaluate all four expression trees first. A successful value does not stop the scan.