|
在第 1 章中我们强调，计算机科学涉及的是命令式（如何做）知识，而数学涉及的是声明式（是什么）知识。确实，编程语言要求程序员以一种指示解决特定问题的逐步方法来表达知识。另一方面，高级语言作为语言实现的一部分，提供了大量方法论知识，将用户从关注指定计算将如何进行的无数细节中解放出来。
大多数编程语言（包括 Lisp）都是围绕计算数学函数的值来组织的。面向表达式的语言（如 Lisp、Fortran 和 Algol）利用了这样一个"双关"：描述函数值的表达式也可以被解释为计算该值的手段。正因为如此，大多数编程语言都强烈偏向于单向计算（具有明确定义输入和输出的计算）。然而，也有一些根本不同的编程语言放宽了这种偏向。我们在第 3.3.5 节看到了这样一个例子，其中的计算对象是算术约束。在约束系统中，计算的方向和顺序不那么明确；在执行计算时，系统必须提供比普通算术计算更详细的"如何做"知识。然而，这并不意味着用户完全免于提供命令式知识的责任。有许多约束网络实现了同一组约束，用户必须从数学上等价的一组网络中选择一个合适的网络来指定特定的计算。
第 4.3 节的非确定性程序求值器也偏离了编程是关于构造计算单向函数的算法的观点。在非确定性语言中，表达式可以有多个值，因此计算处理的是关系而非单值函数。逻辑编程通过将关系式编程视角与一种称为合一的强大的符号模式匹配相结合，扩展了这一思想。58
这种方法在可行时，可以成为编写程序的非常强大的方式。部分力量来自于这样一个事实：单个"是什么"事实可以用来解决多个本应具有不同"如何做"组成部分的不同问题。作为一个例子，考虑 append 操作，它接受两个列表作为参数，并将它们的元素合并成一个列表。在像 Lisp 这样的过程式语言中，我们可以像在第 2.2.1 节中那样，基于基本的列表构造器 cons 来定义 append：
(define (append x y)
(if (null? x)
y
(cons (car x) (append (cdr x) y))))
这个过程可以看作是以下两条规则到 Lisp 的翻译，第一条覆盖第一个列表为空的情况，第二条处理非空列表（即两个部分的 cons）的情况：
使用 append 过程，我们可以回答诸如以下的问题：
求 (a b) 和 (c d) 的 append。
但同样的两条规则也足以回答以下类型的问题，而过程无法回答这些问题：
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).
在逻辑编程语言中，程序员通过陈述上述关于 append 的两条规则来编写 append"过程"。"如何做"知识由解释器自动提供，使得这两条规则能够被用来回答所有三种类型的关于 append 的问题。60
当代的逻辑编程语言（包括我们这里实现的这种）存在重大缺陷，因为它们通用的"如何做"方法可能导致虚假的无穷循环或其他不良行为。逻辑编程是计算机科学中一个活跃的研究领域。61
在本章前面，我们探索了实现解释器的技术，描述了对于类 Lisp 语言的解释器（实际上，对于任何传统语言的解释器）至关重要的元素。现在我们将应用这些思想来讨论逻辑编程语言的解释器。我们将这种语言称为查询语言，因为它对于通过用该语言表述的查询（或问题）从数据库中检索信息非常有用。尽管查询语言与 Lisp 非常不同，但我们发现用我们一直使用的同一个通用框架来描述该语言是很方便的：即作为一个基本元素的集合，加上使我们能够组合简单元素以创建更复杂元素的组合手段，以及使我们能够将复杂元素视为单一概念单元的抽象手段。逻辑编程语言的解释器比像 Lisp 这样的语言的解释器要复杂得多。然而，我们将看到我们的查询语言解释器包含许多在第 4.1 节的解释器中也存在的相同元素。特别地，会有一个根据类型对表达式分类的"eval"部分，和一个实现语言抽象机制的"apply"部分（在 Lisp 中是过程，在逻辑编程中是规则）。此外，框架数据结构在实现中扮演着核心角色，它确定了符号与其关联值之间的对应关系。我们的查询语言实现另一个有趣方面是，我们大量使用了第 3 章中介绍的流。
逻辑编程在提供用于信息检索的数据库接口方面表现出色。我们将在本章中实现的查询语言正是设计用于这一目的。
为了说明查询系统的作用，我们将展示它如何被用来管理 Microshaft（波士顿地区一家蓬勃发展的科技公司）的人事记录数据库。该语言提供模式导向的人员信息访问，还可以利用通用规则进行逻辑推理。
Microshaft 的人事数据库包含关于公司人员的断言。以下是关于公司常驻计算机 wizard Ben Bitdiddle 的信息：
(address (Bitdiddle Ben) (Slumerville (Ridge Road) 10))
(job (Bitdiddle Ben) (computer wizard))
(salary (Bitdiddle Ben) 60000)
每个断言都是一个列表（这里是三元组），其元素本身也可以是列表。
作为常驻 wizard，Ben 负责公司的计算机部门，他管理着两名程序员和一名技术员。以下是他们的信息：
(address (Hacker Alyssa P) (Cambridge (Mass Ave) 78))
(job (Hacker Alyssa P) (computer programmer))
(salary (Hacker Alyssa P) 40000)
(supervisor (Hacker Alyssa P) (Bitdiddle Ben))
(address (Fect Cy D) (Cambridge (Ames Street) 3))
(job (Fect Cy D) (computer programmer))
(salary (Fect Cy D) 35000)
(supervisor (Fect Cy D) (Bitdiddle Ben))
(address (Tweakit Lem E) (Boston (Bay State Road) 22))
(job (Tweakit Lem E) (computer technician))
(salary (Tweakit Lem E) 25000)
(supervisor (Tweakit Lem E) (Bitdiddle Ben))
还有一名程序员实习生，由 Alyssa 管理：
(address (Reasoner Louis) (Slumerville (Pine Tree Road) 80))
(job (Reasoner Louis) (computer programmer trainee))
(salary (Reasoner Louis) 30000)
(supervisor (Reasoner Louis) (Hacker Alyssa P))
所有这些人员都在计算机部门，这是由他们工作描述中的第一个词 computer 指示的。
Ben 是一位高级雇员。他的主管就是公司的大老板本人：
(supervisor (Bitdiddle Ben) (Warbucks Oliver))
(address (Warbucks Oliver) (Swellesley (Top Heap Road)))
(job (Warbucks Oliver) (administration big wheel))
(salary (Warbucks Oliver) 150000)
除了 Ben 管理的计算机部门外，公司还有一个会计部门，由一名总会计师和他的助手组成：
(address (Scrooge Eben) (Weston (Shady Lane) 10))
(job (Scrooge Eben) (accounting chief accountant))
(salary (Scrooge Eben) 75000)
(supervisor (Scrooge Eben) (Warbucks Oliver))
(address (Cratchet Robert) (Allston (N Harvard Street) 16))
(job (Cratchet Robert) (accounting scrivener))
(salary (Cratchet Robert) 18000)
(supervisor (Cratchet Robert) (Scrooge Eben))
大老板还有一名秘书：
(address (Aull DeWitt) (Slumerville (Onion Square) 5))
(job (Aull DeWitt) (administration secretary))
(salary (Aull DeWitt) 25000)
(supervisor (Aull DeWitt) (Warbucks Oliver))
数据库还包含关于哪些工作可以由从事其他工作的人来完成的断言。例如，计算机 wizard 可以同时做计算机程序员和计算机技术员的工作：
(can-do-job (computer wizard) (computer programmer))
(can-do-job (computer wizard) (computer technician))
计算机程序员可以代替实习生：
(can-do-job (computer programmer)
(computer programmer trainee))
(can-do-job (administration secretary)
(administration big wheel))
查询语言允许用户通过在系统提示符下提出查询来从数据库中检索信息。例如，要找到所有计算机程序员，可以说
;;; 查询输入：
(job ?x (computer programmer))
系统将响应以下条目：
;;; 查询结果：
(job (Hacker Alyssa P) (computer programmer))
(job (Fect Cy D) (computer programmer))
输入查询指定我们正在寻找数据库中与某个模式匹配的条目。在这个例子中，该模式指定了由三个元素组成的条目，其中第一个是字面符号 job，第二个可以是任何东西，第三个是字面列表 (computer programmer)。可以作为匹配列表中第二个元素的"任何东西"由一个模式变量 ?x 指定。模式变量的一般形式是一个符号，被认为是变量的名称，前面带有一个问号。我们稍后会看到，为什么为模式变量指定名称而不仅仅是在模式中使用 ? 来表示"任何东西"是有用的。系统通过显示数据库中所有匹配指定模式的条目来响应一个简单查询。
一个模式可以有多个变量。例如，查询
(address ?x ?y)
将列出所有雇员的地址。
模式也可以没有变量，在这种情况下，查询只是确定该模式是否是数据库中的一个条目。如果是，就有一个匹配；如果不是，就没有匹配。
同一个模式变量可以在查询中出现多次，指定相同的"任何东西"必须出现在每个位置。这就是变量有名称的原因。例如，
(supervisor ?x ?x)
找出所有自我管理的人（尽管我们的示例数据库中没有这样的断言）。
The query
(job ?x (computer ?type))
匹配所有第三个元素是两元素列表且第一个元素为 computer 的工作条目：
(job (Bitdiddle Ben) (computer wizard))
(job (Hacker Alyssa P) (computer programmer))
(job (Fect Cy D) (computer programmer))
(job (Tweakit Lem E) (computer technician))
同样的模式不匹配
(job (Reasoner Louis) (computer programmer trainee))
因为条目中的第三个元素是一个三元素列表，而模式的第三个元素指定应该有两个元素。如果我们想要改变模式，使得第三个元素可以是任何以 computer 开头的列表，我们可以指定62
(job ?x (computer . ?type))
For example,
(computer . ?type)
匹配数据
(computer programmer trainee)
其中 ?type 为列表 (programmer trainee)。它也匹配数据
(computer programmer)
其中 ?type 为列表 (programmer)，并且匹配数据
(computer)
其中 ?type 为空列表 ()。
我们可以如下描述查询语言对简单查询的处理：
注意，如果模式没有变量，查询就简化为确定该模式是否在数据库中。如果是，那么空赋值（不给任何变量赋值）就使该模式对该数据库成立。
a. 所有由 Ben Bitdiddle 管理的人员；
b. 会计部门所有人员的姓名和工作；
c. 所有居住在 Slumerville 的人的姓名和地址。
简单查询构成了查询语言的基本操作。为了形成复合操作，查询语言提供了组合手段。查询语言之所以成为一种逻辑编程语言，一个原因就是其组合手段反映了用于形成逻辑表达式的组合手段：and、or 和 not。（这里的 and、or 和 not 不是 Lisp 的基本过程，而是内建在查询语言中的操作。）
(and (job ?person (computer programmer))
(address ?person ?where))
产生的输出是
(and (job (Hacker Alyssa P) (computer programmer))
(address (Hacker Alyssa P) (Cambridge (Mass Ave) 78)))
(and (job (Fect Cy D) (computer programmer))
(address (Fect Cy D) (Cambridge (Ames Street) 3)))
(and <query1> <query2> ... <queryn>)
被所有同时满足 <query1> ... <queryn> 的模式变量值集合所满足。
与简单查询一样，系统通过找出所有满足查询的模式变量赋值来处理复合查询，然后显示这些值的查询实例化。
(or (supervisor ?x (Bitdiddle Ben))
(supervisor ?x (Hacker Alyssa P)))
将找出所有由 Ben Bitdiddle 或 Alyssa P. Hacker 管理的雇员：
(or (supervisor (Hacker Alyssa P) (Bitdiddle Ben))
(supervisor (Hacker Alyssa P) (Hacker Alyssa P)))
(or (supervisor (Fect Cy D) (Bitdiddle Ben))
(supervisor (Fect Cy D) (Hacker Alyssa P)))
(or (supervisor (Tweakit Lem E) (Bitdiddle Ben))
(supervisor (Tweakit Lem E) (Hacker Alyssa P)))
(or (supervisor (Reasoner Louis) (Bitdiddle Ben))
(supervisor (Reasoner Louis) (Hacker Alyssa P)))
一般地，
(or <query1> <query2> ... <queryn>)
被那些满足至少一个 <query1> ... <queryn> 的模式变量的所有值集合所满足。
(and (supervisor ?x (Bitdiddle Ben))
(not (job ?x (computer programmer))))
查找所有由 Ben Bitdiddle 管理但不是计算机程序员的员工。一般地，
(not <query1>)
被那些不满足 <query1> 的模式变量的所有赋值所满足。63
最后的组合形式称为 lisp-value。当 lisp-value 是一个模式的第一个元素时，它指定下一个元素是一个 Lisp 谓词，将应用于其余（已实例化的）元素作为参数。一般地，
(lisp-value <predicate> <arg1> ... <argn>)
将被那些使得应用于实例化后的 <arg1> ... <argn> 的 <predicate> 为真的模式变量的赋值所满足。例如，要找出所有薪水超过 $30,000 的人，我们可以写64
(and (salary ?person ?amount)
(lisp-value > ?amount 30000))
a. 所有被 Ben Bitdiddle 管理的人员的姓名连同他们的地址；
b. 所有薪水低于 Ben Bitdiddle 的人员，连同他们的薪水和 Ben Bitdiddle 的薪水；
c. 所有被不在计算机部门的人管理的人员，连同管理者的姓名和工作。
除了基本查询和复合查询之外，查询语言还提供了抽象查询的手段。这些手段由规则提供。例如，规则
(rule (lives-near ?person-1 ?person-2)
(and (address ?person-1 (?town . ?rest-1))
(address ?person-2 (?town . ?rest-2))
(not (same ?person-1 ?person-2))))
指定如果两个人住在同一个城镇，他们就互为近邻。最后的 not 子句防止该规则说所有人都住在自己附近。same 关系由一条非常简单的规则定义：65
下面的规则声明，如果一个人管理着某个人，而后者又管理着其他人，那么这个人就是组织中的"大人物"（wheel）：
(rule (wheel ?person)
(and (supervisor ?middle-manager ?person)
(supervisor ?x ?middle-manager)))
规则的一般形式是
(rule <conclusion> <body>)
其中 <conclusion> 是一个模式，<body> 是任意查询。66 我们可以将规则视为代表了一个大的（甚至是无穷的）断言集合，即规则结论的所有实例化，其中变量赋值满足规则主体。当我们描述简单查询（模式）时，我们说如果实例化的模式在数据库中，则变量赋值满足该模式。但模式不必作为断言显式地位于数据库中。它可以是一个由规则隐含的隐式断言。例如，查询
(lives-near ?x (Bitdiddle Ben))
产生的结果是
(lives-near (Reasoner Louis) (Bitdiddle Ben))
(lives-near (Aull DeWitt) (Bitdiddle Ben))
要找出所有住在 Ben Bitdiddle 附近的计算机程序员，我们可以问
(and (job ?x (computer programmer))
(lives-near ?x (Bitdiddle Ben)))
与复合过程的情况一样，规则可以作为其他规则的一部分使用（正如我们上面在 lives-near 规则中看到的），甚至可以递归定义。例如，规则
(rule (outranked-by ?staff-person ?boss)
(or (supervisor ?staff-person ?boss)
(and (supervisor ?staff-person ?middle-manager)
(outranked-by ?middle-manager ?boss))))
说，如果在组织中，一个老板是一个职员的上级，或者（递归地）该职员的上级被该老板越级，那么该职员就被该老板越级（outranked）。
练习 4.57. 定义一个规则，说明如果 person 1 与 person 2 做相同的工作，或者做 person 1 工作的人也能做 person 2 的工作，并且 person 1 和 person 2 不是同一个人，则 person 1 可以替换 person 2。使用你的规则，给出找出以下内容的查询：
a. 所有可以替换 Cy D. Fect 的人；
b. 所有可以替换某个薪资高于他们的人，连同两个薪资。
练习 4.58. 定义一个规则，说明如果一个人在某个部门工作，但没有在该部门工作的主管，那么该人就是该部门的"大人物"（big shot）。
练习 4.59. Ben Bitdiddle 已经错过了太多的会议。担心他忘记会议的习惯可能会让他丢掉工作，Ben 决定做点什么。他通过断言以下内容，将公司的所有周会议添加到 Microshaft 数据库中：
(meeting accounting (Monday 9am))
(meeting administration (Monday 10am))
(meeting computer (Wednesday 3pm))
(meeting administration (Friday 1pm))
以上的每个断言都是针对整个部门的会议。Ben 还添加了一个涵盖所有部门的全公司会议的条目。公司的所有雇员都参加这个会议。
(meeting whole-company (Wednesday 4pm))
a. 在星期五早上，Ben 想要查询数据库获取那天发生的所有会议。他应该使用什么查询？
b. Alyssa P. Hacker 对此不以为意。她认为能够通过指定自己的姓名来查询她的会议要有用得多。所以她设计了一条规则，说一个人的会议包括所有的 whole-company 会议加上该人所在部门的所有会议。填写 Alyssa 规则的主体。
(rule (meeting-time ?person ?day-and-time)
<rule-body>)
c. Alyssa 在星期三早上到达公司，想知道她那天必须参加哪些会议。在定义了上述规则后，她应该使用什么查询来找出这些信息？
(lives-near ?person (Hacker Alyssa P))
Alyssa P. Hacker 能够找到住在她附近的人，她可以和他们一起拼车上班。另一方面，当她试图通过查询来找出所有互为近邻的人对时
(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 可以由以下两条规则来刻画：
为了在查询语言中表达这一点，我们为一个关系定义两条规则
(append-to-form x y z)
我们可以将其解释为"x 和 y append 形成 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 的。
有了这两条规则，我们可以构造计算两个列表的 append 的查询：
;;; 查询输入：
(append-to-form (a b) (c d) ?z)
;;; 查询结果：
(append-to-form (a b) (c d) (a b c d))
更引人注目的是，我们可以使用同样的规则来问这样一个问题："哪个列表在与 (a b) append 后得到 (a b c d)？"这可以如下完成：
;;; 查询输入：
(append-to-form (a b) ?y (a b c d))
;;; 查询结果：
(append-to-form (a b) (c d) (a b c d))
我们还可以要求找出所有 append 形成 (a b c d) 的列表对：
;;; 查询输入：
(append-to-form ?x ?y (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-to-form (a b c d) () (a b c d))
查询系统在使用规则演绎出上述查询的答案时，可能显得相当智能。实际上，正如我们将在下一节看到的，系统在展开规则时遵循着一个确定的算法。不幸的是，尽管系统在 append 的情况下表现出色，但通用方法在更复杂的情况下可能会失效，正如我们将在 4.4.3 节中看到的。
练习 4.61. 下面的规则实现了一个 next-to 关系，用于找出列表中的相邻元素：
(rule (?x next-to ?y in (?x ?y . ?u)))
(rule (?x next-to ?y in (?v . ?z))
(?x next-to ?y in ?z))
以下查询的响应将是什么？
(?x next-to ?y in (1 (2 3) 4))
(?x next-to 1 in (2 1 3 1))
练习 4.62. 定义规则来实现练习 2.17 的 last-pair 操作，该操作返回一个包含非空列表最后一个元素的列表。在诸如 (last-pair (3) ?x)、(last-pair (1 2 3) ?x) 和 (last-pair (2 ?x) (3)) 等查询上检查你的规则。你的规则在诸如 (last-pair ?x (3)) 这样的查询上是否工作正确？
练习 4.63. 以下数据库（参见创世记第4章）追溯了 Ada 的后代通过该隐（Cain）回到亚当（Adam）的族谱：
(son Adam Cain)
(son Cain Enoch)
(son Enoch Irad)
(son Irad Mehujael)
(son Mehujael Methushael)
(son Methushael Lamech)
(wife Lamech Ada)
(son Ada Jabal)
(son Ada Jubal)
制定诸如"如果 S 是 F 的儿子，且 F 是 G 的儿子，那么 S 是 G 的孙子"和"如果 W 是 M 的妻子，且 S 是 W 的儿子，那么 S 是 M 的儿子"（这在圣经时代可能比今天更真实）的规则，使查询系统能够找到该隐（Cain）的孙子、拉麦（Lamech）的儿子们、玛土撒利（Methushael）的孙子们。 （参见练习 4.69 中用于演绎更复杂关系的规则。）
在 4.4.4 节中，我们将给出查询解释器作为一个过程集合的实现。在本节中，我们给出一个概述，解释系统独立于底层实现细节的总体结构。在描述了解释器的实现之后，我们将能够理解它的一些局限性，以及查询语言的逻辑操作与数学逻辑的操作之间的一些微妙差异。
应该很明显，查询求值器必须执行某种搜索，以便将查询与数据库中的事实和规则进行匹配。实现这一目的的一种方法是将查询系统实现为一个非确定性程序，使用 4.3 节的 amb 求值器（参见练习 4.78）。另一种可能性是借助流来管理搜索。我们的实现采用了第二种方法。
查询系统围绕两个称为模式匹配和合一的核心操作组织。我们首先描述模式匹配，并解释该操作如何与以框架流形式组织的信息一起，使我们能够实现简单查询和复合查询。接下来讨论合一，这是实现规则所需的模式匹配的推广。最后，我们展示整个查询解释器如何通过一个过程组合在一起，该过程对表达式进行分类的方式类似于 eval 对 4.1 节中描述的解释器的表达式进行分类的方式。
模式匹配器是一个测试某个数据是否符合指定模式的程序。例如，数据列表 ((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 的列表。
查询系统使用的模式匹配器以模式、数据和一个指定了各种模式变量绑定的框架作为输入。它检查数据是否以与框架中已有绑定一致的方式匹配模式。如果是，它返回通过匹配可能确定的任何绑定扩充后的给定框架。否则，它指示匹配失败。
例如，使用模式 (?x ?y ?x) 匹配 (a b a)，给定一个空框架，将返回一个指定 ?x 绑定到 a、?y 绑定到 b 的框架。使用相同的模式、相同的数据和一个指定 ?y 绑定到 a 的框架进行尝试将会失败。使用相同的模式、相同的数据以及 ?y 绑定到 b 且 ?x 未绑定的框架进行尝试，将返回由 ?x 到 a 的绑定扩充后的给定框架。
模式匹配器是处理不涉及规则的简单查询所需的全部机制。例如，处理查询
(job ?x (computer programmer))
我们扫描数据库中的所有断言，并选择那些相对于初始空框架与模式匹配的断言。对于我们找到的每个匹配，我们使用匹配返回的框架来实例化模式，为 ?x 提供值。
模式对框架的测试是通过使用流来组织的。给定一个框架，匹配过程逐个遍历数据库条目。对于每个数据库条目，匹配器要么生成一个表示匹配失败的特殊符号，要么生成框架的一个扩充。所有数据库条目的结果被收集到一个流中，该流通过一个过滤器来剔除失败的匹配。结果是一个流，包含通过匹配数据库中某个断言来扩展给定框架的所有框架。67
在我们的系统中，查询接受一个框架输入流，并对流中的每个框架执行上述匹配操作，如图 4.4 所示。也就是说，对于输入流中的每个框架，查询生成一个新的流，该流包含通过匹配数据库中断言对该框架的所有扩展。所有这些流然后被组合成一个巨大的流，其中包含输入流中每个框架的所有可能扩展。这个流就是查询的输出。
|
|
为了回答一个简单查询，我们使用一个输入流仅包含单个空框架的查询。结果输出流包含空框架的所有扩展（即我们查询的所有答案）。然后使用这个框架流生成原始查询模式的副本流，其中变量被每个框架中的值实例化，这就是最终被打印的流。
框架流实现的真正优雅之处在我们处理复合查询时显现出来。复合查询的处理利用了我们的匹配器要求匹配与指定框架一致的能力。例如，处理两个查询的 and，例如
(and (can-do-job ?x (computer programmer trainee))
(job ?person ?x))
（非正式地说，"找出所有能做计算机程序员实习生工作的人"），我们首先找出所有匹配模式
(can-do-job ?x (computer programmer trainee))
这会产生一个流，其中每个框架都包含 ?x 的一个绑定。然后对流中的每个框架，我们找出所有以与 ?x 的给定绑定一致的方式匹配的模式
(job ?person ?x)
条目。每个这样的匹配将产生一个包含 ?x 和 ?person 绑定的框架。两个查询的 and 可以视为两个组件查询的串联组合，如图 4.5 所示。通过第一个查询过滤器的框架再被第二个查询过滤和进一步扩展。
|
图 4.6 展示了计算两个查询的 or 的类似方法，即两个组件查询的并行组合。输入框架流被每个查询分别扩展。然后两个结果流被合并，产生最终的输出流。
|
即使从这个高层描述中，也很明显复合查询的处理可能很慢。例如，由于一个查询可能对每个输入框架产生多个输出框架，而 and 中的每个查询从其前一个查询获取输入框架，一个 and 查询在最坏情况下可能不得不执行指数于查询数量的匹配次数（参见练习 4.76）。68 尽管只处理简单查询的系统相当实用，但处理复杂查询极为困难。69
从框架流的视角来看，某个查询的 not 充当了一个过滤器，移除所有能使该查询被满足的框架。例如，给定模式
(not (job ?x (computer programmer)))
我们尝试为输入流中的每个框架产生满足 (job ?x (computer programmer)) 的扩展框架。我们从输入流中移除所有存在此类扩展的框架。结果是一个仅由那些 ?x 的绑定不满足 (job ?x (computer programmer)) 的框架组成的流。例如，在处理查询
(and (supervisor ?x ?y)
(not (job ?x (computer programmer))))
第一个子句将生成带有 ?x 和 ?y 绑定的框架。然后 not 子句将通过移除所有其中 ?x 的绑定满足 ?x 是计算机程序员这一限制的框架来过滤这些框架。70
lisp-value 特殊形式被实现为框架流上的类似过滤器。我们使用流中的每个框架来实例化模式中的任何变量，然后应用 Lisp 谓词。我们从输入流中移除所有谓词失败的框架。
为了处理查询语言中的规则，我们必须能够找到结论与给定查询模式匹配的规则。规则结论类似于断言，不同之处在于它们可以包含变量，因此我们需要一种模式匹配的推广——称为合一——其中"模式"和"数据"都可能包含变量。
合一器接受两个模式（每个都包含常量和变量），并确定是否可能给变量赋值使得两个模式相等。如果是，它返回一个包含这些绑定的框架。例如，合一 (?x a ?y) 和 (?y ?z a) 将指定一个框架，其中 ?x、?y 和 ?z 都必须绑定到 a。另一方面，合一 (?x ?y a) 和 (?x b ?y) 将失败，因为没有 ?y 的值可以使两个模式相等。（要使模式的第二个元素相等，?y 必须是 b；然而，要使第三个元素相等，?y 必须是 a。）查询系统中使用的合一器，与模式匹配器一样，接受一个框架作为输入，并执行与该框架一致的合一。
合一算法是查询系统在技术上最困难的部分。对于复杂模式，执行合一可能看起来需要演绎推理。例如，要合一 (?x ?x) 和 ((a ?y c) (a b ?z))，算法必须推断出 ?x 应该是 (a b c)，?y 应该是 b，?z 应该是 c。我们可以把这个过程看作是求解模式组件之间的一组方程。一般来说，这些是联立方程，可能需要大量的操作才能求解。71 例如，合一 (?x ?x) 和 ((a ?y c) (a b ?z)) 可以看作是指定联立方程
?x = (a ?y c)
?x = (a b ?z)
这些方程意味着
(a ?y c) = (a b ?z)
这又意味着
a = a, ?y = b, c = ?z,
因此
?x = (a b c)
在成功的模式匹配中，所有模式变量都被绑定，并且它们绑定到的值只包含常量。我们到目前为止看到的所有合一例子也是如此。然而，一般来说，成功的合一可能不完全确定变量值；一些变量可能保持未绑定，而其他变量可能被绑定到包含变量的值。
考虑合一 (?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 将引用这个值。72
合一是查询系统中利用规则进行推理的组件的关键。要了解这是如何实现的，考虑处理一个涉及应用规则的查询，例如
(lives-near ?x (Hacker Alyssa P))
要处理这个查询，我们首先使用上述的普通模式匹配过程来查看数据库中是否有任何断言匹配这个模式。（在这种情况下不会有任何匹配，因为我们的数据库不包含关于谁住在谁附近的直接断言。）下一步是尝试将查询模式与每条规则的结论进行合一。我们发现该模式与规则结论合一
(rule (lives-near ?person-1 ?person-2)
(and (address ?person-1 (?town . ?rest-1))
(address ?person-2 (?town . ?rest-2))
(not (same ?person-1 ?person-2))))
结果得到一个框架，它指定 ?person-2 绑定到 (Hacker Alyssa P)，并且 ?x 应该绑定到（与 ?person-1 相同）的值。现在，相对于这个框架，我们对规则主体给出的复合查询进行求值。成功的匹配将通过提供 ?person-1 的绑定来扩展这个框架，从而提供 ?x 的值，我们可以用它来实例化原始查询模式。
一般来说，查询求值器在尝试于一个指定了某些模式变量绑定的框架中建立一个查询模式时，使用以下方法应用规则：
请注意这与 Lisp 的 eval/apply 求值器中应用过程的方法有多么相似：
这两个求值器之间的相似性不足为奇。正如过程定义是 Lisp 中的抽象手段，规则定义是查询语言中的抽象手段。在每种情况下，我们通过创建适当的绑定并相对于这些绑定求值规则或过程体来展开抽象。
我们在本节前面看到了如何在没有规则的情况下求值简单查询。现在我们已经看到了如何应用规则，我们可以描述如何同时使用规则和断言来求值简单查询。
给定查询模式和一个框架流，我们为输入流中的每个框架产生两个流：
将这两个流追加在一起产生一个流，该流包含给定模式可以与原始框架一致地得到满足的所有方式。这些流（每个输入框架对应一个）现在全部组合起来形成一个大的流，因此它包含了原始输入流中任何框架可以被扩展以产生与给定模式匹配的所有方式。
尽管底层匹配操作复杂，但系统的组织方式与任何语言的求值器非常相似。协调匹配操作的过程称为 qeval，它扮演的角色类似于 Lisp 的 eval 过程。Qeval 接受一个查询和一个框架流作为输入。它的输出是一个框架流，对应于对查询模式的成功匹配，这些匹配扩展了输入流中的某些框架，如图 4.4 所示。与 eval 一样，qeval 对不同类型的表达式（查询）进行分类，并分派到相应的过程。每种特殊形式（and、or、not 和 lisp-value）都有一个过程，简单查询也有一个过程。
驱动循环类似于本章其他求值器的 driver-loop 过程，它从终端读取查询。对于每个查询，它使用查询和一个仅包含单个空框架的流调用 qeval。这将产生所有可能匹配的流（空框架的所有可能扩展）。对于结果流中的每个框架，它使用框架中找到的变量值实例化原始查询。然后打印这个实例化查询的流。74
驱动还检查特殊命令 assert!，该命令表明输入不是查询，而是要添加到数据库中的断言或规则。例如，
(assert! (job (Bitdiddle Ben) (computer wizard)))
(assert! (rule (wheel ?person)
(and (supervisor ?middle-manager ?person)
(supervisor ?x ?middle-manager))))
查询语言中使用的组合手段最初看起来可能与数学逻辑中的 and、or 和 not 操作相同，而查询语言规则的应用实际上是通过一种合法的推理方法完成的。75 然而，将查询语言等同于数学逻辑并不真正有效，因为查询语言提供了一种控制结构，它过程式地解释逻辑语句。我们通常可以利用这种控制结构。例如，要找出所有程序员的主管，我们可以用两种逻辑上等价的形式中的任何一种来构造查询：
(and (job ?x (computer programmer))
(supervisor ?x ?y))
or
(and (supervisor ?x ?y)
(job ?x (computer programmer)))
如果一家公司的主管比程序员多得多（通常情况），最好使用第一种形式而不是第二种，因为对于 and 的第一个子句产生的每个中间结果（框架），都必须扫描数据库。
逻辑编程的目标是向程序员提供将计算问题分解为两个独立问题的技术："什么"要被计算，以及"如何"进行计算。这是通过选择数学逻辑的一个子集来实现的，该子集强大到足以描述任何人们可能想要计算的东西，但又足够弱以具有可控的过程式解释。这里的意图是，一方面，用逻辑编程语言指定的程序应该是一个可以由计算机执行的有效程序。控制（"如何"计算）是通过使用语言的求值顺序来实现的。我们应该能够安排子句的顺序以及每个子句内子目标的顺序，使得计算以一种被认为有效和高效的顺序进行。同时，我们应该能够将计算的结果（"什么"被计算）视为逻辑定律的一个简单推论。
我们的查询语言可以被视为正是数学逻辑的这样一个可过程式解释的子集。一个断言代表一个简单事实（原子命题）。一个规则代表一个蕴含，即规则结论在规则主体成立的那些情况下成立。规则具有自然的程序式解释：要建立规则的结论，先建立规则的主体。因此，规则指定了计算。然而，由于规则也可以被视为数学逻辑的语句，我们可以通过断言完全在数学逻辑内部工作也能得到相同的结果，来论证由逻辑程序完成的任何"推理"的合理性。76
逻辑程序的程序式解释的一个后果是，有可能构造出解决某些问题时效率极低的程序。一种极端的低效情况是系统在进行演绎时陷入无穷循环。作为一个简单的例子，假设我们正在建立一个著名婚姻的数据库，包括
(assert! (married Minnie Mickey))
如果我们现在问
(married Mickey ?who)
我们得不到任何响应，因为系统不知道如果 A 与 B 结婚，那么 B 也与 A 结婚。所以我们断言规则
(assert! (rule (married ?x ?y)
(married ?y ?x)))
并再次查询
(married Mickey ?who)
不幸的是，这将驱使系统进入无穷循环，过程如下：
系统现在处于无穷循环中。实际上，系统是否会在陷入循环之前找到简单答案 (married Minnie Mickey)，取决于关于系统检查数据库中条目顺序的实现细节。这是一个关于可能发生的循环类型的非常简单的例子。相互关联的规则集合可能导致更难预料的循环，而循环的出现可能取决于 and 中子句的顺序（参见练习 4.64）或关于系统处理查询顺序的低层细节。77
查询系统中的另一个怪癖涉及 not。给定 4.4.1 节的数据库，考虑以下两个查询：
(and (supervisor ?x ?y)
(not (job ?x (computer programmer))))
(and (not (job ?x (computer programmer)))
(supervisor ?x ?y))
这两个查询不会产生相同的结果。第一个查询首先找出数据库中所有匹配 (supervisor ?x ?y) 的条目，然后通过移除那些 ?x 的值满足 (job ?x (computer programmer)) 的框架来过滤结果框架。第二个查询首先过滤输入的框架，移除那些可以满足 (job ?x (computer programmer)) 的框架。由于唯一的输入框架是空的，它检查数据库以查看是否有任何模式满足 (job ?x (computer programmer))。由于通常存在这种形式的条目，not 子句过滤掉空框架，返回一个空的框架流。因此，整个复合查询返回一个空流。
问题在于我们的 not 实现实际上是用来对变量的值进行过滤的。如果 not 子句在处理时使用的框架中某些变量保持未绑定状态（如上例中的 ?x），系统将产生意外结果。类似的问题也出现在使用 lisp-value 时——如果某些参数未绑定，Lisp 谓词就无法工作。参见练习 4.77。
查询语言的 not 与数学逻辑的 not 还有更严重的区别。在逻辑中，我们将语句"非 P"解释为 P 不为真。然而，在查询系统中，"非 P"意味着 P 不能从数据库中的知识演绎出来。例如，给定 4.4.1 节的人事数据库，系统会高兴地演绎出各种 not 语句，例如 Ben Bitdiddle 不是棒球爱好者、外面没有下雨，以及 2 + 2 不等于 4。78 换句话说，逻辑编程语言中的 not 反映了所谓的封闭世界假设，即所有相关信息都已包含在数据库中。79
练习 4.64. Louis Reasoner 错误地从数据库中删除了 outranked-by 规则（4.4.1 节）。当他意识到这一点时，他迅速重新安装了它。不幸的是，他对规则做了一个小改动，输入为
(rule (outranked-by ?staff-person ?boss)
(or (supervisor ?staff-person ?boss)
(and (outranked-by ?middle-manager ?boss)
(supervisor ?staff-person ?middle-manager))))
就在 Louis 将这些信息输入系统后，DeWitt Aull 前来查询谁越级了 Ben Bitdiddle。他发出查询
(outranked-by (Bitdiddle Ben) ?who)
在回答之后，系统进入了无穷循环。请解释原因。
练习 4.65. Cy D. Fect 期待着他有一天能在组织中晋升，他发出了一个找出所有大人物（wheel）的查询（使用 4.4.1 节的 wheel 规则）：
(wheel ?who)
令他惊讶的是，系统响应
;;; 查询结果：
(wheel (Warbucks Oliver))
(wheel (Bitdiddle Ben))
(wheel (Warbucks Oliver))
(wheel (Warbucks Oliver))
(wheel (Warbucks Oliver))
为什么 Oliver Warbucks 被列出了四次？
练习 4.66. Ben 一直在扩展查询系统以提供关于公司的统计信息。例如，要找出所有计算机程序员的总薪资，我们可以说
(sum ?amount
(and (job ?x (computer programmer))
(salary ?x ?amount)))
一般来说，Ben 的新系统允许以下形式的表达式
(accumulation-function <variable>
<query pattern>)
其中 accumulation-function 可以是 sum、average 或 maximum 之类的东西。Ben 认为实现这个应该很容易。他只需将查询模式喂给 qeval，这将产生一个框架流。然后他通过一个映射函数传递这个流，该函数从流中的每个框架中提取指定变量的值，并将结果值流喂给累积函数。就在 Ben 完成实现并准备尝试时，Cy 走过来，他还在为练习 4.65 中的 wheel 查询结果感到困惑。当 Cy 向 Ben 展示系统的响应时，Ben 呻吟道："哦，不，我简单的累积方案行不通！"
Ben 刚刚意识到了什么？概述他可以用什么方法来挽救局面。
练习 4.67. 设计一种在查询系统中安装循环检测器的方法，以避免文中和练习 4.64 中演示的那种简单循环。总体思路是系统应该维护其当前演绎链的某种历史记录，并且不应该开始处理它已经在处理的查询。描述这个历史记录中包含哪种信息（模式和框架），以及应该如何进行检查。（在你学习了 4.4.4 节中查询系统实现的细节之后，你可能想修改系统以包含你的循环检测器。）
练习 4.68. 定义规则来实现练习 2.18 的 reverse 操作，该操作返回一个包含给定列表相同元素但逆序排列的列表。（提示：使用 append-to-form。）你的规则能否同时回答 (reverse (1 2 3) ?x) 和 (reverse ?x (1 2 3))？
练习 4.69. 从你在练习 4.63 中制定的数据库和规则开始，设计一个规则来为孙子关系添加"great"前缀。这应该使系统能够推断出 Irad 是 Adam 的曾孙，或者 Jabal 和 Jubal 是 Adam 的第五代孙。（提示：将关于 Irad 的事实表示为 ((great grandson) Adam Irad)。编写判断一个列表是否以 grandson 结尾的规则。利用这个来表达一个规则，允许推导出关系 ((great . ?rel) ?x ?y)，其中 ?rel 是一个以 grandson 结尾的列表。）在诸如 ((great grandson) ?g ?ggs) 和 (?relationship Adam Irad) 这样的查询上检查你的规则。
4.4.2 节描述了查询系统如何工作。现在我们通过呈现系统的完整实现来填充细节。
查询系统的驱动循环重复读取输入表达式。如果表达式是要添加到数据库的规则或断言，则添加该信息。否则假设该表达式是一个查询。驱动将这个查询连同由一个空框架组成的初始框架流传递给求值器 qeval。求值的结果是一个框架流，通过使用在数据库中找到的变量值满足查询来生成。这些框架用于形成一个新的流，由原始查询的副本组成，其中变量被框架流提供的值实例化，这个最终的流被打印在终端上：
(define input-prompt ";;; Query input:")
(define output-prompt ";;; Query results:")
(define (query-driver-loop)
(prompt-for-input input-prompt)
(let ((q (query-syntax-process (read))))
(cond ((assertion-to-be-added? q)
(add-rule-or-assertion! (add-assertion-body q))
(newline)
(display "Assertion added to data base.")
(query-driver-loop))
(else
(newline)
(display output-prompt)
(display-stream
(stream-map
(lambda (frame)
(instantiate q
frame
(lambda (v f)
(contract-question-mark v))))
(qeval q (singleton-stream '()))))
(query-driver-loop)))))
这里，与本章其他求值器中一样，我们对查询语言的表达式使用抽象语法。表达式语法的实现，包括谓词 assertion-to-be-added? 和选择器 add-assertion-body，在 4.4.4.7 节中给出。Add-rule-or-assertion! 在 4.4.4.5 节中定义。
在对输入表达式进行任何处理之前，驱动循环在语法上将其转换为一种使处理更高效的形式。这涉及改变模式变量的表示。当查询被实例化时，任何保持未绑定的变量会在打印前转换回输入表示形式。这些转换由两个过程 query-syntax-process 和 contract-question-mark（4.4.4.7 节）执行。
要实例化一个表达式，我们复制它，将表达式中的任何变量替换为它们在给定框架中的值。值本身也被实例化，因为它们可能包含变量（例如，如果 exp 中的 ?x 由于合一被绑定到 ?y，而 ?y 又被绑定到 5）。如果变量无法实例化时要采取的动作由 instantiate 的过程参数给出。
(define (instantiate exp frame unbound-var-handler)
(define (copy exp)
(cond ((var? exp)
(let ((binding (binding-in-frame exp frame)))
(if binding
(copy (binding-value binding))
(unbound-var-handler exp frame))))
((pair? exp)
(cons (copy (car exp)) (copy (cdr exp))))
(else exp)))
(copy exp))
操作绑定的过程在 4.4.4.8 节中定义。
由 query-driver-loop 调用的 qeval 过程是查询系统的基本求值器。它以查询和框架流作为输入，并返回扩展框架的流。它通过使用 get 和 put 的数据导向分派来识别特殊形式，正如我们在第 2 章中实现通用操作时所做的那样。任何未被识别为特殊形式的查询都被假定为简单查询，由 simple-query 处理。
(define (qeval query frame-stream)
(let ((qproc (get (type query) 'qeval)))
(if qproc
(qproc (contents query) frame-stream)
(simple-query query frame-stream))))
Type 和 目录（在 4.4.4.7 节中定义）实现了特殊形式的抽象语法。
simple-query 过程处理简单查询。它接受一个简单查询（一个模式）和一个框架流作为参数，并返回通过将每个框架扩展为查询的所有数据库匹配而形成的流。
(define (simple-query query-pattern frame-stream)
(stream-flatmap
(lambda (frame)
(stream-append-delayed
(find-assertions query-pattern frame)
(delay (apply-rules query-pattern frame))))
frame-stream))
对于输入流中的每个框架，我们使用 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 查询通过 conjoin 过程处理，如图 4.5 所示。Conjoin 接受合取项和框架流作为输入，返回扩展框架的流。首先，conjoin 处理框架流，找出满足合取中第一个查询的所有可能框架扩展的流。然后，使用这个作为新的框架流，它递归地将 conjoin 应用于其余的查询。
(define (conjoin conjuncts frame-stream)
(if (empty-conjunction? conjuncts)
frame-stream
(conjoin (rest-conjuncts conjuncts)
(qeval (first-conjunct conjuncts)
frame-stream))))
The expression
(put 'and 'qeval conjoin)
当遇到 and 形式时，设置 qeval 分派到 conjoin。
Or 查询的处理类似，如图 4.6 所示。or 的各种析取项的输出流被分别计算，并使用 4.4.4.6 节的 interleave-delayed 过程合并。（参见练习 4.71 和 4.72。）
(define (disjoin disjuncts frame-stream)
(if (empty-disjunction? disjuncts)
the-empty-stream
(interleave-delayed
(qeval (first-disjunct disjuncts) frame-stream)
(delay (disjoin (rest-disjuncts disjuncts)
frame-stream)))))
(put 'or 'qeval disjoin)
合取项和析取项语法的谓词和选择器在 4.4.4.7 节中给出。
Not 由 4.4.2 节概述的方法处理。我们尝试扩展输入流中的每个框架以满足被否定的查询，并且仅当框架不能被扩展时才将其包含在输出流中。
(define (negate operands frame-stream)
(stream-flatmap
(lambda (frame)
(if (stream-null? (qeval (negated-query operands)
(singleton-stream frame)))
(singleton-stream frame)
the-empty-stream))
frame-stream))
(put 'not 'qeval negate)
Lisp-value 是一个类似于 not 的过滤器。流中的每个框架用于实例化模式中的变量，然后应用指定的谓词，谓词返回 false 的框架被从输入流中过滤掉。如果有未绑定的模式变量，则会产生错误。
(define (lisp-value call frame-stream)
(stream-flatmap
(lambda (frame)
(if (execute
(instantiate
call
frame
(lambda (v f)
(error "Unknown pat var -- LISP-VALUE" v))))
(singleton-stream frame)
the-empty-stream))
frame-stream))
(put 'lisp-value 'qeval lisp-value)
Execute 将谓词应用于参数，它必须 eval 谓词表达式以获取要应用的过程。但是，它不能求值参数，因为它们已经是实际参数，而不是求值（在 Lisp 中）会产生参数的表达式。注意 execute 是使用底层 Lisp 系统的 eval 和 apply 实现的。
(define (execute exp)
(apply (eval (predicate exp) user-initial-environment)
(args exp)))
always-true 特殊形式提供了一个总是被满足的查询。它忽略其内容（通常为空），仅传递输入流中的所有框架。Always-true 被 rule-body 选择器（4.4.4.7 节）用于为没有定义主体的规则提供主体（即结论总是被满足的规则）。
(define (always-true ignore frame-stream) frame-stream)
(put 'always-true 'qeval always-true)
定义 not 和 lisp-value 语法的选择器在 4.4.4.7 节中给出。
Find-assertions 由 simple-query（4.4.4.2 节）调用，接受一个模式和一个框架作为输入。它返回一个框架流，每个框架通过给定模式与数据库的匹配来扩展给定的框架。它使用 fetch-assertions（4.4.4.5 节）获取数据库中所有应该与模式和框架进行匹配检查的断言流。这里使用 fetch-assertions 的原因是我们通常可以应用简单的测试，从成功匹配的候选池中消除数据库中的许多条目。如果我们去掉 fetch-assertions 而简单地检查数据库中所有断言的流，系统仍然可以工作，但计算效率会降低，因为我们需要进行更多的匹配器调用。
(define (find-assertions pattern frame)
(stream-flatmap (lambda (datum)
(check-an-assertion datum pattern frame))
(fetch-assertions pattern frame)))
Check-an-assertion 接受模式、数据对象（断言）和框架作为参数，如果匹配成功返回包含扩展框架的单元素流，否则返回 the-empty-stream。
(define (check-an-assertion assertion query-pat query-frame)
(let ((match-result
(pattern-match query-pat assertion query-frame)))
(if (eq? match-result 'failed)
the-empty-stream
(singleton-stream match-result))))
基本的模式匹配器返回符号 failed 或给定框架的扩展。匹配器的基本思想是逐个元素地将模式与数据进行比较，累积模式变量的绑定。如果模式和数据对象相同，匹配成功，返回到目前为止累积的绑定框架。否则，如果模式是一个变量，我们通过将变量绑定到数据来扩展当前框架，只要这与框架中已有的绑定一致。如果模式和数对都是序对，我们（递归地）将模式的 car 与数据的 car 进行匹配以产生一个框架；然后在这个框架中将模式的 cdr 与数据的 cdr 进行匹配。如果这些情况都不适用，则匹配失败，返回符号 failed。
(define (pattern-match pat dat frame)
(cond ((eq? frame 'failed) 'failed)
((equal? pat dat) frame)
((var? pat) (extend-if-consistent pat dat frame))
((and (pair? pat) (pair? dat))
(pattern-match (cdr pat)
(cdr dat)
(pattern-match (car pat)
(car dat)
frame)))
(else 'failed)))
下面是扩展框架的过程，通过添加一个新绑定，前提是与框架中已有的绑定一致：
(define (extend-if-consistent var dat frame)
(let ((binding (binding-in-frame var frame)))
(if binding
(pattern-match (binding-value binding) dat frame)
(extend var dat frame))))
如果框架中没有变量的绑定，我们只需将变量绑定到数据。否则，我们在框架中将数据与框架中变量的值进行匹配。如果存储的值只包含常量（在模式匹配期间由 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)。我们从不修改存储的绑定，也从不为一个给定变量存储多个绑定。
extend-if-consistent 用于操作绑定的过程在 4.4.4.8 节中定义。
如果模式包含一个点后跟一个模式变量，该模式变量匹配数据列表的剩余部分（而不是数据列表的下一个元素），正如练习 2.20 中描述的点尾表示法所预期的那样。虽然我们刚刚实现的模式匹配器不查找点，但它确实如我们所期望的那样工作。这是因为 Lisp 的 read 原语（被 query-driver-loop 用来读取查询并将其表示为列表结构）以特殊方式处理点。
当 read 看到点时，它不会将下一项作为列表的下一个元素（cons 的 car，其 cdr 将是列表的剩余部分），而是将下一项作为列表结构的 cdr。例如，read 为模式 (computer ?type) 产生的列表结构可以通过求值表达式 (cons 'computer (cons '?type '())) 构造，而为 (computer . ?type) 产生的列表结构可以通过求值表达式 (cons 'computer '?type) 构造。
因此，当 pattern-match 递归比较数据列表和带点的模式的 car 和 cdr 时，它最终会将点后的变量（它是模式的 cdr）与数据列表的子列表进行匹配，将变量绑定到该列表。例如，将模式 (computer . ?type) 与 (computer programmer trainee) 匹配，将把 ?type 与列表 (programmer trainee) 进行匹配。
Apply-rules 是 find-assertions（4.4.4.3 节）的规则对应物。它接受一个模式和一个框架作为输入，通过应用数据库中的规则形成扩展框架流。Stream-flatmap 将 apply-a-rule 映射到可能适用的规则流（由 fetch-rules 选择，4.4.4.5 节）上，并组合产生的框架流。
(define (apply-rules pattern frame)
(stream-flatmap (lambda (rule)
(apply-a-rule rule pattern frame))
(fetch-rules pattern frame)))
Apply-a-rule 使用 4.4.2 节概述的方法应用规则。它首先通过将规则结论与给定框架中的模式进行合一来扩充其参数框架。如果成功，它在这个新框架中求值规则主体。
然而，在此之前，程序用唯一的新名称重命名规则中的所有变量。原因是为了防止不同规则应用的变量彼此混淆。例如，如果两个规则都使用名为 ?x 的变量，那么每个规则在应用时可能会向框架添加 ?x 的绑定。这两个 ?x 彼此无关，我们不应被误导以为这两个绑定必须一致。我们可以设计一个更聪明的环境结构而不是重命名变量；然而，我们在这里选择的重命名方法是最直接的，尽管不是最有效的。（参见练习 4.79。）下面是 apply-a-rule 过程：
(define (apply-a-rule rule query-pattern query-frame)
(let ((clean-rule (rename-variables-in rule)))
(let ((unify-result
(unify-match query-pattern
(conclusion clean-rule)
query-frame)))
(if (eq? unify-result 'failed)
the-empty-stream
(qeval (rule-body clean-rule)
(singleton-stream unify-result))))))
提取规则各部分的 rule-body 和 conclusion 选择器在 4.4.4.7 节中定义。
我们通过将一个唯一标识符（如数字）与每个规则应用关联，并将该标识符与原始变量名合并来生成唯一的变量名。例如，如果规则应用标识符是 7，我们可能会将规则中的每个 ?x 改为 ?x-7，将每个 ?y 改为 ?y-7。（Make-new-variable 和 new-rule-application-id 包含在 4.4.4.7 节的语法过程中。）
(define (rename-variables-in rule)
(let ((rule-application-id (new-rule-application-id)))
(define (tree-walk exp)
(cond ((var? exp)
(make-new-variable exp rule-application-id))
((pair? exp)
(cons (tree-walk (car exp))
(tree-walk (cdr exp))))
(else exp)))
(tree-walk rule)))
合一算法实现为一个过程，接受两个模式和一个框架作为输入，返回扩展框架或符号 failed。合一器类似于模式匹配器，但它是对称的——变量的匹配允许在两侧出现。Unify-match 基本上与 pattern-match 相同，只是添加了额外的代码（下面标记为"***"）来处理匹配右侧对象是变量的情况。
(define (unify-match p1 p2 frame)
(cond ((eq? frame 'failed) 'failed)
((equal? p1 p2) frame)
((var? p1) (extend-if-possible p1 p2 frame))
((var? p2) (extend-if-possible p2 p1 frame)) ; ***
((and (pair? p1) (pair? p2))
(unify-match (cdr p1)
(cdr p2)
(unify-match (car p1)
(car p2)
frame)))
(else 'failed)))
在合一中，与在单侧模式匹配中一样，我们只在提议的框架扩展与现有绑定的情况下才接受它。合一中使用的 extend-if-possible 过程与模式匹配中使用的 extend-if-consistent 相同，除了下面程序中标记为"***"的两个特殊检查。在第一个情况下，如果我们试图匹配的变量未绑定，但我们要与之匹配的值本身是一个（不同的）变量，则需要检查该值是否已绑定，如果是，则匹配其值。如果匹配的双方都未绑定，我们可以将任一方绑定到另一方。
第二个检查处理试图将变量绑定到包含该变量的模式的情况。当变量在两个模式中重复出现时，可能会出现这种情况。例如，考虑在一个 ?x 和 ?y 都未绑定的框架中合一两个模式 (?x ?x) 和 (?y <expression involving ?y>)。首先 ?x 与 ?y 匹配，建立 ?x 到 ?y 的绑定。接下来，同一个 ?x 与涉及 ?y 的给定表达式匹配。由于 ?x 已经绑定到 ?y，这导致将 ?y 与该表达式匹配。如果我们将合一器视为找出一组使模式相同的模式变量值，那么这些模式意味着要找到一个 ?y 使得 ?y 等于涉及 ?y 的表达式。没有通用的方法来解决这样的方程，因此我们拒绝这些绑定；这些情况由谓词 depends-on? 识别。80 另一方面，我们不想拒绝将变量绑定到自身的尝试。例如，考虑合一 (?x ?x) 和 (?y ?y)。第二次尝试将 ?x 绑定到 ?y 是将 ?y（?x 的存储值）与 ?y（?x 的新值）匹配。这由 unify-match 的 equal? 子句处理。
(define (extend-if-possible var val frame)
(let ((binding (binding-in-frame var frame)))
(cond (binding
(unify-match
(binding-value binding) val frame))
((var? val) ; ***
(let ((binding (binding-in-frame val frame)))
(if binding
(unify-match
var (binding-value binding) frame)
(extend var val frame))))
((depends-on? val var frame) ; ***
'failed)
(else (extend var val frame)))))
Depends-on? 是一个谓词，测试提议作为模式变量值的表达式是否依赖于该变量。这必须相对于当前框架进行，因为表达式可能包含某个已经有一个依赖于我们测试变量的值的变量。depends-on? 的结构是一个简单的递归树遍历，在必要时我们会替换变量的值。
(define (depends-on? exp var frame)
(define (tree-walk e)
(cond ((var? e)
(if (equal? var e)
true
(let ((b (binding-in-frame e frame)))
(if b
(tree-walk (binding-value b))
false))))
((pair? e)
(or (tree-walk (car e))
(tree-walk (cdr e))))
(else false)))
(tree-walk exp))
设计逻辑编程语言的一个重要问题是如何安排以使在检查给定模式时尽可能少地检查不相关的数据库条目。在我们的系统中，除了将所有断言存储在一个大流中，我们还将所有 car 是常量符号的断言存储在单独的流中，存放在一个由符号索引的表中。要获取可能匹配一个模式的断言，我们首先检查模式的 car 是否是常量符号。如果是，我们返回所有具有相同 car 的已存储断言（供匹配器测试）。如果模式的 car 不是常量符号，我们返回所有已存储的断言。更聪明的方法也可以利用框架中的信息，或者尝试优化模式的 car 不是常量符号的情况。我们没有将索引的准则（使用 car，只处理常量符号的情况）内建到程序中；而是调用体现这些准则的谓词和选择器。
(define THE-ASSERTIONS the-empty-stream)
(define (fetch-assertions pattern frame)
(if (use-index? pattern)
(get-indexed-assertions pattern)
(get-all-assertions)))
(define (get-all-assertions) THE-ASSERTIONS)
(define (get-indexed-assertions pattern)
(get-stream (index-key-of pattern) 'assertion-stream))
Get-stream 在表中查找一个流，如果那里没有存储任何内容，则返回空流。
(define (get-stream key1 key2)
(let ((s (get key1 key2)))
(if s s the-empty-stream)))
规则以类似方式存储，使用规则结论的 car。然而，规则结论是任意模式，因此它们与断言的区别在于可以包含变量。car 是常量符号的模式可以匹配结论以变量开头的规则，以及与模式具有相同 car 的规则。因此，在获取可能匹配一个 car 是常量符号的模式的规则时，我们获取所有结论以变量开头的规则以及结论与模式具有相同 car 的规则。为此，我们将所有结论以变量开头的规则存储在表中的一个单独流中，由符号 ? 索引。
(define THE-RULES the-empty-stream)
(define (fetch-rules pattern frame)
(if (use-index? pattern)
(get-indexed-rules pattern)
(get-all-rules)))
(define (get-all-rules) THE-RULES)
(define (get-indexed-rules pattern)
(stream-append
(get-stream (index-key-of pattern) 'rule-stream)
(get-stream '? 'rule-stream)))
Add-rule-or-assertion! 由 query-driver-loop 用于向数据库添加断言和规则。每个条目适当时存储在索引中，也存储在数据库中所有断言或规则的流中。
(define (add-rule-or-assertion! assertion)
(if (rule? assertion)
(add-rule! assertion)
(add-assertion! assertion)))
(define (add-assertion! assertion)
(store-assertion-in-index assertion)
(let ((old-assertions THE-ASSERTIONS))
(set! THE-ASSERTIONS
(cons-stream assertion old-assertions))
'ok))
(define (add-rule! rule)
(store-rule-in-index rule)
(let ((old-rules THE-RULES))
(set! THE-RULES (cons-stream rule old-rules))
'ok))
要实际存储断言或规则，我们检查它是否可以被索引。如果可以，我们将它存储在适当的流中。
(define (store-assertion-in-index assertion)
(if (indexable? assertion)
(let ((key (index-key-of assertion)))
(let ((current-assertion-stream
(get-stream key 'assertion-stream)))
(put key
'assertion-stream
(cons-stream assertion
current-assertion-stream))))))
(define (store-rule-in-index rule)
(let ((pattern (conclusion rule)))
(if (indexable? pattern)
(let ((key (index-key-of pattern)))
(let ((current-rule-stream
(get-stream key 'rule-stream)))
(put key
'rule-stream
(cons-stream rule
current-rule-stream)))))))
以下过程定义了如何使用数据库索引。如果一个模式（断言或规则结论）以变量或常量符号开头，它将被存储在表中。
(define (indexable? pat)
(or (constant-symbol? (car pat))
(var? (car pat))))
模式在表中存储的键要么是 ?（如果它以变量开头），要么是其开头的常量符号。
(define (index-key-of pat)
(let ((key (car pat)))
(if (var? key) '? key)))
如果模式以常量符号开头，索引将用于检索可能匹配该模式的条目。
(define (use-index? pat)
(constant-symbol? (car pat)))
练习 4.70. 在过程 add-assertion! 和 add-rule! 中，let 绑定的目的是什么？以下 add-assertion! 的实现有什么问题？ 提示：回顾 3.5.2 节中无穷 1 流的定义： (define ones (cons-stream 1 ones))。
(define (add-assertion! assertion)
(store-assertion-in-index assertion)
(set! THE-ASSERTIONS
(cons-stream assertion THE-ASSERTIONS))
'ok)
Stream-append-delayed 和 interleave-delayed 与 stream-append 和 interleave（3.5.3 节）类似， 只是它们接受一个延迟参数（类似于 3.5.4 节中的 integral 过程）。 这在某些情况下推迟了循环（参见练习 4.71）。
(define (stream-append-delayed s1 delayed-s2)
(if (stream-null? s1)
(force delayed-s2)
(cons-stream
(stream-car s1)
(stream-append-delayed (stream-cdr s1) delayed-s2))))
(define (interleave-delayed s1 delayed-s2)
(if (stream-null? s1)
(force delayed-s2)
(cons-stream
(stream-car s1)
(interleave-delayed (force delayed-s2)
(delay (stream-cdr s1))))))
Stream-flatmap 在整个查询求值器中用于将过程映射到框架流上并组合产生的框架流，它是为普通列表在 2.2.3 节中引入的 flatmap 过程的流对应物。但与普通的 flatmap 不同，我们使用交错过程来累积流，而不是简单地追加它们（参见练习 4.72 和 4.73）。
(define (stream-flatmap proc s)
(flatten-stream (stream-map proc s)))
(define (flatten-stream stream)
(if (stream-null? stream)
the-empty-stream
(interleave-delayed
(stream-car stream)
(delay (flatten-stream (stream-cdr stream))))))
求值器还使用以下简单过程来生成一个由单个元素组成的流：
(define (singleton-stream x)
(cons-stream x the-empty-stream))
Type 和 contents，由 qeval（4.4.4.2 节）使用，指定特殊形式由其 car 中的符号标识。它们与 2.4.2 节中的 type-tag 和 contents 过程相同，只是错误消息不同。
(define (type exp)
(if (pair? exp)
(car exp)
(error "Unknown expression TYPE" exp)))
(define (contents exp)
(if (pair? exp)
(cdr exp)
(error "Unknown expression CONTENTS" exp)))
以下过程由 query-driver-loop（在 4.4.4.1 节中）使用，指定规则和断言通过形式为 (assert! <rule-or-assertion>) 的表达式添加到数据库中：
(define (assertion-to-be-added? exp)
(eq? (type exp) 'assert!))
(define (add-assertion-body exp)
(car (contents exp)))
以下是 and、or、not 和 lisp-value 特殊形式（4.4.4.2 节）的语法定义：
(define (empty-conjunction? exps) (null? exps))
(define (first-conjunct exps) (car exps))
(define (rest-conjuncts exps) (cdr exps))
(define (empty-disjunction? exps) (null? exps))
(define (first-disjunct exps) (car exps))
(define (rest-disjuncts exps) (cdr exps))
(define (negated-query exps) (car exps))
(define (predicate exps) (car exps))
(define (args exps) (cdr exps))
以下三个过程定义了规则的语法：
(define (rule? statement)
(tagged-list? statement 'rule))
(define (conclusion rule) (cadr rule))
(define (rule-body rule)
(if (null? (cddr rule))
'(always-true)
(caddr rule)))
Query-driver-loop（4.4.4.1 节）调用 query-syntax-process 来转换表达式中的模式变量，这些变量具有 ?symbol 的形式，转换为内部格式 (? symbol)。也就是说，像 (job ?x ?y) 这样的模式在系统内部实际上被表示为 (job (? x) (? y))。这提高了查询处理的效率，因为系统可以通过检查表达式的 car 是否为符号 ? 来判断表达式是否为模式变量，而不必从符号中提取字符。语法转换由以下过程完成：81
(define (query-syntax-process exp)
(map-over-symbols expand-question-mark exp))
(define (map-over-symbols proc exp)
(cond ((pair? exp)
(cons (map-over-symbols proc (car exp))
(map-over-symbols proc (cdr exp))))
((symbol? exp) (proc exp))
(else exp)))
(define (expand-question-mark symbol)
(let ((chars (symbol->string symbol)))
(if (string=? (substring chars 0 1) "?")
(list '?
(string->symbol
(substring chars 1 (string-length chars))))
symbol)))
一旦变量以这种方式转换后，模式中的变量就是以 ? 开头的列表，而常量符号（用于数据库索引，4.4.4.5 节）就是普通的符号。
(define (var? exp)
(tagged-list? exp '?))
(define (constant-symbol? exp) (symbol? exp))
唯一变量在规则应用期间（4.4.4.4 节）通过以下过程构造。规则应用的唯一标识符是一个数字，每次应用规则时都会递增。
(define rule-counter 0)
(define (new-rule-application-id)
(set! rule-counter (+ 1 rule-counter))
rule-counter)
(define (make-new-variable var rule-application-id)
(cons '? (cons rule-application-id (cdr var))))
当 query-driver-loop 实例化查询以打印答案时，它会将任何未绑定的模式变量转换回正确的打印形式，使用
(define (contract-question-mark variable)
(string->symbol
(string-append "?"
(if (number? (cadr variable))
(string-append (symbol->string (caddr variable))
"-"
(number->string (cadr variable)))
(symbol->string (cadr variable))))))
(define (make-binding variable value)
(cons variable value))
(define (binding-variable binding)
(car binding))
(define (binding-value binding)
(cdr binding))
(define (binding-in-frame variable frame)
(assoc variable frame))
(define (extend variable value frame)
(cons (make-binding variable value) frame))
练习 4.71. Louis Reasoner 想知道为什么 simple-query 和 disjoin 过程（4.4.4.2 节）使用显式的 delay 操作来实现，而不是定义如下：
(define (simple-query query-pattern frame-stream)
(stream-flatmap
(lambda (frame)
(stream-append (find-assertions query-pattern frame)
(apply-rules query-pattern frame)))
frame-stream))
(define (disjoin disjuncts frame-stream)
(if (empty-disjunction? disjuncts)
the-empty-stream
(interleave
(qeval (first-disjunct disjuncts) frame-stream)
(disjoin (rest-disjuncts disjuncts) frame-stream))))
你能给出一些查询的例子，说明这些更简单的定义会导致不良行为吗？
练习 4.72. 为什么 disjoin 和 stream-flatmap 交错流而不是简单地追加它们？给出说明交错效果更好的示例。（提示：为什么我们在 3.5.3 节中使用 interleave？）
练习 4.73. 为什么 flatten-stream 显式使用 delay？将其定义如下会有什么问题：
(define (flatten-stream stream)
(if (stream-null? stream)
the-empty-stream
(interleave
(stream-car stream)
(flatten-stream (stream-cdr stream)))))
练习 4.74. Alyssa P. Hacker 建议在 negate、lisp-value 和 find-assertions 中使用一个更简单的 stream-flatmap 版本。她观察到，在这些情况下映射到框架流上的过程总是产生空流或单例流，因此在合并这些流时不需要交错。
a. 填写 Alyssa 程序中的缺失表达式。
(define (simple-stream-flatmap proc s)
(simple-flatten (stream-map proc s)))
(define (simple-flatten stream)
(stream-map <??>
(stream-filter <??> stream)))
b. 如果我们以这种方式修改，查询系统的行为会改变吗？
练习 4.75. 为查询语言实现一个名为 unique 的新特殊形式。如果数据库中恰好有一个项满足指定的查询，则 unique 应该成功。例如，
(unique (job ?x (computer wizard)))
应打印单个项目的流
(unique (job (Bitdiddle Ben) (computer wizard)))
因为 Ben 是唯一的计算机奇才，并且
(unique (job ?x (computer programmer)))
应打印空流，因为不止一名计算机程序员。此外，
(and (job ?x ?j) (unique (job ?anyone ?j)))
应列出所有仅由一人担任的工作，以及担任这些工作的人。
实现 unique 有两个部分。首先是编写一个处理这种特殊形式的过程，其次是让 qeval 分派到该过程。第二部分很简单，因为 qeval 以数据导向的方式进行分析。如果您的过程名为 uniquely-asserted，您需要做的就是
(put 'unique 'qeval uniquely-asserted)
然后 qeval 将分派到这个过程，处理每个 type（car）为符号 unique 的查询。
真正的问题是编写 uniquely-asserted 过程。它应以 unique 查询的 目录（cdr）和框架流作为输入。对于流中的每个框架，它应使用 qeval 查找满足给定查询的该框架的所有扩展的流。任何不正好包含一个项目的流应被消除。剩余的流应被传递回去，累积成一个大流，作为 unique 查询的结果。这类似于 not 特殊形式的实现。
通过构造一个列出所有恰好监督一个人的查询来测试您的实现。
练习 4.76. 我们将 and 实现为查询的串联组合（图 4.5）的方式很优雅，但效率不高，因为在处理 and 的第二个查询时，我们必须对第一个查询产生的每个框架扫描数据库。如果数据库有 N 个元素，并且一个典型查询产生的输出框架数量与 N 成正比（比如 N/k），那么对第一个查询产生的每个框架扫描数据库将需要 N2/k 次模式匹配器调用。另一种方法是分别处理 and 的两个子句，然后查找所有兼容的输出框架对。如果每个查询产生 N/k 个输出框架，这意味着我们必须执行 N2/k2 次兼容性检查——比我们当前方法所需的匹配次数少 k 倍。
设计一个使用这种策略的 and 实现。您必须实现一个过程，该过程以两个框架作为输入，检查框架中的绑定是否兼容，如果兼容，则产生一个合并两组绑定的框架。此操作类似于合一。
练习 4.77. 在 4.4.3 节中，我们看到如果将这些过滤操作应用于变量未绑定的框架，not 和 lisp-value 可能导致查询语言给出"错误"的答案。设计一种修复这个缺点的方法。一种想法是以"延迟"的方式执行过滤，向框架附加一个过滤"承诺"，该承诺仅在足够多的变量被绑定使操作成为可能时才被履行。我们可以等待所有其他操作执行完毕后再执行过滤。然而，出于效率考虑，我们希望尽可能早地执行过滤，以减少生成的中间框架数量。
练习 4.78. 将查询语言重新设计为非确定性程序，使用 4.3 节的求值器实现，而不是作为流过程。在这种方法中，每个查询将产生一个答案（而不是所有答案的流），用户可以输入 try-again 来查看更多答案。您会发现本节中构建的许多机制都被非确定性搜索和回溯所包含。然而，您可能还会发现，您的新查询语言在行为上与这里实现的版本存在微妙的差异。您能找到说明这种差异的示例吗？
练习 4.79. 当我们在 4.1 节中实现 Lisp 求值器时，我们看到了如何使用局部环境来避免过程参数之间的名称冲突。例如，在求值
(define (square x)
(* x x))
(define (sum-of-squares x y)
(+ (square x) (square y)))
(sum-of-squares 3 4)
时，square 中的 x 和 sum-of-squares 中的 x 之间没有混淆，因为我们在一个专门构造的、包含局部变量绑定的环境中求值每个过程体。在查询系统中，我们使用了不同的策略来避免应用规则时的名称冲突。每次应用规则时，我们都会用保证唯一的新名称重命名变量。Lisp 求值器的类比策略是取消局部环境，而每次应用过程时简单地重命名过程体中的变量。
为查询语言实现一种使用环境而非重命名的规则应用方法。看看您是否能在环境结构的基础上，为查询语言创建处理大型系统的构造，例如块结构过程的规则类比。您能否将这一点与在上下文中进行演绎的问题联系起来（例如，"如果我假设 P 成立，那么我将能够推导出 A 和 B。"）作为解决问题的一种方法？（这个问题是开放式的。一个好的答案可能值得一个博士学位。）
58 逻辑编程源于自动定理证明的长期研究历史。早期的定理证明程序几乎无法完成任何工作，因为它们穷尽式地搜索了所有可能的证明空间。使这种搜索变得可行的重大突破是 20 世纪 60 年代初发现的合一算法和归结原理（Robinson 1965）。例如，Green 和 Raphael（1968）（另见 Green 1969）将归结用作演绎问答系统的基础。在这个时期的大部分时间里，研究人员专注于保证在证明存在时一定能找到证明的算法。这类算法难以控制和引导到某个证明。Hewitt（1969）认识到将编程语言的控制结构与逻辑操作系统的操作相结合的可能性，这导致了 4.3.1 节（脚注 47）中提到的自动搜索工作。与此同时，马赛的 Colmerauer 正在开发用于处理自然语言的基于规则的系统（参见 Colmerauer et al. 1973）。他发明了一种名为 Prolog 的编程语言来表示这些规则。爱丁堡的 Kowalski（1973；1979）认识到 Prolog 程序的执行可以被解释为定理证明（使用一种称为线性 Horn 子句归结的证明技术）。最后这两条线索的融合导致了逻辑编程运动。因此，在分配逻辑编程发展的功劳时，法国人可以指出 Prolog 起源于马赛大学，而英国人则可以强调爱丁堡大学的工作。据麻省理工学院的人说，逻辑编程是由这些小组在试图弄清楚 Hewitt 在其实出但难以理解的博士论文中所谈内容的过程中发展起来的。关于逻辑编程的历史，请参见 Robinson 1983。
59 要看到规则与过程之间的对应关系，让过程中的 x（其中 x 非空）对应规则中的 (cons u v)。那么规则中的 z 对应于 (cdr x) 和 y 的 append。
60 这当然不能免除用户解决如何计算结果的全部问题。存在许多数学上等价的规则集来表达 append 关系，其中只有一些可以被转化为在任何方向上计算的有效装置。此外，有时"是什么"信息并不能提供"如何做"来计算答案的线索。例如，考虑计算满足 y2 = x 的 y 的问题。
61 对逻辑编程的兴趣在 80 年代初期达到顶峰，当时日本政府启动了一个雄心勃勃的项目，旨在构建针对运行逻辑编程语言优化的超快计算机。这类计算机的速度将以 LIPS（每秒逻辑推理次数）而非通常的 FLOPS（每秒浮点运算次数）来衡量。尽管该项目按原计划成功开发了硬件和软件，但国际计算机行业走向了不同的方向。参见 Feigenbaum 和 Shrobe 1993 对该日本项目的概述评估。逻辑编程社区也已转向考虑基于简单模式匹配之外技术的关系编程，例如处理数值约束的能力，如 3.3.5 节的约束传播系统所示。
62 这使用了练习 2.20 中引入的点尾表示法。
63 实际上，这种对 not 的描述仅对简单情况有效。not 的真实行为更为复杂。我们将在 4.4.2 节和 4.4.3 节中检查 not 的特殊之处。
64 Lisp-value 应仅用于执行查询语言中未提供的操作。特别地，它不应被用于测试相等性（因为那是查询语言中匹配设计要做的事）或不相等性（因为这可以通过下面所示的 same 规则来完成）。
65 注意，我们不需要 same 来使两件事相同：我们只需对每个使用相同的模式变量——实际上，我们一开始就只有一件事而不是两件事。例如，参见下面 lives-near 规则中的 ?town 和 wheel 规则中的 ?middle-manager。当我们想要强制两件事不同时，same 很有用，例如 lives-near 规则中的 ?person-1 和 ?person-2。虽然在查询的两个部分中使用相同的模式变量会强制相同的值出现在两个位置，但使用不同的模式变量并不会强制出现不同的值。（分配给不同模式变量的值可以相同或不同。）
66 我们也允许没有主体的规则，如 same，我们将解释这样的规则为：规则结论被变量的任何值满足。
67 因为匹配通常非常昂贵，我们希望避免对数据库的每个元素应用完整的匹配器。这通常通过将过程分解为快速粗匹配和最终匹配来实现。粗匹配过滤数据库，为最终匹配产生一小组候选。通过精心设计，我们可以安排数据库，使粗匹配的某些工作可以在数据库构建时完成，而不是在我们想要选择候选时完成。这称为数据库的索引。围绕数据库索引方案已经建立了庞大的技术体系。我们在 4.4.4 节中描述的实现包含了这种优化的一种简单形式。
68 但这种指数级爆炸在 and 查询中并不常见，因为添加的条件倾向于减少而不是增加产生的框架数量。
69 关于数据库管理系统如何处理复杂查询的文献很多。
70 not 的这种过滤器实现与数学逻辑中 not 的通常含义之间存在微妙的差异。参见 4.4.3 节。
71 在单侧模式匹配中，所有包含模式变量的方程都是显式的，并且已经为未知数（模式变量）求解。
72 理解合一性的另一种方式是，它生成两个输入模式的最一般特化模式。也就是说，(?x a) 和 ((b ?y) ?z) 的合一是 ((b ?y) a)，而上面讨论的 (?x a ?y) 和 (?y ?z a) 的合一是 (a a a)。对于我们的实现，将合一的结果视为框架而不是模式更为方便。
73 由于合一是匹配的推广，我们可以通过使用合一器来产生两个流以简化系统。然而，用简单的匹配器处理简单情况说明了匹配（相对于完整的合一）本身如何是有用的。
74 我们使用框架流（而不是列表）的原因是，规则的递归应用可能生成满足查询的无限数量的值。流中体现的延迟求值在这里至关重要：系统将逐个打印生成的响应，无论响应的数量是有限还是无限。
75 某种特定的推理方法是否合法并不是一个平凡的断言。必须证明，如果从正确的前提出发，只能推导出正确的结论。规则应用所代表的推理方法是 假言推理，这种熟悉的推理方法指出，如果 A 为真且 A 蕴含 B 为真，那么我们可以得出结论 B 为真。
76 我们必须限定这一陈述，同意在谈论逻辑程序完成的"推理"时，我们假设计算会终止。不幸的是，即使这个经过限定的陈述对我们查询语言的实现（以及 Prolog 和大多数其他当前逻辑编程语言中的程序）也不成立，因为我们使用了 not 和 lisp-value。正如我们将在下面描述的，查询语言中实现的 not 并不总是与数学逻辑中的 not 一致，而 lisp-value 引入了额外的复杂性。我们可以通过简单地从语言中移除 not 和 lisp-value，并同意仅使用简单查询、and 和 or 来编写程序，从而实现与数学逻辑一致的语言。然而，这将极大地限制语言的表现力。逻辑编程研究的主要关注点之一是在不过度牺牲表现力的情况下找到与数学逻辑更一致的方法。
77 这不是逻辑的问题，而是我们的解释器提供的逻辑的过程性解释的问题。我们可以编写一个不会在此陷入循环的解释器。例如，我们可以以广度优先而非深度优先的顺序枚举从断言和规则中可推导出的所有证明。然而，这样的系统使得利用程序中演绎的顺序变得更加困难。在 deKleer et al. 1977 中描述了在这种程序中构建复杂控制的一次尝试。另一种不会导致如此严重控制问题的技术是加入特殊知识，例如针对特定类型循环的检测器（练习 4.67）。然而，不存在一种通用方案能够可靠地防止系统在演绎过程中陷入无穷路径。想象一条恶意的规则，形式为"要证明 P(x) 为真，请证明 P(f(x)) 为真"，其中 f 是某个适当选择的函数。
78 考虑查询 (not (baseball-fan (Bitdiddle Ben)))。系统发现 (baseball-fan (Bitdiddle Ben)) 不在数据库中，因此空框架不满足该模式，且不会从初始框架流中被过滤掉。查询的结果因此是空框架，它被用来实例化输入查询以产生 (not (baseball-fan (Bitdiddle Ben)))。
79 关于这种 not 处理方式的讨论和论证可以在 Clark（1978）的文章中找到。
80 通常，将 ?y 与包含 ?y 的表达式合一要求我们能够找到方程 ?y = <包含 ?y 的表达式> 的不动点。有时可以在语法上构造一个看起来是解的表达式。例如，?y = (f ?y) 似乎有不动点 (f (f (f ...)))，我们可以通过从表达式 (f ?y) 开始并反复用 (f ?y) 替换 ?y 来产生它。不幸的是，并非每个这样的方程都有有意义的不动点。这里出现的问题类似于数学中处理无穷级数的问题。例如，我们知道 2 是方程 y = 1 + y/2 的解。从表达式 1 + y/2 开始，反复用 1 + y/2 替换 y 得到
这导致
然而，如果我们从观察到 -1 是方程 y = 1 + 2y 的解开始，进行相同的操作，我们得到
这导致
尽管推导这两个方程所使用的形式操作是相同的，但第一个结果是关于无穷级数的有效断言，而第二个却不是。类似地，对于我们的合一结果，使用任意语法构造的表达式进行推理可能导致错误。
81 大多数 Lisp 系统允许用户通过定义读取器宏字符来修改普通的 read 过程以执行此类转换。引用的表达式已经以这种方式处理：读取器自动将 'expression 转换为 (quote expression)，然后求值器才能看到它。我们可以安排 ?expression 以相同的方式转换为 (? expression)；然而，为了清晰起见，我们在这里显式地包含了转换过程。
Expand-question-mark 和 contract-question-mark 使用了几个名称中包含 string 的过程。 这些是 Scheme 原语。