Failure resumes the next saved alternative.
An explicit evaluator can pass both a success continuation and a failure continuation through guest evaluation. Amb saves the remaining choices in the failure path, while require invokes that path when a candidate violates a constraint.
How can an evaluator turn failure from a terminal error into a request to resume an earlier choice point?
- Evaluate guest expressions with explicit success and failure continuations
- Represent guest compound procedures with lexical environments
- Propagate alternative continuations through operator and operand evaluation
- Implement amb by trying each choice with a failure path to the rest
- Implement require by invoking the current alternative when its predicate is false
- Collect every finite solution or stop at an explicit solution limit
- Keep omitted assignment rollback and fairness policies visible
ambeval receives expression, environment, succeed, and fail. A deterministic expression calls succeed with its value and the failure continuation that should be used if later work rejects that value. An amb form evaluates its first choice and replaces failure with a procedure that tries the remaining choices. Operand evaluation threads these continuations from left to right, so a failure inside a procedure body can revisit an earlier nondeterministic argument.
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.
(begin
(define (tagged-list? expression tag)
(and (pair? expression) (eq? (car expression) tag)))
(define (self-evaluating? expression)
(or (number? expression)
(string? expression)
(boolean? expression)))
(define (quoted? expression) (tagged-list? expression 'quote))
(define (if? expression) (tagged-list? expression 'if))
(define (lambda? expression) (tagged-list? expression 'lambda))
(define (begin? expression) (tagged-list? expression 'begin))
(define (amb? expression) (tagged-list? expression 'amb))
(define (require? expression) (tagged-list? expression 'require))
(define (text-of-quotation expression) (cadr expression))
(define (if-predicate expression) (cadr expression))
(define (if-consequent expression) (caddr expression))
(define (if-alternative expression) (cadddr expression))
(define (lambda-parameters expression) (cadr expression))
(define (lambda-body expression) (cddr expression))
(define (begin-actions expression) (cdr expression))
(define (amb-choices expression) (cdr expression))
(define (require-predicate expression) (cadr expression))
(define (operator expression) (car expression))
(define (operands expression) (cdr expression))
(define (pair-bindings variables values)
(cond ((and (null? variables) (null? values)) '())
((null? variables) (error "too many arguments"))
((null? values) (error "too few arguments"))
(else
(cons (cons (car variables) (car values))
(pair-bindings (cdr variables) (cdr values))))))
(define (extend-environment variables values environment)
(append (pair-bindings variables values) environment))
(define (lookup-variable-value variable environment)
(let ((binding (assoc variable environment)))
(if binding
(cdr binding)
(error "unbound guest variable" variable))))
(define (make-procedure parameters body environment)
(list 'compound parameters body environment))
(define (compound-procedure? procedure)
(tagged-list? procedure 'compound))
(define (procedure-parameters procedure) (cadr procedure))
(define (procedure-body procedure) (caddr procedure))
(define (procedure-environment procedure) (cadddr procedure))
(define (eval-sequence expressions environment succeed fail)
(cond ((null? expressions) (succeed 'ok fail))
((null? (cdr expressions))
(ambeval (car expressions) environment succeed fail))
(else
(ambeval
(car expressions)
environment
(lambda (ignored next-alternative)
(eval-sequence
(cdr expressions)
environment
succeed
next-alternative))
fail))))
(define (get-arguments expressions environment succeed fail)
(if (null? expressions)
(succeed '() fail)
(ambeval
(car expressions)
environment
(lambda (argument next-argument)
(get-arguments
(cdr expressions)
environment
(lambda (remaining next-remaining)
(succeed (cons argument remaining) next-remaining))
next-argument))
fail)))
(define (apply-procedure procedure arguments succeed fail)
(cond ((procedure? procedure)
(succeed (apply procedure arguments) fail))
((compound-procedure? procedure)
(eval-sequence
(procedure-body procedure)
(extend-environment
(procedure-parameters procedure)
arguments
(procedure-environment procedure))
succeed
fail))
(else
(error "not a guest procedure" procedure))))
(define (eval-if expression environment succeed fail)
(ambeval
(if-predicate expression)
environment
(lambda (predicate-value next-predicate)
(ambeval
(if predicate-value
(if-consequent expression)
(if-alternative expression))
environment
succeed
next-predicate))
fail))
(define (eval-require expression environment succeed fail)
(ambeval
(require-predicate expression)
environment
(lambda (predicate-value next-predicate)
(if predicate-value
(succeed 'ok next-predicate)
(next-predicate)))
fail))
(define (eval-amb choices environment succeed fail)
(define (try-next remaining)
(if (null? remaining)
(fail)
(ambeval
(car remaining)
environment
succeed
(lambda () (try-next (cdr remaining))))))
(try-next choices))
(define (eval-application expression environment succeed fail)
(ambeval
(operator expression)
environment
(lambda (procedure next-operator)
(get-arguments
(operands expression)
environment
(lambda (arguments next-arguments)
(apply-procedure
procedure
arguments
succeed
next-arguments))
next-operator))
fail))
(define (ambeval expression environment succeed fail)
(cond ((self-evaluating? expression)
(succeed expression fail))
((symbol? expression)
(succeed
(lookup-variable-value expression environment)
fail))
((quoted? expression)
(succeed (text-of-quotation expression) fail))
((if? expression)
(eval-if expression environment succeed fail))
((lambda? expression)
(succeed
(make-procedure
(lambda-parameters expression)
(lambda-body expression)
environment)
fail))
((begin? expression)
(eval-sequence
(begin-actions expression)
environment
succeed
fail))
((amb? expression)
(eval-amb
(amb-choices expression)
environment
succeed
fail))
((require? expression)
(eval-require expression environment succeed fail))
((pair? expression)
(eval-application expression environment succeed fail))
(else
(error "unknown guest expression" expression))))
(define primitive-environment
(list (cons '+ +) (cons '- -) (cons '* *) (cons '/ /)
(cons '= =) (cons '< <) (cons '> >)
(cons '<= <=) (cons '>= >=)
(cons 'list list) (cons 'cons cons)
(cons 'car car) (cons 'cdr cdr)
(cons 'null? null?) (cons 'pair? pair?)
(cons 'not not) (cons 'abs abs)))
(define (all-values expression solution-limit)
(if (= solution-limit 0)
(list 'truncated '())
(let ((answers '())
(count 0))
(ambeval
expression
primitive-environment
(lambda (value next-alternative)
(set! answers (cons value answers))
(set! count (+ count 1))
(if (= count solution-limit)
(list 'truncated (reverse answers))
(next-alternative)))
(lambda ()
(list 'complete (reverse answers)))))))
(define pair-program
'((lambda (left right)
(begin
(require (< left right))
(require (= (+ left right) 5))
(list left right)))
(amb 1 2 3 4)
(amb 1 2 3 4)))
(all-values pair-program 20)
)- Output
- —
- Value
- —
- Diagnostic
- —
The pair search returns (complete ((1 4) (2 3))). The capped triple search returns (truncated ((1 2 3) (1 2 4) (1 2 5) (1 3 4))).
Follow each amb choice installing a failure continuation for the remaining choices. Then trace get-arguments as a rejected require in the body resumes a later third argument, later second argument, or later first argument. The solution cap stops without claiming that the remaining search is empty.
Change the program before you read the hint.
Change the pair program so left and right are chosen from 1 through 6, require their product to be 12, and collect every solution where left is smaller. Predict the solution order before running it.
Show one hint
The left-to-right amb order tests all right choices for left 1 before moving to left 2. Only ordered factor pairs survive both require forms.