4.4.4 Implementing the Query System

Section 4.4.2 described how the query system works. Now we fill in the

details by presenting a complete implementation of the system.

Subheading: 4.4.4.1The Driver Loop and Instantiation

4.4.2 节描述了查询系统的工作原理。现在我们通过给出系统的完整实现来填补细节。子标题：4.4.4.1 驱动循环与实例化

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

查询系统的驱动循环反复读入输入表达式。如果该表达式是一条待加入数据库的规则或断言，就将相应信息添加进去；否则，该表达式被视为一个查询。驱动循环将此查询连同一个由单个空框架组成的初始框架流一起传给求值器 qeval。求值结果是一个框架流，其中每个框架都是通过用数据库中找到的变量值满足查询而生成的。这些框架被用来构成一个新的流，该流由原始查询的若干副本组成，其中各变量已被框架流提供的值实例化，最终该流被打印到终端：

Here, as in the other evaluators in this chapter, we use an abstract syntax for

the 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 4.4.4.7.

Add-rule-or-assertion! is defined in 4.4.4.5.

与本章其他求值器一样，我们对查询语言的表达式使用抽象语法。表达式语法的实现，包括谓词 assertion-to-be-added? 和选择函数 add-assertion-body，在 4.4.4.7 节给出。Add-rule-or-assertion! 在 4.4.4.5 节定义。

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 (4.4.4.7).

在对输入表达式做任何处理之前，驱动循环先对它进行句法变换，将其转换为一种更高效的处理形式。这涉及改变模式变量的表示方式。在查询被实例化时，任何仍未绑定的变量在打印前都会被转换回输入形式。这些变换由过程 query-syntax-process 和 contract-question-mark（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.

对一个表达式进行实例化，就是复制它，将表达式中的所有变量替换为它们在给定框架中的值。这些值本身也需要被实例化，因为它们可能包含变量（例如，如果 exp 中的 ?x 由于合一而绑定到 ?y，而 ?y 又绑定到 5）。当某个变量无法被实例化时应采取的行动，由传给 instantiate 的一个过程实参指定。

The procedures that manipulate bindings are defined in 4.4.4.8.

Subheading: 4.4.4.2The Evaluator

操作绑定的过程在 4.4.4.8 节定义。子标题：4.4.4.2 求值器

The qeval procedure, 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 special

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 form is assumed to be a simple query, to be

processed by simple-query.

由 query-driver-loop 调用的过程 qeval 是查询系统的基本求值器。它以一个查询和一个框架流作为输入，返回一个扩展后的框架流。它通过使用 get 和 put 进行数据导向分派来识别特殊形式，与我们在第 2 章实现通用操作时的做法完全相同。任何未被识别为特殊形式的查询都被视为简单查询，由 simple-query 处理。

Type and contents, defined in 4.4.4.7, implement

the abstract syntax of the special forms.

Subheading: Simple queries

在 4.4.4.7 节定义的 type 和 contents 实现了特殊形式的抽象语法。子标题：简单查询

The simple-query procedure 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.

过程 simple-query 处理简单查询。它以一个简单查询（即一个模式）和一个框架流作为实参，返回由对每个框架进行数据库匹配扩展而构成的流。

For each frame in the input stream, we use find-assertions

(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

(4.4.4.4) to apply all possible rules, producing another stream of

extended frames. These two streams are combined (using

stream-append-delayed, 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.71). The streams for the individual input frames

are combined using stream-flatmap (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.

Subheading: Compound queries

对输入流中的每个框架，我们用 find-assertions（4.4.4.3）将模式与数据库中所有断言进行匹配，产生一个扩展框架流；再用 apply-rules（4.4.4.4）应用所有可能的规则，产生另一个扩展框架流。这两个流被合并（使用 stream-append-delayed，4.4.4.6），形成在原始框架约束下该模式所有可能满足方式的流（参见练习 4.71）。各个输入框架对应的流再用 stream-flatmap（4.4.4.6）合并成一个大流，表示原始输入流中任意框架通过扩展与给定模式产生匹配的所有方式。子标题：复合查询

And queries are handled as illustrated in Figure 4.5 by the

conjoin procedure. Conjoin 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.

and 查询的处理方式如图 4.5 所示，由过程 conjoin 完成。conjoin 以合取项和框架流作为输入，返回扩展框架流。首先，conjoin 处理框架流，找出满足合取式中第一个查询的所有可能框架扩展的流；然后以此作为新的框架流，递归地将 conjoin 应用于其余查询。

The expression

表达式

sets up qeval to dispatch to conjoin when an and form is

encountered.

令 qeval 在遇到 and 形式时分派到 conjoin。

Or queries are handled similarly, as shown in Figure 4.6. The

output streams for the various disjuncts of the or are computed

separately and merged using the interleave-delayed procedure from

4.4.4.6. (See Exercise 4.71 and Exercise 4.72.)

or 查询的处理方式类似，如图 4.6 所示。or 的各个析取项的输出流分别计算，再用 4.4.4.6 节中的 interleave-delayed 过程合并。（参见练习 4.71 和练习 4.72。）

The predicates and selectors for the syntax of conjuncts and disjuncts are

given in 4.4.4.7.

Subheading: Filters

合取项和析取项语法的谓词和选择函数在 4.4.4.7 节给出。子标题：过滤器

Not is handled by the method outlined in 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.

not 按照 4.4.2 节所述的方法处理：我们尝试将输入流中的每个框架扩展以满足被否定的查询，只有在无法扩展时才将该框架纳入输出流。

Lisp-value is a filter similar to not. 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.

lisp-value 是一个类似于 not 的过滤器。流中的每个框架被用来对模式中的变量进行实例化，然后应用指定的谓词，谓词返回假的框架将从输入流中被过滤掉。如果存在未绑定的模式变量，则产生一个错误。

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.

execute 将谓词应用于实参，它必须对谓词表达式求值以得到待应用的过程；但它不能对实参求值，因为这些实参已经是实际实参，而不是需要在 Lisp 中求值才能产生实参的表达式。注意，execute 是用底层 Lisp 系统的 eval 和 apply 实现的。

The always-true special 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 (4.4.4.7) to provide bodies for rules

that were defined without bodies (that is, rules whose conclusions are always

satisfied).

特殊形式 always-true 提供一个始终得到满足的查询。它忽略自己的内容（通常为空），只是将输入流中所有框架原样传递下去。always-true 由选择函数 rule-body（4.4.4.7）使用，为那些没有定义体的规则（即结论总是得到满足的规则）提供规则体。

The selectors that define the syntax of not and lisp-value are

given in 4.4.4.7.

Subheading: 4.4.4.3Finding Assertions by Pattern Matching

定义 not 和 lisp-value 语法的选择函数在 4.4.4.7 节给出。子标题：4.4.4.3 通过模式匹配查找断言

Find-assertions, called by simple-query (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 (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.

由 simple-query（4.4.4.2）调用的 find-assertions 以一个模式和一个框架作为输入，返回一个框架流，每个框架都是对给定框架通过数据库中某个匹配项的扩展。它使用 fetch-assertions（4.4.4.5）获取数据库中所有应被检查的断言流。在此使用 fetch-assertions 的原因是：我们往往可以施加一些简单的检验，从而从候选匹配池中排除数据库中的许多条目。如果去掉 fetch-assertions，直接检验数据库中所有断言组成的流，系统仍然能够工作，但计算效率会较低，因为需要对匹配器发出更多调用。

Check-an-assertion takes as arguments a pattern, a data object

(assertion), and a frame and returns either a one-element stream containing the

extended frame or the-empty-stream if the match fails.

check-an-assertion 以一个模式、一个数据对象（断言）和一个框架作为实参，返回一个包含扩展后框架的单元素流，若匹配失败则返回 the-empty-stream。

The basic pattern matcher returns either the symbol 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 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

car of the pattern against the car of the data to produce a

frame; in this frame we then match the cdr of the pattern against the

cdr of the data. If none of these cases are applicable, the match fails

and we return the symbol failed.

基本模式匹配器返回符号 failed 或给定框架的一个扩展。匹配器的基本思想是逐元素地将模式与数据进行对比，同时积累对模式变量的绑定。如果模式与数据对象相同，匹配成功，返回迄今积累的绑定框架。否则，如果模式是一个变量，则在与框架中已有绑定一致的前提下，将该变量绑定到数据以扩展当前框架。如果模式和数据都是序对，则递归地将模式的 car 与数据的 car 匹配以得到一个框架，再在该框架中将模式的 cdr 与数据的 cdr 匹配。如果以上情形均不适用，则匹配失败，返回符号 failed。

Here is the procedure that extends a frame by adding a new binding, if this is

consistent with the bindings already in the 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 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 (f ?y) and ?y is unbound,

and we wish to augment this frame by a binding of ?x to (f b).

We look up ?x and find that it is bound to (f ?y). This leads us

to match (f ?y) against the proposed new value (f b) in the same

frame. Eventually this match extends the frame by adding a binding of

?y to b. ?X remains bound to (f ?y). We never

modify a stored binding and we never store more than one binding for a given

variable.

如果框架中该变量没有绑定，我们直接添加该变量到数据的绑定；否则，我们在框架中将数据与该变量的值进行匹配。如果所存储的值只包含常量——而在模式匹配中由 extend-if-consistent 存储的值确实如此——则匹配只是检查所存储的值与新值是否相同：相同则返回未修改的框架，不同则返回失败指示。然而，如果所存储的值是在合一过程中存入的（参见 4.4.4.4），它可能包含模式变量。递归地将已存储的模式与新数据进行匹配，将为该模式中的变量添加或检验绑定。例如，假设框架中 ?x 绑定到 (f ?y)，?y 未绑定，我们希望通过将 ?x 绑定到 (f b) 来扩展该框架。我们查找 ?x，发现它绑定到 (f ?y)，这就使我们在同一框架中将 (f ?y) 与拟新值 (f b) 进行匹配，最终该匹配通过添加 ?y 到 b 的绑定来扩展框架，而 ?x 仍然绑定到 (f ?y)。我们从不修改已存储的绑定，也从不为同一变量存储多个绑定。

The procedures used by extend-if-consistent to manipulate bindings are

defined in 4.4.4.8.

Subheading: Patterns with dotted tails

extend-if-consistent 用于操作绑定的过程在 4.4.4.8 节定义。子标题：带点尾的模式

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.

如果一个模式包含一个点后跟一个模式变量，则该模式变量匹配数据表的其余部分（而不是数据表的下一个元素），这与练习 2.20 中描述的点尾表示法的预期行为一致。虽然我们刚才实现的模式匹配器并不专门查找点，但它的行为确实符合要求。这是因为 Lisp 的 read 基本过程——被 query-driver-loop 用来读取查询并将其表示为表结构——以一种特殊的方式处理点。

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).

当 read 遇到一个点时，它不是把下一个元素作为表的下一个成员（即某个 cons 的 car，其 cdr 将是表的其余部分），而是把下一个元素直接作为表结构的 cdr。例如，read 为模式 (computer ?type) 产生的表结构可以通过对表达式 (cons 'computer (cons '?type '())) 求值来构造，而 (computer . ?type) 对应的表结构则可以通过对表达式 (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).

Subheading: 4.4.4.4Rules and Unification

因此，当 pattern-match 递归地比较数据表与带点模式的 car 和 cdr 时，它最终会将点后面的变量（即模式的某个 cdr）与数据表的某个子表进行匹配，并将该变量绑定到那个子表。例如，将模式 (computer . ?type) 与 (computer programmer trainee) 匹配，会将 ?type 匹配到表 (programmer trainee)。子标题：4.4.4.4 规则与合一

Apply-rules is the rule analog of find-assertions

(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 maps apply-a-rule down the stream of possibly

applicable rules (selected by fetch-rules, 4.4.4.5) and

combines the resulting streams of frames.

Apply-rules 是 find-assertions（4.4.4.3）的规则类比。它以模式和框架为输入，通过对数据库中的规则逐一应用，形成一个由扩充框架组成的流。Stream-flatmap 将 apply-a-rule 映射到可能适用的规则流（由 fetch-rules（4.4.4.5）选出），并将得到的各框架流合并。

Apply-a-rule applies rules using the method outlined in

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.

Apply-a-rule 按照 4.4.2 中概述的方法应用规则。它首先通过将规则结论与给定框架中的模式进行合一来扩充参数框架；若合一成功，则在这个新框架中对规则体求值。

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.79.) Here is the

apply-a-rule procedure:

但在所有这些步骤发生之前，程序会先将规则中的所有变量重命名为唯一的新名称。这样做的原因是防止不同规则应用中的变量相互混淆。例如，若两条规则都使用名为 ?x 的变量，则在各自被应用时都可能向框架中添加一个 ?x 的绑定。这两个 ?x 彼此毫不相干，不应误以为两个绑定必须一致。与其重命名变量，我们也可以设计出更巧妙的环境结构；然而，我们在此选用的重命名方式是最为直接的，尽管未必是最高效的。（见练习 4.79。）下面是 apply-a-rule 过程：

The selectors rule-body and conclusion that extract parts of a

rule are defined in 4.4.4.7.

提取规则各部分的选择函数 rule-body 和 conclusion 在 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. (Make-new-variable and

new-rule-application-id are included with the syntax procedures in

4.4.4.7.)

我们通过将唯一标识符（如一个数字）与每次规则应用关联，并将该标识符与原变量名组合，来生成唯一的变量名。例如，若规则应用标识符为 7，则可将规则中每个 ?x 改为 ?x-7，将每个 ?y 改为 ?y-7。（Make-new-variable 和 new-rule-application-id 与 4.4.4.7 中的语法过程一起给出。）

The unification algorithm is implemented as a procedure that takes as inputs

two patterns and a frame and returns either the extended frame or the symbol

failed. The unifier is like the pattern matcher except that it is

symmetrical—variables are allowed on both sides of the match.

Unify-match is basically the same as pattern-match, except that

there is extra code (marked “***” below) to handle the case where the

object on the right side of the match is a variable.

合一算法实现为一个过程，以两个模式和一个框架为输入，返回扩充后的框架或符号 failed。合一器与模式匹配器相似，区别在于它是对称的——匹配的两侧都允许出现变量。Unify-match 与 pattern-match 基本相同，只是增加了额外代码（在下面标记为 "***"）来处理匹配右侧为变量的情形。

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 extend-if-possible used in unification is the same as the

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.

在合一中，如同单边模式匹配一样，我们只有在所建议的框架扩展与已有绑定一致时才接受它。合一中使用的过程 extend-if-possible 与模式匹配中使用的 extend-if-consistent 基本相同，只是额外增加了两项特殊检查，在下面程序中以 "***" 标出。第一种情形：如果我们试图匹配的变量尚未绑定，但我们试图与之匹配的值本身是一个（不同的）变量，则需要检查该值是否已绑定——若已绑定，则对其值进行匹配；若双方都未绑定，可将任一方绑定到另一方。

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) and (?y ⟨expression involving ?y⟩) 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. There is no general method for solving

such equations, so we reject such bindings; these cases are recognized by the

predicate depends-on?. On the

other hand, we do not want to reject attempts to bind a variable to itself.

For example, consider unifying (?x ?x) and (?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.

第二项检查处理的是将一个变量绑定到含有该变量自身的模式的尝试。只要一个变量在两个模式中都重复出现，就可能产生这种情况。例如，考虑在 ?x 和 ?y 都未绑定的框架中，合一两个模式 (?x ?x) 和 (?y ⟨expression involving ?y⟩)。首先，?x 与 ?y 匹配，建立 ?x 到 ?y 的绑定；接着，同一个 ?x 再与含有 ?y 的给定表达式匹配。由于 ?x 已绑定到 ?y，这就变成了 ?y 与该表达式的匹配。若将合一器理解为寻找一组使两个模式相同的变量值，那么这两个模式意味着：找一个 ?y 使得 ?y 等于含 ?y 的表达式。这类方程没有通用的求解方法，因此我们拒绝此类绑定；这些情形由谓词 depends-on? 识别。另一方面，我们并不想拒绝将变量绑定到自身的尝试。例如，考虑合一 (?x ?x) 与 (?y ?y)：第二次试图将 ?x 绑定到 ?y 时，会将 ?y（?x 的存储值）与 ?y（?x 的新值）进行匹配，这种情况由 unify-match 的 equal? 子句处理。

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.

Depends-on? 是一个谓词，用于检验拟作为某模式变量值的表达式是否依赖于该变量本身。这一检验必须相对于当前框架进行，因为表达式中可能出现某个变量，而该变量已有一个依赖于待检变量的值。depends-on? 的结构是一个简单的递归树遍历，在必要时对变量的值进行代换。

Subheading: 4.4.4.5Maintaining the Data Base

子标题：4.4.4.5 维护数据库

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. In our system, 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.

设计逻辑式程序设计语言时，一个重要问题是如何安排，使得在检验给定模式时，尽可能少地检查数据库中无关的条目。在我们的系统中，除了将所有断言存储在一个大流中，我们还将 car 为常量符号的所有断言分别存储在以该符号为索引的各个流中。为了获取可能与某一模式匹配的断言，我们首先检查该模式的 car 是否为常量符号：如果是，则返回所有具有相同 car 的已存断言（供匹配器检验）；如果模式的 car 不是常量符号，则返回所有已存断言。更聪明的方法还可以利用框架中的信息，或者尝试优化模式 car 不是常量符号的情况。我们没有将索引标准（使用 car，只处理常量符号的情形）直接写死在程序中，而是通过谓词和选择函数来体现这些标准。

Get-stream looks up a stream in the table and returns an empty stream if

nothing is stored there.

Get-stream 在表中查找一个流，若该处没有存储任何内容，则返回空流。

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 ?.

规则的存储方式类似，使用规则结论的 car 作为索引。然而，规则结论是任意模式，因此与断言不同——它们可以包含变量。一个 car 为常量符号的模式，既可以匹配结论以变量开头的规则，也可以匹配结论具有相同 car 的规则。因此，在获取可能与 car 为常量符号的模式匹配的规则时，我们不仅获取结论具有相同 car 的规则，还获取所有结论以变量开头的规则。为此，我们将所有结论以变量开头的规则单独存储在表中的一个流里，以符号 ? 为索引。

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, if

appropriate, and in a stream of all assertions or rules in the data base.

Add-rule-or-assertion! 由 query-driver-loop 调用，用于将断言和规则加入数据库。每个条目在适当的情况下被存入索引，同时也存入数据库中所有断言或规则的流中。

To actually store an assertion or a rule, we check to see if it can be indexed.

If so, we store it in the appropriate stream.

为了实际存储一条断言或规则，我们先检查它是否可以被索引，如果可以，就将其存入相应的流中。

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.

下列过程定义了数据库索引的使用方式。一个模式（断言或规则结论）若以变量或常量符号开头，就会被存入表中。

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 index will be used to retrieve items that might match a pattern if the

pattern starts with a constant symbol.

若某模式以常量符号开头，则索引将被用来检索可能与该模式匹配的条目。