什么是逻辑编程

什么是逻辑编程？

课程之初我们曾强调，计算机科学处理的是命令式（how to，如何做）知识，而数学处理的是声明式（what is，是什么）知识。事实上，编程语言要求程序员以指明解决特定问题的分步方法的形式来表达知识。另一方面，高级语言在其语言实现中内置了大量方法性知识，使用户不必关心一次指定的计算将如何推进的诸多细节。

包括 Lisp 在内的大多数编程语言，都围绕数学函数的求值来组织。面向表达式的语言（如 Lisp、Fortran 和 Algol）利用了一个”双关”：描述函数值的表达式，同时也可以被解释为计算该值的手段。正因如此，大多数编程语言都强烈偏向单向计算（输入和输出都有明确定义的计算）。然而，也有一些截然不同的编程语言放宽了这种偏向。逻辑编程扩展了这一思想，它将编程的关系式视野与一种称为合一（unification）的强大符号模式匹配结合起来。

这种方法在奏效时，可以成为一种非常强大的编程方式。其部分威力来自这样一个事实：一条”是什么”的事实，可以用来解决许多不同的问题，而这些问题各有不同的”如何做”成分。

示例数据库

在深入了解逻辑编程的细节之前，我们需要一个数据库来把玩。你可以用以下命令加载这个数据库：

> (load "~cs61as/lib/query.scm")
> (initialize-data-base microshaft-data-base)
> (query-driver-loop)

Microshaft 公司的人事数据库包含有关公司员工的断言。以下是关于 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)

除了 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))

数据库还包含这样的断言：哪些种类的职位的人可以做其他哪些种类的职位的工作。例如，计算机奇才既可以做计算机程序员的工作，也可以做计算机技术员的工作：

(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))

输入查询指明了我们要在数据库中寻找匹配某种模式（pattern）的条目。在这个例子中，该模式指定条目由三项组成：第一项是字面符号 job，第二项可以是任意内容，第三项是字面表 (computer programmer)。匹配表中第二项的”任意内容”由模式变量（pattern variable）?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 programmer)

其中 ?type 是表 (programmer)，还匹配数据

(computer)

其中 ?type 是空表 ()。

我们可以这样描述查询语言对简单查询的处理过程：

• 系统先找出查询模式中所有满足该模式的变量赋值——也就是说，找出所有变量的取值集合，使得将模式变量实例化（instantiate，即替换）为这些值后，结果就在数据库中。
• 系统通过列出用满足条件的变量赋值实例化后的查询模式，来回应查询。

注意，如果模式没有变量，查询就简化为确定该模式是否在数据库中。如果是，那么不向任何变量赋值的空赋值，就满足该数据库中这个模式。

(assert! (likes brian potstickers))

(load "~cs61as/lib/query.scm")
(initialize-data-base microshaft-data-base)
(query-driver-loop)

复合查询

简单查询构成了查询语言的原语操作。为了构成复合操作，查询语言提供了组合手段。查询语言之所以是一门逻辑编程语言，原因之一在于：这些组合手段反映了构造逻辑表达式时所用的组合手段——与（and）、或（or）和非（not）。（这里的 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>)

被所有同时满足 <query1> <query2> ... <queryn> 的模式变量取值集合所满足。

与简单查询一样，系统处理复合查询时，先找出所有满足查询的模式变量赋值，然后用这些值显示查询的实例化结果。

另一种构造复合查询的手段是 or。例如，

(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> <query2> ... <queryn> 中至少一个查询的模式变量取值集合所满足。

复合查询也可以用 not 构成。例如，

(and (supervisor ?x (Bitdiddle Ben))
     (not (job ?x (computer programmer))))

会找出所有由 Ben Bitdiddle 管理且不是计算机程序员的人。一般地，

(not <query1>)

被所有不满足 <query1> 的模式变量赋值所满足。

最后一种组合形式叫 lisp-value。当 lisp-value 是模式的第一个元素时，它规定下一个元素是一个 Lisp 谓词，应用于其余（已实例化的）元素作为实参。一般地，

(lisp-value <predicate> <arg1> ... <argn>)

被这样的模式变量赋值所满足：将 <predicate> 应用于实例化后的 <arg1> ... <argn> 的结果为真。例如，要找出所有薪水超过 30000 美元的人，我们可以写

(and (salary ?person ?amount)
     (lisp-value > ?amount 30000))

规则

只要只告诉系统孤立的事实，我们就不可能得到特别有趣的回答。但我们还可以告诉它规则（rule），让它能从一个事实推出另一个事实。例如，如果我们有很多这样的事实：

(mother Eve Cain)

那么我们就可以建立一条关于祖母关系的规则：

(assert! (rule (grandmother ?elder ?younger)
               (and (mother ?elder ?mom)
                    (mother ?mom ?younger) )))

这条规则说的是：如果能找到变量的值使第二部分（条件）为真，那么第一部分（结论）就为真。

再次提醒，抵制住做函数组合的冲动！

(assert! (rule (grandmother ?elder ?younger) ;; WRONG!!!!
               (mother ?elder (mother ?younger)) ))

Mother 不是函数，你不能像这个错误示例试图做的那样去”要某个人的母亲”。相反，正如上面正确的版本那样，你必须建立一个变量（?mom），让它取一个能同时满足我们需要的两条母子关系的值。

在这门语言中，assert!、rule、and、or 和 not 这些词有特殊含义。其他一切都只是可以出现在断言或规则中的普通词。

(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)

更多的规则

下面是一条稍微复杂一点的规则：

(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))

(lives-near ?person (Hacker Alyssa P))

(lives-near ?person-1 ?person-2)

(lives-near (Hacker Alyssa P) (Fect Cy D))
(lives-near (Fect Cy D) (Hacker Alyssa P))

逻辑即程序

我们可以把规则看作一种逻辑蕴含：如果一组模式变量赋值满足规则体，那么它就满足结论。因此，我们可以认为查询语言能够基于规则进行逻辑演绎。以 append 操作为例。Append 可以由以下两条规则刻画：

• 对任何表 y，空表和 y 拼接的结果是 y。
• 对任何 u、v、y 和 z，如果 v 和 y 拼接的结果是 z，那么 (cons u v) 和 y 拼接的结果是 (cons u z)。

为了在我们的查询语言中表达这一点，我们为关系

(append x y z)

定义两条规则，可以把它解释为”x 和 y 拼接成 z”：

(assert! (rule (append () ?y ?y)))
(assert! (rule (append (?u . ?v) ?y (?u . ?z))
         (append ?v ?y ?z)))

第一条规则没有规则体，这意味着结论对 ?y 的任何值都成立。注意第二条规则如何利用点尾记号来命名一个表的 car 和 cdr。

有了这两条规则，我们就可以构造查询来计算两个表的拼接：

;;; Query input:
(append (a b) (c d) ?what)
;;; Query results:
(append (a b) (c d) (a b c d))

更引人注目的是，我们可以用同样的规则来提问：“哪个表拼接到 (a b) 之后会得到 (a b c d)？“做法如下：

;;; Query input:
(append (a b) ?what (a b c d))
;;; Query results:
(append (a b) (c d) (a b c d))

逻辑编程的新东西在于，我们可以把一个”函数”倒着跑！我们可以告诉它答案，拿回问题。但真正的魔法是……

;;; Query input:
(append ?this ?that (a b c d))
;;; Query results:
(append () (a b c d) (a b c d))
(append (a) (b c d) (a b c d))
(append (a b) (c d) (a b c d))
(append (a b c) (d) (a b c d))
(append (a b c d) () (a b c d))

我们还可以要求给出所有拼接成 (a b c d) 的表对！我们可以用逻辑编程计算同一个问题的多个答案！不知怎的，它找到了所有能让我们的查询为真的变量值组合。

append 程序是如何工作的？把它和 Scheme 的 append 比较一下：

(define (append a b)
    (if (null? a)
        b
        (cons (car a) (append (cdr a) b)) ))

和 Scheme 程序一样，逻辑程序也有两种情况：一种是基本情况，此时第一个实参为空。在这种情况下，合并后的表就是第二个被拼接的表。还有一种是递归情况，我们把第一个被拼接的表分成它的 car 和 cdr，把给定的问题归约为把 (cdr a) 拼接到 b 的问题。逻辑程序形式不同，但说的是同一件事。

（正如在祖母例子中，我们必须给母亲一个名字而不是用函数调用，这里我们也必须给 (car a) 一个名字——我们叫它 ?u。）

一句告诫

查询系统在用规则推导上述查询的答案时，可能显得颇有智能。实际上，正如我们将在下一节看到的，系统遵循的是一个在解开规则方面完全确定的算法。遗憾的是，尽管系统在 append 的例子中表现得令人印象深刻，这些一般性方法在更复杂的情况下可能会失效。

append 例子中使用的”倒推”魔法并非总能奏效。让我们看下面这个反转链表的例子。

(assert! (rule (reverse (?a . ?x) ?y)
               (and (reverse ?x ?z)
                    (append ?z (?a) ?y) )))

(assert! (reverse () ()))

这对于 (reverse (a b c) ?what) 有效，但反过来不行；它会陷入无限循环。我们也可以写一个只能反向工作的版本：

(assert! (rule (backward (?a . ?x) ?y)
               (and (append ?z (?a) ?y)
                    (backward ?x ?z) )))

(assert! (backward () ()))

但要想写出一个两个方向都能工作的版本就难得多了。就在我们说话之际，逻辑编程的爱好者们仍在努力突破这一思想的极限，但目前，你仍然需要对台面下的算法有所了解，才能确信你的逻辑程序不会循环。

要点

以下是本小节的要点：

• 在逻辑编程中，我们断言事实并提出问题。
• 断言用表来表示。
• 我们用查询语言从数据库中检索信息。
• 规则允许从一个事实推出另一个事实。
• 我们可以用逻辑编程编写诸如 append 这样的程序！

接下来

进入下一小节，了解查询系统是如何工作的！