转载自：https://mp.weixin.qq.com/s/r6CcuC8n7iRaQSzShovl5w
本章有两个主要目标：
1.在Prolog中引入递归定义。
2.表明Prolog程序的声明性含义与其程序含义之间可能存在不匹配。
1 递归定义
谓词可以递归定义。粗略地说，如果谓词中的一个或多个规则引用了自己，则它是递归定义的。
示例1：Eating
考虑以下知识库：
is_digesting(X,Y) :- just_ate(X,Y).
is_digesting(X,Y) :-
just_ate(X,Z),
is_digesting(Z,Y).
just_ate(mosquito,blood(john)).
just_ate(frog,mosquito).
just_ate(stork,frog).
乍一看，这似乎很普通：这只是一个包含三个事实和两个规则的知识库。但是is_digesting / 2谓词的定义是递归的。请注意，is_digesting / 2是（至少部分地）根据自身定义的，因为is_digesting / 2函子同时出现在第二条规则的头部和规则体中。但是，至关重要的是，这种循环性存在“逃离”的危险。这是由出现在第一条规则中的just_ate / 2谓词提供的。 （重要的是，第一条规则的规则体未提及is_digesting / 2。）现在，让我们考虑一下此定义的声明性和程序性含义。
“声明性”一词用于谈论Prolog知识库的逻辑含义。也就是说，Prolog知识库的声明性含义只是“它说了什么”，或者“如果我们将其理解为逻辑语句的集合，则意味着什么”。而且此递归定义的声明性含义非常简单。第一个子句（转义子句，即非递归子句，或者通常称为基子句）只是说：如果X刚吃掉Y，那么X现在正在消化Y。这显然是一个明智的定义。
那么第二个子句，即递归子句呢？这就是说：如果X刚吃掉Z并且Z在消化Y，那么X也在消化Y。同样，这显然是一个明智的定义。
因此，现在我们知道了此递归定义的含义，但是当我们提出实际上需要使用该定义的查询时会发生什么呢？也就是说，此定义实际上是做什么的？要使用正常的Prolog项，其程序含义是什么？
这也是相当简单的。基本规则类似于我们所见过的所有早期规则。也就是说，如果我们询问X是否正在消化Y，那么Prolog可以使用此规则来问一个问题：X刚刚吃了Y吗？
递归子句呢？这为Prolog提供了另一种确定X是否正在消化Y的策略：它可以尝试找到一些Z，使得X刚吃掉Z，而Z正在消化Y。也就是说，该规则使Prolog将任务分解为两个子任务。希望这样做最终会导致一些简单的问题，这些问题只需在知识库中查找答案即可解决。下图总结了这种情况：
让我们看看它是如何工作的。如果我们构成查询：
?-is_digesting(stork,mosquito).
然后Prolog如下工作。首先，它尝试利用列出的与is_digesting有关的第一条规则；即基本规则。这表明如果X刚吃了Y，X正在消化Y。通过将X与stork和Y与mosquito合一，它实现了以下目标：
no
但是知识库没有包含stork刚刚吃过mosquito的信息，因此这种尝试失败了。因此，Prolog接下来尝试利用第二条规则。通过将X与stork和Y与mosquito合一，可以实现以下目标：
just_ate(stork,Z),
is_digesting(Z,mosquito).
也就是说，为了显示is_digesting（stork，mosquito），Prolog需要找到Z的值，这样，首先，
just_ate(stork,Z).
其次，
is_digesting(Z,mosquito).
Z的值就是frog。立刻
just_ate(stork,frog).
将成功，因为此事实已列在知识库中。并推论
is_digesting(frog,mosquito).
几乎一样简单，因为is_digesting / 2的第一子句将此目标简化为
just_ate(frog,mosquito).
这是知识库中列出的事实。
好吧，这是我们第一个递归规则定义的例子。我们将学到更多有关它们的信息，但请立即提出一个非常实用的说明。希望很明显，当您编写一个递归谓词时，它应始终至少包含两个子句：一个基本子句（该子句在某个时候停止递归）和一个包含递归的子句。如果您不这样做，Prolog可能会陷入无休止的无用计算序列。例如，下面是一个非常简单的递归规则定义示例：
p:-p.
而已。没有其他的。简单而美丽。从声明性的角度来看，这是一个非常明智的定义（即使很无聊）：它说“如果属性p成立，那么属性p成立”。你不能对此争论。
但是从程序角度来看，这是一个非常危险的规则。实际上，我们这里有最终的危险递归规则：双方完全一样，并且没有让我们脱离的基本子句。考虑一下当我们提出以下查询时会发生什么：
?- p.
Prolog问自己：“我怎么证明p？”的意思是：“嘿，我有一个规则！要证明p，我只需要证明p！”。因此，它再次问自己：“我怎么证明p？”并且意识到，“嘿，我有一个规则！要证明p，我只需要证明p！”。因此，它问自己（再次）：“我怎么证明p？”并且意识到，“嘿，我有一个规则！要证明p，我只需要证明p！”，依此类推。
如果您进行此查询，那么Prolog不会回答您：它将继续前进，在无休止的搜索中拼命地运行。也就是说，它不会终止，您必须中断它。当然，如果使用跟踪，则可以一次完成一个步骤，直到厌倦了观看Prolog循环。
示例2：后代
现在我们对Prolog中涉及的递归有所了解，现在该问为什么它如此重要了。实际上，这是一个可以在多个层面上回答的问题，但是现在，让我们保持实用性。因此：在编写有用的Prolog程序时，递归定义真的那么重要吗？如果是这样，为什么？
让我们考虑一个例子。假设我们有一个知识库，记录有关child关系的事实：
child(bridget,caroline).
child(caroline,donna).
也就是说，卡罗琳（Caroline）是布里奇特（Bridget）的孩子，唐娜（Donna）是卡罗琳（Caroline）的孩子。现在假设我们希望定义后代关系。也就是说，是孩子，或孩子的子女，或孩子的子女的子女，等等。这是第一次尝试这样做。我们可以在知识库中添加以下两个非递归规则：
descend(X,Y) :- child(X,Y).
descend(X,Y) :- child(X,Z),
child(Z,Y).
现在，很明显，这些定义在一定程度上可行，但是它们显然受到限制：它们仅定义了两代或更少的后代。上面的知识库是可以的，但是假设我们获得了关于子关系的更多信息，并且我们将事实child列表扩展为：
child(anne,bridget).
child(bridget,caroline).
child(caroline,donna).
child(donna,emily).
现在，我们的两个规则不足。例如，如果我们提出查询
?- descend(anne,donna).
或
?- descend(bridget,emily).
我们得到的答案是false，这不是我们想要的。当然，我们可以通过添加以下两个规则来“解决”此问题：
descend(X,Y) :- child(X,Z_1),
child(Z_1,Z_2),
child(Z_2,Y).
descend(X,Y) :- child(X,Z_1),
child(Z_1,Z_2),
child(Z_2,Z_3),
child(Z_3,Y).
但是，面对现实，这很笨拙而且很难阅读。此外，如果我们添加更多child事实，则随着我们事实child列表的增加，我们很容易发现自己必须添加越来越多的规则，这些规则如下：
descend(X,Y) :- child(X,Z_1),
child(Z_1,Z_2),
child(Z_2,Z_3),
.
.
.
child(Z_17,Z_18).
child(Z_18,Z_19).
child(Z_19,Y).
这不是特别令人愉快（或明智）的方法！
但是我们根本不需要这样做。我们完全可以避免必须使用更长的规则。以下递归谓词定义完全按照我们想要的方式修复了所有问题：
descend(X,Y) :- child(X,Y).
descend(X,Y) :- child(X,Z),
descend(Z,Y).
这是什么意思?基本子句的声明性含义是：如果Y是X的子代(child)，则Y是X的后代(descendant)。显然是明智的。那么递归子句呢？它的声明性含义是：如果Z是X的子代(child)，并且Y是Z的后代(descendant)，则也Y是X的后代(descendant)。同样，这是正确的。
现在，让我们通过一个示例来看看此递归谓词的程序含义。当我们提出查询时会发生什么：
descend(anne,donna)
Prolog首先尝试第一个规则。规则开头的变量X与anne合一，Y与donna合一，Prolog尝试证明的下一个目标是
child(anne,donna)
但是，此尝试失败了，因为知识库既不包含事实child(anne, donna)，也不包含任何可以推断出事实的规则。因此，Prolog回溯并寻找证明的另一种方法descend(anne, donna)。它在知识库中找到第二条规则，现在具有以下子目标：
child(anne,_633),
descend(_633,donna).
Prolog采用了第一个子目标，并尝试将其与知识库中的某些东西合一起来。它发现事实child（anne，bridget），变量_633被实例化为bridget。现在满足了第一个子目标，Prolog移至第二个子目标。它必须证明
descend(bridget, donna)
这是谓词descend/ 2的第一个递归调用。和前面一样，Prolog从第一个规则开始，但是失败了，因为目标
child(bridget, donna)
无法证明。回溯，Prolog发现有第二种可能性需要检查descend(bridget, donna)，即第二条规则，它再次为Prolog提供了两个新的子目标：
child(bridget, _1785),
descend(_1785, donna).
第一个变量可以与知识库的事实child(bridget,caroline)合一，因此变量_1785用caroline实例化。下一个Prolog试图证明
descend(caroline, donna).
这是谓词descend/ 2的第二次递归调用。和以前一样，它首先尝试第一个规则，从而获得以下新目标：
child(caroline, donna)
这次Prolog成功，因为child(caroline, donna)是数据库中的事实。 Prolog找到了目标descend(caroline, donna)（第二个递归调用）的证明。但是，这意味着descend(bridget, donna)（第一个递归调用）也成立，这意味着我们原始的查询descend(anne, donna)也成立。
这是查询descend(anne, donna)的搜索树。确保您了解它与本文中的讨论有何关系；也就是说，Prolog在尝试证明此查询时如何遍历此搜索树。
从此示例中可以明显看出，无论我们添加多少代子代，我们都将始终能够计算出后代关系。也就是说，递归定义既通用又紧凑：它包含非递归规则中的所有信息，此外还有更多信息。非递归规则仅将后代概念定义为固定的世代数：如果我们想完全捕获该概念，我们将需要写下无数个非递归规则，这当然是不可能的。但是，实际上，这就是递归规则为我们所做的事情：它将处理任意数量的世代所需的信息捆绑到仅三行代码中。
递归规则非常重要。它们能够将大量信息打包成紧凑的形式，并以自然的方式定义谓词。作为Prolog程序员，您将进行的大部分工作都涉及编写递归规则。
示例3：后继者
在上一章中，我们指出通过合一构建结构是Prolog编程中的关键思想。既然我们知道了递归，我们可以对此进行更有趣的说明。
如今，当人类写数字时，他们通常使用十进制表示法（0、1、2、3、4、5、6、7、8、9、10、11、12等），但是您可能知道，还有许多其他符号。例如，由于计算机硬件通常基于数字电路，因此计算机通常使用二进制表示法来表示数字（0、1、10、11、100、101、110、111、1000等），因为0可以是实现为关闭开关，将1设为打开。其他文化使用不同的系统。例如，古代的巴比伦人使用的是60为底的系统，而古古罗马人使用了一种特别的系统（I，II，III，IV，V，VI，VII，VIII，IX，X）。最后一个示例表明符号问题可能很重要。如果您不相信这一点，请尝试找出一种系统的方式来进行罗马符号的长除法。您会发现，这是一项令人沮丧的任务。显然，罗马人有一群专门从事此工作的专业人士（现代会计师的类比）。
嗯，这是数字的另一种写法，有时在数学逻辑中使用。它仅使用四个符号：0，succ和左右括号。这种数字风格由以下归纳定义：
1. 0 is a numeral
2. If X is a numeral, then so is succ(X).
很显然，succ可以理解为后继者的缩写。也就是说，succ(X)表示通过在X表示的数字上加一而获得的数字。因此，这是一个非常简单的表示法：它只是说0是一个数字，而所有其他数字都是通过在前面堆叠succ符号来构建的。（实际上，由于这种简单性，它已用于数学逻辑。尽管用这种表示法进行家族记述作为表示法并不是一件令人愉快的事情，但是用事实证明这很容易。）
现在，到了这一阶段，我们应该可以将这个定义转换为Prolog程序了。下面的知识库可以做到这一点：
numeral(0).
numeral(succ(X)):- numeral(X).
因此，如果我们提出类似的查询
numeral(succ(succ(succ(0)))).
我们得到的答案trun.
但是我们可以做一些更有趣的事情。考虑当我们发出以下查询时会发生什么：
numeral(X).
也就是说，我们说的是“OK，请给我一些数字”。然后，我们可以与Prolog进行以下对话：
X = 0 ;
X = succ(0) ;
X = succ(succ(0)) ;
X = succ(succ(succ(0))) ;
X = succ(succ(succ(succ(0)))) ;
X = succ(succ(succ(succ(succ(0))))) ;
X = succ(succ(succ(succ(succ(succ(0)))))) ;
X = succ(succ(succ(succ(succ(succ(succ(0))))))) ;
X = succ(succ(succ(succ(succ(succ(succ(succ(0))))))))..
是的，Prolog在数：但真正重要的是它的工作方式。很简单，它在递归定义中回溯，并实际上使用合一来构建数字。这是一个有启发性的示例，理解它很重要。最好的方法是坐下来尝试一下，然后打开跟踪。
构建和绑定。递归，合一和证明搜索。这些想法是Prolog编程的核心。每当我们必须生成或分析递归结构化的对象（例如这些数字）时，这些想法的相互作用便使Prolog成为强大的工具。例如，在下一章中，我们将介绍表，这是一个非常重要的递归数据结构，并且我们将看到Prolog是一种自然的表处理语言。许多应用程序（计算语言学是一个很好的例子）大量使用了递归结构化的对象，例如树和特征结构。因此，事实证明Prolog在此类应用中很有用也就不足为奇了。
示例4：加法
作为最后一个示例，让我们看看是否可以使用在上一节中介绍的数字表示形式进行简单的算术运算。让我们尝试定义加法。也就是说，我们要定义一个谓词add / 3，当给定两个数字作为第一个和第二个参数时，返回将它们加起来作为第三个参数的结果。例如：
?- add(succ(succ(0)), succ(succ(0)), succ(succ(succ(succ(0))))).
true
?- add(succ(succ(0)),succ(0),Y).
Y = succ(succ(succ(0)))
有两件事需要注意：
1.只要第一个参数为0，第三个参数就必须与第二个参数相同：
?- add(0,succ(succ(0)),Y).
Y = succ(succ(0))
?- add(0,0,Y).
Y = 0
我们要在基本子句中使用这种情况。
2. 假设我们要将两个数字X和Y相加（例如succ(succ(succ(0)))和succ(succ(0))），并且X不为0。现在，如果X1是数字它的一个succ函子小于X（在我们的示例中为succ(succ(0))），如果我们知道将X1和Y相加的结果（我们称之为Z）（即succ(succ(succ(succ( 0))))），那么很容易计算将X和Y相加的结果：我们只需要向Z添加一个succ-functor。这就是我们想用递归子句表达的内容。
这是谓词定义，恰好表达了我们刚才所说的内容：
add(0,Y,Y).
add(succ(X),Y,succ(Z)) :-
add(X,Y,Z).
那么，如果我们给Prolog这个谓词定义然后问：
?- add(succ(succ(succ(0))), succ(succ(0)), R).
让我们逐步介绍Prolog处理此查询的方式。查询的跟踪和搜索树如下所示。
第一个参数不为0，这意味着只能使用add / 3的第二个子句。这导致add / 3的递归调用。最外层的succ函子被剥离掉原始查询的第一个参数，结果成为递归查询的第一个参数。第二个参数不变地传递给递归查询，而递归查询的第三个参数是一个变量，在下面给出的跟踪中为内部变量_G648。请注意，_G648尚未实例化。但是，它与R（我们在原始查询中用作第三个参数的变量）共享值，因为当查询与第二子句的开头合一时，R被实例化为succ（_G648）。但这意味着R不再是一个完全无法实例化的变量。现在它是一个复合项，其变量带有（未实例化的）变量。
接下来的两个步骤基本相同。每走一步，第一个参数就会减小一层；下面给出的跟踪和搜索树都很好地显示了这一点。同时，在每个步骤中将succ函子添加到R中，但始终未实例化最里面的变量。在第一次递归调用之后，R是succ（_G648）。在第二次递归调用之后，_G648用succ（_G650）实例化，因此R是succ（succ（_G650）。在第三次递归调用之后，_G650用succ（_G652）实例化，因此R变成succ（succ（succ（ _G652）））。搜索树逐步显示了此实例。
在这个阶段，所有的succ函子都被剥离了第一个参数，我们可以应用基本子句。第三个参数等同于第二个参数，因此最终填充了复合项R中的“ hole”（未实例化的变量），我们已经完成了。这是我们查询的完整轨迹：
Call: (6) add(succ(succ(succ(0))), succ(succ(0)), R)
Call: (7) add(succ(succ(0)), succ(succ(0)), _G648)
Call: (8) add(succ(0), succ(succ(0)), _G650)
Call: (9) add(0, succ(succ(0)), _G652)
Exit: (9) add(0, succ(succ(0)), succ(succ(0)))
Exit: (8) add(succ(0), succ(succ(0)), succ(succ(succ(0))))
Exit: (7) add(succ(succ(0)), succ(succ(0)),
succ(succ(succ(succ(0)))))
Exit: (6) add(succ(succ(succ(0))), succ(succ(0)),
succ(succ(succ(succ(succ(0))))))
这是搜索树：
2 规则排序，目标排序和终止
Prolog是创建逻辑编程语言的第一次合理成功的尝试。底层逻辑编程是一种简单的（和诱人的）愿景：程序员的任务只是描述问题。程序员应（用逻辑语言）写下描述性状态的说明性规范（即：知识库）。程序员不必告诉计算机该怎么做。要获取信息，他或她只是问一些问题。逻辑编程系统负责确定如何获得答案。
嗯，就是这个主意，很明显，Prolog已朝这个方向采取了一些重要步骤。但是Prolog并不是一种完整的逻辑编程语言，请重复一遍。如果仅考虑Prolog程序的声明性含义，那么您将处在非常艰难的时期。正如我们在上一章中学到的，Prolog有一种非常具体的方法来解决查询的问题：它从上至下搜索知识库，从左至右搜索子句，并使用回溯来从错误的选择中恢复。这些程序方面对您进行查询时实际发生的事情具有重要影响。我们已经看到了程序和程序之间不匹配的一个生动例子。 知识库的声明性含义（还记得p：-p程序吗？），正如我们现在将要看到的，很容易定义知识库（从逻辑上读取）描述相同的情况，但是行为却截然不同。让我们考虑一下。
回忆一下我们之前的子代程序(我们称其为descend1.pl):
child(anne,bridget).
child(bridget,caroline).
child(caroline,donna).
child(donna,emily).
descend(X,Y) :- child(X,Y).
descend(X,Y) :- child(X,Z),
descend(Z,Y).
我们将对其进行更改，然后将结果称为descend2.pl：
child(anne,bridget).
child(bridget,caroline).
child(caroline,donna).
child(donna,emily).
descend(X,Y) :- child(X,Z),
descend(Z,Y).
descend(X,Y) :- child(X,Y).
我们要做的就是更改规则顺序。因此，如果将程序作为纯粹的逻辑定义来阅读，则没有任何改变。但是这种变化会引起程序上的差异吗？是的，但是没什么大不了的。例如，如果您遍历示例，您将看到descend1.pl找到的第一个解决方案是
X = anne
Y = bridget
而descend2.pl找到的第一个解决方案是
X = anne
Y = emily
但是（您应该检查）这两个程序生成的答案完全相同，它们只是以不同的顺序找到它们。这是一个普遍的观点。粗略地讲（我们将在后面进行说明），更改Prolog程序中的规则顺序不会更改（直到找到解决方案的顺序）程序的行为。
让我们继续前进。我们将对descend2.pl进行一个小的更改，并将结果称为descend3.pl：
child(anne,bridget).
child(bridget,caroline).
child(caroline,donna).
child(donna,emily).
descend(X,Y) :- descend(Z,Y),
child(X,Z).
descend(X,Y) :- child(X,Y).
注意区别。在这里，我们更改了规则中的目标顺序，而不是规则顺序。现在，再次，如果我们将程序作为纯粹的逻辑定义来读取，则没有任何改变。它与前两个版本的含义相同。但是这次程序的行为发生了巨大变化。例如，如果您构成查询
descend(anne, emily).
您将收到一条错误消息（“超出本地堆栈”，或类似的消息）。 Prolog正在循环。为什么？好吧，为了满足查询的descend(anne, emily)，Prolog使用了第一条规则。这意味着其下一个目标将是满足查询
descend(W1, emily)
对于一些新变量W1。但是要实现这个新目标，Prolog再次必须使用第一个规则，这意味着其下一个目标将是
descend(W2, Emily)
对于一些新变量W2。当然，这又意味着它的下一个目标将是descend(W3, emily)，然后descend(W4, emily)，依此类推。也就是说，目标顺序的变化（乍一看是无害的）导致了程序灾难。为了使用标准项，我们在这里有一个左递归规则的经典示例，也就是一条规则，其中主体的最左边的项与规则的头部相同（对变量进行取模）。如我们的示例所示，这样的规则很容易引起非终止计算。目标秩序，尤其是左递归，是所有非终结性邪恶的根源。
但是，正如我们前面所说的，我们需要对规则排序做一个小小的警告。前面我们说过，规则排序只会更改找到解决方案的顺序。但是，如果我们正在使用非终止程序，则可能并非如此。要看到这一点，请考虑我们descend?.pl程序的第四个（也是最后一个）变体，即descend4.pl：
child(anne,bridget).
child(bridget,caroline).
child(caroline,donna).
child(donna,emily).
descend(X,Y) :- child(X,Y).
descend(X,Y) :- descend(Z,Y),
child(X,Z).
该程序是与descend3.pl其规则顺序相反。现在（再次），该程序具有与其他变体相同的声明性含义，但在程序上与它的亲戚也有所不同。首先，也是最明显的是，它在程序上与descend1.pl和descend2.pl完全不同。特别是，由于它包含左递归规则，因此此新程序不会在某些输入时终止。例如（就像descend3.pl一样），当我们构成查询时，此新程序不会终止
descend(anne, emily).
但是descend4.pl在程序上与descend3.pl不同。规则顺序反转确实有所作为。例如，如果我们构成查询，那么descend3.pl将不会终止
descend(anne, bridget).
但是，在这种情况下，descend4.pl将终止，因为规则反转使它能够应用非递归规则并暂停。因此，当涉及到非终止程序时，规则顺序的更改可能会导致发现一些额外的解决方案。尽管如此，在程序上真正重要的是目标排序而不是规则排序。为了确保终止，我们需要注意规则主体中目标的顺序。修补规则顺序并不能解决终止问题的根源-充其量只能提供一些额外的解决方案。
总而言之，我们的四个变体后代程序都是Prolog知识库，它们描述的情况完全相同，但行为却有所不同。 descend1.pl和descend2.pl之间的行为差异（仅在规则排序方式上有所不同）相对较小：它们生成相同的解决方案，但顺序不同。但是，descend3.pl和descend4.pl在程序上与它们前的另两个很不同，这是因为它们在目标排序方式上与它们不同。特别是，这两个变体都包含左递归规则，在两种情况下，这都会导致非终止行为。规则顺序在descend3.pl和descend4.pl之间的变化仅 意味着在某些情况下，descend4.pl将终止，而descend3.pl不会终止。
对于产生有效的Prolog程序的实用性，我们的讨论会有什么影响？最好是说以下几点。通常，您可以通过声明式思考（即，通过准确描述问题的方式进行思考）来获得有关如何编写程序的总体思路（全局）。这是一种解决问题的极好方法，当然也是与逻辑编程精神保持一致的一种方法。但是，一旦完成此操作，就需要考虑Prolog如何与您编写的知识库一起使用。特别是，为了确保终止，您需要检查给定的目标顺序是否合理。基本的经验法则是，永远不要将与头部给出的目标相同（模变量名）的东西写为规则体的最左目标。而是将此类目标（触发递归调用）尽可能地朝尾巴的右侧放置。也就是说，将它们放在测试各种（非递归）终止条件的目标之后。这样做为Prolog提供了运行上的机会，可以通过如此的递归定义的方式以找到解决方案。
3 练习
练习3.1 在本文中，我们讨论了谓词
descend(X,Y) :- child(X,Y).
descend(X,Y) :- child(X,Z),
descend(Z,Y).
假设我们重新定义该谓词如下：
descend(X,Y) :- child(X,Y).
descend(X,Y) :- descend(X,Z),
descend(Z,Y).
这会有问题吗？
练习3.2 您知道这些木制的俄罗斯玩偶（Matryoshka玩偶）中较小的包含在较大的木制娃娃中吗？这是示意图：
首先，使用谓词directIn / 2编写一个知识库，该谓词对哪个娃娃直接包含在另一个娃娃中进行编码。然后，定义一个in / 2的递归谓词，告诉我们哪个玩偶（直接或间接）包含在其他哪个玩偶中。例如，in（katarina，natasha）中的查询应评估为true，而in（olga，katarina）中的查询应失败。
练习3.3 我们具有以下知识库：
directTrain(saarbruecken,dudweiler).
directTrain(forbach,saarbruecken).
directTrain(freyming,forbach).
directTrain(stAvold,freyming).
directTrain(fahlquemont,stAvold).
directTrain(metz,fahlquemont).
directTrain(nancy,metz).
也就是说，该知识库包含有关城镇的事实，这些城镇可以乘坐直达火车往返。但是，当然，我们可以通过将火车直行链接在一起来进一步旅行。写一个递归谓词travelFromTo/2，告诉我们何时可以乘火车在两个城镇之间旅行。例如，当给出查询时
travelFromTo(nancy, saarbruecken).
它应该回答是。
练习3.5 二叉树是所有内部节点都有两个孩子的树。最小的二叉树仅包含一个叶节点。我们将叶子节点表示为leaf（Label）。例如，leaf（3）和leaf（7）是叶节点，因此是小的二叉树。给定两个二叉树B1和B2，我们可以使用函子tree/ 2将它们合并为一个二叉树，如下所示：tree（B1，B2）。因此，从叶子leaf（1）和leaf（2）中，我们可以构建二叉树tree（leaf（1），leaf（2））。从二叉树tree（leaf（1），leaf（2））和leaf（4）中，我们可以构建二叉树tree（tree（leaf（1），leaf（2）），leaf（4））。
现在，定义一个谓词swap / 2，它生成二叉树的镜像，这是它的第一个参数。例如：
?- swap(tree(tree(leaf(1), leaf(2)), leaf(4)),T).
T = tree(leaf(4), tree(leaf(2), leaf(1))).
true
4 实践环节
到现在为止，您应该对编写和运行基本的Prolog程序感到更自在。在这个实践环节中，我们首先建议两个系列的键盘练习，它们将帮助您熟悉Prolog中的递归定义，然后为您提供一些要解决的编程问题。
首先，键盘练习。由于递归编程对于Prolog如此重要，因此重要的是您必须牢牢掌握它所涉及的内容。特别重要的是，了解使用递归定义时变量实例化的过程，并且理解为什么目标在规则中的顺序可以在终止和非终止之间产生区别，这一点很重要。所以：
1.加载descend1.pl，打开跟踪，然后键入查询descend(anne, emily)。算出Prolog找出答案所需的步骤（即，您必须按回车键几次）。现在关闭跟踪并键入查询descend(X, Y)。有多少个答案？
2.加载descend2.pl。这是descend1.pl的变体，规则顺序相反。重复您对descend1.pl执行的跟踪，然后比较结果。
3.加载descend3.pl。这是descend2.pl的变体，其中递归规则内的目标顺序已切换，从而产生了左递归规则。因此，即使对于诸如descend(anne, bridget)之类的简单查询，Prolog也不会终止。使用trace逐步完成一个示例，以确认这一点。
4.加载descend4.pl。这是通过切换规则顺序获得的Descend3.pl的变体。因此，descend4.pl还包含一个左递归规则，并且不会在所有输入上终止。但是它确实在某些输入上终止，而descend3.pl没有。它会找到哪些其他解决方案？
正如我们在本文中所说，目标排序而非规则排序才是真正意义上的程序。但是对于非终止程序，规则顺序更改可能会产生意想不到的效果。回顾文本中讨论的后继程序(我们将其命名为numeral1.pl):
numeral(0).
numeral(succ(X)) :- numeral(X).
让我们交换两个子句的顺序，然后将结果命名为numeric2.pl：
numeral(succ(X)) :- numeral(X).
numeral(0).
显然，该程序的声明性或逻辑性内容与早期版本完全相同。但是，程序上的区别是什么？
1.创建一个包含numerical2.pl的文件，加载它，并研究如果我们对特定数字进行查询会发生什么情况。例如，假设我们问：
numeral(succ(succ(succ(0)))).
numeral1.pl和numeral2.pl在此类输入上的行为是否相同？
2.其次，看一下我们尝试生成数字时会发生什么，也就是说，假设我们构成查询
numeral(X).
程序显示相同的行为吗？
这里有一些程序供您尝试。
1.想象以下知识库描述了一个迷宫。事实决定了哪些点是连接的，也就是说，您可以一步一步从哪些点到达其他哪些点。此外，假设所有路径都是单向街道，那么您只能沿一个方向行走。因此，您可以从点1到达点2，但反之则不行。
connected(1,2).
connected(3,4).
connected(5,6).
connected(7,8).
connected(9,10).
connected(12,13).
connected(13,14).
connected(15,16).
connected(17,18).
connected(19,20).
connected(4,1).
connected(6,3).
connected(4,7).
connected(6,11).
connected(14,9).
connected(11,15).
connected(16,12).
connected(14,17).
connected(16,19).
写一个谓词path/2，告诉您将上述知识库中给出的连接链接在一起时，可以从迷宫中的哪些点到达其他点。您能从第5点到达第10点吗？从第1点开始，您还能到达哪一点？从第13点可以到达哪些点？
2.我们获得以下旅行信息知识库：
byCar(auckland,hamilton).
byCar(hamilton,raglan).
byCar(valmont,saarbruecken).
byCar(valmont,metz).
byTrain(metz,frankfurt).
byTrain(saarbruecken,frankfurt).
byTrain(metz,paris).
byTrain(saarbruecken,paris).
byPlane(frankfurt,bangkok).
byPlane(frankfurt,singapore).
byPlane(paris,losAngeles).
byPlane(bangkok,auckland).
byPlane(singapore,auckland).
byPlane(losAngeles,auckland).
编写谓词travel / 2，它确定通过将汽车，火车和飞机旅行链接在一起，是否可以从一个地方到另一个地方旅行。例如，您的程序应对查询travel(valmont, raglan)回答“true”。
3.因此，通过使用travel / 2来查询上述数据库，您可以发现有可能从Valmont到Raglan。如果您正在计划这样的航行，那已经是有用的事情了，但是您可能更希望拥有从Valmont到Raglan的精确路线。写一个谓词travel / 3，告诉您从一个地方到另一个地方要走的路线。例如，程序应响应
X = go(valmont,metz,
go(metz,paris,
go(paris,losAngeles)))
到查询travel(valmont, losAngeles,X).
4.扩展谓词travel/ 3，以便它不仅告诉您从一个地方到达另一个地方的路线，而且还告诉您旅行的方式。也就是说，新程序应该让我们在航行的每个阶段都知道我们需要乘汽车，火车还是飞机旅行。