Section 4.4.2 described how the query system works. Now we fill in the details by presenting a complete implementation of the system.

4.4.4.1 The Driver Loop

The driver loop for the query system repeatedly reads input expressions. If the expression is a rule or assertion to be added to the data base, then the information is added. Otherwise the expression is assumed to be a query. The driver passes this query to evaluate_query together with an initial frame stream consisting of a single empty frame. The result of the evaluation is a stream of frames generated by satisfying the query with variable values found in the data base. These frames are used to form a new stream consisting of copies of the original query in which the variables are instantiated with values supplied by the stream of frames, and this final stream is displayed:

const input_prompt = "Query input:";
const output_prompt = "Query results:";

function query_driver_loop() {
    const input = user_read(input_prompt) + ";";
    if (is_null(input)) {
        display("evaluator terminated");
    } else {
	const expression = parse(input);
        const query = convert_to_query_syntax(expression);
        if (is_assertion(query)) {
            add_rule_or_assertion(assertion_body(query));
            display("Assertion added to data base.");
        } else {
            display(output_prompt);
            display_stream(
              stream_map(
                 frame =>
                   unparse(instantiate_expression(expression, frame)),
                 evaluate_query(query, singleton_stream(null))));
        }
        return query_driver_loop();
    }
}

Here, as in the other evaluators in this chapter, we use parse to transform a component of the query language given as a string into a JavaScript syntax representation. (We append a semicolon to the input expression string because parse expects a statement.) Then we further transform the syntax representation to a conceptual level appropriate for the query system using convert_to_query_syntax, which is declared in section 4.4.4.7 along with the predicate is_assertion and the selector assertion_body. The function add_rule_or_assertion is declared in section 4.4.4.5. The frames resulting from query evaluation are used to instantiate the syntax representation, and the result is unparsed into a string for display. The functions instantiate_expression and unparse are declared in section 4.4.4.7.

4.4.4.2 The Evaluator

The evaluate_query function, called by the query_driver_loop, is the basic evaluator of the query system. It takes as inputs a query and a stream of frames, and it returns a stream of extended frames. It identifies syntactic forms by a data-directed dispatch using get and put, just as we did in implementing generic operations in chapter 2. Any query that is not identified as a syntactic form is assumed to be a simple query, to be processed by simple_query.

function evaluate_query(query, frame_stream) {
   const qfun = get(type(query), "evaluate_query");
   return is_undefined(qfun)
          ? simple_query(query, frame_stream)
          : qfun(contents(query), frame_stream);
}

The functions type and contents, defined in section 4.4.4.7, implement the abstract syntax of the syntactic forms.

Simple queries

The simple_query function handles simple queries. It takes as arguments a simple query (a pattern) together with a stream of frames, and it returns the stream formed by extending each frame by all data-base matches of the query.

function simple_query(query_pattern, frame_stream) {
   return stream_flatmap(
              frame =>
                stream_append_delayed(
                    find_assertions(query_pattern, frame),
                    () => apply_rules(query_pattern, frame)),
              frame_stream);
}

For each frame in the input stream, we use find_assertions (section 4.4.4.3) to match the pattern against all assertions in the data base, producing a stream of extended frames, and we use apply_rules (section 4.4.4.4) to apply all possible rules, producing another stream of extended frames. These two streams are combined (using stream_append_delayed, section 4.4.4.6) to make a stream of all the ways that the given pattern can be satisfied consistent with the original frame (see exercise 4.68). The streams for the individual input frames are combined using stream_flatmap (section 4.4.4.6) to form one large stream of all the ways that any of the frames in the original input stream can be extended to produce a match with the given pattern.

Compound queries

We handle and queries as illustrated in figure 4.10 with the conjoin function, which takes as inputs the conjuncts and the frame stream and returns the stream of extended frames. First, conjoin processes the stream of frames to find the stream of all possible frame extensions that satisfy the first query in the conjunction. Then, using this as the new frame stream, it recursively applies conjoin to the rest of the queries.

function conjoin(conjuncts, frame_stream) {
   return is_empty_conjunction(conjuncts)
          ? frame_stream
          : conjoin(rest_conjuncts(conjuncts),
                    evaluate_query(first_conjunct(conjuncts),
                                   frame_stream));
}

The statement

put("and", "evaluate_query", conjoin);

sets up evaluate_query to dispatch to conjoin when an and is encountered.

We handle or queries similarly, as shown in figure 4.12. The output streams for the various disjuncts of the or are computed separately and merged using the interleave_delayed function from section 4.4.4.6. (See exercises 4.68 and 4.69.)

function disjoin(disjuncts, frame_stream) {
   return is_empty_disjunction(disjuncts)
          ? null
          : interleave_delayed(
               evaluate_query(first_disjunct(disjuncts), frame_stream),
               () => disjoin(rest_disjuncts(disjuncts), frame_stream));
}
put("or", "evaluate_query", disjoin);

The predicates and selectors for the representation of conjuncts and disjuncts are given in section 4.4.4.7.

Filters

The not syntactic form is handled by the method outlined in section 4.4.2. We attempt to extend each frame in the input stream to satisfy the query being negated, and we include a given frame in the output stream only if it cannot be extended.

function negate(exps, frame_stream) {
   return stream_flatmap(
              frame =>
                is_null(evaluate_query(negated_query(exps),
                                       singleton_stream(frame)))
                ? singleton_stream(frame)
                : null,
              frame_stream);
}
put("not", "evaluate_query", negate);

The javascript_predicate syntactic form is a filter similar to not. Each frame in the stream is used to instantiate the variables in the predicate, the instantiated predicate is evaluated, and the frames for which the predicate evaluates to false are filtered out of the input stream. The instantiated predicate is evaluated using evaluate from section 4.1 with the_global_environment and thus can handle any JavaScript expression, as long as all pattern variables are instantiated prior to evaluation.

function javascript_predicate(exps, frame_stream) {
   return stream_flatmap(
              frame =>
                evaluate(instantiate_expression(
                             javascript_predicate_expression(exps),
                             frame),
                         the_global_environment)
                ? singleton_stream(frame)
                : null,
              frame_stream);
}
put("javascript_predicate", "evaluate_query", javascript_predicate);

The always_true syntactic form provides for a query that is always satisfied. It ignores its contents (normally empty) and simply passes through all the frames in the input stream. The rule_body selector (section 4.4.4.7) uses always_true to provide bodies for rules that were defined without bodies (that is, rules whose bodies are always satisfied).

function always_true(ignore, frame_stream) {
    return frame_stream;
}
put("always_true", "evaluate_query", always_true);

The selectors that define the syntax of not and javascript_predicate are given in section 4.4.4.7.

4.4.4.3 Finding Assertions by Pattern Matching

The function find_assertions, called by simple_query (section 4.4.4.2), takes as input a pattern and a frame. It returns a stream of frames, each extending the given one by a data-base match of the given pattern. It uses fetch_assertions (section 4.4.4.5) to get a stream of all the assertions in the data base that should be checked for a match against the pattern and the frame. The reason for fetch_assertions here is that we can often apply simple tests that will eliminate many of the entries in the data base from the pool of candidates for a successful match. The system would still work if we eliminated fetch_assertions and simply checked a stream of all assertions in the data base, but the computation would be less efficient because we would need to make many more calls to the matcher.

function find_assertions(pattern, frame) {
    return stream_flatmap(
               datum => check_an_assertion(datum, pattern, frame),
               fetch_assertions(pattern, frame));
}

The function check_an_assertion takes as arguments a data object (an assertion), a pattern, and a frame and returns either a one-element stream containing the extended frame or null if the match fails.

function check_an_assertion(assertion, query_pat, query_frame) {
    const match_result = pattern_match(query_pat, assertion, 
                                       query_frame);
    return match_result === "failed"
           ? null
           : singleton_stream(match_result);
}

The basic pattern matcher returns either the string "failed" or an extension of the given frame. The basic idea of the matcher is to check the pattern against the data, element by element, accumulating bindings for the pattern variables. If the pattern and the data object are the same, the match succeeds and we return the frame of bindings accumulated so far. Otherwise, if the pattern is a variable (checked by the function is_variable declared in section 4.4.4.7) we extend the current frame by binding the variable to the data, so long as this is consistent with the bindings already in the frame. If the pattern and the data are both pairs, we (recursively) match the head of the pattern against the head of the data to produce a frame; in this frame we then match the tail of the pattern against the tail of the data. If none of these cases are applicable, the match fails and we return the string "failed".

function pattern_match(pattern, data, frame) {
    return frame === "failed"
           ? "failed"
           : equal(pattern, data)
           ? frame   
           : is_variable(pattern)
           ? extend_if_consistent(pattern, data, frame)
           : is_pair(pattern) && is_pair(data)
           ? pattern_match(tail(pattern),
                           tail(data),
                           pattern_match(head(pattern),
                                         head(data),
                                         frame))
           : "failed";
}

Here is the function that extends a frame by adding a new binding, if this is consistent with the bindings already in the frame:

function extend_if_consistent(variable, data, frame) {
    const binding = binding_in_frame(variable, frame);
    return is_undefined(binding)
           ? extend(variable, data, frame)
           : pattern_match(binding_value(binding), data, frame);
}

If there is no binding for the variable in the frame, we simply add the binding of the variable to the data. Otherwise we match, in the frame, the data against the value of the variable in the frame. If the stored value contains only constants, as it must if it was stored during pattern matching by extend_if_consistent, then the match simply tests whether the stored and new values are the same. If so, it returns the unmodified frame; if not, it returns a failure indication. The stored value may, however, contain pattern variables if it was stored during unification (see section 4.4.4.4). The recursive match of the stored pattern against the new data will add or check bindings for the variables in this pattern. For example, suppose we have a frame in which $x is bound to list("f", $y) and $y is unbound, and we wish to augment this frame by a binding of $x to list("f", "b"). We look up $x and find that it is bound to list("f", $y). This leads us to match list("f", $y) against the proposed new value list("f", "b") in the same frame. Eventually this match extends the frame by adding a binding of $y to "b". The variable $x remains bound to list("f", $y). We never modify a stored binding and we never store more than one binding for a given variable.

The functions used by extend_if_consistent to manipulate bindings are defined in section 4.4.4.8.

4.4.4.4 Rules and Unification

The function apply_rules is the rule analog of find_assertions (section 4.4.4.3). It takes as input a pattern and a frame, and it forms a stream of extension frames by applying rules from the data base. The function stream_flatmap maps apply_a_rule down the stream of possibly applicable rules (selected by fetch_rules, section 4.4.4.5) and combines the resulting streams of frames.

function apply_rules(pattern, frame) {
    return stream_flatmap(rule => apply_a_rule(rule, pattern, frame),
                          fetch_rules(pattern, frame));
}

The function apply_a_rule applies a rule using the method outlined in section 4.4.2. It first augments its argument frame by unifying the rule conclusion with the pattern in the given frame. If this succeeds, it evaluates the rule body in this new frame.

Before any of this happens, however, the program renames all the variables in the rule with unique new names. The reason for this is to prevent the variables for different rule applications from becoming confused with each other. For instance, if two rules both use a variable named $x, then each one may add a binding for $x to the frame when it is applied. These two $x's have nothing to do with each other, and we should not be fooled into thinking that the two bindings must be consistent. Rather than rename variables, we could devise a more clever environment structure; however, the renaming approach we have chosen here is the most straightforward, even if not the most efficient. (See exercise 4.76.) Here is the apply_a_rule function:

function apply_a_rule(rule, query_pattern, query_frame) {
    const clean_rule = rename_variables_in(rule);
    const unify_result = unify_match(query_pattern,
                                     conclusion(clean_rule),
                                     query_frame);
    return unify_result === "failed"
           ? null
           : evaluate_query(rule_body(clean_rule),
                            singleton_stream(unify_result));
}

The selectors rule_body and conclusion that extract parts of a rule are defined in section 4.4.4.7.

We generate unique variable names by associating a unique identifier (such as a number) with each rule application and combining this identifier with the original variable names. For example, if the rule-application identifier is 7, we might change each $x in the rule to $x_7 and each $y in the rule to $y_7. (The functions make_new_variable and new_rule_application_id are included with the syntax functions in section 4.4.4.7.)

function rename_variables_in(rule) {
    const rule_application_id = new_rule_application_id();
    function tree_walk(exp) {
        return is_variable(exp) 
               ? make_new_variable(exp, rule_application_id)
               : is_pair(exp)
               ? pair(tree_walk(head(exp)),
                      tree_walk(tail(exp)))
               : exp;
    }
    return tree_walk(rule);
}

The unification algorithm is implemented as a function that takes as inputs two patterns and a frame and returns either the extended frame or the string "failed". The unifier is like the pattern matcher except that it is symmetrical—variables are allowed on both sides of the match. The function unify_match is basically the same as pattern_match, except that there is an extra clause (marked *** below) to handle the case where the object on the right side of the match is a variable.

function unify_match(p1, p2, frame) {
    return frame === "failed"
           ? "failed"
           : equal(p1, p2)
           ? frame
           : is_variable(p1) 
           ? extend_if_possible(p1, p2, frame)
           : is_variable(p2)                    // ***
           ? extend_if_possible(p2, p1, frame)  // ***
           : is_pair(p1) && is_pair(p2)
           ? unify_match(tail(p1),
                         tail(p2),
                         unify_match(head(p1),
                                     head(p2),
                                     frame))
           : "failed";
}

In unification, as in one-sided pattern matching, we want to accept a proposed extension of the frame only if it is consistent with existing bindings. The function extend_if_possible used in unification is the same as the function extend_if_consistent used in pattern matching except for two special checks, marked *** in the program below. In the first case, if the variable we are trying to match is not bound, but the value we are trying to match it with is itself a (different) variable, it is necessary to check to see if the value is bound, and if so, to match its value. If both parties to the match are unbound, we may bind either to the other.

The second check deals with attempts to bind a variable to a pattern that includes that variable. Such a situation can occur whenever a variable is repeated in both patterns. Consider, for example, unifying the two patterns list($x, $x) and list($y, $\langle$$expression$ $involving$ $y$\rangle$) in a frame where both $x and $y are unbound. First $x is matched against $y, making a binding of $x to $y. Next, the same $x is matched against the given expression involving $y. Since $x is already bound to $y, this results in matching $y against the expression. If we think of the unifier as finding a set of values for the pattern variables that make the patterns the same, then these patterns imply instructions to find a $y such that $y is equal to the expression involving $y. We reject such bindings; these cases are recognized by the predicate depends_on.[1] On the other hand, we do not want to reject attempts to bind a variable to itself. For example, consider unifying list($x, $x) and list($y, $y). The second attempt to bind $x to $y matches $y (the stored value of $x ) against $y (the new value of $x). This is taken care of by the equal clause of unify_match.

function extend_if_possible(variable, value, frame) {
    const binding = binding_in_frame(variable, frame);
    if (! is_undefined(binding)) {
        return unify_match(binding_value(binding), 
                            value, frame); 
    } else if (is_variable(value)) {                 // ***
        const binding = binding_in_frame(value, frame);
        return ! is_undefined(binding)
               ? unify_match(variable,
                             binding_value(binding),
                             frame)
               : extend(variable, value, frame);
    } else if (depends_on(value, variable, frame)) { // ***
        return "failed";
    } else {
        return extend(variable, value, frame);
    }
}

The function depends_on is a predicate that tests whether an expression proposed to be the value of a pattern variable depends on the variable. This must be done relative to the current frame because the expression may contain occurrences of a variable that already has a value that depends on our test variable. The structure of depends_on is a simple recursive tree walk in which we substitute for the values of variables whenever necessary.

function depends_on(expression, variable, frame) {
    function tree_walk(e) {
        if (is_variable(e)) {
            if (equal(variable, e)) {
                return true;
            } else {
                const b = binding_in_frame(e, frame);
                return is_undefined(b)
                       ? false
                       : tree_walk(binding_value(b));
            }
        } else {
            return is_pair(e) 
                   ? tree_walk(head(e)) || tree_walk(tail(e))
                   : false;
        }
    }
    return tree_walk(expression);
}

4.4.4.5 Maintaining the Data Base

One important problem in designing logic programming languages is that of arranging things so that as few irrelevant data-base entries as possible will be examined in checking a given pattern. For this purpose, we will represent an assertion as a list whose head is a string that represents the kind of information of the assertion. We store the assertions in separate streams, one for each kind of information, in a table indexed by the kind. To fetch an assertion that may match a pattern, we return (to be tested using the matcher) all the stored assertions that have the same head (the same kind of information). Cleverer methods could also take advantage of information in the frame. We avoid building our criteria for indexing into the program; instead we call on predicates and selectors that embody our criteria.

function fetch_assertions(pattern, frame) {
    return get_indexed_assertions(pattern);
}
function get_indexed_assertions(pattern) {
    return get_stream(index_key_of(pattern), "assertion-stream");
}

The function get_stream looks up a stream in the table and returns an empty stream if nothing is stored there.

function get_stream(key1, key2) {
    const s = get(key1, key2);
    return is_undefined(s) ? null : s;
}

Rules are stored similarly, using the head of the rule conclusion. A pattern can match rules whose conclusions have the same head. Thus, when fetching rules that might match a pattern we fetch all rules whose conclusions have the same head as the pattern.

function fetch_rules(pattern, frame) {
    return get_indexed_rules(pattern);
}
function get_indexed_rules(pattern) {
    return get_stream(index_key_of(pattern), "rule-stream");
}

The function add_rule_or_assertion is used by query_driver_loop to add assertions and rules to the data base. Each item is stored in the index.

function add_rule_or_assertion(assertion) {
    return is_rule(assertion) 
           ? add_rule(assertion)
           : add_assertion(assertion);
}
function add_assertion(assertion) {
    store_assertion_in_index(assertion);
    return "ok";
}
function add_rule(rule) {
    store_rule_in_index(rule);
    return "ok";
}

To actually store an assertion or a rule, we store it in the appropriate stream.

function store_assertion_in_index(assertion) {
    const key = index_key_of(assertion);
    const current_assertion_stream =
                get_stream(key, "assertion-stream");
    put(key, "assertion-stream",
        pair(assertion, () => current_assertion_stream));
}
function store_rule_in_index(rule) {
    const pattern = conclusion(rule);
    const key = index_key_of(pattern);
    const current_rule_stream = 
                get_stream(key, "rule-stream");
    put(key, "rule-stream",
        pair(rule, () => current_rule_stream));
}

The key under which a pattern (an assertion or rule conclusion) is stored in the table is the string it starts with.

function index_key_of(pattern) { return head(pattern); }

4.4.4.6 Stream Operations

The query system uses a few stream operations that were not presented in chapter 3.

The functions stream_append_delayed and interleave_delayed are just like stream_append and interleave (section 3.5.3), except that they take a delayed argument (like the integral function in section 3.5.4). This postpones looping in some cases (see exercise 4.68).

function stream_append_delayed(s1, delayed_s2) {
    return is_null(s1)
           ? delayed_s2()
           : pair(head(s1),
                  () => stream_append_delayed(stream_tail(s1),
                                              delayed_s2));
}
function interleave_delayed(s1, delayed_s2) {
    return is_null(s1)
           ? delayed_s2()
           : pair(head(s1),
                  () => interleave_delayed(delayed_s2(),
                                           () => stream_tail(s1)));
}

The function stream_flatmap, which is used throughout the query evaluator to map a function over a stream of frames and combine the resulting streams of frames, is the stream analog of the flatmap function introduced for ordinary lists in section 2.2.3. Unlike ordinary flatmap, however, we accumulate the streams with an interleaving process, rather than simply appending them (see exercises 4.69 and 4.70).

function stream_flatmap(fun, s) {
    return flatten_stream(stream_map(fun, s));
}
function flatten_stream(stream) {
    return is_null(stream)
           ? null
           : interleave_delayed(
                 head(stream),
                 () => flatten_stream(stream_tail(stream)));
}

The evaluator also uses the following simple function to generate a stream consisting of a single element:

function singleton_stream(x) {
    return pair(x, () => null);
}

4.4.4.7 Query Syntax Functions and Instantiation

We saw in section 4.4.4.1 that the driver loop first transforms an input string into the JavaScript syntax representation. The input is designed to look like a JavaScript expression so that we can use the parse function from section 4.1.2 and also to support JavaScript notation in javascript_predicate. For example,

parse('job($x, list("computer", "wizard"));');

yields

list("application",
     list("name", "job"),
     list(list("name", "$x"),
          list("application",
               list("name", "list"),
               list(list("literal", "computer"),
                    list("literal", "wizard")))))

The tag "application" indicates that syntactically, the query would be treated as a function application in JavaScipt. The function unparse transforms the syntax back into a string:

unparse(parse('job($x, list("computer", "wizard"));'));

'job($x, list("computer", "wizard"))'

In the query processor, we assumed a query-language-specific representation of assertions, rules, and queries. The function convert_to_query_syntax transforms the syntax representation into that representation. Using the same example,

convert_to_query_syntax(parse('job($x, list("computer", "wizard"));'));

yields

list("job", list("name", "$x"), list("computer", "wizard"))

Query-system functions such as add_rule_or_assertion in section 4.4.4.5 and evaluate_query in section 4.4.4.2 operate on the query-language-specific representation using selectors and predicates such as type, contents, is_rule, and first_conjunct declared below. Figure 4.13 depicts the three abstraction barriers used by the query system and how the transformation functions parse, unparse, and convert_to_query_syntax bridge them.

Figure 4.13 Syntax abstraction in the query system.

Handling pattern variables

The predicate is_variable is used on the query-language-specific representation during query processing and on the JavaScript syntax representation during instantiation to identify names that start with a dollar sign. We assume there is a function char_at that returns a string containing only the character of the given string at the given position.[2]

function is_variable(exp) {
    return is_name(exp) && char_at(symbol_of_name(exp), 0) === "$";
}

Unique variables are constructed during rule application (in section 4.4.4.4) by means of the following functions. The unique identifier for a rule application is a number, which is incremented each time a rule is applied.[3]

let rule_counter = 0;

function new_rule_application_id() {
   rule_counter = rule_counter + 1;
   return rule_counter;
}
function make_new_variable(variable, rule_application_id) {
   return make_name(symbol_of_name(variable) + "_" +
                    stringify(rule_application_id));
}

The function convert_to_query_syntax

The function convert_to_query_syntax recursively transforms the JavaScript syntax representation into the query-language-specific representation by simplifying assertions, rules, and queries such that the symbol of a name in a function expression of an application becomes a tag, except that if the symbol is "pair" or "list", an (untagged) JavaScript pair or list is built. This means that convert_to_query_syntax interprets applications of the constructors pair and list during the transformation, and processing functions such as pattern_match of section 4.4.4.3 and unify_match of section 4.4.4.4 can operate directly on the intended pairs and lists rather than on the syntax representation generated by the parser. The (one-element) argument list of javascript_predicate remains unprocessed, as explained below. A variable remains unchanged, and a literal is simplified to the primitive value it contains.

function convert_to_query_syntax(exp) {
   if (is_application(exp)) {
     const function_symbol = symbol_of_name(function_expression(exp));
     if (function_symbol === "javascript_predicate") {
       return pair(function_symbol, arg_expressions(exp));
     } else {
       const processed_args = map(convert_to_query_syntax,
                                  arg_expressions(exp));
       return function_symbol === "pair"
              ? pair(head(processed_args), head(tail(processed_args)))
              : function_symbol === "list"
              ? processed_args
              : pair(function_symbol, processed_args);
     }
   } else if (is_variable(exp)) {
     return exp;
   } else { // exp is literal
     return literal_value(exp);
   }
}

An exception to this processing is javascript_predicate. Since the instantiated JavaScript syntax representation of its predicate expression is passed to evaluate of section 4.1.1, the original syntax representation coming from parse needs to remain intact in the query-language-specific representation of the expression. In this example of section 4.4.1

and(salary($person, $amount), javascript_predicate($amount > 50000))

convert_to_query_syntax produces a data structure in which a JavaScript syntax representation is embedded in a query-language-specific representation:

list("and",
     list("salary", list("name", "$person"), list("name", "$amount")),
     list("javascript_predicate",
          list("binary_operator_combination",
               ">",
               list("name", "$amount"),
               list("literal", 50000))))

In order to evaluate the javascript_predicate subexpression of that processed query, the function javascript_predicate in section 4.4.4.2 calls the function instantiate_expression (below) on the embedded JavaScript syntax representation of $amount > 50000 to replace the variable list("name", "$amount") by a literal, for example list("literal", 70000), that represents the primitive value to which $amount is bound, here 70000. The JavaScript evaluator can evaluate the instantiated predicate, which now represents 70000 > 50000.

Instantiating an expression

The function javascript_predicate of section 4.4.4.2 and the driver loop of section 4.4.4.1 call instantiate_expression on an expression to obtain a copy in which any variable in the expression is replaced by its value in a given frame. The input and result expressions use the JavaScript syntax representation, so any value that results from instantiating a variable needs to be converted from its form in the binding to the JavaScript syntax representation.

function instantiate_expression(expression, frame) {
   return is_variable(expression)
          ? convert(instantiate_term(expression, frame))
          : is_pair(expression)
          ? pair(instantiate_expression(head(expression), frame),
                 instantiate_expression(tail(expression), frame))
          : expression;
}

The function instantiate_term takes a variable, pair, or primitive value as first argument and a frame as second argument and recursively replaces the variables in the first argument by their values in the frame until a primitive value or an unbound variable is reached. When the process encounters a pair, a new pair is constructed whose parts are the instantiated versions of the original parts. For example, if $x is bound to the pair $[\texttt{\$y}, 5]$ in a frame $f$ as the result of unification, and $y is in turn bound to 3, the result of applying instantiate_term to list("name", "$x") and $f$ is the pair $[3, 5]$. function instantiate_term(term, frame) { if (is_variable(term)) { const binding = binding_in_frame(term, frame); return is_undefined(binding) ? term // leave unbound variable as is : instantiate_term(binding_value(binding), frame); } else if (is_pair(term)) { return pair(instantiate_term(head(term), frame), instantiate_term(tail(term), frame)); } else { // $\texttt{term}$ is a primitive value return term; } } The function convert constructs a JavaScript syntax representation for a variable, pair, or primitive value returned by instantiate_term. A pair in the original becomes an application of JavaScript's pair constructor and a primitive value becomes a literal. function convert(term) { return is_variable(term) ? term : is_pair(term) ? make_application(make_name("pair"), list(convert(head(term)), convert(tail(term)))) : // $\texttt{term}$ is a primitive value make_literal(term); } To illustrate these three functions, consider what happens when the query

job($x, list("computer", "wizard"))

whose JavaScript syntax representation is given at the beginning of section 4.4.4.7, is processed by the driver loop. Let's say a frame $g$ of the result stream binds the variable $x to the pair $[\texttt{"Bitdiddle"}, \texttt{\$y}]$ and the variable $y to the pair $[\texttt{"Ben"}, \texttt{null}]$. Then instantiate_term(list("name", "$\$$x"), $g$) returns the list

list("Bitdiddle", "Ben")

which convert transforms into

list("application",
     list("name", "pair"),
     list(list("literal", "Bitdiddle"),
          list("application",
               list("name", "pair"),
               list(list("literal", "Ben"),
                    list("literal", null)))))

The result of instantiate_expression applied to the JavaScript syntax representation of the query and the frame $g$ is:

list("application",
     list("name", "job"),
     list(list("application",
               list("name", "pair"),
               list(list("literal", "Bitdiddle"),
                    list("application",
                         list("name", "pair"),
                         list(list("literal", "Ben"),
                              list("literal", null))))),
          list("application",
               list("name", "list"),
               list(list("literal", "computer"),
                    list("literal", "wizard")))))

The driver loop unparses this representation and displays it as:

'job(list("Bitdiddle", "Ben"), list("computer", "wizard"))'

The function unparse

The function unparse transforms a component given in the JavaScript syntax representation into a string by applying the syntax rules of section 4.1.2. We describe unparse only for those kinds of expressions that appear in the examples of section 4.4.1, leaving statements and the remaining kinds of expressions as exercise 4.2. A literal is transformed by stringifying its value, and a name is transformed into its symbol. An application is formatted by unparsing the function expression, which we can assume to be a name here, followed by the comma-separated argument expression strings enclosed in parentheses. Binary operator combinations are formatted using infix notation. function unparse(exp) { return is_literal(exp) ? stringify(literal_value(exp)) : is_name(exp) ? symbol_of_name(exp) : is_list_construction(exp) ? unparse(make_application(make_name("list"), element_expressions(exp))) : is_application(exp) && is_name(function_expression(exp)) ? symbol_of_name(function_expression(exp)) + "(" + comma_separated(map(unparse, arg_expressions(exp))) + ")" : is_binary_operator_combination(exp) ? "(" + unparse(first_operand(exp)) + " " + operator_symbol(exp) + " " + unparse(second_operand(exp)) + ")" $\langle{}$unparsing other kinds of JavaScript components$\rangle$ : error(exp, "unknown syntax -- unparse"); }

function comma_separated(strings) {
   return accumulate((s, acc) => s + (acc === "" ? "" : ", " + acc),
                     "",
                     strings);
}

The function unparse would work fine without the clause

: is_list_construction(exp)
? unparse(make_application(make_name("list"), 
                           element_expressions(exp)))

but the output string would be unnecessarily verbose in cases where pattern variables are instantiated by lists. In the example above, where processing the query

job($x, list("computer", "wizard"))

yields a frame that binds $x to $[\texttt{"Bitdiddle"}, [\texttt{"Ben"}, \texttt{null}]]$, unparse produces

'job(list("Bitdiddle", "Ben"), list("computer", "wizard"))'

However, without the clause it would produce

'job(pair("Bitdiddle", pair("Ben", null)), list("computer", "wizard"))'

which explicitly constructs the two pairs that make up the first list. To achieve the more concise formatting used throughout section 4.4.1, we inserted the clause to check if the expression constructs a list, in which case we format it as a single application of list to the list of element expressions that we extract from the expression. A list construction is the literal null or an application of pair whose second argument is itself a list construction.

function is_list_construction(exp) {
   return (is_literal(exp) && is_null(literal_value(exp))) ||
          (is_application(exp) && is_name(function_expression(exp)) &&
           symbol_of_name(function_expression(exp)) === "pair" &&
           is_list_construction(head(tail(arg_expressions(exp)))));
}

Extracting the element expressions from a given list construction amounts to collecting the first arguments of applications of pair until the literal null is reached. function element_expressions(list_constr) { return is_literal(list_constr) ? null // $\texttt{list\char`_constr}$ is literal $\texttt{null}$ : // $\texttt{list\char`_constr}$ is application of $\texttt{pair}$ pair(head(arg_expressions(list_constr)), element_expressions( head(tail(arg_expressions(list_constr))))); }

Predicates and selectors for the query-language-specific representation

The functions type and contents, used by evaluate_query (section 4.4.4.2), specify that a syntactic form of a query-language-specific representation is identified by the string in its head. They are the same as the type_tag and contents functions in section 2.4.2, except for the error message.

function type(exp) {
   return is_pair(exp)
          ? head(exp)
          : error(exp, "unknown expression type");
}
function contents(exp) {
   return is_pair(exp)
          ? tail(exp)
          : error(exp, "unknown expression contents");
}

The following functions, used by query_driver_loop (in section 4.4.4.1), specify that rules and assertions are added to the data base by an assert command, which the function convert_to_query_syntax transforms into a pair of the form ["assert", $rule$-$or$-$assertion$]:

function is_assertion(exp) {
   return type(exp) === "assert";
}
function assertion_body(exp) { return head(contents(exp)); }

Here are the declarations of the predicates and selectors for the and, or, not, and javascript_predicate syntactic forms (section 4.4.4.2):

function is_empty_conjunction(exps) { return is_null(exps); }

function first_conjunct(exps) { return head(exps); }

function rest_conjuncts(exps) { return tail(exps); }

function is_empty_disjunction(exps) { return is_null(exps); }

function first_disjunct(exps) { return head(exps); }

function rest_disjuncts(exps) { return tail(exps); }

function negated_query(exps) { return head(exps); }

function javascript_predicate_expression(exps) { return head(exps); }

The following three functions define the query-language-specific representation of rules:

function is_rule(assertion) {
    return is_tagged_list(assertion, "rule");
}
function conclusion(rule) { return head(tail(rule)); }

function rule_body(rule) {
    return is_null(tail(tail(rule)))
           ? list("always_true")
           : head(tail(tail(rule)));
}

4.4.4.8 Frames and Bindings

Frames are represented as lists of bindings, which are variable-value pairs:

function make_binding(variable, value) {
    return pair(variable, value);
}
function binding_variable(binding) {
    return head(binding);
}
function binding_value(binding) {
    return tail(binding);
}
function binding_in_frame(variable, frame) {
    return assoc(variable, frame);
}
function extend(variable, value, frame) {
    return pair(make_binding(variable, value), frame);
}

Exercise 4.68 Louis Reasoner wonders why the simple_query and disjoin functions (section 4.4.4.2) are implemented using delayed expressions rather than being defined as follows:

function simple_query(query_pattern, frame_stream) {
    return stream_flatmap(
               frame =>
                 stream_append(find_assertions(query_pattern, frame),
                               apply_rules(query_pattern, frame)),
               frame_stream);
}
function disjoin(disjuncts, frame_stream) {
    return is_empty_disjunction(disjuncts)
           ? null
           : interleave(
                 evaluate_query(first_disjunct(disjuncts), frame_stream),
                 disjoin(rest_disjuncts(disjuncts), frame_stream));
}

Can you give examples of queries where these simpler definitions would lead to undesirable behavior?

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.69 Why do disjoin and stream_flatmap interleave the streams rather than simply append them? Give examples that illustrate why interleaving works better. (Hint: Why did we use interleave in section 3.5.3?)

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.70 Why does flatten_stream use a delayed expression in its body? What would be wrong with defining it as follows:

function flatten_stream(stream) {
    return is_null(stream)
           ? null
           : interleave(head(stream),
                        flatten_stream(stream_tail(stream)));
}

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.71 Alyssa P. Hacker proposes to use a simpler version of stream_flatmap in negate, javascript_predicate, and find_assertions. She observes that the function that is mapped over the frame stream in these cases always produces either the empty stream or a singleton stream, so no interleaving is needed when combining these streams.

Fill in the missing expressions in Alyssa's program. function simple_stream_flatmap(fun, s) { return simple_flatten(stream_map(fun, s)); } function simple_flatten(stream) { return stream_map($\langle{}$??$\rangle$, stream_filter($\langle{}$??$\rangle$, stream)); }
Does the query system's behavior change if we change it in this way?

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.72 Implement for the query language a syntactic form called unique. Applictions of unique should succeed if there is precisely one item in the data base satisfying a specified query. For example,

unique(job($x, list("computer", "wizard")))

should print the one-item stream

unique(job(list("Bitdiddle", "Ben"), list("computer", "wizard")))

since Ben is the only computer wizard, and

unique(job($x, list("computer", "programmer")))

should print the empty stream, since there is more than one computer programmer. Moreover,

and(job($x, $j), unique(job($anyone, $j)))

should list all the jobs that are filled by only one person, and the people who fill them.

There are two parts to implementing unique. The first is to write a function that handles this syntactic form, and the second is to make evaluate_query dispatch to that function. The second part is trivial, since evaluate_query does its dispatching in a data-directed way. If your function is called uniquely_asserted, all you need to do is

put("unique", "evaluate_query", uniquely_asserted);

and evaluate_query will dispatch to this function for every query whose type (head) is the string "unique".

The real problem is to write the function uniquely_asserted. This should take as input the contents (tail) of the unique query, together with a stream of frames. For each frame in the stream, it should use evaluate_query to find the stream of all extensions to the frame that satisfy the given query. Any stream that does not have exactly one item in it should be eliminated. The remaining streams should be passed back to be accumulated into one big stream that is the result of the unique query. This is similar to the implementation of the not syntactic form.

Test your implementation by forming a query that lists all people who supervise precisely one person.

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.73 Our implementation of and as a series combination of queries (figure 4.10) is elegant, but it is inefficient because in processing the second query of the and we must scan the data base for each frame produced by the first query. If the data base has $N$ elements, and a typical query produces a number of output frames proportional to $N$ (say $N/k$), then scanning the data base for each frame produced by the first query will require $N^{2}/k$ calls to the pattern matcher. Another approach would be to process the two clauses of the and separately, then look for all pairs of output frames that are compatible. If each query produces $N/k$ output frames, then this means that we must perform $N^{2}/k^{2}$ compatibility checks—a factor of $k$ fewer than the number of matches required in our current method.

Devise an implementation of and that uses this strategy. You must implement a function that takes two frames as inputs, checks whether the bindings in the frames are compatible, and, if so, produces a frame that merges the two sets of bindings. This operation is similar to unification.

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.74 In section 4.4.3 we saw that not and javascript_predicate can cause the query language to give wrong answers if these filtering operations are applied to frames in which variables are unbound. Devise a way to fix this shortcoming. One idea is to perform the filtering in a delayed manner by appending to the frame a promise to filter that is fulfilled only when enough variables have been bound to make the operation possible. We could wait to perform filtering until all other operations have been performed. However, for efficiency's sake, we would like to perform filtering as soon as possible so as to cut down on the number of intermediate frames generated.

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.75 Redesign the query language as a nondeterministic program to be implemented using the evaluator of section 4.3, rather than as a stream process. In this approach, each query will produce a single answer (rather than the stream of all answers) and the user can type retry to see more answers. You should find that much of the mechanism we built in this section is subsumed by nondeterministic search and backtracking. You will probably also find, however, that your new query language has subtle differences in behavior from the one implemented here. Can you find examples that illustrate this difference?

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.76 When we implemented the JavaScript evaluator in section 4.1, we saw how to use local environments to avoid name conflicts between the parameters of functions. For example, in evaluating

function square(x) {
    return x * x;
}
function sum_of_squares(x, y) {
    return square(x) + square(y);
}
sum_of_squares(3, 4);

there is no confusion between the x in square and the x in sum_of_squares, because we evaluate the body of each function in an environment that is specially constructed to contain bindings for the local names. In the query system, we used a different strategy to avoid name conflicts in applying rules. Each time we apply a rule we rename the variables with new names that are guaranteed to be unique. The analogous strategy for the JavaScript evaluator would be to do away with local environments and simply rename the variables in the body of a function each time we apply the function.

Implement for the query language a rule-application method that uses environments rather than renaming. See if you can build on your environment structure to create constructs in the query language for dealing with large systems, such as the rule analog of block-structured functions. Can you relate any of this to the problem of making deductions in a context (e.g., If I supposed that $P$ were true, then I would be able to deduce $A$ and $B$.) as a method of problem solving? (This problem is open-ended.)

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.