4.3.3 Implementing the amb Evaluator - SICP Comparison Edition

The evaluation of an ordinary JavaScript program may return a value, may never terminate, or may signal an error. In nondeterministic JavaScript the evaluation of 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 JavaScript is complicated by this extra case.

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

Execution functions and continuations

Recall that the execution functions for the ordinary evaluator take one argument: the environment of execution. In contrast, the execution functions in the amb evaluator take three arguments: the environment, and two functions called continuation functions. The evaluation of 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 components may represent choices among alternatives. The evaluation of such 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(), 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 retry request, to find another value of the 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();
if the user types 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 functions for the amb evaluator, and also the basic analyze function, are identical to those in the evaluator of section 4.1.7, except for the fact that we need additional syntax functions to recognize the amb syntactic form:

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);
}

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.[2]

We must also add to the dispatch in analyze a clause that will recognize such expressions and generate an appropriate execution function: $\ldots$ : is_amb(component) ? analyze_amb(component) : is_application(component) $\ldots$

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

function ambeval(component, env, succeed, fail) {      
    return analyze(component)(env, succeed, fail);
}

A success continuation is a 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 function of no arguments. So the general form of an execution function is (env, succeed, fail) => { // $\texttt{succeed}\,$ is $\texttt{(value, fail) =>}~\ldots$ // $\texttt{fail}\,$ is $\texttt{() =>}~\ldots$ $\ldots$ }

For example, executing ambeval($component$, the_global_environment, (value, fail) => value, () => "failed"); will attempt to evaluate the given component and will return either the component's value (if the evaluation succeeds) or the string "failed" (if the evaluation fails). The call to ambeval in the driver loop shown below uses much more complicated continuation functions, which continue the loop and support the retry request.

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

Simple expressions

The execution 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 functions simply succeed with the value of the expression, passing along the failure continuation that was passed to them.

function analyze_literal(component) {
    return (env, succeed, fail) =>
             succeed(literal_value(component), fail);
}

function analyze_name(component) {
    return (env, succeed, fail) =>
             succeed(lookup_symbol_value(symbol_of_name(component),
                                         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 name always succeeds. If lookup_symbol_value fails to find the name, it signals an error, as usual. Such a failure indicates a program bug—a reference to an unbound 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 function generated by analyze_conditional invokes the predicate execution 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 pfun fails, the original failure continuation for the conditional expression is called. 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); }

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)); }

Declarations and assignments

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

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 function for assignments starts out like the one for declarations. It first attempts to obtain the new value to be assigned to the name. If this evaluation of vfun fails, the assignment fails.

If 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.[3]

This is accomplished by giving 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 function instead, to undo the assignment before actually calling fail2.

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);
}

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);
}

Function applications

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

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 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 has a success continuation whose value is the new list resulting from using pair to adjoin the newly obtained argument to the list of accumulated arguments: 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 function application, which is performed by execute_application, is accomplished in the same way as for the ordinary evaluator, except for the need to manage the continuations.

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 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 function for amb defines a loop try_next that cycles through the execution functions for all the possible values of the amb expression. Each execution 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.

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 a program. The driver uses a function called internal_loop, which takes as argument a function retry. The intent is that calling retry should go on to the next untried alternative in the nondeterministic evaluation. The function internal_loop either calls retry in response to the user typing 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 reinvoke the internal loop with a retry function that will be able to try the next alternative. This next_alternative 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.

const input_prompt = "amb-evaluate input:";
const output_prompt =  "amb-evaluate value:";

function driver_loop(env) {
    function internal_loop(retry) {
        const input = user_read(input_prompt);
        if (is_null(input)) {
            display("evaluator terminated");
        } else if (input === "retry") {
            return retry();
        } else {
            display("Starting a new problem");
            const program = parse(input);
            const locals = scan_out_declarations(program);
            const unassigneds = list_of_unassigned(locals);
            const program_env = extend_environment(
                                    locals, unassigneds, env);
            return ambeval(
                       program,  
                       program_env,
                       // ambeval success
                       (val, next_alternative) => {
                           user_print(output_prompt, val);
                           return internal_loop(next_alternative);
                       },
                       // ambeval failure
                       () => {
                           display("There are no more values of");
                           display(input);
                           return driver_loop(program_env);
                       });
        }
    }
    return internal_loop(() => {
                             display("There is no current problem");
                             return driver_loop(env);
                         });
}

The initial call to internal_loop uses a retry 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 retry when there is no evaluation in progress.

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.48 Implement a new 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.47.

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.49 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:

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]]]

amb-evaluate input:

retry

amb-evaluate value:
["a", ["c", [3, null]]]

What values would have been displayed if we had used the original meaning of assignment rather than permanent assignment?

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.50 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.51 With the new kind of assignment as described in exercise 4.49 and the construct if (evaluation_succeeds_take) { $\ldots$ } else { $\ldots$ } as in exercise 4.50, what will be the result of evaluating

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;
}

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.52 If we had not realized that require could be implemented as an ordinary 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 syntactic form. This would require syntax functions

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

: is_require(component)
? analyze_require(component)

as well the function analyze_require that handles require expressions. Complete the following definition of analyze_require. 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); }

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.