?表處理與遞歸

1、表頭與表尾

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

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

表表 頭表 尾

［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” ［］

［］無定義無定義

**表頭與表尾示例** 表 2、**表的匹配合一** 在程序中是用“|”來區(qū)分表頭和表尾的，而且還可以使用變量.例如一般地用“`［H|T］“`來表示一個表，其中 H、T 都是變量，H 為表頭，T為表尾.注意，此處 H 是一個元素（表中第一個元素），而 T 則是一個表（除第一個元素外表中的其余元素按原來順序組成的表）.表的這種表示法很有用，它為表的操作提供了極大的方便.如下面的表所示即為用這種表示法通過匹配合一提取表頭和表尾的例子. | 表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］］ |

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

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

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

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

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

接下來我們通過三個例子來更詳細地了解表的操作.

例6-1：設計一個能判斷對象 X 是表 L 的成員的程序.

我們可以這樣設想：

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

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

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

member（X， ［X | Tail］）.

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

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

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

則回答“yes”.同樣對于詢問：

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

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

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

均回答“yes”.但若詢問：

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

則回答“no”.如果我們這樣詢問：

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

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

X = a1

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

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

append（［］， L， L）.

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

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

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

對于這個程序，如果我們詢問：

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

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

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

當然，對于這個程序也可以給出其他各種詢問，如：

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：表的倒置，即求一個表的逆序表.

reverse（［］， ［］）.

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

這里，reverse的第一個項是輸入，即原表；第二個項是輸出，即原表的倒置.

?回溯控制

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

截斷謂詞的語法格式很簡單，就是一個感嘆號“！”.！ 的語義如下.

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

若“！”位于子句體的最后，則它就阻止對它所在子句的頭謂詞的所有子句的回溯訪向，而讓回溯跳過該頭謂詞（子目標），去訪問前一個子目標（如果有的話）.

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

舉個例子：

考慮下面的程序

p（a）. （7 - 1）

p（b）. （7 - 2）

q（b）. （7 - 3）

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

r（c）.12345

對于目標：r（X）.可有一個解：

Y = b

但當我們把式（7 - 4）改為：

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

時，卻無解.為什么？

這是由于添加了截斷謂詞“！”.因為式（7 - 4’）中求解子目標 p（X） 時，X 被約束到 a，然后跳過“！”，但在求解子目標 q（a） 時遇到麻煩，于是又回溯到“！”，而“！”阻止了對 p（X）的下一個子句 p（b） 和 r 的下一個定義子句 r（c） 的訪問.從而導致整個求解失敗.

再舉個例子：

設有程序：

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

g0 ：- g14. （7 - 6）

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

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

... ...12345

給出目標：g0.

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

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

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

八、程序舉例

下面給出幾個簡單而又典型的程序實例.通過這些程序，讀者可以進一步體會和理解 Prolog 程序的風格和能力，也可以掌握一些基本的編程技巧.

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

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

程序中未含目標，所以運行時需給出外部目標.例如當給出目標：

path（a， e）.1

時，系統(tǒng)將回答yes，但當給出目標：

path（e， a）.1

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

run.1

且在程序中增加子句：

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

run.12

屏幕上將會輸出：

X = b

X = c

X = d

X = e

X = d

X = e

X = e1234567

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

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

/* 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

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

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

/* 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

程序中對表的處理使用了遞歸.程序中也未給出目標，需要在運行時臨時給出.例如當給出目標：

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

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

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