邏輯程式設計 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 表達法，使這個組合程式也變得稍微簡單一點點。

以 Prolog 示範規則推論系統

規則推論系統，須由規則推論引擎、知識庫、以及輸入事實三者構成。推理方法有向前鏈接 (forward chaining) 和向後鏈接 (backward chaining) 方式，分別對應二種不同的需要。向前鏈接是由規則的前提向規則的結論方向串連可用的規則，由原因導出結果。向後鏈接是由規則的結論向規則的前提方向串連可用的規則，由結果導出原因。於是，前者適用於預測和決策，而後者適用於診斷和歸納。
Prolog 是法文 programmation en logique ，即英文 programming in logic 的合併詞，是個以邏輯操作為主的程式語言。 Prolog 的推理方法是向後鏈接，而且，將 Prolog 系統比擬為推論引擎，是使用 Markov 演算法作為規則歸納策略。說「比擬為推論引擎」，指 Prolog 並不是完整的專家系統框架。不過， Prolog 提供了足夠的基礎架構，可能做出小型、甚至大型的規則推論系統。
本篇以一份小、且不完整的規則知識庫，解決學術界一項著名的小問題「猴子取香蕉」 (the monkey and bananas problem) ，作為對於規則推論系統的展示。
問題描述：

在空間中有猴子，和香蕉、梯子、躺椅等物品，散置於各處。猴子窩在躺椅上，香蕉懸在高處，而且躺椅、香蕉和梯子彼此相隔特定距離。猴子必須站在夠高的位置，並靠近夠近的距離，才能取得香蕉。於是，問題是：猴子該如何取得香蕉？

猴子取香蕉的問題在學術界有各面的討論，例如，研究心理與認知的人關心動物如何操作心理的機能以達成學習。我們對於規則推論系統的討論，則關心要解決這件問題，該建立哪些知識，以及該如何使用這些知識來推理。以下是我的程式。須注意這份程式只是示範，並是知識未建置完整。所示範的重點是：可建立足夠的知識以取得解答，以及掌握 Prolog 向後鏈接推理方法的原則撰寫規則。

% The monkey and bananas problem

% Naming principle:
% 1. Adjectives: for checking properties.
% 2. Verbs: for goals with two members, i.e., a subjective and a objective.
% 3. Past Participles: for goals with two members, i.e., two objectives.

% facts
:-
assert(near(monkey, position(3, 4))),
assert(near(bananas, position(5, 2))),
assert(near(ladder, position(1, 1))),
assert(near(couch, position(3, 4))),
assert(on(monkey, couch)),
assert(light(bananas)),
assert(light(ladder)),
assert(high(bananas)).

% backward chaining rules
holds(monkey, W) :-
not(high(W)),
light(W),
made_neared(monkey, W),
format('Monkey holds ~w.~n', W)
;
high(W),
light(W),
made_neared(ladder, W),
not(on(monkey, ladder)),
climbs(monkey, ladder),
holds(monkey, W)
;
high(W),
light(W),
made_neared(ladder, W),
on(monkey, ladder),
holds(monkey, W)
.
made_neared(O1, O2) :-
near(O1, P1),
near(O2, P2),
moves(O1, P2),
format('Now ~w is near ~w at ~w.~n', [O1, O2, P2])
;
near(O1, P),
near(O2, P),
format('~w and ~w are at the same position.~n', [O1, O2])
.
moves(S, P) :-
retractall(near(S, _)),
assert(near(S, P)),
format('Action performed: moving ~w to ~w.~n', [S, P])
.
climbs(S, O) :-
retractall(high(_)),
assert(on(S, O)),
format('~w climbs on ~w.~n', [S, O])
.

Prolog 的基本符號有：小寫開頭符號為詞彙 (term)，大寫開頭符號為變數，帶有參數的詞彙為描述詞 (predicate)。 ":-" 是規則的中介符號，其左邊項是規則的結論，右邊項是規則的前提。句點是一則完整描述的結尾，逗點是 and 連接詞，分號是 or 連接詞。一則完整描述若只帶有左邊項（沒有右邊項和 ":-" 符號），是單元詞彙，代表既存在的事實。一則完整描述若只有右邊項和 ":-" 符號，代表一則查詢。以上程式撰寫了事實與規則。程式的啟動狀態為：

near(monkey, position(3, 4))
near(bananas, position(5, 2))
near(ladder, position(1, 1))
near(couch, position(3, 4))
on(monkey, couch)
light(bananas)
light(ladder)
high(bananas)

以上描述詞彙，使用 assert 描述詞和逗號組合成查詢句型，使程式被載入時能動態地建立這些詞彙。（ Prolog 中，只有動態建立的描述詞才能被動態地刪除。）這些詞彙稱為事實，構成推論系統的工作空間及狀態。
規則的組成結構，以第一條規則為例，是：

holds(monkey, W) :-
not(high(W)),
light(W),
made_neared(monkey, W),
format('Monkey holds ~w.~n', W).

要找到一項目標 holds(monkey, W) ，「要猴子抓住某物品W」，附帶若干條件例如「物品W位置不高」、「物品W很輕」，則必須找到一項前置目標 made_neared(monkey, W) ，「要讓猴子與物品W是位置接近的」。最後一項 format('Monkey holds ~w.~n', W) 是將物品W放進字串 "Monkey holds ~w.~n" 的 ~w 位置，作為結果輸出。最後一項輸出存在的意義是，引用的這一項規則之後，狀態為「猴子抓住了香蕉」。其他規則比照於此，都包含了一項目標 (goal)、必要的前置目標 (subgoal)、相關的條件、以及引用規則之後的狀態。將程式存檔為 .pl 副檔名，用 Prolog 載入這份程式，並輸入查詢：

?- holds(monkey, bananas).

以上查詢是問「猴子抓住香蕉，怎麼做？」結果輸出為：

Action performed: to move ladder to position(5, 2).
Now ladder is near bananas at position(5, 2).
monkey climbs on ladder.
Action performed: to move monkey to position(5, 2).
Now monkey is near bananas at position(5, 2).
Monkey holds bananas.
true

換個查詢：

?- holds(monkey, ladder).

「猴子怎麼取梯子？」結果輸出為：

Action performed: to move monkey to position(1, 1).
Now monkey is near ladder at position(1, 1).
Monkey holds ladder.
true

以上例子要展示，對於一些有多個解決方向的問題，也許不適合直接寫一條演算法，或者不適合強制決定一項結果。而使用了規則推論系統，只要寫了適合的規則知識，就能夠取得可接受的答案。雖然答案的正確程度取決於規則的正確程度，不過，此系統的優勢是對於取得解答的要求與限制是寬鬆的、軟性的。
備註： Prolog 的規則格式，左邊項幾乎只能有一項描述詞，而缺乏 and 或 or 連接詞的寫法。因應於此限制，規則的四項構成物件：目標、前置目標、相關條件、以及引用規則的描述，只有目標寫在左邊項。其他使用向前鏈接推理的系統，例如 OPS ，規則格式寫成 "if ... then ..." 格式，能夠容許左邊項和右邊項都有 and 或 or 連接詞的寫法，則是在左邊項寫了前置目標和相關條件，並在右邊項則寫了目標和引用描述。