4.4 Logic Programming - CloneableX/SICP-learning GitHub Wiki
在第 1 章我们通过计算机科学学习了实践性知识（关于如何做的知识），以及通过数学学习了概念性知识（关于是什么的知识）。诚然，编程语言只有通过程序员才能够逐步实现解决特定问题的能力。但从另一方面来看，将高级语言作为编程语言实现的基础使用，也可以通过大量方法论知识使用户免于关心特定的实现细节。
包括 Lisp 在内，大量的编程语言的目的都是为了解决数学函数问题。面向表达式的语言（例如 Lisp、Fortran 和 Algol）都利用了“双关”概念，表达式既能表示函数值也能解释函数值计算的意义。由于这种特性，许多编程语言主要偏向于单向计算（只基于定义好的输入输出进行计算）。不过，也存在一些编程语言采用完全不同的技术倾向。在第 3 章我们已经见过类似的示例，示例中的计算对象由算术限制主导。在限制系统中，计算顺序和计算方向都不是预先定义好的，这种计算系统需要获得比原生算数运算更多的实践性知识。但是，这并不意味着用户将提供实践性知识的能力完全释放。在限制系统中，其中有许多限制网络，它们实现类似的一级限制，然后用户必须选择其中一个子限制网络开启运算。
上一节的非确定性程序求值器也是一种非单一方向运算的实现方式。在非确定性编程语言中，表达式存在多个值，并且计算中需要处理的函数关系也不再是单一的关系。逻辑编程扩展了这种概念，主要是将一种关于关系的编程模型与一种称为 一体化（unification） 的标识模式合并而成。
这是一种指导我们编写程序的强大方式。它的强大主要来自通过一个概念性知识便能够解决许多种由该概念产生的实践性问题。例如，思考 append 程式，它能够将两个列表拼接成一个列表。在程序语言中，例如 Lisp 中，我们需要在列表构造器 cons 的基础上实现 append 的计算，就像我们在第 2 章实现的一样。
(define (append x y)
(if (null? x) y (cons (car x) (append (cdr x) y))))我们可以将上述程式视为下列两个规则翻译为 Lisp 的形式。
- 对于任何列表 y，空列表与 y
append操作的结果都为 y - 对于任意 u、v、y 和 z，如果 v 与 y
append的结果为 z，则(cons u v)与 yappend的结果为(cons u z)
通过 append 程式我们能够解决查找 (a b) 和 (c d) 的拼接结果问题，但同样的规则却无法解决下列两个问题。
- 查找列表 y，列表 y 与
(a b)append的结果为(a b c d) - 查找所有列表 x 和列表 y 的可能性，其中 x 和 y 拼接结果为
(a b c d)
在逻辑编程语言中，程序员通过 append 的两条规则实现 append 程式。那么，解释器便能够自动产生一系列解决上述三种关于 append 类型的问题的规则。
现代的逻辑编程语言（包括我们即将实现的）还存在一些重大的缺陷，此类语言的通用实现方法可能导致虚假的无限循环或其他不符合预期的行为。逻辑编程是计算机科学中较为活跃的一个研究领域。
在本章前面的内容中，我们已经探讨过解释器的实现技术以及描述了类 Lisp 语言解释器中的核心元素。现在，我们要利用这此概念对逻辑编程语言进行讨论。我们称这门编程语言为 查询语言（query language），因为它对于基于标准查询构建的数据信息（或问题）的检索十分有效。虽然查询语言与 Lisp 十分不同，但我们依然能够找到它们之间关于描述语言规范的相同框架。比如基础元素，以及将简单元素构建为复杂元素的方法和将复杂元素抽象的方法。显而易见，逻辑编程语言的解释器比类 Lisp 语言的解释器更加复杂。但是，查询语言解释器还是会包含许多与类 Lisp 解释器中元素相似的元素。尤其是逻辑语言解释器中依然会包含区分表达式类型的 eval 部分，及实现语言抽象原理的 apply 部分。并且，框架数据结构依然会扮演该解释器的核心角色，它将决定标识与标识关联的数值之间的通信方式。除此之外，我们在实现查询语言时会大量使用流。
逻辑编程擅长提供用于信息检索的数据接口。我们在本章实现的逻辑语言也是同样的用法。
我们会通过微软员工信息管理系统的例子说明查询系统的运作方式。逻辑语言提供了模式化访问员工信息的方式，同时还能受益于通用规则的逻辑推演功能。
微软的员工信息数据库包括对于企业员工的断言。下列是 Ben Bitdiddle 的员工信息，他是一位退休的计算机引导员。
(address (Bitdiddle Ben) (Slumerville (Ridge Road) 10))
(job (Bitdiddle Ben) (computer wizard))
(salary (Bitdiddle Ben) 60000)
每个断言都是一个列表（在上述例子中是三元组），列表中元素也可以是列表。
作为退休的计算机向导员，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)
除此之外，公司还有会计部，该部门包含一名主会计师及他的助理。
(address (Scrooge Eben) (Weston (Shady Lane) 10))
(job (Scrooge Eben) (accounting chief accountant))
(salary (Scrooge Eben) 75000)
(supervisor (Scrooge Eben) (Warbucks Oliver))
(address (Crachet Robert) (Allston (N Harvard Street) 16))
(job (Crachet 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))
数据库中也包含员工能够从事的其他工作。例如，一名计算机向导员也可以成为一名程序员或一名技术员。
(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))
查询语言允许用户通过键入查询的方式从数据库中推演信息。例如，通过下列查询语句可以获取所有程序员信息。
;;; Query input:
(job ?x (computer programmer))系统的计算结果如下。
;;; Query results:
(job (Hacker Alyssa P) (computer programmer))
(job (Fect Cy D) (computer programmer))键入的查询语句能够指定数据库数据的匹配模式。在上述例子中，匹配模式包含三个元素，第一个元素是字符标识 job，第二个元素可以是任何事物，第三个元素是字符列表（computer programmer)。其中匹配模式中的第二个元素 ?x 表示模式变量。模式变量通常是一个标识，这个标识表示变量名称，并在名称前添加问号。我们将在后面的内容中解释为什么模式变量需要使用变量名称而不直接使用问号即可。系统会返回数据库中所有匹配指定模式的数据。
一个模式可以有多个变量，例如 (address ?x ?y) 的查询目标是所有员工地址。
不过匹配模式也可以没有变量，这种匹配模式用于查询一条数据。如果条件匹配只会存在一条匹配数据，如果不匹配则没有匹配的数据。
同样的模式变量能够在一个查询语句中多次出现，它们表示同样的事物出现在变量对应的位置。这就是模式变量需要有变量名称的原因。例如 (supervisor ?x ?x) 将查找自己是自己的管理者的所有员工数据（尽管数据库中没有符合这种情况的数据）。
查询语句 (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 开头的员工职位信息，可以修改为 (job ?x (computer . ?type))。
例如 (computer . ?type) 能够匹配数据 (computer programmer trainee)，其中的 ?type 能够匹配到 (programmer trainee)。(computer . ?type) 也能够匹配 (computer programmer)，此时 ?type 匹配的信息为 (programmer)；同样也可以匹配 (computer)，此时的 ?type 匹配结果是空列表。
综上所述，我们能够将查询语言的查询过程作如下描述。
- 系统会查找所有满足查询模式的变量赋值，也就是说所有变量值替换模式的变量后再与数据库中的数据进行匹配。
- 系统会列举所有查询模式进行变量赋值实例化后数据库中完全符合的数据
如果匹配模式中没有变量，查询语句会退化为直接与数据库中的数据匹配。也就是说，不对变量进行赋值并直接在数据库中查找符合查询模式的数据。
简单查询只是查询语言中的基础操作。为了构造复合操作，查询语言提供了结合基本查询的方法。结合基本查询语句也就是要通过逻辑将其连接，所以只要通过逻辑表达式就能够构建复合查询语句，逻辑表达式包括 and、or 和 not（这里的逻辑表达式不是 Lisp 的基础程式，它们都是由查询语言构建的基础程式）。
我们可以通过 and 查询所有程序员员工的地址信息。
(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>) 限制了模式变量的值必须同时符合所有的查询语句。
如同简单的查询语句一样，系统在处理复合查询时也需要为所有的模式变量赋值，然后对数据库结果进行匹配。
另一种构建复合查询语句的方式是 or。示例如下。
(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>) 只需要符合其中一个查询语句即可。
通过 not 也可以构建复合查询语句，示例如下。
(and (supervisor ?x (Bitdiddle Ben))
(not (job ?x (computer programmer))))上述示例将查找上司是 Ben Bitdiddle，并且职位不是程序员的员工信息。(not <query1>) 要求匹配信息不满足查询语句 <query1>。
最后一种构建复合查询语句的方式为 lisp-value。当匹配模式的第一个元素是 lisp-value 时，紧接着的下一个元素是一个 Lisp 的谓词，并且它将作为之后的实例化元素的参数进行应用。通常来说，(list-value <predicate> <arg1> ... <argn>) 会将模式变量都进行赋值，并且将 <predicate> 应用于 <arg1> ... <argn> 的结果都是 true。例如，查询所有薪资大于 $30000 的查询语句可以如下编写。
(and (salary ?person ?amount) (list-value > ?amount 30000))在提供基础查询和复合查询后，查询语言需要提供对查询语句抽象的方法。通过规则可以对查询语句进行抽象处理，规则编写如下。
(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 可以通过一个基本规则表示。
(rule (same ?x ?x))下列规则表示如果某人是其他人的上司，同时他管理的人也是管理者，则此人为组织的核心管理人员。
(rule (wheel ?person)
(and (supervisor ?middle-manager ?person)
(supervisor ?x ?middle-manager)))规则的语法为 (rule <conclusion> <body>)。其中的 <conclusion> 是一个模式，<body> 中可以包含任何查询语句。我们可以认为规则表示一组断言（数量甚至可以是无限），也就是说所有带有变量赋值的规则结语都要符合规则体的断言。在描述简单查询时，我们可以说如果模式的实例化存在于数据库中则意味着变量赋值符合一个匹配模式。但模式并不需要存在于数据库中才能称为断言，它也可以是应用于规则的断言。例如，查询语句 (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))))上述例子表示只要企业老板是当前员工的直接领导，或该员工的领导上司是老板，则该员工受该企业老板的管理。
我们可以将规则视为一种逻辑表示，如果模式变量赋值与规则体相匹配，则它符合规则结论。并且，我们可以认为逻辑语言在规则的基础上拥有了逻辑推演能力。例如，我们思考 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)
(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 的例子令人印象深刻，不过后面的章节会展示复杂示例导致系统崩溃的情况。
在本章的最后，我们将实现一个查询解释器，所以本节需要提前讲解独立于实现细节的查询系统结构。在讲解完成后，还将研究查询语言逻辑操作的限制，以及它与数据逻辑操作之间的细微差别。
显而易见，查询求值器能够根据查询匹配的规则和内容从数据库中查找数据。实现查询系统的其中一种办法就是使用非确定性编程，也就是之前讲到的 amb 求值器；另一种方法则是通过流实现。我们选择的实现方法为第二种。
查询系统包含两个核心操作，分别为 模式匹配（pattern matching） 和 一体化（unification）。首先解释模式匹配如何运作，它将信息集中在框架的流中，以此使我们能够实现基础查询和复合查询。接着解释一体化，一体化就是一种需要实现规则的匹配模式的泛化。最后，我们将展示查询解释器以类似 eval 分类表达式的方式编排程式的具体细节。
模式匹配是一个检测数据是否符合待定模式的程序。例如，((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 和 ?y 分别绑定 a 和 b。但是该列表与模式 (?x a ?y) 并不匹配，因为此模式指定列表的第二个元素为 a。
查询系统要应用模式匹配就需要一个模式、一个数据及一个保存模式变量与数值绑定关系的框架。模式匹配将检测数据是否与框架中绑定数值的模式匹配。如果匹配，将返回增补后的框架，框架的增补内容为匹配确定的绑定关系。否则，这表示着匹配失败。
例如，在一个空框架中使用模式 (?x ?y ?x) 匹配 (a b a)，返回结果为一个存储了 ?x 和 ?y 绑定关系的框架，其中 ?x 与 a 绑定，?y 与 b 绑定。如果以一个 ?y 已经绑定 a 的框架运算上述匹配，将得到失败的结果。如果以一个 ?y 绑定 b，?x 未进行绑定的框架运算上述匹配将产生一个扩展的框架，其中扩展了 ?x 与 a 的绑定。
模式匹配器只需要处理基础查询的机制，不需要关心规则。例如，处理查询 (job ?x (computer programmer)) 时，我们只需要扫描数据库中的所有假设，并在一个预先准备好的空框架中与模式进行匹配。对于每个匹配，我们利用通过匹配返回的框架实例化模式，并为模式中的 ?x 赋值。
在框架中进行的模式检测通过流实现。给定一个框架，匹配过程对数据库中的数据逐个检测。对于每条数据，匹配器都会生成一个标识，以此标识表示匹配失败或框架得到扩展。所有数据的检测结果都存储于流中，然后通过过滤器去除失败的结果。最终将得到一个存储扩展框架的流。
在我们的系统中，查询需要一个框架流作为输入，并基于流中的每个框架进行匹配操作，整个过程正如下图所示。对于输入的框架流，查询会通过与数据库数据匹配的方式产生一个由扩展框架组成的流。所有的流最后会组成一个更庞大的流，其中包含输入框架流中所有的框架扩展的可能性，这个流也是查询的输出流。
处理基础查询时，我们会基于由一个空框架构成的流进行查询。作为结果的输出流包含空框架的所有扩展（也就是该查询的所有结果）。接着将输出的框架流用于生成基于查询模式通过每个框架中参数实例化结果的流，最终生成的流才是最后的输出结果。
框架流这种实现方式的真正精妙之处在于处理复合查询时也十分便捷。复合查询的处理过程中需要通过匹配器在一个指定的组合框架的基础上进行匹配即可。例如，处理下列通过 and 连接的复合查询时。
(and (can-do-job ?x (computer programmer trainee))
(job ?person ?x))首先会查询所有匹配 (can-do-job ?x (computer programmer trainee)) 模式的结果，然后产生一个框架流，其中的每个框架都记录了 ?x 的绑定关系。接着基于流中的每个框架查询与模式 (job ?person ?x) 的匹配结果，该模式进行匹配时 ?x 的绑定关系基于流中的每个框架。最后，查询结果将产生包含 ?x 和 ?person 绑定关系的框架。所以 and 连接的查询可以看作两个查询组件的组合，如同下图。通过第一个查询产生的框架将作为第二个查询的框架基础应用。
下图展示了通过 or 形成的复合查询的计算过程，其中的两个查询分别进行。输入的框架流分别基于两个查询扩展，然后再将两个查询产生的框架流进行合并产生最终结果。
即使从高层级的描述来说，复合查询的执行过程也很缓慢。例如，当一个查询对于一个输入框架能够产生多于一个输出构架时，在 and 中的每个查询都要基于前一个查询的框架进行计算，所以整个复合查询的消耗以基于查询数量指数级提升。虽然对于基础查询系统的效率已经足够，但处理复合查询时执行效率上还存在缺陷。
从框架流的视角出发，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 绑定关系的框架，然后第二个查询将去除绑定了参数 ?x 并且 ?x 是计算机程序员的框架。
这种 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。我们可以认为解决模式等价的过程是一组方程。通常来说，这些方程会同时运行，所以需要大量的操作处理。例如，一体化 (?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 的值。所以这个匹配无法限制 ?y 的值，所以在结果框架中 ?y 没有绑定值。不过，上述匹配能够限制 ?x 的值，只要提供 ?y 的值则 ?x 也将得到结果。所以 ?x 与模式 (b ?y) 的绑定关系也将记录于框架中。如果在稍后的计算中 ?y 与某个数值绑定（通过以此框架为基础的模式匹配或一体化操作实现），则 ?x 也将绑定上数值。
一体化是查询系统的关键部分，它能够制造对规则的引用。要了解这是如何达成的，就需要思考包含规则的查询的执行过程。例如，(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 需要一个查询和一个框架流作为输入，它的输出是一个框架流，与成功匹配的查询模式一致，它是基于输入框架的扩展框架，具体如下图。eval、qeval 需要区分不同类型的表达式（查询）及为每个表达式（查询）委派相应的程式。每个行列形式（and、or、not 及 lisp-value）都有一个对应的程式，以及一个应用于基础查询的程式。
驱动循环与其他求值器的 driver-loop 程式类似，它需要从终端中读取查询。对于每个查询，会调用 qeval 并传入查询和由一个空框架构成的流。由此将产生所有匹配可能的流（也就是基于空框架的所有可能扩展）。对于结果流中的每个框架，它将通过框架中变量绑定的数值实例化初始查询，实例化后的查询将被打印。
同时驱动还需要检查特殊命令 assert!，该命令表示当前输入不是查询而是数据录入或规则。示例如下。
(assert! (job (Bitdiddle Ben)
(computer wizard)))
(assert! (rule (wheel ?person)
(and (supervisor ?middle-manager ?person)
(supervisor ?x ?middle-manager))))查询语言中的组合方法（and、or 及 not）初看之下就是数学逻辑，并且查询语言规则的应用实质上是通过合法推演实现的。尽管如此，查询语言并不等于数学逻辑，因为查询语言提供了解释程式逻辑状态的控制结构。例如，查询所有程序员的上司时，可以定义出两个逻辑等价的查询。
(and (job ?x (computer programmer)) (supervisor ?x ?y))
(and (supervisor ?x ?y) (job ?x (computer programmer)))如果企业中一个程序员有多个上司，最好使用第一个查询，因为 and 查询会先根据第一个子查询的扫描数据库。
逻辑语言的目标是向程序员提供解耦可计算问题为「计算什么」和「如何计算」的技术。这项技术是通过查询数学逻辑状态的子集实现，这个逻辑子集要足够强大能够描述希望计算的事物，同时足够弱，能够有一个可按的程序性解释。这样做的目的是一门逻辑编程语言中的程序应该是能够在任何计算机中运行的高效程序。控制（也就是如何计算）受语言的计算顺序影响。我们应该能够编排子查询的顺序以及每个子查询中子目标的顺序，以此使计算呈现有序的状态，使程序能够逐渐向高效演化。同时，我们还应该能够如同简单的逻辑规则结果一样看到计算结果（也就是计算什么）。
我们的查询语言可以被视作程式化可解释的数学逻辑。数据库数据可视作基础事实（也就是一个原子观点）。规则表示规则体情况的结论隐喻。每个规则都有一个自然程式的解释：为了建立规则结论，就要构建规则体。因此，规则就是算式。不过，由于规则也能视作数学逻辑陈述，所以我们能够通过断言规则能够完全在数学逻辑中运转并产生相同结果来证明逻辑程式的推演是合理的。
逻辑程序的程式解释器可能构成十分低效的程序。其中一种较极限的低效程序例子为无限循环。举个简单的示例，假设我们在数据库中初始化了一些名人婚姻，其中包括 (assert! (married Minnie Mickey))。如果此时我们输入查询 (married Mickey ?who)，将不会产生任何结果，因为不知道是否 A 嫁给了 B 等价于 B 娶了 A。所以我们需要添加规则 (assert! (rule (married ?x ?y) (married ?y ?x)))，然后再次查询 (married Mickey ?who)。
不幸的是，这将导致系统出现死循环，具体过程如下。
- 系统查找
married规则并应用，接着规则(married ?x ?y)与查询模式(married Mickey ?who)一体化成功，并产生一个框架，其中?x绑定Mickey，?y绑定?who。然后解释器继续在该框架的基础上执行规则体(married ?y ?x)，实际上就是处理查询(married ?who Mickey)。 - 数据库中的一个数据直接作为答案出现
(married Minnie Mickey) - 但
married规则依然可以被应用，于是解释体再一次运行了规则体，这次处理的查询等价于(married Mickey ?who)。
此时的系统陷入了无限循环。并且，系统能否在进行循环前找到答案 (married Minnie Mickey) 依赖于系统检测数据库数据顺序的实现细节。这是一个可能出现的情况的简单示例。有些内部关联的规则可能会导致更加难以预计的循环出现，而且循环的出现会信赖于 and 子查询的顺序或系统处理查询的底层实现细节顺序上。
查询系统中的另一种诡异情况与 not 有关。基于上一节的数据库思考下列查询。
(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 子句处理了框架变量尚未绑定，则是系统将产生不可预计的结果。类似的问题在使用 lisp-value 时也会出现，如果其中有参数尚未绑定 Lisp 的谓词判断也将失效。
关于查询语言中的 not 与数学逻辑中的 not 还有很多差异。在数学逻辑中，我们陈述「not P」就表示 P 非真。而在查询系统中，「not P」表示 P 无法从数据库中推导得出。例如，之前存储员工信息的数据库，系统能够顺畅地推导出关于 not 陈述，例如 Ben Bitdiddle 不是一个棒球迷，今天没有下雨，2 + 2 不是 4。但从另一方面来讲，逻辑编程语言中的 not 反映了封闭世界假说，也就是说它假设所有相关的信息都已经存储于数据库中。
之前的章节已经介绍了查询系统的运行机制，现在我们要在运行机制的构架下填充细节，完成查询系统的实现。
查询系统的驱动循环将不断读取输入的表达式。如果表达式是规则或数据录入，则将信息添加至系统中。否则，就认为输入表达式为查询。然后驱动将查询语句和初始框架流（由一个空框架构成）传递给求值器 qeval。接着根据数据库匹配数据生成携带对应变量及变量值绑定关系的框架流。最后将扩展的框架流应用于初始查询的拷贝，并由此构成一个新的流，该流最终将用于终端打印。
(define input-promt ";;; Query input:")
(define output-promt ";;; 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 和 add-rule-or-assertion!。
在处理输入表达式前，驱动循环为了使处理流程更加高效对表达式进行了语法转化。转化过程包括模式变量表现形式，当查询语句实例化时，任何未绑定的变量在被打印前都要被转化为输入形式。整个转化过程通过 query-syntax-process 和 contract-question-mark 两个程式实现。
为了完成表达式的实例化，我们将表达式进行拷贝，并通过给定框架的变量绑定关系替换表达式的变量为变量值。当数值中包含变量的情况也成立时（例如，如果查询语句的一体化结果为 ?x 与 ?y 绑定，并且 ?y 与 5 绑定），则认为变量值实例化完成。如果变量无法被实例化，则需要采取使用程式参数中的实例化方法。
(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))维护绑定关系的程式将在后面的章节讲解。
qeval 程式由 query-driver-loop 调用，它是整个查询系统的求值器基础。需要向该程式提供一个查询和一个框架流作为输入，它将返回一个扩展框架流。它通过 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 和 contents 将在后面的章节实现。
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 使数据库中的数据与模式进行匹配操作，并产生一个扩展框架流，接着使用 apply-rules 应用所有可能的规则，并产生另一个扩展框架流。然后将两个流结合（通过 stream-append-delayed 程式）创造一个包含所有描述给定模式能够与原始构架结合适配的方式的流，转换过程通过 stream-flatmap 对初始框架流的每个框架遍历实现。
and 查询由 conjoin 程式处理。conjoin 的输入为交集和框架流，并返回扩展框架流。首先，conjoin 通过框架流查找适配交集中第一个查询的所有可能的扩展框架形成的流。然后将该框架流作为新的框架流递归地应用于 conjoin 的剩余查询。
(define (conjoin conjuncts frame-stream)
(if (empty-conjunction? conjuncts)
frame-stream
(conjoin (rest-conjucts conjuncts)
(qeval (first-conjunct conjuncts) frame-stream))))表达式 (put 'and 'qeval conjoin) 会促使 qeval 遇到 and 形式时委派给 conjoin 程式处理。
or 查询语句的处理过程与之类似。or 不同分支的输出流将分别计算，然后通过 interleave-delayed 程式综合。
(define (disjoin disjuncts frame-stream)
(if (empty-disjunction? disjuncts)
the-ehmpty-stream
(interleave-delayed
(qeval (first-disjunct disjuncts) frame-stream)
(delay (disjoin (rest-disjuncts disjuncts) frame-stream)))))
(put 'or 'qeval disjoin)交集和并集语法的选择器及谓词将在后面的章节实现。
not 通过之前描述的方法实现。我们将扩展输入流中的每个框架，并适配查询的反向结果，在输入流中只会包含无法被扩展的框架。
(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))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 通常被没有定义规则体的规则（有一些规则需要在任何情况下都适配）查询器使用。
(define (always-true ignore frame-stream) frame-stream)
(put 'always-true 'qeval always-true)not 和 lisp-value 的语法查询器定义在后面的章节给出。
find-assertions 由 simple-query 调用，它的输入为一个模式和一个框架。它将返回一个框架流，其中每个框架都由数据库中与模式匹配的数据扩展。它通过 fetch-assertions 获取数据库所有与模式匹配的数据流和框架。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 数值，然后在当前框架中匹配模式与数据的 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 匹配期间存储的，则只需要检查变量绑定关系是否已经存储，以及新的数值是否相同。如果已经存储并且数据相同，则返回未经修改的框架；反之，返回一个失败的标识。然而，如果绑定关系是在一体化期间存储，则存储数据可能包含模式变量。于是存储的模式与数据的递归匹配可能导致添加变量绑定关系或检测变量绑定关系。例如，假设存在一个框架，其中 ?x 与 (f ?y) 绑定，?y 未绑定，并且我们希望该框架的 ?x 绑定值更新为 (f b)。通过查找我们得知 ?x 与 (f ?y) 绑定，这导致在同样的框架中需要 (f ?y) 与 (f b) 绑定。最后，匹配通过添加 ?y 与 b 的绑定关系扩展了框架。我们从不会修改已经存在的绑定，也不会为一个变量存储多个绑定关系。
使用 extend-if-consistent 维护绑定关系的程式在后面的章节中讲解。
如果一个模式在模式变量前加上了点符号，则该模式变量将匹配数据列表的其余元素（不是数据列表的下一个元素）。尽管之前实现的模式匹配器未处理点符号的情况，但它也能够满足我们的需求。因为 Lisp 的 read 基础程式会以特殊的方式处理点符号。
当 read 发现点符号时，它会将下一个数据从列表的下一个元素替换为列表的余下元素。例如，read 读取 (computer ?type) 模式时产生的列表与 (cons 'computer (cons '?type '())) 产生的列表一致，而 (computer . ?type) 将产生的列表结构与 (cons 'computer '?type) 一致。
因此，pattern-match 将递归比较数据列表中的 cars 和 cdrs 数值，如果模式中存在点符号，则会将点后面的变量与数据列表的子列表比较，并为该列表绑定变量关系。例如，将 (computer programmer trainee) 数据与 (computer . ?type) 匹配，?type 的结果为列表 (programmer trainee)。
apply-rules 与 find-assertioins 的处理逻辑类似。它的输入参数为一个模式和一个框架，并返回通过向数据库应用规则产生的扩展框架流。stream-flatmap 通过 apply-a-rule 应用可运行的规则流，并组合产生框架流。
(define (apply-rules pattern frame)
(stream-flatmap (lambda (rule)
(apply-a-rule rule pattern frame))
(fetch-rules pattern frame)))apply-a-rule 通过之前描述的逻辑实现。首先将规则与给定框架中的模式一体化，如果一体化成功，则在新框架的基础上运算规则体。
不过，在上述步骤发生前，程序会通过新名称对规则中所有变量进行唯一命名。这么做的理由是能够避免变量在不同规则中的应用引起混淆。例如，如果两个规则都存在变量 ?x，当两个规则被应用时在框架中都会添加关于 ?x 的绑定关系。而两个 ?x 根本上不是同一事物，这将导致我们无法确定使用哪个绑定关系进行计算。相比重命名变量，我们更倾向于使用更加灵活的环境结构，但目前选择重命名的原因在于它更加简洁，而不是因为它更加高效。下列是 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 的实现将在后面讲解。
通过为每个规则分配唯一标识，并将唯一标识与变量原有名称结合的方式生成变量的唯一命名。例如，如果规则应用的标识为 7，则将该规则中的变量 ?x 和 ?y 重命名为 ?x-7 和 ?y-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 基本类似，不过 unify-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 类似，不过 extend-if-possible 与 extend-if-consistent 有两处区别，已经在下面的程序中使用 「***」进行了标识。在第一种情况中，如果试图匹配的变量尚未绑定，而且与该变量匹配的也是一个变量，则是我们必须检查后者是否与数值绑定，如果已经绑定数值则是将前者与数值匹配。如果两个变量都尚未绑定，则是将其中一个变量与另一个绑定。
在第二种情况中，需要为含有变量的模式绑定变量。变量只要在任一模式中存在这种情形都成立。例如，思考 (?x ?x) 与 (?y <expression involving ?y>) 在同一框架中的一体化，其中 ?x 和 ?y 未绑定。首先，?x 与 ?y 匹配，所以将 ?x 与 ?y 绑定。然后，?x 与含有 ?y 的表达式匹配。由于 ?x 与 ?y 已经绑定，则是 ?y 就与该表达式匹配。如果将统一器看作为模式变量查找一组数值并使模式相等的工具，则是意味着 ?y 的结果要通过 ?y 与 ?y 表达式形成的等式解得。等式的解并没有通用方法，所以我们会拒绝该情况的绑定，这种情况可以通过 depend-on? 判定。另一方面，我们也不希望排除变量与它自身绑定。例如，思考 (?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))))))
((pair? e)
(or (tree-walk (car e))
(tree-walk (cdr e))))
(else false)))
(tree-walk exp))设计逻辑编程语言的另一个核心问题是数据库中的数据如何存储。在我们的系统中，通过将数据存在在流中实现，存储的每条数据的 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 值是常量标识的模式能够匹配以同样常量标识为名称的规则。因此，需要获取相应名称的规则就是获取与模式起始标识相同名称的规则。基于规则存储的需求，我们将所有规则的名称起始变量存储于另一个流中，并以标识 ? 为下标。
(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 (indexalbe? 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)))如果模式以一个常量标识开头，则能够通过下标取回对应数据。
(deifne (use-index? pat) (constant-symbol? (car pat)))查询系统会用到一些流操作。 stream-append-delayed 和 interleave-delayed 与 stream-append 和 interleave 极为相似，不过前面两个程式参数存在延迟操作的情况。延迟循环操作也是类似的情况。
(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 在查询求值器转换框架流时使用，它能够结合框架结果流，它与之前讲解的 flatmap 类似。不过与 flatmap 不同的是，我们需要通过交织操作累积流，而不是单纯地将流拼接。
(define (stream-flatmap proc s)
(flattern-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 中用于区分特殊形式的委派操作。它们与 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 中用于甄别规则和数据，并添加至数据库中。
(define (assertion-to-be-added? exp)
(eq? (type exp) 'assert!))
(define (add-assertion-body exp) (car (contents exp)))下面是关于 and、or、not 和 lisp-value 语法定义。
(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-disjunct 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 通过调用 query-syntax-process 对表达式中的模式变量进行转化，也就是将 ?symbol 转化为 (? symbol)。按照这种转换方式，(job ?x ?y) 在系统内部将表示为 (job (? x) (? y))。这将提高查询操作的效率，因为这表示当表达式是模式变量时系统能够通过 car 的结果进行判断，而不是从标识中提取字符判断。语法转化通过下列程式实现。
(define (query-syntax-process exp)
(map-over-symbols expand-question-mark exp))
(define (map-over-symbbols 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)))当变量按照上述程式转换后，模式中的变量都将以 ? 开头，并且常量标识只剩下标识部分。
(define (var? exp) (tagged-list? exp '?))
(define (constant-symbol? exp) (symbol? exp))利用下列程式在应用规则期间能够构造唯一变量。规则应用时的唯一标识是一个数字，在每次规则应用时都要递增。
(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))