4.4 逻辑编程

在本节中，我们将介绍一种称为logic的声明式查询语言，它是专门为本文设计的。在计算机程序的结构和解释中，它是基于Prolog和声明语言的。数据记录表示为方案列表，查询表示为方案值。逻辑解释器是一个完整的实现，它依赖于前一章的Scheme项目。

4.4.1 事实与查询

数据库存储表示系统中事实的记录。查询解释器的目的是检索直接从数据库记录中提取的事实集合，以及使用逻辑推理从数据库中推断出新的事实。逻辑语言中的事实语句由关键字fact后面的一个或多个列表组成。一个简单的事实就是一个列表。一位对美国总统感兴趣的养狗人可能会用逻辑语言记录她收集的狗的家谱，如下：

(fact (parent abraham barack))
(fact (parent abraham clinton))
(fact (parent delano herbert))
(fact (parent fillmore abraham))
(fact (parent fillmore delano))
(fact (parent fillmore grover))
(fact (parent eisenhower fillmore))

每个事实都不是Scheme表达式中的过程应用程序，而是声明的关系。第一个事实宣称:“狗亚伯拉罕是巴拉克的父母。”关系类型不需要预先定义。不应用关系，而是与查询匹配。

查询也由一个或多个列表组成，但以关键字查询开始。查询可以包含变量，这些变量是以问号开头的符号。变量被查询解释器匹配为事实：

(query (parent abraham ?child))
Success!
child: barack
child: clinton

查询解释器的响应是Success！以指示查询与某些事实相匹配。下面几行显示了将查询与数据库中的事实相匹配的变量?子变量的替换。

复合事实。事实还可能包含变量和多个子表达式。一个多重表达的事实以结论开始，然后是假设。要使结论为真，必须满足所有假设：

(fact <conclusion> <hypothesis0> <hypothesis1> ... <hypothesisN>)

例如，关于孩子的事实可以基于数据库中已经存在的关于父母的事实来声明：

(fact (child ?c ?p) (parent ?p ?c))

以上事实可以解读为：?c是p的子结点，前提是p是c的父结点一个查询，现在可以参考这个事实：

(query (child ?child fillmore))
Success!
child: abraham
child: delano
child: grover

上面的查询要求查询解释器将定义child的事实与关于fillmore的各种父事实结合起来。该语言的用户不需要知道这些信息是如何组合的，只需要知道结果具有特定的形式。这取决于查询解释器来证明(亚伯拉罕·菲尔莫尔)是真实的，给出了可用的事实。

查询不需要包含变量；它可能只是验证一个事实：

(query (child herbert delano))
Success!

不匹配任何事实的查询将返回失败：

(query (child eisenhower ?parent))
Failed.

否定我们可以通过使用特殊关键字not来检查某些查询是否与任何事实不符：

(query (not <relation>))

如果<关系>失败则查询成功，如果<关系>成功则查询失败。这种想法被称为否定失败。

(query (not (parent abraham clinton)))
Failed.
(query (not (parent abraham barack)))
Failed.

有时，作为失败的否定可能是违反直觉的，人们可能期望否定的工作方式。考虑以下查询的结果：

(query (not (parent abraham ?who)))

为什么这个查询失败了？当然，有许多符号可以被绑定？谁应该为谁持有。然而，否定的步骤表明，我们首先检查关系(父亚伯拉罕?谁)。这种关系之所以成功，是因为谁又能与巴拉克或克林顿捆绑在一起。因为这段关系成功了，所以对这段关系的否定必然失败。

4.4.2 递归事实

逻辑语言还允许递归事实。也就是说，事实的结论可能依赖于包含相同符号的假设。例如，祖先关系是用两个事实定义的。如果a是y的父代，或者a是y的父代，那么a就是y的父代：

(fact (ancestor ?a ?y) (parent ?a ?y))
(fact (ancestor ?a ?y) (parent ?a ?z) (ancestor ?z ?y))

一个简单的查询就可以列出herbert的所有祖先：

(query (ancestor ?a herbert))
Success!
a: delano
a: fillmore
a: eisenhower

复合查询。一个查询可能有多个子表达式，在这种情况下，必须通过向变量赋值符号来同时满足所有的子表达式。如果一个变量在查询中出现多次，那么它必须在每个上下文中取相同的值。下面的查询可以找到赫伯特和巴拉克的祖先：

(query (ancestor ?a barack) (ancestor ?a herbert))
Success!
a: fillmore
a: eisenhower

递归事实可能需要很长的推理链来匹配查询和数据库中现有的事实。例如，为了证明这个事实(祖先菲尔莫尔·赫伯特)，我们必须依次证明以下每一个事实：

(parent delano herbert)       ; (1), a simple fact
(ancestor delano herbert)     ; (2), from (1) and the 1st ancestor fact
(parent fillmore delano)      ; (3), a simple fact
(ancestor fillmore herbert)   ; (4), from (2), (3), & the 2nd ancestor fact

这样，只要查询解释器能够发现，一个事实就可以暗示大量的额外事实，甚至无限多。

分层的事实。到目前为止，每个事实和查询表达式都是一个符号列表。此外，事实列表和查询列表可以包含列表，提供一种表示分层数据的方法。每只狗的颜色可以与名字一起存储一个额外的记录：

(fact (dog (name abraham) (color white)))
(fact (dog (name barack) (color tan)))
(fact (dog (name clinton) (color white)))
(fact (dog (name delano) (color white)))
(fact (dog (name eisenhower) (color tan)))
(fact (dog (name fillmore) (color brown)))
(fact (dog (name grover) (color tan)))
(fact (dog (name herbert) (color brown)))

查询可以清晰地表达层次事实的完整结构，或者它们可以将变量匹配到整个列表：

(query (dog (name clinton) (color ?color)))
Success!
color: white
(query (dog (name clinton) ?info))
Success!
info: (color white)

数据库的很大一部分功能在于查询解释器能够将多种事实连接到一个查询中。下面的查询可以找到所有的狗对，其中一个是另一个的祖先，他们共享一个颜色：

(query (dog (name ?name) (color ?color))
       (ancestor ?ancestor ?name)
       (dog (name ?ancestor) (color ?color)))
Success!
name: barack color: tan ancestor: eisenhower
name: clinton color: white ancestor: abraham
name: grover color: tan ancestor: eisenhower
name: herbert color: brown ancestor: fillmore

变量可以引用层级记录中的列表，也可以使用点表示法。点后面的变量与事实列表的其余部分相匹配。虚线列表可以出现在事实或查询中。下面的例子通过列出狗的祖先链来构建狗的谱系。年轻的巴拉克跟随着一群尊敬的总统小狗：

(fact (pedigree ?name) (dog (name ?name) . ?details))
(fact (pedigree ?child ?parent . ?rest)
      (parent ?parent ?child)
      (pedigree ?parent . ?rest))
(query (pedigree barack . ?lineage))
Success!
lineage: ()
lineage: (abraham)
lineage: (abraham fillmore)
lineage: (abraham fillmore eisenhower)

声明式或逻辑编程可以以显著的效率表达事实之间的关系。例如，如果我们想表示两个列表可以通过追加来形成一个更长的列表，其中包含第一个列表的元素，然后是第二个列表的元素，那么我们就声明两个规则。首先，一个基本案例声明，将一个空列表添加到任何列表都会得到这个列表：

(fact (append-to-form () ?x ?x))

使用这两个事实，查询解释器可以计算附加任意两个列表的结果：

(query (append-to-form (a b c) (d e) ?result))
Success!
result: (a b c d e)

此外，它还可以计算所有可能的左链表对和右链表对，这些对可以附加形成链表(a b c d e)：

(query (append-to-form ?left ?right (a b c d e)))
Success!
left: () right: (a b c d e)
left: (a) right: (b c d e)
left: (a b) right: (c d e)
left: (a b c) right: (d e)
left: (a b c d) right: (e)
left: (a b c d e) right: ()

尽管我们的查询解释器看起来相当智能，但我们将看到，它通过一个重复多次的简单操作找到这些组合：匹配环境中包含变量的两个列表。