Section 4.4.2 described how the query system works. Now we fill in the details by presenting a complete implementation of the system.
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 the evaluator qeval 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 printed at the terminal: displayed:
| Original | JavaScript |
| (define input-prompt ";;; Query input:") (define output-prompt ";;; Query results:") (define (query-driver-loop) (prompt-for-input input-prompt) (let ((q (query-syntax-process (read)))) (cond ((assertion-to-be-added? q) (add-rule-or-assertion! (add-assertion-body q)) (newline) (display "Assertion added to data base.") (query-driver-loop)) (else (newline) (display output-prompt) (display-stream (stream-map (lambda (frame) (instantiate q frame (lambda (v f) (contract-question-mark v)))) (qeval q (singleton-stream '())))) (query-driver-loop))))) | 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(); } } |
| Original | JavaScript | |
| Here, as in the other evaluators in this chapter, we use an abstract syntax for expressions of the query language. The implementation of the expression syntax, including the predicate assertion-to-be-added? and the selector add-assertion-body, is given in section 4.4.4.7. Add-rule-or-assertion! is defined in section 4.4.4.5. | 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. |
| Original | JavaScript | |
|
Before doing any processing on an input expression, the driver loop transforms it syntactically into a form that makes the processing more efficient. This involves changing the representation of pattern variables. When the query is instantiated, any variables that remain unbound are transformed back to the input representation before being printed. These transformations are performed by the two procedures query-syntax-process and contract-question-mark (section 4.4.4.7). To instantiate an expression, we copy it, replacing any variables in the expression by their values in a given frame. The values are themselves instantiated, since they could contain variables (for example, if ?x in exp is bound to ?y as the result of unification and ?y is in turn bound to 5). The action to take if a variable cannot be instantiated is given by a procedural argument to instantiate. (define (instantiate exp frame unbound-var-handler) (define (copy exp) (cond ((var? exp) (let ((binding (binding-in-frame exp frame))) (if binding (copy (binding-value binding)) (unbound-var-handler exp frame)))) ((pair? exp) (cons (copy (car exp)) (copy (cdr exp)))) (else exp))) (copy exp)) The procedures that manipulate bindings are defined in section 4.4.4.8. |
The qeval evaluate_query procedure, function, called by the query-driver-loop, 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 special 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 special syntactic form is assumed to be a simple query, to be processed by simple-query. simple_query.
| Original | JavaScript |
| (define (qeval query frame-stream) (let ((qproc (get (type query) 'qeval))) (if qproc (qproc (contents query) frame-stream) (simple-query query frame-stream)))) | 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 simple-query simple_query procedure 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.
| Original | JavaScript |
| (define (simple-query query-pattern frame-stream) (stream-flatmap (lambda (frame) (stream-append-delayed (find-assertions query-pattern frame) (delay (apply-rules query-pattern frame)))) frame-stream)) | 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 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 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, 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.82). The streams for the individual input frames are combined using stream-flatmap 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.
And queries are handled as illustrated in figure 4.9 by the We handle and queries as illustrated in figure 4.10 with the conjoin procedure. 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.
| Original | JavaScript |
| (define (conjoin conjuncts frame-stream) (if (empty-conjunction? conjuncts) frame-stream (conjoin (rest-conjuncts conjuncts) (qeval (first-conjunct conjuncts) frame-stream)))) | function conjoin(conjuncts, frame_stream) { return is_empty_conjunction(conjuncts) ? frame_stream : conjoin(rest_conjuncts(conjuncts), evaluate_query(first_conjunct(conjuncts), frame_stream)); } |
| Original | JavaScript |
| (put 'and 'qeval conjoin) | put("and", "evaluate_query", conjoin); |
Or queries are handled We handle or queries similarly, as shown in figure 4.11. figure 4.12. The output streams for the various disjuncts of the or are computed separately and merged using the interleave-delayed interleave_delayed procedure function from section 4.4.4.6. (See exercises 4.82 and 4.83.)
| Original | JavaScript |
| (define (disjoin disjuncts frame-stream) (if (empty-disjunction? disjuncts) the-empty-stream (interleave-delayed (qeval (first-disjunct disjuncts) frame-stream) (delay (disjoin (rest-disjuncts disjuncts) frame-stream))))) (put 'or 'qeval disjoin) | 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 syntax representation of conjuncts and disjuncts are given in section 4.4.4.7.
Not is 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.
| Original | JavaScript |
| (define (negate operands frame-stream) (stream-flatmap (lambda (frame) (if (stream-null? (qeval (negated-query operands) (singleton-stream frame))) (singleton-stream frame) the-empty-stream)) frame-stream)) (put 'not 'qeval negate) | 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); |
Lisp-value The javascript_predicate syntactic form is a filter similar to not.
| Original | JavaScript | |
| Each frame in the stream is used to instantiate the variables in the pattern, the indicated predicate is applied, and the frames for which the predicate returns false are filtered out of the input stream. An error results if there are unbound pattern variables. | 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. |
| Original | JavaScript |
| (define (lisp-value call frame-stream) (stream-flatmap (lambda (frame) (if (execute (instantiate call frame (lambda (v f) (error "Unknown pat var - - LISP-VALUE" v)))) (singleton-stream frame) the-empty-stream)) frame-stream)) (put 'lisp-value 'qeval lisp-value) | 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); |
| Original | JavaScript | |
| Execute, which applies the predicate to the arguments, must eval the predicate expression to get the procedure to apply. However, it must not evaluate the arguments, since they are already the actual arguments, not expressions whose evaluation (in Lisp) will produce the arguments. Note that execute is implemented using eval and apply from the underlying Lisp system. |
The always-true special form 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. Always-true is used by the rule-body selector (section 4.4.4.7) 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).
| Original | JavaScript |
| (define (always-true ignore frame-stream) frame-stream) (put 'always-true 'qeval always-true) | function always_true(ignore, frame_stream) { return frame_stream; } put("always_true", "evaluate_query", always_true); |
Find-assertions, The function find_assertions, called by simple-query 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 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 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 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.
| Original | JavaScript |
| (define (find-assertions pattern frame) (stream-flatmap (lambda (datum) (check-an-assertion datum pattern frame)) (fetch-assertions pattern frame))) | function find_assertions(pattern, frame) { return stream_flatmap( datum => check_an_assertion(datum, pattern, frame), fetch_assertions(pattern, frame)); } |
Check-an-assertion The function check_an_assertion takes as arguments a data object (assertion), (an assertion), a pattern, and a frame and returns either a one-element stream containing the extended frame or the-empty-stream null if the match fails.
| Original | JavaScript |
| (define (check-an-assertion assertion query-pat query-frame) (let ((match-result (pattern-match query-pat assertion query-frame))) (if (eq? match-result 'failed) the-empty-stream (singleton-stream match-result)))) | 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); } |
| Original | JavaScript |
| (define (pattern-match pat dat frame) (cond ((eq? frame 'failed) 'failed) ((equal? pat dat) frame) ((var? pat) (extend-if-consistent pat dat frame)) ((and (pair? pat) (pair? dat)) (pattern-match (cdr pat) (cdr dat) (pattern-match (car pat) (car dat) frame))) (else '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 procedure function that extends a frame by adding a new binding, if this is consistent with the bindings already in the frame:
| Original | JavaScript |
| (define (extend-if-consistent var dat frame) (let ((binding (binding-in-frame var frame))) (if binding (pattern-match (binding-value binding) dat frame) (extend var dat 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); } |
The procedures functions used by extend-if-consistent extend_if_consistent to manipulate bindings are defined in section 4.4.4.8.
| Original | JavaScript | |
|
If a pattern contains a dot followed by a pattern variable, the pattern variable matches the rest of the data list (rather than the next element of the data list), just as one would expect with the dotted-tail notation described in exercise 2.20. Although the pattern matcher we have just implemented doesn't look for dots, it does behave as we want. This is because the Lisp read primitive, which is used by query-driver-loop to read the query and represent it as a list structure, treats dots in a special way. When read sees a dot, instead of making the next item be the next element of a list (the car of a cons whose cdr will be the rest of the list) it makes the next item be the cdr of the list structure. For example, the list structure produced by read for the pattern (computer ?type) could be constructed by evaluating the expression (cons 'computer (cons '?type '())), and that for (computer ?type) could be constructed by evaluating the expression (cons 'computer '?type). Thus, as pattern-match recursively compares cars and cdrs of a data list and a pattern that had a dot, it eventually matches the variable after the dot (which is a cdr of the pattern) against a sublist of the data list, binding the variable to that list. For example, matching the pattern (computer ?type) against (computer programmer trainee) will match ?type against the list (programmer trainee). |
Dotted tail notation is unnecessary in the JavaScript edition. We simply use the pair constructor rather than the list constructor when we want to refer to the rest of a list, as shown in section 4.4.1. See also section 4.4.4.7. |
Apply-rules The function apply_rules is the rule analog of find-assertions 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. Stream-flatmap The function stream_flatmap maps apply-a-rule apply_a_rule down the stream of possibly applicable rules (selected by fetch-rules, fetch_rules, section 4.4.4.5) and combines the resulting streams of frames.
| Original | JavaScript |
| (define (apply-rules pattern frame) (stream-flatmap (lambda (rule) (apply-a-rule rule pattern frame)) (fetch-rules pattern frame))) | function apply_rules(pattern, frame) { return stream_flatmap(rule => apply_a_rule(rule, pattern, frame), fetch_rules(pattern, frame)); } |
Apply-a-rule applies rules 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, named $x, then each one may add a binding for ?x $x to the frame when it is applied. These two ?x's $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.90.) Here is the apply-a-rule apply_a_rule procedure: function:
| Original | JavaScript |
| (define (apply-a-rule rule query-pattern query-frame) (let ((clean-rule (rename-variables-in rule))) (let ((unify-result (unify-match query-pattern (conclusion clean-rule) query-frame))) (if (eq? unify-result 'failed) the-empty-stream (qeval (rule-body clean-rule) (singleton-stream unify-result)))))) | 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)); } |
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 $x in the rule to ?x-7 $x_7 and each ?y $y in the rule to ?y-7. $y_7. (Make-new-variable (The functions make_new_variable and new-rule-application-id new_rule_application_id are included with the syntax procedures functions in section 4.4.4.7.)
| Original | JavaScript |
| (define (rename-variables-in rule) (let ((rule-application-id (new-rule-application-id))) (define (tree-walk exp) (cond ((var? exp) (make-new-variable exp rule-application-id)) ((pair? exp) (cons (tree-walk (car exp)) (tree-walk (cdr exp)))) (else exp))) (tree-walk rule))) | 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
procedure
function
that takes as inputs two patterns and a frame and returns either the
extended frame or the
symbol failed.
string "failed".
The unifier is like the pattern matcher except that it is
symmetrical—variables are allowed on both sides of the match.
Unify-match
The function unify_match
is basically the same as
pattern-match,
pattern_match,
except that there is
extra code
an extra clause
(marked
***
below) to handle
the case where the object on the right side of the match is a variable.
| Original | JavaScript |
| (define (unify-match p1 p2 frame) (cond ((eq? frame 'failed) 'failed) ((equal? p1 p2) frame) ((var? p1) (extend-if-possible p1 p2 frame)) ((var? p2) (extend-if-possible p2 p1 frame)) ; *** ((and (pair? p1) (pair? p2)) (unify-match (cdr p1) (cdr p2) (unify-match (car p1) (car p2) frame))) (else 'failed))) | 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
procedure
function
extend-if-possible
extend_if_possible
used in unification is the same as the
extend-if-consistent
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 (?x ?x) list($x, $x) and (?y $\langle expression$ $involving$ ?y$\rangle$) list($y, $\langle$$expression$ $involving$ $y$\rangle$) in a frame where both ?x $x and ?y $y are unbound. First ?x $x is matched against ?y, $y, making a binding of ?x $x to ?y. $y. Next, the same ?x $x is matched against the given expression involving ?y. $y. Since ?x $x is already bound to ?y, $y, this results in matching ?y $y against the expression. 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 $y such that ?y $y is equal to the expression involving ?y. $y. There is no general method for solving such equations, so we We reject such bindings; these cases are recognized by the predicate depends-on?depends_on.[1] On the other hand, we do not want to reject attempts to bind a variable to itself. For example, consider unifying (?x ?x) list($x, $x) and (?y ?y). list($y, $y). The second attempt to bind ?x $x to ?y $y matches ?y $y (the stored value of ?x (the stored value of $x ) against ?y $y (the new value of ?x). (the new value of $x). This is taken care of by the equal? equal clause of unify-match. unify_match.
| Original | JavaScript |
| (define (extend-if-possible var val frame) (let ((binding (binding-in-frame var frame))) (cond (binding (unify-match (binding-value binding) val frame)) ((var? val) ; *** (let ((binding (binding-in-frame val frame))) (if binding (unify-match var (binding-value binding) frame) (extend var val frame)))) ((depends-on? val var frame) ; *** 'failed) (else (extend var val frame))))) | 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); } } |
Depends-on? 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? depends_on is a simple recursive tree walk in which we substitute for the values of variables whenever necessary.
| Original | JavaScript |
| (define (depends-on? exp var frame) (define (tree-walk e) (cond ((var? e) (if (equal? var e) true (let ((b (binding-in-frame e frame))) (if b (tree-walk (binding-value b)) false)))) ((pair? e) (or (tree-walk (car e)) (tree-walk (cdr e)))) (else false))) (tree-walk exp)) | 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); } |
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. Then, in addition to storing all assertions in one big stream, we store all assertions whose cars are constant symbols in separate streams, in a table indexed by the symbol. To fetch an assertion that may match a pattern, we first check to see if the car of the pattern is a constant symbol. If so, we return (to be tested using the matcher) all the stored assertions that have the same car. If the pattern's car is not a constant symbol, we return all the stored assertions. Cleverer methods could also take advantage of information in the frame, or try also to optimize the case where the car of the pattern is not a constant symbol. We avoid building our criteria for indexing (using the car, handling only the case of constant symbols) into the program; instead we call on predicates and selectors that embody our criteria. 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.
| Original | JavaScript |
| (define THE-ASSERTIONS the-empty-stream) (define (fetch-assertions pattern frame) (if (use-index? pattern) (get-indexed-assertions pattern) (get-all-assertions))) (define (get-all-assertions) THE-ASSERTIONS) (define (get-indexed-assertions pattern) (get-stream (index-key-of pattern) 'assertion-stream)) | function fetch_assertions(pattern, frame) { return get_indexed_assertions(pattern); } function get_indexed_assertions(pattern) { return get_stream(index_key_of(pattern), "assertion-stream"); } |
| Original | JavaScript |
| (define (get-stream key1 key2) (let ((s (get key1 key2))) (if s s the-empty-stream))) | function get_stream(key1, key2) { const s = get(key1, key2); return is_undefined(s) ? null : s; } |
| Original | JavaScript | |
| Rules are stored similarly, using the car of the rule conclusion. Rule conclusions are arbitrary patterns, however, so they differ from assertions in that they can contain variables. A pattern whose car is a constant symbol can match rules whose conclusions start with a variable as well as rules whose conclusions have the same car. Thus, when fetching rules that might match a pattern whose car is a constant symbol we fetch all rules whose conclusions start with a variable as well as those whose conclusions have the same car as the pattern. For this purpose we store all rules whose conclusions start with a variable in a separate stream in our table, indexed by the symbol ?. | 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. |
| Original | JavaScript |
| (define THE-RULES the-empty-stream) (define (fetch-rules pattern frame) (if (use-index? pattern) (get-indexed-rules pattern) (get-all-rules))) (define (get-all-rules) THE-RULES) (define (get-indexed-rules pattern) (stream-append (get-stream (index-key-of pattern) 'rule-stream) (get-stream '? 'rule-stream))) | function fetch_rules(pattern, frame) { return get_indexed_rules(pattern); } function get_indexed_rules(pattern) { return get_stream(index_key_of(pattern), "rule-stream"); } |
Add-rule-or-assertion! The function add_rule_or_assertion is used by query-driver-loop query_driver_loop to add assertions and rules to the data base. Each item is stored in the index.
| Original | JavaScript |
| (define (add-rule-or-assertion! assertion) (if (rule? assertion) (add-rule! assertion) (add-assertion! assertion))) (define (add-assertion! assertion) (store-assertion-in-index assertion) (let ((old-assertions THE-ASSERTIONS)) (set! THE-ASSERTIONS (cons-stream assertion old-assertions)) 'ok)) (define (add-rule! rule) (store-rule-in-index rule) (let ((old-rules THE-RULES)) (set! THE-RULES (cons-stream rule old-rules)) 'ok)) | 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.
| Original | JavaScript |
| (define (store-assertion-in-index assertion) (if (indexable? assertion) (let ((key (index-key-of assertion))) (let ((current-assertion-stream (get-stream key 'assertion-stream))) (put key 'assertion-stream (cons-stream assertion current-assertion-stream)))))) (define (store-rule-in-index rule) (let ((pattern (conclusion rule))) (if (indexable? pattern) (let ((key (index-key-of pattern))) (let ((current-rule-stream (get-stream key 'rule-stream))) (put key 'rule-stream (cons-stream rule current-rule-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)); } |
| Original | JavaScript | |
| The following procedures define how the data-base index is used. A pattern (an assertion or a rule conclusion) will be stored in the table if it starts with a variable or a constant symbol. (define (indexable? pat) (or (constant-symbol? (car pat)) (var? (car pat)))) The key under which a pattern is stored in the table is either ? (if it starts with a variable) or the constant symbol with which it starts. | The key under which a pattern (an assertion or rule conclusion) is stored in the table is the string it starts with. |
| Original | JavaScript |
| (define (index-key-of pat) (let ((key (car pat))) (if (var? key) '? key))) | function index_key_of(pattern) { return head(pattern); } |
| Original | JavaScript | |
| The index will be used to retrieve items that might match a pattern if the pattern starts with a constant symbol. (define (use-index? pat) (constant-symbol? (car pat))) |
| Original | JavaScript | |
|
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.
|
Stream-append-delayed The functions stream_append_delayed and interleave-delayed interleave_delayed are just like stream-append stream_append and interleave (section 3.5.3), except that they take a delayed argument (like the integral procedure function in section 3.5.4). This postpones looping in some cases (see exercise 4.82).
| Original | JavaScript |
| (define (stream-append-delayed s1 delayed-s2) (if (stream-null? s1) (force delayed-s2) (cons-stream (stream-car s1) (stream-append-delayed (stream-cdr s1) delayed-s2)))) (define (interleave-delayed s1 delayed-s2) (if (stream-null? s1) (force delayed-s2) (cons-stream (stream-car s1) (interleave-delayed (force delayed-s2) (delay (stream-cdr s1)))))) | 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))); } |
Stream-flatmap, The function stream_flatmap, which is used throughout the query evaluator to map a procedure function over a stream of frames and combine the resulting streams of frames, is the stream analog of the flatmap procedure 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.83 and 4.84).
| Original | JavaScript |
| (define (stream-flatmap proc s) (flatten-stream (stream-map proc s))) (define (flatten-stream stream) (if (stream-null? stream) the-empty-stream (interleave-delayed (stream-car stream) (delay (flatten-stream (stream-cdr stream)))))) | 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 procedure function to generate a stream consisting of a single element:
| Original | JavaScript |
| (define (singleton-stream x) (cons-stream x the-empty-stream)) | function singleton_stream(x) { return pair(x, () => null); } |
| Original | JavaScript | |
|
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
more appropriate,
query-language-specific,
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.
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
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) 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. 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 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.4. 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))))); } 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))); } |
| Original | JavaScript | |
|
Type and contents, used by qeval (section 4.4.4.2), specify that a special form is identified by the symbol in its car. They are the same as the type-tag and contents procedures in section 2.4.2, except for the error message. (define (type exp) (if (pair? exp) (car exp) (error "Unknown expression TYPE" exp))) (define (contents exp) (if (pair? exp) (cdr exp) (error "Unknown expression CONTENTS" exp))) The following procedures, used by query-driver-loop (in section 4.4.4.1), specify that rules and assertions are added to the data base by expressions of the form (assert! rule-or-assertion): (define (assertion-to-be-added? exp) (eq? (type exp) 'assert!)) (define (add-assertion-body exp) (car (contents exp))) Here are the syntax definitions for the and, or, not, and lisp-value special forms (section 4.4.4.2): (define (empty-conjunction? exps) (null? exps)) (define (first-conjunct exps) (car exps)) (define (rest-conjuncts exps) (cdr exps)) (define (empty-disjunction? exps) (null? exps)) (define (first-disjunct exps) (car exps)) (define (rest-disjuncts exps) (cdr exps)) (define (negated-query exps) (car exps)) (define (predicate exps) (car exps)) (define (args exps) (cdr exps)) The following three procedures define the syntax of rules: (define (rule? statement) (tagged-list? statement 'rule)) (define (conclusion rule) (cadr rule)) (define (rule-body rule) (if (null? (cddr rule)) '(always-true) (caddr rule))) Query-driver-loop (section 4.4.4.1) calls query-syntax-process to transform pattern variables in the expression, which have the form ?symbol, into the internal format (? symbol). That is to say, a pattern such as (job ?x ?y) is actually represented internally by the system as (job (? x) (? y)). This increases the efficiency of query processing, since it means that the system can check to see if an expression is a pattern variable by checking whether the car of the expression is the symbol ?, rather than having to extract characters from the symbol. The syntax transformation is accomplished by the following procedure:[4] (define (query-syntax-process exp) (map-over-symbols expand-question-mark exp)) (define (map-over-symbols proc exp) (cond ((pair? exp) (cons (map-over-symbols proc (car exp)) (map-over-symbols proc (cdr exp)))) ((symbol? exp) (proc exp)) (else exp))) (define (expand-question-mark symbol) (let ((chars (symbol->string symbol))) (if (string=? (substring chars 0 1) "?") (list '? (string->symbol (substring chars 1 (string-length chars)))) symbol))) Once the variables are transformed in this way, the variables in a pattern are lists starting with ?, and the constant symbols (which need to be recognized for data-base indexing, section 4.4.4.5) are just the symbols. (define (var? exp) (tagged-list? exp '?)) (define (constant-symbol? exp) (symbol? exp)) Unique variables are constructed during rule application (in section 4.4.4.4) by means of the following procedures. The unique identifier for a rule application is a number, which is incremented each time a rule is applied. (define rule-counter 0) (define (new-rule-application-id) (set! rule-counter (+ 1 rule-counter)) rule-counter) (define (make-new-variable var rule-application-id) (cons '? (cons rule-application-id (cdr var)))) When query-driver-loop instantiates the query to print the answer, it converts any unbound pattern variables back to the right form for printing, using (define (contract-question-mark variable) (string->symbol (string-append "?" (if (number? (cadr variable)) (string-append (symbol->string (caddr variable)) "-" (number->string (cadr variable))) (symbol->string (cadr variable)))))) |
Frames are represented as lists of bindings, which are variable-value pairs:
| Original | JavaScript |
| (define (make-binding variable value) (cons variable value)) (define (binding-variable binding) (car binding)) (define (binding-value binding) (cdr binding)) (define (binding-in-frame variable frame) (assoc variable frame)) (define (extend variable value frame) (cons (make-binding variable value) frame)) | 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); } |
| Original | JavaScript |
| (define (simple-query query-pattern frame-stream) (stream-flatmap (lambda (frame) (stream-append (find-assertions query-pattern frame) (apply-rules query-pattern frame))) frame-stream)) (define (disjoin disjuncts frame-stream) (if (empty-disjunction? disjuncts) the-empty-stream (interleave (qeval (first-disjunct disjuncts) frame-stream) (disjoin (rest-disjuncts disjuncts) frame-stream)))) | 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)); } |
| Original | JavaScript |
| (define (flatten-stream stream) (if (stream-null? stream) the-empty-stream (interleave (stream-car stream) (flatten-stream (stream-cdr stream))))) | function flatten_stream(stream) { return is_null(stream) ? null : interleave(head(stream), flatten_stream(stream_tail(stream))); } |
-
Fill in the missing expressions in Alyssa's program.
Original JavaScript (define (simple-stream-flatmap proc s) (simple-flatten (stream-map proc s))) (define (simple-flatten stream) (stream-map ?? (stream-filter ?? stream))) 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?
| Original | JavaScript |
| (unique (job ?x (computer wizard))) | unique(job($x, list("computer", "wizard"))) |
| Original | JavaScript |
| (unique (job (Bitdiddle Ben) (computer wizard))) | unique(job(list("Bitdiddle", "Ben"), list("computer", "wizard"))) |
| Original | JavaScript |
| (unique (job ?x (computer programmer))) | unique(job($x, list("computer", "programmer"))) |
| Original | JavaScript |
| (and (job ?x ?j) (unique (job ?anyone ?j))) | and(job($x, $j), unique(job($anyone, $j))) |
| Original | JavaScript |
| (put 'unique 'qeval uniquely-asserted) | put("unique", "evaluate_query", uniquely_asserted); |
wronganswers 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
delayedmanner by appending to the frame a
promiseto 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.
| Original | JavaScript |
| (define (square x) (* x x)) (define (sum-of-squares x y) (+ (square x) (square y))) (sum-of-squares 3 4) | function square(x) { return x * x; } function sum_of_squares(x, y) { return square(x) + square(y); } sum_of_squares(3, 4); |
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.)