4.4.3 Is Logic Programming Mathematical Logic?

The means of combination used in the query language may at first seem identical

to the operations and, or, and not of mathematical logic,

and the application of query-language rules is in fact accomplished through a

legitimate method of inference. This

identification of the query language with mathematical logic is not really

valid, though, because the query language provides a

control structure

that interprets the logical statements procedurally. We can often

take advantage of this control structure. For example, to find all of the

supervisors of programmers we could formulate a query in either of two

logically equivalent forms:

查询语言中使用的组合方法，乍看之下似乎与数理逻辑中的 `and`、`or`、`not` 运算完全相同，而且查询语言规则的应用确实是通过一种合法的推理方法来实现的。然而，将查询语言等同于数理逻辑并不真正成立，因为查询语言提供了一种控制结构 (control structure)，以过程化的方式解释逻辑语句。我们通常可以利用这一控制结构。例如，为找出所有程序员的主管，我们可以用两种逻辑上等价的形式之一来表述查询：

or

或者

If a company has many more supervisors than programmers (the usual case), it is

better to use the first form rather than the second because the data base must

be scanned for each intermediate result (frame) produced by the first clause of

the and.

若公司中的主管人数远多于程序员（通常如此），则使用第一种形式优于第二种，因为数据库必须为 `and` 的第一个子句所产生的每个中间结果（框架）进行一次扫描。

The aim of logic programming is to provide the programmer with techniques for

decomposing a computational problem into two separate problems: “what” is to

be computed, and “how” this should be computed. This is accomplished by

selecting a subset of the statements of mathematical logic that is powerful

enough to be able to describe anything one might want to compute, yet weak

enough to have a controllable procedural interpretation. The intention here is

that, on the one hand, a program specified in a logic programming language

should be an effective program that can be carried out by a computer. Control

(“how” to compute) is effected by using the order of evaluation of the

language. We should be able to arrange the order of clauses and the order of

subgoals within each clause so that the computation is done in an order deemed

to be effective and efficient. At the same time, we should be able to view the

result of the computation (“what” to compute) as a simple consequence of the

laws of logic.

逻辑式程序设计 (logic programming) 的目标，是为程序员提供一种将计算问题分解为两个独立问题的技术：计算"什么"，以及"如何"计算。其实现途径是：从数理逻辑的陈述中选取一个子集，该子集既足够强大，能够描述一切可能需要计算的内容，又足够受限，具有可控的过程化解释。其意图在于：一方面，用逻辑式程序设计语言写成的程序应当是计算机可以执行的有效程序；控制（"如何"计算）由语言的求值顺序来体现，我们应当能够安排子句的顺序以及每个子句内子目标的顺序，使计算以被认为高效的方式进行。另一方面，我们也应当能够将计算结果（"什么"）视为数理逻辑定律的简单推论。

Our query language can be regarded as just such a procedurally interpretable

subset of mathematical logic. An assertion represents a simple fact (an atomic

proposition). A rule represents the implication that the rule conclusion holds

for those cases where the rule body holds. A rule has a natural procedural

interpretation: To establish the conclusion of the rule, establish the body of

the rule. Rules, therefore, specify computations. However, because rules can

also be regarded as statements of mathematical logic, we can justify any

“inference” accomplished by a logic program by asserting that the same result

could be obtained by working entirely within mathematical logic.

Subheading: Infinite loops

我们的查询语言可以被视为数理逻辑中这样一个具有过程化解释的子集。断言表示一个简单事实（一个原子命题）。规则表示这样一种蕴含关系：凡规则体成立之处，规则的结论也成立。规则具有自然的过程化解释：要确立规则的结论，就去确立规则的体。因此，规则指定了计算。然而，由于规则也可以被看作数理逻辑的陈述，我们可以为逻辑程序所完成的任何"推理"进行辩护——只需断言同样的结果完全可以在数理逻辑的框架内得到。

小节标题：无限循环 (Infinite loops)

A consequence of the procedural interpretation of logic programs is that it is

possible to construct hopelessly inefficient programs for solving certain

problems. An extreme case of inefficiency occurs when the system falls into

infinite loops in making deductions. As a simple example, suppose we are

setting up a data base of famous marriages, including

逻辑程序过程化解释的一个后果，是在求解某些问题时可能构造出极其低效的程序。极端低效的情形出现在系统在进行推导时陷入无限循环。作为一个简单示例，假设我们正在建立一个著名婚姻的数据库，其中包括：

If we now ask

若现在我们查询：

we will get no response, because the system doesn’t know that if A is

married to B, then B is married to A. So we assert the rule

系统不会给出任何回应，因为它不知道若 A 与 B 结婚，则 B 也与 A 结婚。于是我们断言如下规则：

and again query

再次进行查询：

Unfortunately, this will drive the system into an infinite loop, as follows:

遗憾的是，这将使系统陷入无限循环，过程如下：

The system finds that the married rule is applicable; that is, the rule

conclusion (married ?x ?y) successfully unifies with the query pattern

(married Mickey ?who) to produce a frame in which ?x is bound to

Mickey and ?y is bound to ?who. So the interpreter

proceeds to evaluate the rule body (married ?y ?x) in this frame—in

effect, to process the query (married ?who Mickey).

系统发现 `married` 规则可以应用，即规则的结论 `(married ?x ?y)` 能成功与查询模式 `(married Mickey ?who)` 合一，产生一个 `?x` 绑定到 `Mickey`、`?y` 绑定到 `?who` 的框架。于是解释器在此框架中对规则体 `(married ?y ?x)` 进行求值——实际上是处理查询 `(married ?who Mickey)`。

One answer appears directly as an assertion in the data base: (married

Minnie Mickey).

数据库中有一个直接的断言给出了答案：`(married Minnie Mickey)`。

The married rule is also applicable, so the interpreter again evaluates

the rule body, which this time is equivalent to (married Mickey ?who).

`married` 规则同样可以应用，于是解释器再次对规则体进行求值，这次等价于处理查询 `(married Mickey ?who)`。

The system is now in an infinite loop. Indeed, whether the system will find

the simple answer (married Minnie Mickey) before it goes into the loop

depends on implementation details concerning the order in which the system

checks the items in the data base. This is a very simple example of the kinds

of loops that can occur. Collections of interrelated rules can lead to loops

that are much harder to anticipate, and the appearance of a loop can depend on

the order of clauses in an and (see Exercise 4.64) or on low-level

details concerning the order in which the system processes

queries.

Subheading: Problems with not

系统现在陷入了无限循环。事实上，系统是否能在进入循环之前找到简单答案 `(married Minnie Mickey)`，取决于系统检查数据库各条目的顺序这一实现细节。这是可能出现的各种循环中极为简单的一例。相互关联的规则集合可以导致难以预料的循环，而循环的出现与否可能取决于 `and` 中子句的顺序（见练习 4.64），或系统处理查询时的底层顺序细节。

小节标题：`not` 的问题 (Problems with not)

Another quirk in the query system concerns not. Given the data base of

4.4.1, consider the following two queries:

查询系统的另一个奇特之处涉及 `not`。给定 4.4.1 节的数据库，考虑以下两个查询：

These two queries do not produce the same result. The first query begins by

finding all entries in the data base that match (supervisor ?x ?y), and

then filters the resulting frames by removing the ones in which the value of

?x satisfies (job ?x (computer programmer)). The second query

begins by filtering the incoming frames to remove those that can satisfy

(job ?x (computer programmer)). Since the only incoming frame is empty,

it checks the data base to see if there are any patterns that satisfy

(job ?x (computer programmer)). Since there generally are entries of

this form, the not clause filters out the empty frame and returns an

empty stream of frames. Consequently, the entire compound query returns an

empty stream.

这两个查询产生的结果并不相同。第一个查询先找出数据库中所有与 `(supervisor ?x ?y)` 匹配的条目，然后对结果框架进行过滤，移除其中 `?x` 的值满足 `(job ?x (computer programmer))` 的那些框架。第二个查询则先对传入的框架进行过滤，移除那些能满足 `(job ?x (computer programmer))` 的框架。由于唯一传入的框架是空框架，系统就检查数据库中是否存在满足 `(job ?x (computer programmer))` 的模式。由于通常存在这样的条目，`not` 子句将空框架过滤掉，返回一个空的框架流。因此，整个复合查询返回一个空流。

The trouble is that our implementation of not really is meant to serve

as a filter on values for the variables. If a not clause is processed

with a frame in which some of the variables remain unbound (as does ?x

in the example above), the system will produce unexpected results. Similar

problems occur with the use of lisp-value—the Lisp predicate can’t

work if some of its arguments are unbound. See Exercise 4.77.

问题在于，我们对 `not` 的实现本意是作为变量值的过滤器。若在某个框架中处理 `not` 子句时，该框架中仍有部分变量未被绑定（如上例中的 `?x`），系统将产生意想不到的结果。类似的问题也出现在 `lisp-value` 的使用中——若某些参数未被绑定，Lisp 谓词便无法正常工作。参见练习 4.77。

There is also a much more serious way in which the not of the query

language differs from the not of mathematical logic. In logic, we

interpret the statement “not P” to mean that P is not true. In the

query system, however, “not P” means that P is not deducible from the

knowledge in the data base. For example, given the personnel data base of

4.4.1, the system would happily deduce all sorts of not

statements, such as that Ben Bitdiddle is not a baseball fan, that it is not

raining outside, and that 2 + 2 is not 4. In other words, the not of logic programming

languages reflects the so-called

closed world assumption that all

relevant information has been included in the data base.

还有一种更为根本的方式，使查询语言中的 `not` 与数理逻辑中的 `not` 有所不同。在逻辑中，"非 P"意味着 P 不为真。然而在查询系统中，"非 P"意味着 P 无法从数据库中的知识中推导出来。例如，给定 4.4.1 节的人事数据库，系统会欣然推导出各种各样的否定陈述，例如：Ben Bitdiddle 不是棒球迷，现在外面没有下雨，以及 2 + 2 不等于 4。换言之，逻辑式程序设计语言中的 `not` 体现了所谓的封闭世界假设 (closed world assumption)，即认为所有相关信息都已包含在数据库中。