在上一章節里面，我給大家演示了一個Prolog特有的神奇的功能：它能夠回答你提出的問題！在這一章里面，我將簡單的解釋一下Prolog是如何能夠回答你的問題的。 首先，還是自己試著把下面的程序寫一下，然后加載到SWI-Prolog里面。 ~~~ parent(di,yuqing). parent(keyuan,jianbo). parent(jianbo,di). ancestor(X,Y):-parent(X,Y). ancestor(X,Y):-parent(X,Z),ancestor(Z,Y). ~~~ 然后我們問Prolog: ~~~ ?- ancestor(keyuan,yuqing). ~~~ Prolog系統會試圖證明這個查詢，很顯然，程序會返回”true.”那么，Prolog系統是如何找到答案的呢？當我們向Prolog提問”ancestor(keyuan,yuqing)”的時候，Prolog首先會在它的知識庫里面尋找”ancestor”的定義，當然，它找到了兩個”ancestor”的定義： ~~~ ancestor(X,Y):-parent(X,Y). ancestor(X,Y):-parent(X,Z),ancestor(Z,Y). ~~~ 按照默認的規定，它會首先取第一個規則：“ancestor(X,Y):-parent（X,Y).”由于這個規則里面的X,Y是變量，Prolog會給這兩個變量賦值，使得： ~~~ ancestor(keyuan,yuqing) = ancestor(X,Y) ~~~ 很顯然，X=keyuan,Y=yuqing。之后，Prolog會把ancestor換成后面的條件： ~~~ ancestor(keyuan,yuqing) ==> parent(keyuan,yuqing). ~~~ 之后，Prolog試圖證明”parent(keyuan,yuqing)”,根據上面的程序，很顯然，這是錯的，會返回：”false”。那么，之后Prolog會怎么辦呢？記得上面說過，ancestor有兩個規則吧，我們之前根據慣例選擇了第一個規則，現在我們可以試一下第二個規則：”ancestor(X,Y):-parent(X,Z),ancestor(Z,Y).”根據這個規則，Prolog會把”ancestor(keyuan,yuqing).”換成了： ~~~ parent(keyuan,Z),ancestor(Z,yuqing). ~~~ 之前Prolog需要證明一個式子(ancestor(keyuan,yuqing).)，現在Prolog需要證明兩個式子了。因為這兩個式子中間是一個逗號，逗號的意思是”且“，所以只有當這兩個式子都是”true”時候，整個的查詢才是”true”。首先，Prolog會嘗試第一個”parent(keyuan,Z).“它會在知識庫里面找到：”parent(keyuan,jianbo)”。于是，Z=jianbo。這時候，我們之前的那兩個式子變成了： ~~~ parent(keyuan,jianbo),ancestor(jianbo,yuqing). ~~~ 然后，Prolog嘗試證明第二個式子：”ancestor(jianbo,yuqing)”。同樣的道理，Prolog首先找到的是：”ancestor(X,Y):-parent(X,Y)”，于是想證明”ancestor(jianbo,yuqing)”就變成了要證明”parent(jianbo,yuqing)”。很顯然”parent(jianbo,yuqing)”會返回”false”。這時候，程序會試著把”ancestor(jianbo,yuqing)”替換成”parent(jianbo,Z1),ancestor(Z1,yuqing)”。要注意的是，此處我們不用Z作為變量了，而是用Z1作為變量，這叫做變量的重命名。原因是我們之前已經用過Z做變量了，為了把現在這個Z變量和之前的Z變量區別開來，我們把現在的Z變量重命名為Z1。很顯然，無論變量的名字如何，它都是一個變量，理論上我們可以把它賦值成任何值，所以修改名字不會改變變量的含義。根據我們的知識庫，此時Z1應該等于di。于是我們得到了兩個式子： ~~~ parent(jianbo,di),ancestor(di,yuqing). ~~~ 把”ancestor(di,yuqing).”換成”parent(di,yuqing)”，我們得到一個事實(fact),所以”parent(di,yuqing)”是真。 綜上所述，我們其實是用回溯的方式把”ancestor(keyuan,yuqing).”換成了： ~~~ parent(keyuan,jianbo),parent(jianbo,di),parent(di,yuqing). ~~~ 由于上面的三個式子都是真的，所以”ancestor(keyuan,yuqing).”是真的。 下面這個圖顯示了Prolog是如何證明你的查詢的：  通過這個簡單的例子，我們可以得出，Prolog通過三個方面來嘗試著證明你給的查詢(query)： * 匹配(unifing/matching)。例如上面的”ancestor(keyuan,yuqing) = ancestor(X,Y)”，Prolog試圖從它的知識庫里面找出最符合你的查詢的規則或者是事實。 * 變量重命名(variable renaming)。例如上面的”parent(jianbo,Z1),ancestor(Z1,yuqing)”，因為在同一個查詢(query)里面已經有了”Z”，所以Prolog系統將重復的Z命名為Z1。(事實上，在Prolog內部，變量根本不會用”Z”,”Z1”這樣的名字，Prolog的編譯程序的時候就已經將”Z”換成了”G132329392049”這類名字以保證名字不會重復)。 * 回溯(back-tracking)。這是Prolog最最重要的一個特性。Prolog是用深度優先(depth-first search)的算法來尋找答案的。當一個規則或者是事實不符合時，Prolog會通過回溯的方式回到之前的狀態，然后去嘗試另外的規則或者是事實，知道你的查詢(query)被證明為止。如果所有的可能性都搜索過了，你的查詢仍然不能得到證實，那么Prolog會認為你的查詢證實不了，返回”false”。有關回溯算法的詳細介紹你可以去網絡上搜索一下。 到這里，這一章就結束了，希望你對Prolog程序的執行順序有了一個初步的了解。說實話，Prolog的程序回溯執行方式有時候我自己都想不明白，特別是遇到特別復雜的問題的時候。這個時候，最好的辦法就是拿一張紙一支筆，親自畫一下程序的回溯圖，就想上面的那個圖一樣，這樣就能幫助你理解程序了～ ## 加分習題 1. 我們有如下代碼： parent(tom,bob). parent(pam,bob). parent(pam,liz). parent(pam,bob). male(tom). male(bob). female(liz). female(pam). sister(X,Y):- ~~~ parent(Z,X), parent(Z,Y), female(X), X\=Y. ~~~ 請比照著上面的教程里面”ancestor(keyuan,yuqing)”的執行順序圖畫一個 ?-sister(liz,bob). 的執行圖。(注：程序中的”X\=Y”是X不等于Y的意思) 2. (這道題有點難度哦)請看下圖：  我們的目的是要在上面表格中白色的方格(帶有LXX標識的方格)里面填上英文單詞，可供選擇的單詞有： ~~~ word(d,o,g). word(r,u,n). word(t,o,p). word(f,i,v,e). word(f,o,u,r). word(l,o,s,t). word(m,e,s,s). word(u,n,i,t). word(b,a,k,e,r). word(f,o,r,u,m). word(g,r,e,e,n). word(s,u,p,e,r). word(p,r,o,l,o,g). word(v,a,n,i,s,h). word(w,o,n,d,e,r). word(y,e,l,l,o,w). ~~~ 試著寫出一個規則solution. ~~~ solution(L1,L2,L3,L4,L5,L6,L7,L8,L9,L10,L11,L12,L13,L14,L15,L16). ~~~