?表處理與遞歸

1、表頭與表尾

表是 Prolog 中一種非常有用的數(shù)據(jù)結(jié)構(gòu).表的表述能力很強(qiáng)，數(shù)字中的序列、集合，通常語(yǔ)言中的數(shù)組、記錄等均可用表來(lái)表示.表的最大特點(diǎn)是其長(zhǎng)度不固定，在程序的運(yùn)行過(guò)程中可動(dòng)態(tài)地變化.具體來(lái)講，就是在程序運(yùn)行時(shí)，可對(duì)表施行一些操作，如給表中添加一個(gè)元素，或從中刪除一個(gè)元素，或者將兩個(gè)表合并為一個(gè)表等.用表還可以方便地構(gòu)造堆棧、隊(duì)列、鏈表、樹等動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu).

表還有一個(gè)重要特點(diǎn)，就是它可分為頭和尾兩部分.表頭是表中第一個(gè)元素，而表尾是表中除第一個(gè)元素外的其余元素按原來(lái)順序組成的表.例如下面的表所示就是一個(gè)例子.

表表 頭表 尾

［1， 2， 3， 4， 5］ 1 2， 3， 4， 5］

［apple， orange， banana］ apple ［orange， banana］

［［a， b］， ［c］， ［d， e］］ ［a， b］ ［［c］， ［d， e］］

［“Prolog”］ “Prolog” ［］

［］無(wú)定義無(wú)定義

**表頭與表尾示例** 表 2、**表的匹配合一** 在程序中是用“|”來(lái)區(qū)分表頭和表尾的，而且還可以使用變量.例如一般地用“`［H|T］“`來(lái)表示一個(gè)表，其中 H、T 都是變量，H 為表頭，T為表尾.注意，此處 H 是一個(gè)元素（表中第一個(gè)元素），而 T 則是一個(gè)表（除第一個(gè)元素外表中的其余元素按原來(lái)順序組成的表）.表的這種表示法很有用，它為表的操作提供了極大的方便.如下面的表所示即為用這種表示法通過(guò)匹配合一提取表頭和表尾的例子. | 表1 | 表2 | 合一后的變量值 | |：————-：|：————-：|：————-：| | ［X | Y］ | ［a， b， c］ | X = a， Y = ［b， c］ | | ［X | Y］ | ［a］ | X = a， Y = ［］ | | ［a | Y］ | ［X， b］ | X = a， Y = ［b］ | | ［X， Y， Z］ | ［a， b， c］ | X = a， Y = b， Z = c | | ［［a， Y］ | Z］ | ［［X， b］， ［c］］ | X = a， Y = b， Z = ［［c］］ |

**表的匹配合一示例** 表 還需說(shuō)明的是，表中的“|”后面只能有一個(gè)變量.例如寫法 ［X | Y， Z］ 就是錯(cuò)誤的.但豎杠前面的變量可以多于一個(gè).例如寫法 ［ X， Y | Z］ 是允許的.這樣，這個(gè)表同 ［a， b， c］ 匹配合一后，有：

X = a， Y = b， Z = ［c］1

另外，豎杠的前面和后面也可以是常量，例如 ［a | Y］ 和 ［X | b］ 都是允許的，但需要注意，后一個(gè)表稱為無(wú)尾表，如果它同表 ［a | Y］ 匹配，則有：

X = a， Y = b （而不是 Y = ［b］）1

如果無(wú)“|”，則不能分離出表尾.例如，表 ［X， Y， Z］ 與 ［a， b， c］ 合一后得 X = a，Y = b，Z = c，其中變量 Z 并非等于 ［c］ .

接下來(lái)我們通過(guò)三個(gè)例子來(lái)更詳細(xì)地了解表的操作.

例6-1：設(shè)計(jì)一個(gè)能判斷對(duì)象 X 是表 L 的成員的程序.

我們可以這樣設(shè)想：

如果 X 與表 L 中的第一個(gè)元素（即表頭）是同一個(gè)對(duì)象，則 X 就是 L的成員；

如果 X 是 L 的尾部的成員，則 X 也就是 L 的成員.

根據(jù)這種邏輯關(guān)系，有下面的 Prolog 程序：

member（X， ［X | Tail］）.

member（X， ［Head | Tail］） ：- member（X， Tail）.12

其中第一個(gè)子句的語(yǔ)義就是上面的第一句話；第二個(gè)子句的語(yǔ)義就是上面的第二句話.可以看出，這個(gè)程序中使用了遞歸技術(shù)，因?yàn)橹^詞 member 的定義中又含有它自身.利用這個(gè)程序就可以判定任意給定的一個(gè)對(duì)象和一個(gè)表之間是否具有 member（成員）關(guān)系.例如，取表 L 為 ［a， b， c， d］，取 X 為 a，對(duì)上面的程序提出如下詢問(wèn)：

Goal ： member（a， ［a， b， c， d］）.1

則回答“yes”.同樣對(duì)于詢問(wèn)：

Goal ： member（b， ［a， b， c， d］）.

Goal ： member（c， ［a， b， c， d］）.

Goal ： member（d， ［a， b， c， d］）.123

均回答“yes”.但若詢問(wèn)：

Goal ： member（e， ［a， b， c， d］）.1

則回答“no”.如果我們這樣詢問(wèn)：

Goal ： member（X， ［a， b， c， d］）.1

意思是要證明存在這樣的 X，它是該表的成員，這時(shí)系統(tǒng)返回 X 的值，即：

X = a1

如果需要的話，系統(tǒng)還會(huì)給出 X 的其他所有值.

例6-2：寫一個(gè)表的拼接程序，即把兩個(gè)表連接成一個(gè)表.

append（［］， L， L）.

append（［H | T］， L2， ［H | Tn］） ：- append（T， L2， Tn）.12

程序中第一個(gè)子句的意思是空表同任一表 L 拼接的結(jié)果仍為表 L；第二個(gè)子句的意思是說(shuō)，一個(gè)非空的表 L1 與另一個(gè)表 L2 拼接的結(jié)果 L3 是這樣一個(gè)表，它的頭是 L1 的頭，它的尾是由 L1 的尾 T 同 L2 拼接的結(jié)果 Tn.這個(gè)程序刻畫了兩個(gè)表與它們的拼接表之間的邏輯關(guān)系.

可以看出，謂詞 append 是遞歸定義的，子句append（［］， L， L）.為終結(jié)條件即遞歸出口.

對(duì)于這個(gè)程序，如果我們?cè)儐?wèn)：

Goal ： append（［1， 2， 3］， ［4， 5］， L）.1

則系統(tǒng)便三次遞歸調(diào)用程序中的第二個(gè)子句，最后從第一個(gè)子句終止，然后反向依次求出每次的拼接表，最后輸出：

L=［1， 2， 3， 4， 5］1

當(dāng)然，對(duì)于這個(gè)程序也可以給出其他各種詢問(wèn)，如：

Goal ： append（［1， 2， 3］， ［4， 5］， ［1， 2， 3， 4， 5］）.1

系統(tǒng)回答yes.

Goal ： append（［1， 2， 3］， ［4， 5］， ［1， 2， 3， 4， 5， 6］）.1

系統(tǒng)回答no.

Goal ： append（［1， 2， 3］， Y， ［1， 2， 3， 4， 5］）.1

系統(tǒng)回答X = ［4， 5］.

Goal ： append（X， ［4， 5］， ［1， 2， 3， 4， 5］）.1

系統(tǒng)回答X = ［1， 2， 3］.

Goal ： append（X， Y， ［1， 2， 3， 4， 5］）.1

系統(tǒng)回答

X = ［］， Y = ［1， 2， 3， 4， 5］

X = ［1］， Y = ［2， 3， 4， 5］

X = ［1， 2］， Y = ［3， 4， 5］

X = ［1， 2， 3］， Y = ［4， 5］

等（如果需要所有解的話）.12345

例6-3：表的輸出

print（［］）.

print（［H | T］） ：- write（H）， print（T）.12

例6-4：表的倒置，即求一個(gè)表的逆序表.

reverse（［］， ［］）.

reverse（［H | T］， L） ：- reverse（T， L1）， append（L1， ［H］， L）.12

這里，reverse的第一個(gè)項(xiàng)是輸入，即原表；第二個(gè)項(xiàng)是輸出，即原表的倒置.

?回溯控制

Prolog 在搜索目標(biāo)解的過(guò)程中，具有回溯機(jī)制，即當(dāng)某一個(gè)子目標(biāo)“Gi”不能滿足時(shí)，就返回到該子目標(biāo)的前一個(gè)子目標(biāo)“Gi-1”，并放棄“Gi-1”的當(dāng)前約束值，使它重新匹配合一.在實(shí)際問(wèn)題中，有時(shí)卻不需要回溯，為此 Prolog 中就專門定義了一個(gè)阻止回溯的內(nèi)部謂同——“！”，稱為截?cái)嘀^詞.

截?cái)嘀^詞的語(yǔ)法格式很簡(jiǎn)單，就是一個(gè)感嘆號(hào)“！”.！ 的語(yǔ)義如下.

若將“！”插在子句體內(nèi)作為一個(gè)子目標(biāo)，它總是立即成功.

若“！”位于子句體的最后，則它就阻止對(duì)它所在子句的頭謂詞的所有子句的回溯訪向，而讓回溯跳過(guò)該頭謂詞（子目標(biāo)），去訪問(wèn)前一個(gè)子目標(biāo)（如果有的話）.

若“！”位于其他位置，則當(dāng)其后發(fā)生回溯且回溯到“！”處時(shí)，就在此處失敗，并且“！”還使它所在子句的頭謂詞（子目標(biāo)）整個(gè)失敗（即阻止再去訪問(wèn)頭謂詞的其余子向（如果有的話），即迫使系統(tǒng)直接回溯到該頭謂詞（子目標(biāo)）的前一個(gè)子目標(biāo)（如果有的話））.

舉個(gè)例子：

考慮下面的程序

p（a）. （7 - 1）

p（b）. （7 - 2）

q（b）. （7 - 3）

r（X） ：- p（X）， q（X）. （7 - 4）

r（c）.12345

對(duì)于目標(biāo)：r（X）.可有一個(gè)解：

Y = b

但當(dāng)我們把式（7 - 4）改為：

r（X） ：- p（X）， ！， q（X）. （7 - 4‘）1

時(shí)，卻無(wú)解.為什么？

這是由于添加了截?cái)嘀^詞“！”.因?yàn)槭剑? - 4’）中求解子目標(biāo) p（X） 時(shí)，X 被約束到 a，然后跳過(guò)“！”，但在求解子目標(biāo) q（a） 時(shí)遇到麻煩，于是又回溯到“！”，而“！”阻止了對(duì) p（X）的下一個(gè)子句 p（b） 和 r 的下一個(gè)定義子句 r（c） 的訪問(wèn).從而導(dǎo)致整個(gè)求解失敗.

再舉個(gè)例子：

設(shè)有程序：

g0 ：- g11， g12， g13. （7 - 5）

g0 ：- g14. （7 - 6）

g12 ：- g21， ！， g23. （7 - 7）

g12 ：- g24， g25. （7 - 8）

... ...12345

給出目標(biāo)：g0.

假設(shè)運(yùn)行到子目標(biāo) g23 時(shí)失敗，這時(shí)如果子句（7 - 7）中無(wú)“！”的話，則會(huì)回溯到 g21，并且如果 g21 也失敗的話，則會(huì)訪問(wèn)下面的子句（7 - 8）.但由于有“！”存在，所以不能回溯到 g21，而直接宣告 g12 失敗.于是由子句（7 - 5），這時(shí)則回溯到 g11.如果我們把子句（7 - 7）改為：

g12 ：- g21， g23， ！. （7 - 9）1

當(dāng)然這時(shí)若 g23 失敗時(shí)，便可回溯到 g21，而當(dāng) g21 也失敗時(shí)，便回溯到 g12，即子句（7 - 8）被“激活”.但對(duì)于修改后的程序，如果 g13 失敗，則雖然可回溯到 g12，但對(duì) g12 不做任何事情便立即跳過(guò)它，而回溯到 g11.如果子句（7 - 9）中無(wú)“！”，則當(dāng) g13 失敗時(shí)，回溯到 g12 便去考慮子句（7 - 8），只有當(dāng)子句（7 - 8）再失敗時(shí)才回溯到 g11.

八、程序舉例

下面給出幾個(gè)簡(jiǎn)單而又典型的程序?qū)嵗?通過(guò)這些程序，讀者可以進(jìn)一步體會(huì)和理解 Prolog 程序的風(fēng)格和能力，也可以掌握一些基本的編程技巧.

例8-1：下面是一個(gè)簡(jiǎn)單的路徑查詢程序.程序中的事實(shí)描述了如下圖所示的有向圖，規(guī)則是圖中兩節(jié)點(diǎn)間有通路的定義.

predicates

road（symbol， symbol）

path（symbol， symbol）

clauses

road（a， b）.

road（a， c）.

road（b， d）.

road（c， d）.

road（d， e）.

road（b， e）.

path（X， Y） ：- road（X， Y）.

path（X， Y） ：- road（X， Z）， path（Z， Y）.123456789101112

程序中未含目標(biāo)，所以運(yùn)行時(shí)需給出外部目標(biāo).例如當(dāng)給出目標(biāo)：

path（a， e）.1

時(shí)，系統(tǒng)將回答yes，但當(dāng)給出目標(biāo)：

path（e， a）.1

時(shí)，系統(tǒng)則回答no，如果給出目標(biāo)：

run.1

且在程序中增加子句：

run ：- path（a， X）， write（”X =“， X）， nl， fail.

run.12

屏幕上將會(huì)輸出：

X = b

X = c

X = d

X = e

X = d

X = e

X = e1234567

即從 a 出發(fā)到其他節(jié)點(diǎn)的全部路徑.

例8-2：下面是一個(gè)求階乘程序，程序中使用了遞歸.

/* a Factorial Program */

domains

n， f = integer

predicates

factorial（n， f）

goal

readint（I），

factorial（I， F），

write（I， ”！=“， F）.

clauses

factorial（1， 1）.

factorial（N， Res） ：-

N》 0，

N1 = N - 1，

factorial（N1， FacN1），

Res = N * FacN1.12345678910111213141516

程序運(yùn)行時(shí)，從鍵盤上輸入一個(gè)整數(shù)，屏幕上將顯示其階乘數(shù).

例8-3：下面是一個(gè)表的排序程序，采用插入排序法.

/* insert sort */

domains

listi = integer*

predicates

insert_sort（listi， listi）

insert（integer， listi， listi）

asc_order（integer， integer）

clauses

insert_sort（［］， ［］）.

insert\_sort（［H | Tail］， Sorted_list） ：-

insert_sort（Tail， Sorted\_Tail），

insert（H， Sorted_Tial， Sorted\_list）.

insert（X， ［Y | Sorted_list1］） ：-

asc_order（X， Y）， ！，

insert（X， Sorted_list， Sorted\_list1）.

insert（X， Sorted_list， ［X | Sorted\_list］）.

asc_order（X， Y） ：- X》 Y.1234567891011121314151617

程序中對(duì)表的處理使用了遞歸.程序中也未給出目標(biāo)，需要在運(yùn)行時(shí)臨時(shí)給出.例如當(dāng)給出目標(biāo)：

insert_sort（［5， 3， 4， 2， 6， 1， 7， 8， 9， 0］， L）.1

時(shí)，系統(tǒng)將輸出：

L = ［0， 1， 2， 3， 4， 5， 6， 7， 8， 9］1