In Chapter 1 we stressed that computer science deals with imperative (how
to) knowledge, whereas mathematics deals with declarative (what is) knowledge.
Indeed, programming languages require that the programmer express knowledge in
a form that indicates the step-by-step methods for solving particular problems.
On the other hand, high-level languages provide, as part of the language
implementation, a substantial amount of methodological knowledge that frees the
user from concern with numerous details of how a specified computation will
progress.
在第 1 章，我们强调计算机科学处理的是命令式（如何做）知识，而数学处理的是陈述式（是什么）知识。确实，程序设计语言要求程序员以逐步说明求解特定问题方法的形式来表达知识。另一方面，高级语言作为语言实现的一部分，提供了大量方法论知识，从而将用户从如何推进特定计算的诸多细节中解放出来。
Most programming languages, including Lisp, are organized around computing the
values of mathematical functions. Expression-oriented languages (such as Lisp,
Fortran, and Algol) capitalize on the “pun” that an expression that describes
the value of a function may also be interpreted as a means of computing that
value. Because of this, most programming languages are strongly biased toward
unidirectional computations (computations with well-defined inputs and
outputs). There are, however, radically different programming languages that
relax this bias. We saw one such example in 3.3.5, where the
objects of computation were arithmetic constraints. In a constraint system the
direction and the order of computation are not so well specified; in carrying
out a computation the system must therefore provide more detailed “how to”
knowledge than would be the case with an ordinary arithmetic computation. This
does not mean, however, that the user is released altogether from the
responsibility of providing imperative knowledge. There are many constraint
networks that implement the same set of constraints, and the user must choose
from the set of mathematically equivalent networks a suitable network to
specify a particular computation.
大多数程序设计语言，包括 Lisp，都以计算数学函数的值为核心组织方式。以表达式为中心的语言（如 Lisp、Fortran 和 Algol）利用了这样一个“双关”：描述函数值的表达式同时也可以被解释为计算该值的手段。正因如此，大多数程序设计语言都强烈偏向于单向计算（具有明确定义的输入和输出的计算）。然而，也存在一些截然不同的程序设计语言，它们放宽了这种偏向。我们在 3.3.5 节见过这样一个例子，其中计算的对象是算术约束。在约束系统中，计算的方向和顺序并不那么明确；在执行计算时，系统必须提供比普通算术计算更为详细的“如何做”知识。然而这并不意味着用户完全免除了提供命令式知识的责任。能够实现同一组约束的约束网络有很多，用户必须从数学上等价的网络集合中选择一个合适的网络来指定特定的计算。
The nondeterministic program evaluator of 4.3 also moves away
from the view that programming is about constructing algorithms for computing
unidirectional functions. In a nondeterministic language, expressions can have
more than one value, and, as a result, the computation is dealing with
relations rather than with single-valued functions. Logic programming extends
this idea by combining a relational vision of programming with a powerful kind
of symbolic pattern matching called
unification.
4.3 节的非确定性程序求值器同样偏离了“程序设计就是为单向函数构造算法”这一观点。在非确定性语言中，表达式可以拥有多个值，因而计算处理的是关系而非单值函数。逻辑式程序设计 (logic programming) 通过将程序设计的关系视角与一种称为合一 (unification) 的强大符号模式匹配相结合，进一步发展了这一思想。
This approach, when it works, can be a very powerful way to write programs.
Part of the power comes from the fact that a single “what is” fact can be
used to solve a number of different problems that would have different “how
to” components. As an example, consider the append operation, which
takes two lists as arguments and combines their elements to form a single list.
In a procedural language such as Lisp, we could define append in terms
of the basic list constructor cons, as we did in 2.2.1:
这种方法在奏效时，是一种非常强大的程序编写方式。其部分威力来源于：一个单一的“是什么”事实可以用于解决若干在“如何做”层面各不相同的问题。以 `append` 操作为例，它以两个表为参数，将它们的元素合并成一个表。在 Lisp 这样的过程式语言中，我们可以借助基本的表构造函数 `cons` 来定义 `append`，正如我们在 2.2.1 节所做的那样：
This procedure can be regarded as a translation into Lisp of the following two
rules, the first of which covers the case where the first list is empty and the
second of which handles the case of a nonempty list, which is a cons of
two parts:
这个过程可以看作将下面两条规则翻译成了 Lisp：第一条规则针对第一个表为空的情况，第二条规则处理非空表的情况——非空表是由两个部分构成的 `cons`：
For any list y, the empty list and y append to form
y.
对于任意表 `y`，空表与 `y` 拼接的结果是 `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.
Using the append procedure, we can answer questions such as
Find the append of (a b) and (c d).
对于任意 `u`、`v`、`y` 和 `z`，若 `v` 与 `y` 拼接得到 `z`，则 `(cons u v)` 与 `y` 拼接得到 `(cons u z)`。利用 `append` 过程，我们可以回答诸如“求 `(a b)` 与 `(c d)` 的拼接结果”之类的问题。
But the same two rules are also sufficient for answering the following sorts of
questions, which the procedure can’t answer:
Find a list y that appends with (a b) to produce (a
b c d).
Find all x and y that append to form (a b c d).
但这同样的两条规则也足以回答以下几类该过程无法回答的问题：找一个表 `y`，使它与 `(a b)` 拼接后得到 `(a b c d)`；找出所有拼接后得到 `(a b c d)` 的 `x` 和 `y`。
In a logic programming language, the programmer writes an append
“procedure” by stating the two rules about append given above. “How
to” knowledge is provided automatically by the interpreter to allow this
single pair of rules to be used to answer all three types of questions about
append.
在逻辑式程序设计语言中，程序员通过陈述上述关于 `append` 的两条规则来编写 `append` “过程”。“如何做”的知识由解释器自动提供，使得这单独一对规则就能用于回答有关 `append` 的全部三类问题。
Contemporary logic programming languages (including the one we implement here)
have substantial deficiencies, in that their general “how to” methods can
lead them into spurious infinite loops or other undesirable behavior. Logic
programming is an active field of research in computer
science.
当代逻辑式程序设计语言（包括我们在此实现的这种）存在相当明显的不足：其通用的“如何做”方法可能使它们陷入虚假的无限循环或其他不良行为。逻辑式程序设计是计算机科学中一个活跃的研究领域。
Earlier in this chapter we explored the technology of implementing interpreters
and described the elements that are essential to an interpreter for a Lisp-like
language (indeed, to an interpreter for any conventional language). Now we
will apply these ideas to discuss an interpreter for a logic programming
language. We call this language the
query language, because it is
very useful for retrieving information from data bases by formulating
在本章前面部分，我们探讨了实现解释器的技术，描述了 Lisp 式语言解释器（乃至任何传统语言解释器）所必需的基本要素。现在，我们将运用这些思想讨论一个逻辑式程序设计语言的解释器。我们将这种语言称为查询语言 (query language)，因为它非常适合通过构造
queries, or questions, expressed in the language. Even though the
query language is very different from Lisp, we will find it convenient to
describe the language in terms of the same general framework we have been using
all along: as a collection of primitive elements, together with means of
combination that enable us to combine simple elements to create more complex
elements and means of abstraction that enable us to regard complex elements as
single conceptual units. An interpreter for a logic programming language is
considerably more complex than an interpreter for a language like Lisp.
Nevertheless, we will see that our query-language interpreter contains many of
the same elements found in the interpreter of 4.1. In
particular, there will be an “eval” part that classifies expressions
according to type and an “apply” part that implements the language’s
abstraction mechanism (procedures in the case of Lisp, and
rules in
the case of logic programming). Also, a central role is played in the
implementation by a frame data structure, which determines the correspondence
between symbols and their associated values. One additional interesting aspect
of our query-language implementation is that we make substantial use of
streams, which were introduced in Chapter 3.
查询（即用该语言表达的问题）来从数据库中检索信息。尽管查询语言与 Lisp 差异很大，我们仍会发现沿用迄今为止一直使用的通用框架来描述它是方便的：将其视为一组基本元素，加上使我们能够把简单元素组合成更复杂元素的组合方法，以及使我们能够把复杂元素视为单一概念单元的抽象方法。逻辑式程序设计语言的解释器比 Lisp 这样的语言的解释器复杂得多。尽管如此，我们将看到，我们的查询语言解释器包含许多与 4.1 节解释器相同的元素。特别地，其中将有一个“eval”部分，按类型对表达式进行分类；还有一个“apply”部分，实现语言的抽象机制（在 Lisp 中是过程，在逻辑式程序设计中是规则）。此外，框架数据结构在实现中扮演着核心角色，它确定符号与其关联值之间的对应关系。我们的查询语言实现还有一个值得关注的方面：我们大量使用了第 3 章引入的流。
(define (append x y)
(if (null? x)
y
(cons (car x) (append (cdr x) y))))