邏輯程式設計 Prolog

最近花不少時間重新看 Prolog 和 Erlang 的程式寫法，感想是，邏輯程式工具的威力真強。

Prolog 是一種老派的邏輯式程式語言，它的目標是執行邏輯系統。邏輯系統是一些事實和一些規則組成的一組「資料庫」，在系統定義範圍內，可以找到有一些情況被滿足。例如最簡單的三段論法說：

morale(X) :- man(X).

man(socrates).

?- man(socrates).

yes

?- man(me).

no

以上程式中，大寫符號是變數，小寫符號是常在詞彙。句子呈現 X :- Y 是規則，讀做 X if Y ，在邏輯表達式是寫成 X <- Y 。另一種普通的句子是事實。而末尾有 ?- 開頭的，是查詢句。根據以上程式，有些對邏輯一知半解的會大叫：「喔！原來我不道德！」但只是因為以上的三段論與現實的認知稍有差別：邏輯句子表達的是語意的最基本部份，但是日常用語的語意結構非常複雜。

Prolog 程式只要定義幾個句子，執行器就會找出一些滿足這些句子的情況。邏輯推論也是如此。設想有個句子定義可以從一列資料的某個位置取出一項資料：

element_at([X|_], 1, X).

element_at([_|Y], N, Z) :- element_at(Y, N1, Z), N is N1 + 1.

第一句說，對開頭為X的一列資料取第一項，答案是X。第二句則使用了遞迴定義。 (第二句讀作：(右邊) 如果 Y 的第 N1 位置是 Z ，則 (左邊) Y 前面多一項資料，這一列的第 N 位置是 Z 。) 以這樣的寫法，除了可以從一列裏指定位置取得資料之外：

?- element_at([a,b,c,d,e], 2, X).

X = b

還可以查詢在什麼位置可以找到指定的資料：

?- element_at([a,b,b,c], N, b).

N = 2;

N = 3

程式的評估，基本上是反覆檢查可以成立的句子，於是可以將所有的情況一筆一筆找出來。所以，寫一些列出各種情況的程式就變得很簡單。例如，寫個組合程式：

combination(0, _, []).

combination(_, [], []).

combination(1, X, [Z]) :- element_at(X, _, Z).

combination(N, [X|Y], [X|Z]) :- N > 1, N1 is N - 1, combination(N1, Y, Z).

combination(N, [_|Y], Z) :- N > 1, combination(N, Y, Z), length(Z, N).

第四句只考慮一列的第一個元素X參與在答案中的情況，而第五句純粹考慮第一個元素不參與在答案中的情況。 (第四句讀作： (右邊) 如果對 Y 取 N1 個元素的一種組合是 Z ，則 (左邊) 對 Y 前面加了一項 X ，取 N 個元素的一種組合，就是 Z 前面也加 X 。因果關係！) 寫程式時，考慮答案只考慮各種情況的其中一種，但程式執行時， Prolog 就像內建迴圈機能一樣，反複將各種情況一樣接著一樣列出來：

?- combination(3, [a,b,c,d,e], X).

X = [a,b,c];

X = [a,b,d];

X = [a,b,e];

X = [a,c,d];

X = [a,c,e];

......

跟 Erlang 比較， Erlang 程式沒有反覆測試每一條句子的執行方式，因為 Erlang 是函數式語言，函數的特性是從多個輸入也必須只對應到一個值。不過， Erlang 也是經由長期用 Prolog 慢慢開發完成的。這是我拿 Prolog 和 Erlang 對照檢視的原因。

Erlang 的組合程式：

combination(0, _) -> [[]];

combination(_, []) -> [[]];

combination(1, X) -> [ [Z] || Z <- X ];

combination(N, [X|Y]) -> [ [X|Z] || Z <- combination(N-1, Y) ] ++

[ Z || Z <-combination(N, Y), length(Z) == N ].

(第四句讀作： (左邊) 想求得 Y 列前面有個 X 的資料取 N 個元素的各種組合情況，先求 (右邊) 可能是對 Y 求 N-1 個元素的各種組合情況，再將 X 套到每個組合情況之前，或者是直接求 Y 中取 N 個元素的各種組合情況。至於末尾檢查 length(Z) == N ，是要克服後半程式結果的不一致情形。)

執行結果：

> test:combination(3, [a,b,c,d,e]).

[[a,b,c],

[a,b,d],

[a,b,e],

[a,c,d],

[a,c,e],

[a,d,e],

[b,c,d],

[b,c,e],

[b,d,e],

[c,d,e]]

Erlang 缺乏逐步列出各種情況的機能，所以要列出全部的組合情況，用 Erlang 必須把各種答案都算出來，並收集成一列。寫 Erlang 程式顯然比寫 Prolog 程式更辛苦一點點，不過， Erlang 提供 List Comprehension 表達法，使這個組合程式也變得稍微簡單一點點。