X=[she is]
这些例子说明PROLOG中变量实例化的含义。在目标append(X、Y、Z)中，三个变元的任何一个都可以为变量，甚至当Z为表时，X和Y均可为变量。这种性质有人称为可逆性。
（3）用PROLOG写last函数，即求出给定表的最后一个元素。 分析：如果表L只有一个元素，则该元素即为最后一个元素。
如果表L有多于一个元素的元素，则去掉头元素，求出剩余表（即尾）的最后一个元素。目标last(X,L)，表示表L的最后一个元素为X，其程序如下：
last(X,[X]).
last(X,[_|Y]):—last(X,Y). (4)谓词length,求表的长度。 length([],0):—!.
length([H|T],X):—length(T,Y),X is Y+1.
这里的“！”符号将在以后介绍，它的作用是使得调用谓词length的目标不可重新满足。例如，当用户通过询问length([1,2,3,4],L)得到L=4后，若他要求再重新满足length(1,2,3,4],L)这个目标（通过打；和return键），则失败。目前读者在读这个程序时可以认为“！”符号不存在（下同）。
（5）写一个PROLOG程序求Fibonacci数，Fibonacci序列定义为： fo=1 f1=1
fn=fn-1 + f n-2 n≥2
设fib(N,X)表示第N个Fibonacci 数为X，则程序为： fib(0,1):-! fib(1,1):-!
fib(N,X):-N1 is N-1,
N2 is N-2
fib(N1,Z1),fib(N2,Z2), X is Z1+Z2.
6.递归注意点
在使用递归定义时，须注意以下两点： （1）不能写循环递归定义。 例如：parent(X,Y):- child(Y,X).
child(A,B):- parent(B,A).
在这例子中，为满足parent(X,Y),建立了child(Y,X)作为子目标，而谓词child的定义中利用了parent(B,A)作为子目标。这样在问有关child和parent的问题时，将导致无限循环，PROLOG永远不能推出任何结果。
（2）左递归定义的问题。 例如:
person(X):- person(Y),mother(X,Y). person(adam).
这里第一个规则是左递归定义，即定义person(X)时，它的第一个（子句体中左面的一个）子目标就是person本身。于是当一目标匹配这一规则时，将首先要满足这个子目标，而这个子目标本质上等价于原始目标，因此该规则又将被利用。例如：？—person(X)
PROLOG将首先利用规则，且产生子目标person(Y)。为了满足这一子目标，PROLOG再一次取第一个规则，并且产生另一个等价的子目标。这样如此继续，直到用完空间。当然，如果有机会去找到事实person(adam),则将开始产生解。问题是PROLOG的搜索规则是必须在试验第一种可能性失败后才能搜索第二个可能。而在这里，第一个规则的寻找任务是无限长，为了避免上面这种左递归引起的无限循环，可以把事实放在规则之前，即
person(adam). person(X):— person(Y),mother(X,Y) 事实上，作为一般启示，只要有可能总应把事实放在规则之前。
三、PROLOG的搜索方法
1．关于PROLOG的控制
众所周知，计算机越来越广泛地用于解决非数值问题，对于这一类应用，最自然的数据结构，基本操作和控制结构与那些主要用来进行数值计算的数据结构、基本操作的控制结构有着很大的不同，作为非数值问题处理语言，PROLOG的数据结构适应于这类问题的要求。
PROLOG系统实现自动搜索、自动进行模式匹配以及回溯，这便把人工智能系统中最基本的操作和实现技术加入PROLOG实现系统内部，从而大大简化了所解问题的表述。
通过前面的叙述，大家已经看到，PROLOG程序不同于一般程序语言所写的程序。在PROLOG程序中不存在一般语言所具有的条件、循环和转向等控制结构成份，它仅含有事实、规则和询问。PROLOG系统根据用户给出的所解问题的已知事实和有关规则这些前提，自动地进行搜索查找、判断和推理，最后回答用户提出的问题，因此，PROLOG把实现搜索匹配和回溯的控制操作放进了系统内部，从而使用户一级上的控制达到了更高一级水平。
PROLOG系统还提供了不少内部谓词。所谓内部谓词是指用户不必定义就可使用的谓词。内部谓词既可以实现PROLOG无法定义的内容，又为用户提供了常用的谓词，其目的是使程序具有较高的执行效率，最典型的内部谓词是：用来限制PROLOG搜索查找过程的cut操作，cut操作是用户用来告诉PROLOG系统如何改进（加速）搜索或回溯过程，以避免那些不必要的徒劳搜索，从而减少组合爆炸的后果。
如何掌握PROLOG的这些控制过程，这对于写出好的PROLOG程序将是重要的。 2．PROLOG的搜索和回溯
前面，我们已经讲述过，当用户打入一个询问后，PROLOG就到它已取得的事实和规则的数据库中去寻找是否有匹配的子句。其寻找方法是，从上到下地在数据库中找匹配的子句（若找到的匹配子句有多个子目标，则从左到右地逐个去满足）。如果与某一子句匹配成功，询问中的一目标被满足，则PROLOG在数据库中那个匹配子句的地方作一标记，这个位置标记符与该特定目标联系。下面将讨论位置标记符（为直观起见，把它看作为指针）的作用。
本节试图通过两个例子来说明：
①PROLOG是如何对含有多个目标的询问（或多个目标的规则体）进行搜索匹配？②在匹配过程中何时回溯以及如何回溯？③在搜索时对递归定义的规则如何逐层展开？第1个例子侧重说明前两点。第2个例子侧重说明第③点，所以该例子包含了递归定义的规则。
例1设有下列事实和规则： / * | * / likes(tom,talk).
/ * 2 * / likes(robert,swim). / * 3 * / likes(jane,swim). / * 4 * / likes(jane,swim).
/ * 5 * / friend(john,X):-likes(X,talk),likes(x,swim). 现有问题：
？—friend(john,Who)
首先看一下PROLOG的搜索过程：
①PROLOG试图通过满足目标friend(john,Who)来回答问题。首先需要指出，即每个目标保持有它自己的位置记符。设此目标的指针为Pj。根据自顶向下的搜索方法，它找到5行规则，因此指针为Pj指向第5行，同时X与Who共享。
②由于①找到的是一条规则，所以匹配此规则就必须去满足它的两个子目标。于是根据自左向右的原则，PROLOG先去设法满足第一个子目标likes(x,talk)，作为一个新的目标，PROLOLG分配另一指针Pt给此子目标，且自顶向下搜索数据库。找到第一行的事实匹配，因此Pt指向第1行，X被实例化为tom，又因X与Who共享，所以Who也为tom。
③在第一个子目标满足后，PROLOG又去满足它的右邻第二个子目标。对它也自顶向下搜索数据库，当它的指针Ps指向第5行之后发现找不到事实likes(tom,swim),设法重新找一个X，这称试图重新满足它。但在这之前首先需要把它在先前被满足时所实例化的变量X脱解为非实例化，即把X的Who和值tom去掉，然后从Pt所指向的第2行向下寻找，看是否有另一子句能满足子目标like（X，talk）。此时找到第3行能满足它，因此指针Pt指向第3行，X被实例化为robert，同样who也为robert，第一子目标满足。
④在第一子目标重新满足后，PROLOG再一次去满足第二个目标likes(robert,swim)，它不同于目标likes(tom,swim)。因此PROLOG自顶向下搜索数据库找到第2行匹配，这时Ps指向第2行，这里不妨仍用PS作为目标likes(robert,swim)的指针，这样第5行规则中的两个子目标均满足，因此目标friend(john,Who)与第5行的规则匹配，即目标friend(john,Who)成功，并有：Who=robert
综上所述，在企图满足一目标时可能发生的情况是：
当我们要满足一目标时，从数据库的顶开始搜索，这时有两种可能：
a. 找到一匹配的事实，此时可以说目标已被匹配成功。这目标的指针指向数据库中所匹配的事实，并且实例化先前未被实例化的变量；若匹配一个规则头，则应左到右去设法满足规则的所有子目标。
b. 找不到匹配的事实或规则头，此时说明目标失败，若该目标有左邻，则设法重新满足邻目标，这就是回溯，回到先前一个目标。
当我们设法重新满足一目标时，从这个目标（需要新满足）的指针所指向的地方向下搜索，这时必须把先前在这目标满足时所实例化的任何变戏法量去掉实例化（脱解）。这就是所谓取消先前这一目标所做的所有工作，然后开始恢复搜索数据库，如前面叙述的那样，这个新的被回溯的目标仍可能成功或失败。
下面我们用直观的图示法来描述上述例子的匹配过程。 综上所述，在企图满足一目标时可能发生的情况是：
当我们要满足一目标时，从数据库的顶开始搜索，这时有两种可能： a．找到一匹配的事实，此时可以说目标已被匹配成功。该目标的指针指向数据库中所匹配的事实，并且实例化先前未实例化的变量；若匹配一个规则头，则应从左到右去设法满足规则的所有子目标。
b．找不到匹配的事实或规则头，此时说明目标失败。若该目标有左邻，则设法重新满足左邻目标，这就是回溯，回到先前一个目标。
当我们设法重新满足一目标时，从这个目标（需要新满足）的指针所指向的地方向下搜索，这时必须把先前在这目标满足时所实例化的任何变量去掉实例化（脱解）。这就是所谓取消先前这一目标所做的所有工作，然后开始恢复搜索数据库，如前面叙述的那样，这个新的被回溯的目标仍可能成功或失败。
下面我们给出第2个例子，说明合有递归定义的规则，PROLOG如何逐层展开去满足所提的问题。由于递归便可能产生无限多个可能的解。
例2，用PROLOG定义谓词is-integer
Is-integer(N)的含义是：只要N被实例化为一个整数，则目标is-integer(N)成功；若N未被实例化，则目标is-integer(N)将引起选择一整数，且N被实例化为此整数。
程序如下：
/ * 1 * / is-integer(o).
/ * 2 * / is-integer(X):-is-integer(Y), X is Y+1.