Exercise 4.60 · 习题

Exercise 4.60: By giving the query

(lives-near ?person (Hacker Alyssa P))

Alyssa P. Hacker is able to find people who live near her, with whom she can
ride to work. On the other hand, when she tries to find all pairs of people
who live near each other by querying

(lives-near ?person-1 ?person-2)

she notices that each pair of people who live near each other is listed twice;
for example,

(lives-near (Hacker Alyssa P) (Fect Cy D))
(lives-near (Fect Cy D) (Hacker Alyssa P))

Why does this happen? Is there a way to find a list of people who live near
each other, in which each pair appears only once? Explain.

Logic as programs

We can regard a rule as a kind of logical implication: If an assignment
of values to pattern variables satisfies the body, then it satisfies the
conclusion. Consequently, we can regard the query language as having the
ability to perform
logical deductions based upon the rules. As an
example, consider the append operation described at the beginning of
4.4. As we said, append can be characterized by the
following two rules:

For any list y, the empty list and y append to form
y.

For any u, v, y, and z, (cons u v) and
y append to form (cons u z) if v and y
append to form z.

To express this in our query language, we define two rules for a relation

(append-to-form x y z)

which we can interpret to mean “x and y append to form
z”:

(rule (append-to-form () ?y ?y))
(rule (append-to-form (?u . ?v) ?y (?u . ?z))
(append-to-form ?v ?y ?z))

The first rule has no body, which means that the conclusion holds for any value
of ?y. Note how the second rule makes use of dotted-tail notation to
name the car and cdr of a list.

Given these two rules, we can formulate queries that compute the append
of two lists:

;;; Query input:
(append-to-form (a b) (c d) ?z)

;;; Query results:
(append-to-form (a b) (c d) (a b c d))

What is more striking, we can use the same rules to ask the question “Which
list, when appended to (a b), yields (a b c d)?” This is
done as follows:

;;; Query input:
(append-to-form (a b) ?y (a b c d))

;;; Query results:
(append-to-form (a b) (c d) (a b c d))

We can also ask for all pairs of lists that append to form (a b c
d):

;;; Query input:
(append-to-form ?x ?y (a b c d))

;;; Query results:
(append-to-form () (a b c d) (a b c d))
(append-to-form (a) (b c d) (a b c d))
(append-to-form (a b) (c d) (a b c d))
(append-to-form (a b c) (d) (a b c d))
(append-to-form (a b c d) () (a b c d))

The query system may seem to exhibit quite a bit of intelligence in using the

rules to deduce the answers to the queries above. Actually, as we will see in

the next section, the system is following a well-determined algorithm in

unraveling the rules. Unfortunately, although the system works impressively in

the append case, the general methods may break down in more complex

cases, as we will see in 4.4.3.

练习 4.60：Alyssa P. Hacker 通过查询

(lives-near ?person (Hacker Alyssa P))

找到了住在她附近、可以与她拼车上班的人。然而，当她试图通过查询

(lives-near ?person-1 ?person-2)

找出所有彼此相邻而居的人对时，她注意到每对相邻的人都被列出了两次；例如：

(lives-near (Hacker Alyssa P) (Fect Cy D))
(lives-near (Fect Cy D) (Hacker Alyssa P))

为什么会这样？有没有办法找出一个每对只出现一次的相邻人员表？请加以说明。

逻辑即程序

我们可以把一条规则视为一种逻辑蕴含：若某组模式变量赋值满足规则体，则它也满足规则结论。因此，我们可以认为查询语言具有根据规则进行逻辑推导的能力。以 4.4 开头描述的 append 操作为例。如前所述，append 可由以下两条规则刻画：

对任意表 y，空表与 y 拼接后形成 y。

对任意 u、v、y 和 z，若 v 与 y 拼接后形成 z，则 (cons u v) 与 y 拼接后形成 (cons u z)。

为了用查询语言表达这一点，我们为关系

(append-to-form x y z)

定义两条规则，其含义可理解为"x 与 y 拼接形成 z"：

(rule (append-to-form () ?y ?y))
(rule (append-to-form (?u . ?v) ?y (?u . ?z))
(append-to-form ?v ?y ?z))

第一条规则没有体，这意味着对 ?y 的任何值结论都成立。注意第二条规则如何利用点尾记法来命名表的 car 和 cdr。

有了这两条规则，我们可以构造查询来计算两个表的拼接：

;;; Query input:
(append-to-form (a b) (c d) ?z)

;;; Query results:
(append-to-form (a b) (c d) (a b c d))

更引人注目的是，我们还可以用同样的规则来回答这样的问题："哪个表与 (a b) 拼接后得到 (a b c d)？"方法如下：

;;; Query input:
(append-to-form (a b) ?y (a b c d))

;;; Query results:
(append-to-form (a b) (c d) (a b c d))

我们还可以查询所有拼接后形成 (a b c d) 的表对：

;;; Query input:
(append-to-form ?x ?y (a b c d))

;;; Query results:
(append-to-form () (a b c d) (a b c d))
(append-to-form (a) (b c d) (a b c d))
(append-to-form (a b) (c d) (a b c d))
(append-to-form (a b c) (d) (a b c d))
(append-to-form (a b c d) () (a b c d))

查询系统在利用规则推导上述查询答案时，似乎展现出相当的智能。实际上，正如我们在下一节将看到的，该系统按照一种确定的算法来展开规则。遗憾的是，尽管系统在 append 这个例子中表现出色，但这些通用方法在更复杂的情形下可能会失效，我们将在 4.4.3 中看到这一点。