An explicit evaluator passes a success continuation and a failure continuation through guest evaluation. Amb saves remaining choices in the failure path.
Guiding question
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 selected finite search and reports complete. The second deliberately stops after four solutions and reports truncated. The lesson evaluator covers ordered amb choices, require, procedure application, and success or failure continuation transfer.
SICP code7,667 of 1,048,576 UTF-8 bytes
(begin(define(tagged-list?expressiontag)(and(pair?expression)(eq?(carexpression)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-quotationexpression)(cadrexpression))(define(if-predicateexpression)(cadrexpression))(define(if-consequentexpression)(caddrexpression))(define(if-alternativeexpression)(cadddrexpression))(define(lambda-parametersexpression)(cadrexpression))(define(lambda-bodyexpression)(cddrexpression))(define(begin-actionsexpression)(cdrexpression))(define(amb-choicesexpression)(cdrexpression))(define(require-predicateexpression)(cadrexpression))(define(operatorexpression)(carexpression))(define(operandsexpression)(cdrexpression))(define(pair-bindingsvariablesvalues)(cond((and(null?variables)(null?values))'())((null?variables)(error"too many arguments"))((null?values)(error"too few arguments"))(else(cons(cons(carvariables)(carvalues))(pair-bindings(cdrvariables)(cdrvalues))))))(define(extend-environmentvariablesvaluesenvironment)(append(pair-bindingsvariablesvalues)environment))(define(lookup-variable-valuevariableenvironment)(let((binding(assocvariableenvironment)))(ifbinding(cdrbinding)(error"unbound guest variable"variable))))(define(make-procedureparametersbodyenvironment)(list'compoundparametersbodyenvironment))(define(compound-procedure?procedure)(tagged-list?procedure'compound))(define(procedure-parametersprocedure)(cadrprocedure))(define(procedure-bodyprocedure)(caddrprocedure))(define(procedure-environmentprocedure)(cadddrprocedure))(define(eval-sequenceexpressionsenvironmentsucceedfail)(cond((null?expressions)(succeed'okfail))((null?(cdrexpressions))(ambeval(carexpressions)environmentsucceedfail))(else(ambeval(carexpressions)environment(lambda(ignorednext-alternative)(eval-sequence(cdrexpressions)environmentsucceednext-alternative))fail))))(define(get-argumentsexpressionsenvironmentsucceedfail)(if(null?expressions)(succeed'()fail)(ambeval(carexpressions)environment(lambda(argumentnext-argument)(get-arguments(cdrexpressions)environment(lambda(remainingnext-remaining)(succeed(consargumentremaining)next-remaining))next-argument))fail)))(define(apply-procedureprocedureargumentssucceedfail)(cond((procedure?procedure)(succeed(applyprocedurearguments)fail))((compound-procedure?procedure)(eval-sequence(procedure-bodyprocedure)(extend-environment(procedure-parametersprocedure)arguments(procedure-environmentprocedure))succeedfail))(else(error"not a guest procedure"procedure))))(define(eval-ifexpressionenvironmentsucceedfail)(ambeval(if-predicateexpression)environment(lambda(predicate-valuenext-predicate)(ambeval(ifpredicate-value(if-consequentexpression)(if-alternativeexpression))environmentsucceednext-predicate))fail))(define(eval-requireexpressionenvironmentsucceedfail)(ambeval(require-predicateexpression)environment(lambda(predicate-valuenext-predicate)(ifpredicate-value(succeed'oknext-predicate)(next-predicate)))fail))(define(eval-ambchoicesenvironmentsucceedfail)(define(try-nextremaining)(if(null?remaining)(fail)(ambeval(carremaining)environmentsucceed(lambda()(try-next(cdrremaining))))))(try-nextchoices))(define(eval-applicationexpressionenvironmentsucceedfail)(ambeval(operatorexpression)environment(lambda(procedurenext-operator)(get-arguments(operandsexpression)environment(lambda(argumentsnext-arguments)(apply-procedureprocedureargumentssucceednext-arguments))next-operator))fail))(define(ambevalexpressionenvironmentsucceedfail)(cond((self-evaluating?expression)(succeedexpressionfail))((symbol?expression)(succeed(lookup-variable-valueexpressionenvironment)fail))((quoted?expression)(succeed(text-of-quotationexpression)fail))((if?expression)(eval-ifexpressionenvironmentsucceedfail))((lambda?expression)(succeed(make-procedure(lambda-parametersexpression)(lambda-bodyexpression)environment)fail))((begin?expression)(eval-sequence(begin-actionsexpression)environmentsucceedfail))((amb?expression)(eval-amb(amb-choicesexpression)environmentsucceedfail))((require?expression)(eval-requireexpressionenvironmentsucceedfail))((pair?expression)(eval-applicationexpressionenvironmentsucceedfail))(else(error"unknown guest expression"expression))))(defineprimitive-environment(list(cons'++)(cons'--)(cons'**)(cons'//)(cons'==)(cons'<<)(cons'>>)(cons'<=<=)(cons'>=>=)(cons'listlist)(cons'conscons)(cons'carcar)(cons'cdrcdr)(cons'null?null?)(cons'pair?pair?)(cons'notnot)(cons'absabs)))(define(all-valuesexpressionsolution-limit)(if(=solution-limit0)(list'truncated'())(let((answers'())(count0))(ambevalexpressionprimitive-environment(lambda(valuenext-alternative)(set!answers(consvalueanswers))(set!count(+count1))(if(=countsolution-limit)(list'truncated(reverseanswers))(next-alternative)))(lambda()(list'complete(reverseanswers)))))))(definepair-program'((lambda(leftright)(begin(require(<leftright))(require(=(+leftright)5))(listleftright)))(amb1234)(amb1234)))(all-valuespair-program20))
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 search stops when it exhausts its choices or reaches the configured solution cap.
Try it yourself
Change the program and compare the result.
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 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.