4.3.3 Implementing the <span style="color:green">Amb</span> <span style="color:blue">amb</span> Evaluator

Permalink copied!

4.3.3 Implementing the Amb amb Evaluator

The evaluation of an ordinary Scheme expression JavaScript program may return a value, may never terminate, or may signal an error. In nondeterministic Scheme JavaScript the evaluation of an expression a program may in addition result in the discovery of a dead end, in which case evaluation must backtrack to a previous choice point. The interpretation of nondeterministic Scheme JavaScript is complicated by this extra case.

We will construct the amb evaluator for nondeterministic Scheme JavaScript by modifying the analyzing evaluator of section 4.1.7.[1] As in the analyzing evaluator, evaluation of an expression a component is accomplished by calling an execution procedure function produced by analysis of that expression. component. The difference between the interpretation of ordinary Scheme JavaScript and the interpretation of nondeterministic Scheme JavaScript will be entirely in the execution procedures. functions.

Execution procedures functions and continuations

Recall that the execution procedures functions for the ordinary evaluator take one argument: the environment of execution. In contrast, the execution procedures functions in the amb evaluator take three arguments: the environment, and two procedures functions called continuation procedures. continuation functions. The evaluation of an expression a component will finish by calling one of these two continuations: If the evaluation results in a value, the success continuation is called with that value; if the evaluation results in the discovery of a dead end, the failure continuation is called. Constructing and calling appropriate continuations is the mechanism by which the nondeterministic evaluator implements backtracking.

It is the job of the success continuation to receive a value and proceed with the computation. Along with that value, the success continuation is passed another failure continuation, which is to be called subsequently if the use of that value leads to a dead end.

It is the job of the failure continuation to try another branch of the nondeterministic process. The essence of the nondeterministic language is in the fact that expressions components may represent choices among alternatives. The evaluation of such an expression a component must proceed with one of the indicated alternative choices, even though it is not known in advance which choices will lead to acceptable results. To deal with this, the evaluator picks one of the alternatives and passes this value to the success continuation. Together with this value, the evaluator constructs and passes along a failure continuation that can be called later to choose a different alternative.

A failure is triggered during evaluation (that is, a failure continuation is called) when a user program explicitly rejects the current line of attack (for example, a call to require may result in execution of (amb), amb(), an expression that always fails—see section 4.3.1). The failure continuation in hand at that point will cause the most recent choice point to choose another alternative. If there are no more alternatives to be considered at that choice point, a failure at an earlier choice point is triggered, and so on. Failure continuations are also invoked by the driver loop in response to a try-again retry request, to find another value of the expression. program.

In addition, if a side-effect operation (such as assignment to a variable) occurs on a branch of the process resulting from a choice, it may be necessary, when the process finds a dead end, to undo the side effect before making a new choice. This is accomplished by having the side-effect operation produce a failure continuation that undoes the side effect and propagates the failure.

In summary, failure continuations are constructed by

amb expressions—to provide a mechanism to make alternative choices if the current choice made by the amb expression leads to a dead end;
the top-level driver—to provide a mechanism to report failure when the choices are exhausted;
assignments—to intercept failures and undo assignments during backtracking.

Failures are initiated only when a dead end is encountered. This occurs

if the user program executes (amb); amb();
if the user types try-again retry at the top-level driver.

Failure continuations are also called during processing of a failure:

When the failure continuation created by an assignment finishes undoing a side effect, it calls the failure continuation it intercepted, in order to propagate the failure back to the choice point that led to this assignment or to the top level.
When the failure continuation for an amb runs out of choices, it calls the failure continuation that was originally given to the amb, in order to propagate the failure back to the previous choice point or to the top level.

Structure of the evaluator

The syntax- and data-representation procedures functions for the amb evaluator, and also the basic analyze procedure, function, are identical to those in the evaluator of section 4.1.7, except for the fact that we need additional syntax procedures functions to recognize the amb special form:[2] the amb syntactic form:

Original	JavaScript
`(define (amb? exp) (tagged-list? exp 'amb)) (define (amb-choices exp) (cdr exp))`	`function is_amb(component) { return is_tagged_list(component, "application") && is_name(function_expression(component)) && symbol_of_name(function_expression(component)) === "amb"; } function amb_choices(component) { return arg_expressions(component); }`

Original		JavaScript
		We continue to use the parse function of section 4.1.2, which doesn't support `amb` as a syntactic form and instead treats `amb(`$\ldots$`)` as a function application. The function `is_amb` ensures that whenever the name `amb` appears as the function expression of an application, the evaluator treats the application as a nondeterministic choice point.[3]

We must also add to the dispatch in analyze a clause that will recognize this special form and generate an appropriate execution procedure: such expressions and generate an appropriate execution function:

Original	JavaScript
`((amb? exp) (analyze-amb exp))`	`$\ldots$ : is_amb(component) ? analyze_amb(component) : is_application(component) $\ldots$`

The top-level procedure function ambeval (similar to the version of eval evaluate given in section 4.1.7) analyzes the given expression component and applies the resulting execution procedure function to the given environment, together with two given continuations:

Original	JavaScript
`(define (ambeval exp env succeed fail) ((analyze exp) env succeed fail))`	`function ambeval(component, env, succeed, fail) { return analyze(component)(env, succeed, fail); }`

A success continuation is a procedure function of two arguments: the value just obtained and another failure continuation to be used if that value leads to a subsequent failure. A failure continuation is a procedure function of no arguments. So the general form of an execution procedure function is

Original	JavaScript
`(lambda (env succeed fail) ;; succeed is (lambda (value fail) $\ldots$) ;; fail is (lambda () $\ldots$) $\ldots$)`	`(env, succeed, fail) => { // $\texttt{succeed}\,$ is $\texttt{(value, fail) =>}~\ldots$ // $\texttt{fail}\,$ is $\texttt{() =>}~\ldots$ $\ldots$ }`

For example, executing

Original		JavaScript
`(ambeval exp the-global-environment (lambda (value fail) value) (lambda () 'failed))`		`ambeval($component$, the_global_environment, (value, fail) => value, () => "failed");`

will attempt to evaluate the given expression component and will return either the expression's component's value (if the evaluation succeeds) or the symbol failed string "failed" (if the evaluation fails). The call to ambeval in the driver loop shown below uses much more complicated continuation procedures, functions, which continue the loop and support the try-again retry request.

Most of the complexity of the amb evaluator results from the mechanics of passing the continuations around as the execution procedures functions call each other. In going through the following code, you should compare each of the execution procedures functions with the corresponding procedure function for the ordinary evaluator given in section 4.1.7.

Simple expressions

The execution procedures functions for the simplest kinds of expressions are essentially the same as those for the ordinary evaluator, except for the need to manage the continuations. The execution procedures functions simply succeed with the value of the expression, passing along the failure continuation that was passed to them.

Original	JavaScript
`(define (analyze-self-evaluating exp) (lambda (env succeed fail) (succeed exp fail)))`	`function analyze_literal(component) { return (env, succeed, fail) => succeed(literal_value(component), fail); }`

Original	JavaScript
`(define (analyze-variable exp) (lambda (env succeed fail) (succeed (lookup-variable-value exp env) fail)))`	`function analyze_name(component) { return (env, succeed, fail) => succeed(lookup_symbol_value(symbol_of_name(component), env), fail); }`

Original	JavaScript
`(define (analyze-lambda exp) (let ((vars (lambda-parameters exp)) (bproc (analyze-sequence (lambda-body exp)))) (lambda (env succeed fail) (succeed (make-procedure vars bproc env) fail))))`	`function analyze_lambda_expression(component) { const params = lambda_parameter_symbols(component); const bfun = analyze(lambda_body(component)); return (env, succeed, fail) => succeed(make_function(params, bfun, env), fail); }`

Notice that looking up a variable name always succeeds. If lookup-variable-value lookup_symbol_value fails to find the variable, name, it signals an error, as usual. Such a failure indicates a program bug—a reference to an unbound variable; name; it is not an indication that we should try another nondeterministic choice instead of the one that is currently being tried.

Conditionals and sequences

Conditionals are also handled in a similar way as in the ordinary evaluator. The execution procedure function generated by analyze-if analyze_conditional invokes the predicate execution procedure pproc function pfun with a success continuation that checks whether the predicate value is true and goes on to execute either the consequent or the alternative. If the execution of pproc pfun fails, the original failure continuation for the if conditional expression is called.

Original

JavaScript

(define (analyze-if exp) (let ((pproc (analyze (if-predicate exp))) (cproc (analyze (if-consequent exp))) (aproc (analyze (if-alternative exp)))) (lambda (env succeed fail) (pproc env ;; success continuation for evaluating the predicate ;; to obtain pred-value (lambda (pred-value fail2) (if (true? pred-value) (cproc env succeed fail2) (aproc env succeed fail2))) ;; failure continuation for evaluating the predicate fail))))

function analyze_conditional(component) { const pfun = analyze(conditional_predicate(component)); const cfun = analyze(conditional_consequent(component)); const afun = analyze(conditional_alternative(component)); return (env, succeed, fail) => pfun(env, // success continuation for evaluating the predicate // to obtain $\texttt{pred\char`_value}$ (pred_value, fail2) => is_truthy(pred_value) ? cfun(env, succeed, fail2) : afun(env, succeed, fail2), // failure continuation for evaluating the predicate fail); }

Original		JavaScript
Sequences are also handled in the same way as in the previous evaluator, except for the machinations in the subprocedure `sequentially` that are required for passing the continuations. Namely, to sequentially execute `a` and then `b`, we call `a` with a success continuation that calls `b`. `(define (analyze-sequence exps) (define (sequentially a b) (lambda (env succeed fail) (a env ;; success continuation for calling a (lambda (a-value fail2) (b env succeed fail2)) ;; failure continuation for calling a fail))) (define (loop first-proc rest-procs) (if (null? rest-procs) first-proc (loop (sequentially first-proc (car rest-procs)) (cdr rest-procs)))) (let ((procs (map analyze exps))) (if (null? procs) (error "Empty sequence - - ANALYZE")) (loop (car procs) (cdr procs))))`		Sequences are also handled in the same way as in the previous evaluator, except for the machinations in the subfunction `sequentially` that are required for passing the continuations. Namely, to sequentially execute `a` and then `b`, we call `a` with a success continuation that calls `b`. function analyze_sequence(stmts) { function sequentially(a, b) { return (env, succeed, fail) => a(env, // success continuation for calling $\texttt{a}$ (a_value, fail2) => is_return_value(a_value) ? succeed(a_value, fail2) : b(env, succeed, fail2), // failure continuation for calling $\texttt{a}$ fail); } function loop(first_fun, rest_funs) { return is_null(rest_funs) ? first_fun : loop(sequentially(first_fun, head(rest_funs)), tail(rest_funs)); } const funs = map(analyze, stmts); return is_null(funs) ? env => undefined : loop(head(funs), tail(funs)); }

Definitions Declarations and assignments

Definitions Declarations are another case where we must go to some trouble to manage the continuations, because it is necessary to evaluate the definition-value expression before actually defining the new variable. declaration-value expression before actually declaring the new name. To accomplish this, the definition-value declaration-value execution procedure vproc function vfun is called with the environment, a success continuation, and the failure continuation. If the execution of vproc vfun succeeds, obtaining a value val for the defined variable, the variable is defined and the success is propagated: declared name, the name is declared and the success is propagated:

Original	JavaScript
`(define (analyze-definition exp) (let ((var (definition-variable exp)) (vproc (analyze (definition-value exp)))) (lambda (env succeed fail) (vproc env (lambda (val fail2) (define-variable! var val env) (succeed 'ok fail2)) fail))))`	`function analyze_declaration(component) { const symbol = declaration_symbol(component); const vfun = analyze(declaration_value_expression(component)); return (env, succeed, fail) => vfun(env, (val, fail2) => { assign_symbol_value(symbol, val, env); return succeed(undefined, fail2); }, fail); }`

Assignments are more interesting. This is the first place where we really use the continuations, rather than just passing them around. The execution procedure function for assignments starts out like the one for definitions. declarations. It first attempts to obtain the new value to be assigned to the variable. name. If this evaluation of vproc vfun fails, the assignment fails.

If vproc vfun succeeds, however, and we go on to make the assignment, we must consider the possibility that this branch of the computation might later fail, which will require us to backtrack out of the assignment. Thus, we must arrange to undo the assignment as part of the backtracking process.[4]

This is accomplished by giving vproc vfun a success continuation (marked with the comment *1* below) that saves the old value of the variable before assigning the new value to the variable and proceeding from the assignment. The failure continuation that is passed along with the value of the assignment (marked with the comment *2* below) restores the old value of the variable before continuing the failure. That is, a successful assignment provides a failure continuation that will intercept a subsequent failure; whatever failure would otherwise have called fail2 calls this procedure function instead, to undo the assignment before actually calling fail2.

Original

JavaScript

(define (analyze-assignment exp) (let ((var (assignment-variable exp)) (vproc (analyze (assignment-value exp)))) (lambda (env succeed fail) (vproc env (lambda (val fail2) ; *1* (let ((old-value (lookup-variable-value var env))) (set-variable-value! var val env) (succeed 'ok (lambda () ; *2* (set-variable-value! var old-value env) (fail2))))) fail))))

function analyze_assignment(component) { const symbol = assignment_symbol(component); const vfun = analyze(assignment_value_expression(component)); return (env, succeed, fail) => vfun(env, (val, fail2) => { // *1* const old_value = lookup_symbol_value(symbol, env); assign_symbol_value(symbol, val, env); return succeed(val, () => { // *2* assign_symbol_value(symbol, old_value, env); return fail2(); }); }, fail); }

Original		JavaScript
		Return statements and blocks Analyzing return statements is straightforward. The return expression is analyzed to produce an execution function. The execution function for the return statement calls that execution function with a success continuation that wraps the return value in a return value object and passes it to the original success continuation. `function analyze_return_statement(component) { const rfun = analyze(return_expression(component)); return (env, succeed, fail) => rfun(env, (val, fail2) => succeed(make_return_value(val), fail2), fail); }` The execution function for blocks calls the body's execution function on an extended environment, without changing success or failure continuations. `function analyze_block(component) { const body = block_body(component); const locals = scan_out_declarations(body); const unassigneds = list_of_unassigned(locals); const bfun = analyze(body); return (env, succeed, fail) => bfun(extend_environment(locals, unassigneds, env), succeed, fail); }`

Procedure Function applications

The execution procedure function for applications contains no new ideas except for the technical complexity of managing the continuations. This complexity arises in analyze-application, analyze_application, due to the need to keep track of the success and failure continuations as we evaluate the operands. argument expressions. We use a procedure get-args function get_args to evaluate the list of operands, argument expressions, rather than a simple map as in the ordinary evaluator.

Original	JavaScript
`(define (analyze-application exp) (let ((fproc (analyze (operator exp))) (aprocs (map analyze (operands exp)))) (lambda (env succeed fail) (fproc env (lambda (proc fail2) (get-args aprocs env (lambda (args fail3) (execute-application proc args succeed fail3)) fail2)) fail))))`	`function analyze_application(component) { const ffun = analyze(function_expression(component)); const afuns = map(analyze, arg_expressions(component)); return (env, succeed, fail) => ffun(env, (fun, fail2) => get_args(afuns, env, (args, fail3) => execute_application(fun, args, succeed, fail3), fail2), fail); }`

In get-args, notice how cdring down the list of aproc execution procedures and consing up the resulting list of args is accomplished by calling each aproc in the list with a success continuation that recursively calls get-args. In get_args, notice how walking down the list of afun execution functions and constructing the resulting list of args is accomplished by calling each afun in the list with a success continuation that recursively calls get_args. Each of these recursive calls to get-args get_args has a success continuation whose value is the cons of the newly obtained argument onto the list of accumulated arguments: new list resulting from using pair to adjoin the newly obtained argument to the list of accumulated arguments:

Original	JavaScript
`(define (get-args aprocs env succeed fail) (if (null? aprocs) (succeed '() fail) ((car aprocs) env ;; success continuation for this aproc (lambda (arg fail2) (get-args (cdr aprocs) env ;; success continuation for recursive ;; call to get-args (lambda (args fail3) (succeed (cons arg args) fail3)) fail2)) fail)))`	function get_args(afuns, env, succeed, fail) { return is_null(afuns) ? succeed(null, fail) : head(afuns)(env, // success continuation for this $\texttt{afun}$ (arg, fail2) => get_args(tail(afuns), env, // success continuation for // recursive call to $\texttt{get\char`_args}$ (args, fail3) => succeed(pair(arg, args), fail3), fail2), fail); }

The actual procedure function application, which is performed by execute-application, execute_application, is accomplished in the same way as for the ordinary evaluator, except for the need to manage the continuations.

Original

JavaScript

(define (execute-application proc args succeed fail) (cond ((primitive-procedure? proc) (succeed (apply-primitive-procedure proc args) fail)) ((compound-procedure? proc) ((procedure-body proc) (extend-environment (procedure-parameters proc) args (procedure-environment proc)) succeed fail)) (else (error "Unknown procedure type - - EXECUTE-APPLICATION" proc))))

function execute_application(fun, args, succeed, fail) { return is_primitive_function(fun) ? succeed(apply_primitive_function(fun, args), fail) : is_compound_function(fun) ? function_body(fun)( extend_environment(function_parameters(fun), args, function_environment(fun)), (body_result, fail2) => succeed(is_return_value(body_result) ? return_value_content(body_result) : undefined, fail2), fail) : error(fun, "unknown function type - execute_application"); }

Evaluating amb expressions

The amb special syntactic form is the key element in the nondeterministic language. Here we see the essence of the interpretation process and the reason for keeping track of the continuations. The execution procedure function for amb defines a loop try-next try_next that cycles through the execution procedures functions for all the possible values of the amb expression. Each execution procedure function is called with a failure continuation that will try the next one. When there are no more alternatives to try, the entire amb expression fails.

Original	JavaScript
`(define (analyze-amb exp) (let ((cprocs (map analyze (amb-choices exp)))) (lambda (env succeed fail) (define (try-next choices) (if (null? choices) (fail) ((car choices) env succeed (lambda () (try-next (cdr choices)))))) (try-next cprocs))))`	`function analyze_amb(component) { const cfuns = map(analyze, amb_choices(component)); return (env, succeed, fail) => { function try_next(choices) { return is_null(choices) ? fail() : head(choices)(env, succeed, () => try_next(tail(choices))); } return try_next(cfuns); }; }`

Driver loop

The driver loop for the amb evaluator is complex, due to the mechanism that permits the user to retry in evaluating an expression. a program. The driver uses a procedure function called internal-loop, internal_loop, which takes as argument a procedure function try-again. retry. The intent is that calling try-again retry should go on to the next untried alternative in the nondeterministic evaluation. Internal-loop The function internal_loop either calls try-again retry in response to the user typing try-again retry at the driver loop, or else starts a new evaluation by calling ambeval.

The failure continuation for this call to ambeval informs the user that there are no more values and reinvokes the driver loop.

The success continuation for the call to ambeval is more subtle. We print the obtained value and then invoke the internal loop again reinvoke the internal loop with a try-again retry procedure function that will be able to try the next alternative. This next-alternative next_alternative procedure function is the second argument that was passed to the success continuation. Ordinarily, we think of this second argument as a failure continuation to be used if the current evaluation branch later fails. In this case, however, we have completed a successful evaluation, so we can invoke the failure alternative branch in order to search for additional successful evaluations.

Original

JavaScript

(define input-prompt ";;; Amb-Eval input:") (define output-prompt ";;; Amb-Eval value:") (define (driver-loop) (define (internal-loop try-again) (prompt-for-input input-prompt) (let ((input (read))) (if (eq? input 'try-again) (try-again) (begin (newline) (display ";;; Starting a new problem ") (ambeval input the-global-environment ;; ambeval success (lambda (val next-alternative) (announce-output output-prompt) (user-print val) (internal-loop next-alternative)) ;; ambeval failure (lambda () (announce-output ";;; There are no more values of") (user-print input) (driver-loop))))))) (internal-loop (lambda () (newline) (display ";;; There is no current problem") (driver-loop))))

The initial call to internal-loop internal_loop uses a try-again retry procedure function that complains that there is no current problem and restarts the driver loop. This is the behavior that will happen if the user types try-again retry when there is no evaluation in progress.

Original		JavaScript
		We start the driver loop as usual, by setting up the global environment and passing it as the enclosing environment for the first iteration of `driver_loop`. `const the_global_environment = setup_environment(); driver_loop(the_global_environment);`

Exercise 4.59 Implement a new special syntactic form ramb that is like amb except that it searches alternatives in a random order, rather than from left to right. Show how this can help with Alyssa's problem in exercise 4.58.

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.60 Implement a new kind of assignment called permanent-set! that Change the implementation of assignment so that it is not undone upon failure. For example, we can choose two distinct elements from a list and count the number of trials required to make a successful choice as follows:

Original	JavaScript
`(define count 0) (let ((x (an-element-of '(a b c))) (y (an-element-of '(a b c)))) (permanent-set! count (+ count 1)) (require (not (eq? x y))) (list x y count));;; Starting a new problem ;;; Amb-Eval value: (a b 2) ;;; Amb-Eval input:`	`let count = 0; let x = an_element_of("a", "b", "c"); let y = an_element_of("a", "b", "c"); count = count + 1; require(x !== y); list(x, y, count);Starting a new problem amb-evaluate value: ["a", ["b", [2, null]]]`

Original	JavaScript
`try-again;;; Amb-Eval value: (a c 3)`	`amb-evaluate input:retryamb-evaluate value: ["a", ["c", [3, null]]]`

Original		JavaScript
What values would have been displayed if we had used `set!` here rather than `permanent-set!`?		What values would have been displayed if we had used the original meaning of assignment rather than permanent assignment?

Original		JavaScript
Exercise 4.61 Implement a new construct called `if-fail` that permits the user to catch the failure of an expression. `If-fail` takes two expressions. It evaluates the first expression as usual and returns as usual if the evaluation succeeds. If the evaluation fails, however, the value of the second expression is returned, as in the following example: `;;; Amb-Eval input:` `(if-fail (let ((x (an-element-of '(1 3 5)))) (require (even? x)) x) 'all-odd);;; Starting a new problem ;;; Amb-Eval value: all-odd ;;; Amb-Eval input:` `(if-fail (let ((x (an-element-of '(1 3 5 8)))) (require (even? x)) x) 'all-odd);;; Starting a new problem ;;; Amb-Eval value: 8` There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.		Exercise 4.62 We shall horribly abuse the syntax for conditional statements, by implementing a construct of the following form: `if (evaluation_succeeds_take) { $statement$ } else { $alternative$ }` The construct permits the user to catch the failure of a statement. It evaluates the statement as usual and returns as usual if the evaluation succeeds. If the evaluation fails, however, the given alternative statement is evaluated, as in the following example: `amb-evaluate input:if (evaluation_succeeds_take) { const x = an_element_of(list(1, 3, 5)); require(is_even(x)); x; } else { "all odd"; }Starting a new problem amb-evaluate value: "all odd"` `amb-evaluate input:if (evaluation_succeeds_take) { const x = an_element_of(list(1, 3, 5, 8)); require(is_even(x)); x; } else { "all odd"; }Starting a new problem amb-evaluate value: 8` Implement this construct by extending the `amb` evaluator. Hint: The function `is_amb` shows how to abuse the existing JavaScript syntax in order to implement a new syntactic form. There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.63 With permanent-set! the new kind of assignment as described in exercise 4.60 and if-fail the construct if (evaluation_succeeds_take) { $\ldots$ } else { $\ldots$ } as in exercise 4.62, what will be the result of evaluating

Original	JavaScript
`(let ((pairs '())) (if-fail (let ((p (prime-sum-pair '(1 3 5 8) '(20 35 110)))) (permanent-set! pairs (cons p pairs)) (amb)) pairs))`	`let pairs = null; if (evaluation_succeeds_take) { const p = prime_sum_pair(list(1, 3, 5, 8), list(20, 35, 110)); pairs = pair(p, pairs); // using permanent assignment amb(); } else { pairs; }`

Exercise 4.64 If we had not realized that require could be implemented as an ordinary procedure function that uses amb, to be defined by the user as part of a nondeterministic program, we would have had to implement it as a special syntactic form. This would require syntax procedures functions

Original	JavaScript
`(define (require? exp) (tagged-list? exp 'require)) (define (require-predicate exp) (cadr exp))`	`function is_require(component) { return is_tagged_list(component, "require"); } function require_predicate(component) { return head(tail(component)); }`

and a new clause in the dispatch in analyze

Original	JavaScript
`((require? exp) (analyze-require exp))`	`: is_require(component) ? analyze_require(component)`

as well the procedure function analyze-require analyze_require that handles require expressions. Complete the following definition of analyze-require. analyze_require.

Original	JavaScript
`(define (analyze-require exp) (let ((pproc (analyze (require-predicate exp)))) (lambda (env succeed fail) (pproc env (lambda (pred-value fail2) (if ?? ?? (succeed 'ok fail2))) fail))))`	`function analyze_require(component) { const pfun = analyze(require_predicate(component)); return (env, succeed, fail) => pfun(env, (pred_value, fail2) => $\langle{}$??$\rangle$ ? $\langle{}$??$\rangle$ : succeed("ok", fail2), fail); }`

[1] We chose to implement the lazy evaluator in section 4.2 as a modification of the ordinary metacircular evaluator of section 4.1.1. In contrast, we will base the amb evaluator on the analyzing evaluator of section 4.1.7, because the execution procedures functions in that evaluator provide a convenient framework for implementing backtracking.

[2] We assume that the evaluator supports let (see exercise 4.31), which we have used in our nondeterministic programs.

[3] With this treatment, amb is no longer a name with proper scoping. To avoid confusion, we must refrain from declaring amb as a name in our nondeterministic programs.

[4] We didn't worry about undoing definitions, since we can assume that internal definitions are scanned out (section 4.1.6). didn't worry about undoing declarations, since we assume that a name can't be used prior to the evaluation of its declaration, so its previous value doesn't matter.

< Previous

Next >

4.3.3 Implementing the Amb amb Evaluator

Execution procedures functions and continuations

Structure of the evaluator

Simple expressions

Conditionals and sequences

Definitions Declarations and assignments

Return statements and blocks

Procedure Function applications

Evaluating amb expressions

Driver loop