4.4.2 How the Query System Works

In section 4.4.4 we will present an implementation of the query

interpreter as a collection of procedures. In this section we give an overview

that explains the general structure of the system independent of low-level

implementation details. After describing the implementation of the

interpreter, we will be in a position to understand some of its limitations and

some of the subtle ways in which the query language’s logical operations differ

from the operations of mathematical logic.

在 4.4.4 节中，我们将以一组过程的形式给出查询解释器的具体实现。本节先从整体上介绍系统的一般结构，而不涉及底层实现细节。在描述解释器的实现之后，我们将能够理解其若干局限性，以及查询语言的逻辑操作与数理逻辑运算之间若干微妙的差异。

It should be apparent that the query evaluator must perform some kind of search

in order to match queries against facts and rules in the data base. One way to

do this would be to implement the query system as a nondeterministic program,

using the amb evaluator of 4.3 (see Exercise 4.78).

Another possibility is to manage the search with the aid of streams. Our

implementation follows this second approach.

显然，查询求值器必须执行某种形式的搜索，才能将查询与数据库中的事实和规则相匹配。一种做法是将查询系统实现为非确定性程序，借助 4.3 节的 amb 求值器（见练习 4.78）。另一种方案是借助流来管理搜索。我们的实现采用第二种方法。

The query system is organized around two central operations called

查询系统围绕两个核心操作组织，分别称为

pattern matching and

unification. We first describe

pattern matching and explain how this operation, together with the organization

of information in terms of streams of frames, enables us to implement both

simple and compound queries. We next discuss unification, a generalization of

pattern matching needed to implement rules. Finally, we show how the entire

query interpreter fits together through a procedure that classifies expressions

in a manner analogous to the way eval classifies expressions for the

interpreter described in 4.1.

Subheading: Pattern matching

模式匹配 (pattern matching) 与合一 (unification)。我们首先描述模式匹配，并解释这一操作如何与以框架流为单位组织信息的方式相结合，使我们既能实现简单查询，也能实现复合查询。接着讨论合一——模式匹配的一种推广，用于实现规则。最后，我们将展示整个查询解释器如何通过一个对表达式进行分类的过程整合在一起，这与 4.1 节描述的解释器中 eval 对表达式分类的方式类似。

小节标题：模式匹配

A

pattern matcher is a program that tests whether some datum fits a

specified pattern. For example, the data list ((a b) c (a b)) matches

the pattern (?x c ?x) with the pattern variable ?x bound to

(a b). The same data list matches the pattern (?x ?y ?z) with

?x and ?z both bound to (a b) and ?y bound to

c. It also matches the pattern ((?x ?y) c (?x ?y)) with

?x bound to a and ?y bound to b. However, it does

not match the pattern (?x a ?y), since that pattern specifies a list

whose second element is the symbol a.

模式匹配器 (pattern matcher) 是一种程序，用于检验某个数据项是否符合指定的模式。例如，数据表 ((a b) c (a b)) 与模式 (?x c ?x) 匹配，此时模式变量 ?x 被绑定到 (a b)。同一数据表也与模式 (?x ?y ?z) 匹配，其中 ?x 与 ?z 均绑定到 (a b)，?y 绑定到 c。它还与模式 ((?x ?y) c (?x ?y)) 匹配，其中 ?x 绑定到 a，?y 绑定到 b。但它不与模式 (?x a ?y) 匹配，因为该模式要求表的第二个元素为符号 a。

The pattern matcher used by the query system takes as inputs a pattern, a

datum, and a

frame that specifies bindings for various pattern

variables. It checks whether the datum matches the pattern in a way that is

consistent with the bindings already in the frame. If so, it returns the given

frame augmented by any bindings that may have been determined by the match.

Otherwise, it indicates that the match has failed.

查询系统所用的模式匹配器以一个模式、一个数据项以及一个指定了各模式变量绑定的框架作为输入。它检验数据项是否以与框架中已有绑定一致的方式匹配该模式。若匹配成功，返回给定框架加上本次匹配所确定的所有新绑定后的增强框架；否则，表示匹配失败。

For example, using the pattern (?x ?y ?x) to match (a b a) given

an empty frame will return a frame specifying that ?x is bound to

a and ?y is bound to b. Trying the match with the same

pattern, the same datum, and a frame specifying that ?y is bound to

a will fail. Trying the match with the same pattern, the same datum,

and a frame in which ?y is bound to b and ?x is unbound

will return the given frame augmented by a binding of ?x to a.

例如，用模式 (?x ?y ?x) 匹配 (a b a)，在空框架下，将返回一个指定 ?x 绑定到 a、?y 绑定到 b 的框架。若用同一模式、同一数据项，但在 ?y 已绑定到 a 的框架下尝试匹配，则匹配失败。若在 ?y 绑定到 b 而 ?x 未绑定的框架下尝试匹配，则返回给定框架加上 ?x 绑定到 a 后的增强框架。

The pattern matcher is all the mechanism that is needed to process simple

queries that don’t involve rules. For instance, to process the query

模式匹配器是处理不涉及规则的简单查询所需的全部机制。例如，要处理如下查询：

we scan through all assertions in the data base and select those that match the

pattern with respect to an initially empty frame. For each match we find, we

use the frame returned by the match to instantiate the pattern with a value for

?x.

Subheading: Streams of frames

我们遍历数据库中所有断言，选出那些在初始空框架下与该模式匹配的断言。对于找到的每个匹配，我们用匹配返回的框架将模式实例化，得到 ?x 的具体值。

小节标题：框架流

The testing of patterns against frames is organized through the use of streams.

Given a single frame, the matching process runs through the data-base entries

one by one. For each data-base entry, the matcher generates either a special

symbol indicating that the match has failed or an extension to the frame. The

results for all the data-base entries are collected into a stream, which is

passed through a filter to weed out the failures. The result is a stream of

all the frames that extend the given frame via a match to some assertion in the

data base.

模式与框架的检验过程通过流来组织。给定一个框架，匹配过程逐一遍历数据库中的条目。对每个数据库条目，匹配器要么产生一个表示匹配失败的特殊符号，要么产生对该框架的一个扩展。所有数据库条目的结果被汇集到一个流中，再经过过滤器筛除失败情形。最终结果是一个流，包含所有通过与数据库某条断言匹配而扩展给定框架所得到的框架。

In our system, a query takes an input stream of frames and performs the above

matching operation for every frame in the stream, as indicated in Figure 4.4.

That is, for each frame in the input stream, the query generates a new

stream consisting of all extensions to that frame by matches to assertions in

the data base. All these streams are then combined to form one huge stream,

which contains all possible extensions of every frame in the input stream.

This stream is the output of the query.

Figure 4.4: A query processes a stream of frames.

在我们的系统中，一个查询以一个框架流为输入，对流中的每个框架执行上述匹配操作，如图 4.4 所示。也就是说，对输入流中的每个框架，查询产生一个新流，包含该框架通过与数据库断言匹配所得的所有扩展。所有这些流随后被合并为一个巨大的流，包含输入流中每个框架所有可能扩展的结果。这个流就是查询的输出。

图 4.4：查询处理一个框架流。

To answer a simple query, we use the query with an input stream consisting of a

single empty frame. The resulting output stream contains all extensions to the

empty frame (that is, all answers to our query). This stream of frames is then

used to generate a stream of copies of the original query pattern with the

variables instantiated by the values in each frame, and this is the stream that

is finally printed.

Subheading: Compound queries

为了回答一个简单查询，我们以一个由单一空框架构成的输入流来运行该查询。所得的输出流包含对空框架的所有扩展（即该查询的所有答案）。这个框架流随后被用于生成原始查询模式的若干副本的流，各副本中的变量由对应框架中的值实例化，最终打印出的便是这个流。

小节标题：复合查询

The real elegance of the stream-of-frames implementation is evident when we

deal with compound queries. The processing of compound queries makes use of

the ability of our matcher to demand that a match be consistent with a

specified frame. For example, to handle the and of two queries, such as

框架流实现方案的真正优雅之处，在处理复合查询时得以充分体现。复合查询的处理利用了匹配器要求匹配必须与指定框架一致这一能力。例如，要处理两个查询的 and，比如：

(informally, “Find all people who can do the job of a computer programmer

trainee”), we first find all entries that match the pattern

（非正式地说，"找出所有能胜任计算机程序员实习生职务的人"），我们首先找出与如下模式匹配的所有条目：

This produces a stream of frames, each of which contains a binding for

?x. Then for each frame in the stream we find all entries that match

这产生一个框架流，其中每个框架都包含对 ?x 的绑定。然后对于流中的每个框架，找出与如下模式匹配的所有条目：

in a way that is consistent with the given binding for ?x. Each such

match will produce a frame containing bindings for ?x and

?person. The and of two queries can be viewed as a series

combination of the two component queries, as shown in Figure 4.5. The

frames that pass through the first query filter are filtered and further

extended by the second query.

其方式与给定的 ?x 绑定一致。每一个这样的匹配都将产生一个包含 ?x 和 ?person 绑定的框架。两个查询的 and 可以被视为两个组成查询的串行组合，如图 4.5 所示。通过第一个查询过滤器的框架将被第二个查询进一步过滤和扩展。

Figure 4.5: The and combination of two queries is produced by operating on the stream of frames in series.

图 4.5：两个查询的 and 组合通过对框架流的串行操作来实现。

Figure 4.6 shows the analogous method for computing the or of two

queries as a parallel combination of the two component queries. The input

stream of frames is extended separately by each query. The two resulting

streams are then merged to produce the final output stream.

图 4.6 展示了计算两个查询的 or 的类似方法——将两个组成查询并行组合。输入的框架流分别被两个查询各自扩展，所得的两个流再合并，产生最终的输出流。

Figure 4.6: The or combination of two queries is produced by operating on the stream of frames in parallel and merging the results.

图 4.6：两个查询的 or 组合通过对框架流的并行操作并合并结果来实现。

Even from this high-level description, it is apparent that the processing of

compound queries can be slow. For example, since a query may produce more than

one output frame for each input frame, and each query in an and gets its

input frames from the previous query, an and query could, in the worst

case, have to perform a number of matches that is exponential in the number of

queries (see Exercise 4.76). Though systems for

handling only simple queries are quite practical, dealing with complex queries

is extremely difficult.

即便从这一高层描述也可以看出，复合查询的处理可能相当缓慢。例如，由于一个查询对每个输入框架可能产生不止一个输出框架，而 and 中的每个查询从前一个查询获取输入框架，因此在最坏情况下，and 查询所需的匹配次数可能随查询数量呈指数级增长（见练习 4.76）。尽管只处理简单查询的系统完全实用，处理复杂查询则极为困难。

From the stream-of-frames viewpoint, the not of some query acts as a

filter that removes all frames for which the query can be satisfied. For

instance, given the pattern

从框架流的视角来看，某查询的 not 充当一个过滤器，移除所有该查询能够被满足的框架。例如，给定模式：

we attempt, for each frame in the input stream, to produce extension frames

that satisfy (job ?x (computer programmer)). We remove from the input

stream all frames for which such extensions exist. The result is a stream

consisting of only those frames in which the binding for ?x does not

satisfy (job ?x (computer programmer)). For example, in processing the

query

对于输入流中的每个框架，我们尝试生成满足 `(job ?x (computer programmer))` 的扩展框架。凡能生成此类扩展的框架，一律从输入流中移除。结果是一个仅由那些 `?x` 的绑定不满足 `(job ?x (computer programmer))` 的框架组成的流。例如，在处理该查询时，

the first clause will generate frames with bindings for ?x and

?y. The not clause will then filter these by removing all frames

in which the binding for ?x satisfies the restriction that ?x is

a computer programmer.

第一个子句将产生带有 `?x` 和 `?y` 绑定的框架。随后，`not` 子句通过移除所有 `?x` 的绑定满足"?x 是计算机程序员"这一限制条件的框架，对这些框架进行过滤。

The lisp-value special form is implemented as a similar filter on frame

streams. We use each frame in the stream to instantiate any variables in the

pattern, then apply the Lisp predicate. We remove from the input stream all

frames for which the predicate fails.

Subheading: Unification

`lisp-value` 特殊形式作为对框架流的类似过滤器来实现。我们用流中的每个框架对模式中的变量进行实例化，然后应用 Lisp 谓词。凡谓词失败的框架，均从输入流中移除。

小节标题：合一 (Unification)

In order to handle rules in the query language, we must be able to find the

rules whose conclusions match a given query pattern. Rule conclusions are like

assertions except that they can contain variables, so we will need a

generalization of pattern matching—called

unification—in which

both the “pattern” and the “datum” may contain variables.

为了在查询语言中处理规则，我们必须能够找到其结论与给定查询模式相匹配的规则。规则的结论与断言相似，但可以包含变量，因此我们需要模式匹配的一种推广——称为合一 (unification)——其中"模式"和"数据"都可以包含变量。

A unifier takes two patterns, each containing constants and variables, and

determines whether it is possible to assign values to the variables that will

make the two patterns equal. If so, it returns a frame containing these

bindings. For example, unifying (?x a ?y) and (?y ?z a) will

specify a frame in which ?x, ?y, and ?z must all be bound

to a. On the other hand, unifying (?x ?y a) and (?x b ?y)

will fail, because there is no value for ?y that can make the two

patterns equal. (For the second elements of the patterns to be equal,

?y would have to be b; however, for the third elements to be

equal, ?y would have to be a.) The unifier used in the query

system, like the pattern matcher, takes a frame as input and performs

unifications that are consistent with this frame.

合一器接受两个模式，每个模式都包含常量和变量，并判断是否可能为变量赋值，使两个模式相等。若可以，则返回一个包含这些绑定的框架。例如，合一 `(?x a ?y)` 与 `(?y ?z a)` 将指定一个框架，其中 `?x`、`?y` 和 `?z` 必须全部绑定到 `a`。另一方面，合一 `(?x ?y a)` 与 `(?x b ?y)` 将失败，因为不存在使两个模式相等的 `?y` 的值。（若要使模式的第二个元素相等，`?y` 必须是 `b`；然而，若要使第三个元素相等，`?y` 必须是 `a`。）查询系统中使用的合一器与模式匹配器一样，以框架作为输入，并执行与该框架一致的合一。

The unification algorithm is the most technically difficult part of the query

system. With complex patterns, performing unification may seem to require

deduction. To unify (?x ?x) and ((a ?y c) (a b ?z)), for

example, the algorithm must infer that ?x should be (a b c),

?y should be b, and ?z should be c. We may think

of this process as solving a set of equations among the pattern components. In

general, these are simultaneous equations, which may require substantial

manipulation to solve. For example, unifying (?x ?x) and

((a ?y c) (a b ?z)) may be thought of as specifying the simultaneous

equations

合一算法是查询系统中技术上最为复杂的部分。对于复杂的模式，执行合一看起来似乎需要推导。例如，合一 `(?x ?x)` 与 `((a ?y c) (a b ?z))` 时，算法必须推断出 `?x` 应为 `(a b c)`，`?y` 应为 `b`，`?z` 应为 `c`。我们可以将这一过程看作对模式各分量之间方程组的求解。一般来说，这些是联立方程，可能需要大量处理才能求解。例如，合一 `(?x ?x)` 与 `((a ?y c) (a b ?z))` 可被看作指定如下联立方程：

These equations imply that

这些方程意味着

which in turn implies that

这进而意味着

and hence that

从而得出

In a successful pattern match, all pattern variables become bound, and the

values to which they are bound contain only constants. This is also true of

all the examples of unification we have seen so far. In general, however, a

successful unification may not completely determine the variable values; some

variables may remain unbound and others may be bound to values that contain

variables.

在成功的模式匹配中，所有模式变量都会被绑定，且绑定的值只包含常量。迄今所见的所有合一示例也都如此。然而，一般来说，成功的合一不一定能完全确定变量的值；某些变量可能仍未被绑定，而另一些则可能被绑定到包含变量的值上。

Consider the unification of (?x a) and ((b ?y) ?z). We can

deduce that ?x = (b ?y) and a = ?z, but we cannot further solve

for ?x or ?y. The unification doesn’t fail, since it is

certainly possible to make the two patterns equal by assigning values to

?x and ?y. Since this match in no way restricts the values

?y can take on, no binding for ?y is put into the result frame.

The match does, however, restrict the value of ?x. Whatever value

?y has, ?x must be (b ?y). A binding of ?x to the

pattern (b ?y) is thus put into the frame. If a value for ?y is

later determined and added to the frame (by a pattern match or unification that

is required to be consistent with this frame), the previously bound ?x

will refer to this value.

Subheading: Applying rules

考虑合一 `(?x a)` 与 `((b ?y) ?z)`。我们可以推出 `?x = (b ?y)` 以及 `a = ?z`，但无法进一步求解 `?x` 或 `?y`。合一并不失败，因为只要为 `?x` 和 `?y` 赋以适当的值，显然可以使两个模式相等。由于此次匹配完全不限制 `?y` 的取值，因此结果框架中不会为 `?y` 添加任何绑定。但匹配确实限制了 `?x` 的值：无论 `?y` 取何值，`?x` 必须是 `(b ?y)`。因此，框架中将加入 `?x` 到模式 `(b ?y)` 的绑定。若 `?y` 的值在之后被确定并添加到框架中（通过要求与该框架保持一致的模式匹配或合一），则先前已绑定的 `?x` 将引用该值。

小节标题：应用规则 (Applying rules)

Unification is the key to the component of the query system that makes

inferences from rules. To see how this is accomplished, consider processing a

query that involves applying a rule, such as

合一是查询系统中从规则进行推理这一组件的关键所在。为了理解其实现方式，考虑处理一个涉及应用规则的查询，例如：

To process this query, we first use the ordinary pattern-match procedure

described above to see if there are any assertions in the data base that match

this pattern. (There will not be any in this case, since our data base

includes no direct assertions about who lives near whom.) The next step is to

attempt to unify the query pattern with the conclusion of each rule. We find

that the pattern unifies with the conclusion of the rule

处理该查询时，我们首先使用上文描述的普通模式匹配过程，检查数据库中是否存在与此模式匹配的断言。（本例中不会有任何匹配，因为我们的数据库不包含关于谁住在谁附近的直接断言。）下一步是尝试将查询模式与每条规则的结论进行合一。我们发现该模式能与如下规则的结论合一：

resulting in a frame specifying that ?person-2 is bound to (Hacker

Alyssa P) and that ?x should be bound to (have the same value as)

?person-1. Now, relative to this frame, we evaluate the compound query

given by the body of the rule. Successful matches will extend this frame by

providing a binding for ?person-1, and consequently a value for

?x, which we can use to instantiate the original query pattern.

从而生成一个框架，指定 `?person-2` 绑定到 `(Hacker Alyssa P)`，而 `?x` 应绑定到（与之取相同值的）`?person-1`。现在，相对于该框架，我们对规则体给出的复合查询进行求值。成功的匹配将通过为 `?person-1` 提供绑定来扩展该框架，进而给出 `?x` 的值，从而可以用来实例化原始查询模式。

In general, the query evaluator uses the following method to apply a rule when

trying to establish a query pattern in a frame that specifies bindings for some

of the pattern variables:

一般来说，查询求值器在一个为某些模式变量指定了绑定的框架中，用如下方法来应用规则以确立某个查询模式：

Unify the query with the conclusion of the rule to form, if successful, an

extension of the original frame.

将查询与规则的结论进行合一，若成功，则形成对原始框架的扩展。

Relative to the extended frame, evaluate the query formed by the body of the

rule.

相对于扩展后的框架，对由规则体构成的查询进行求值。

Notice how similar this is to the method for applying a procedure in the

eval/apply evaluator for Lisp:

请注意，这与在 Lisp 的 eval/apply 求值器中应用过程的方法何其相似：

Bind the procedure’s parameters to its arguments to form a frame that extends

the original procedure environment.

将过程的形参绑定到其实参，构成一个扩展原过程环境的框架。

Relative to the extended environment, evaluate the expression formed by the

body of the procedure.

相对于这个扩展后的环境，对由过程体构成的表达式求值。

The similarity between the two evaluators should come as no surprise. Just as

procedure definitions are the means of abstraction in Lisp, rule definitions

are the means of abstraction in the query language. In each case, we unwind

the abstraction by creating appropriate bindings and evaluating the rule or

procedure body relative to these.

Subheading: Simple queries

两个求值器之间的相似性不足为奇。正如过程定义是 Lisp 中抽象的方法，规则定义是查询语言中抽象的方法。在每种情形下，我们都通过创建适当的绑定并相对于这些绑定对规则或过程体求值，来展开这一抽象。

小节标题：简单查询

We saw earlier in this section how to evaluate simple queries in the absence of

rules. Now that we have seen how to apply rules, we can describe how to

evaluate simple queries by using both rules and assertions.

本节前面已经介绍了在没有规则的情况下如何求值简单查询。既然我们已经了解了如何应用规则，现在可以描述如何同时利用规则和断言来求值简单查询。

Given the query pattern and a stream of frames, we produce, for each frame in

the input stream, two streams:

给定查询模式和一个框架流，对于输入流中的每个框架，我们产生两个流：

a stream of extended frames obtained by matching the pattern against all

assertions in the data base (using the pattern matcher), and

一个由扩展框架组成的流，这些框架是通过将模式与数据库中所有断言进行匹配（使用模式匹配器）而得到的；以及

a stream of extended frames obtained by applying all possible rules (using the

unifier).

一个由扩展框架组成的流，这些框架是通过应用所有可能的规则（使用合一器）而得到的。

Appending these two streams produces a stream that consists of all the ways

that the given pattern can be satisfied consistent with the original frame.

These streams (one for each frame in the input stream) are now all combined to

form one large stream, which therefore consists 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: The query evaluator and the driver loop

将这两个流合并，得到一个流，其中包含给定模式在原始框架约束下所有可能的满足方式。这些流（输入流中每个框架各对应一个）随后被合并为一个大流，从而包含原始输入流中任意框架能够扩展并与给定模式匹配的所有方式。

小节标题：查询求值器与驱动循环

Despite the complexity of the underlying matching operations, the system is

organized much like an evaluator for any language. The procedure that

coordinates the matching operations is called qeval, and it plays a role

analogous to that of the eval procedure for Lisp. Qeval takes as

inputs a query and a stream of frames. Its output is a stream of frames,

corresponding to successful matches to the query pattern, that extend some

frame in the input stream, as indicated in Figure 4.4. Like eval,

qeval classifies the different types of expressions (queries) and

dispatches to an appropriate procedure for each. There is a procedure for each

special form (and, or, not, and lisp-value) and one

for simple queries.

尽管底层匹配操作颇为复杂，整个系统的组织方式与任何语言的求值器大同小异。协调各匹配操作的过程名为 qeval，其作用与 Lisp 解释器中 eval 过程的作用类似。qeval 接受一个查询和一个框架流作为输入，输出一个框架流——这些框架对应查询模式的成功匹配，是对输入流中某个框架的扩展，如图 4.4 所示。与 eval 一样，qeval 对不同类型的表达式（查询）进行分类，并派发到相应的处理过程。针对每种特殊形式（and、or、not 以及 lisp-value）各有一个过程，另有一个过程处理简单查询。

The driver loop, which is analogous to the driver-loop procedure for the

other evaluators in this chapter, reads queries from the terminal. For each

query, it calls qeval with the query and a stream that consists of a

single empty frame. This will produce the stream of all possible matches (all

possible extensions to the empty frame). For each frame in the resulting

stream, it instantiates the original query using the values of the variables

found in the frame. This stream of instantiated queries is then

printed.

驱动循环与本章其他求值器中的 driver-loop 过程类似，从终端读取查询。对每个查询，它以该查询和一个由单一空框架组成的流为参数调用 qeval。这将产生所有可能匹配的流（即对空框架的所有可能扩展）。对于结果流中的每个框架，它用该框架中各变量的值对原始查询进行实例化。最终打印出这个由实例化查询组成的流。

The driver also checks for the special command assert!, which signals

that the input is not a query but rather an assertion or rule to be added to

the data base. For instance,

驱动循环还检查特殊命令 assert!，该命令表示输入不是一个查询，而是一个待添加到数据库中的断言或规则。例如，