從X到Prolog

在我先前專欄〈用「邏輯」寫程式〉中，曾經提過Prolog。對許多開發者來說，可能從未聽說這門語言，或者覺得它學術性濃厚，也許會像第一次接觸函數式程式設計那般，覺得新奇。

有些人會想到Learn y in x minutes，確實地，也存在著〈Learn Prolog in x minutes〉（https://goo.gl/A4PF9n）這份文件，只是這比較像個備忘，而不是個教學。而且，大部份人比較想知道的是：如果我有個X程式，改寫成Prolog時該如何表達。

Prolog是個基於事實（fact）與規則（rule）的語言，因此，不用急著想將X程式轉為Prolog來作為練習，我們可以找些本身就用事實與規則來描述的問題，作為熟悉的開始，像是有向圖（Directed Graph）。

例如，若圖中有a、b、c、d、e五個節點，edge(a, b)表示可單向地由a到達b，這是一個事實；另外，還有edge(a, d)、edge(d, e)、edge(e, b)與edge(b, c)，你可以輕易根據這些事實，重繪出一張圖。

如果想要知道節點M，是否可透過兩個邊，單向通往節點N，那麼，就建立單向通往能成立的規則tedge(M, N) :- edge(M, S), edge(S, N)。也就是：如果有某個節點S，由M單向通往S成立，且由S單向通往N成立，那麼，由M經兩個邊單向通往N就成立。

進一步地，你也許會想要知道，可否單向地經由任意邊從M通往N，這可以列出以下規則：

path(M, N) :- edge(M, S), edge(S, N).
path(M, N) :- edge(M, S1), edge(S1, S2), edge(S2, N).
path(M, N) :- edge(M, S1), edge(S1, S2), edge(S2, S3), edge(S3, N).

因為目前的圖只有5個節點，在最長的路徑中間，也只需要經過3個節點，因此，上面的規則尚足以符合需求，不過，如果有更多節點與更多事實，如上逐條撰寫規則，就太沒效率了，因為上面的規則，實際已出現了重複的成立條件——想想看，edge(S1, S2), edge(S2, N)如果成立，不就等同於path(S1, N)成立嗎？而這就形成了遞迴規則：

path(M, N) :- edge(M, S), edge(S, N).
path(M, N) :- edge(M, S), path(S, N).

初接觸Prolog時，看到文件中的遞迴規則，有時會覺得神奇。實際上，遞迴規則，也是觀察重複的成立條件而來。現在，你可以簡單地用path(a, e)，查詢a、e是否單向相通，或者更進一步地，用path(M, c)問問看，哪些節點可以單向地通往c點。

瞭解合一與歸結

雖然撰寫Prolog時，多半是在進行事實與規則的宣告，然而，解釋器（interpreter）本身是命令式的，因此在能夠撰寫事實與簡單的規則之後，能夠瞭解Prolog如何解題，會是重要的一部份。

因為，這有助於我們瞭解：在其他非基於邏輯的語言中，有哪些命令式的演算在Prolog中是不必要的。而且，Prolog在解題過程中，會不斷重複兩個重要動作：合一（Unification）與歸結（Resolution）。

舉個例子來說，如果想知道a單向通過兩個邊時，與哪些點相連，可以使用tedge(a, X)查詢，Prolog會使用規則tedge(M, N)；接著，進行M是a、N是X的合一動作，下一步，將tedge(a, X)查詢歸結為edge(a, S), edge(S, X)查詢；隨後，使用S是b對edge(a, S), edge(S, X)進行合一，而edge(a, b)為事實，因此，將edge(a, b), edge(b, X)歸結為edge(b, X)查詢；接著，使用X為c，對edge(b, X)進行合一，而得到edge(b, c)，由於這是個事實，因此X可能的值之一為c。

如果在edge(a, S), edge(S, X)使用S為c，edge(a, c)不是事實，就不用再歸結（因為「且」只要前者不成立，整個就可判斷不成立）；接著，使用S是d合一，而成為edge(a, d), edge(d, X)，歸結為edge(d, X)，再使用X是e合一為edge(d, e)，而這是個事實，因此X可能的另一值為e。

回想一下命令式的語言中，同樣的問題，就必須迭代與節點相接的節點，接著判斷其關係（方向性），而在Prolog中，這兩個部份都由解釋器來處理，也就是說，如果在命令式語言中，作了類似合一與歸結的流程，在撰寫Prolog程式時，就可以去除這類演算。

處理函式間的關係

當然，除了明顯是具有關係的問題之外，程式中還是會面對數學運算之類的問題，像是對清單進行計數與加總這類問題。

實際上，數學運算之類的問題，可以看作是函式與函式之間的關係問題。舉個簡單的例子，像是function avg2(n1, n2) = {return (n1 + n2 / 2);}這樣的函式，該怎麼寫成Prolog程式呢？

首先一定要釐清的是，Prolog程式中的規則不是函式——規則的結果只會是成立或不成立，不會有傳回值，然而，如果稍微瞭解合一與歸結的過程，就可以在規則中設計AVG之類的變數，讓Prolog去求解AVG，也就是可以寫成：avg2(N1, N2, AVG) :- AVG is (N1 + N2) / 2。不過要小心，AVG並不是傳出參數的概念，而是應該理解為「如果AVG is (N1 + N2) / 2成立，那麼avg2(N1, N2, AVG)就成立」。

由於Prolog解釋器會處理合一與歸結，因此，命令式語言中不必要的演算法，並不需要出現在Prolog程式碼之中，所以，結果就是：Prolog的程式碼看來就是宣告式風格。

事實上，如果看到一個數學相關的問題，像是對清單進行計數與加總，可以先試著以函數式程式設計的風格，將相關的函式撰寫出來，然後，再使用上頭將avg2(n1, n2)轉換為avg2(N1, N2, AVG)的方式，寫出Prolog的程式碼——就算是快速排序法這類更為複雜的問題，也可以如此。

這是因為，採用函數式程式設計的風格撰寫時，最後，程式碼會是宣告函式是什麼（What），而不是函式中如何（How）進行運算。而在這個過程中，被消除的「如何進行運算」，就是不必要的命令式演算法。

不過，別誤會了，函數式程式設計與Prolog之間，有著本質上的不同。

例如，在avg2(N1, N2, AVG) :- AVG is (N1 + N2) / 2, write(AVG)這樣的規則中，write(AVG)會列印出AVG的值，從函數式程式設計的觀點來看，會說這是有副作用，而說它不是純函數式，但並不是這麼解釋——對Prolog來說，其實是：如果AVG is (N1 + N2) / 2成立且write(AVG)成立，那麼，avg2(N1, N2, AVG)才會成立。

你的程式中有什麼呢？

世界上有許多程式語言，每種都有其思想，而學習不同程式語言的目的，就在於會訝異，解決問題竟然可以有這麼多不同的切入方向。

從另一個角度來看，也就表示了，必要時，程式可以包含這些方向中的其中幾個，也許是命令式的想法，也許是物件導向，也許是數學，或者，也有可能是邏輯。

那麼你寫出來的程式中會有什麼呢？是否什麼都沒有？沒有演算法、物件導向、數學，也許連邏輯都沒有，這可不是開玩笑，現實中，的確發現有程式包含了if(a>10 && a<2)這樣的奇妙邏輯。

現今接觸程式設計，越來越簡單了，這不能說是壞事，畢竟這也表示，目前世界關注的重點之一，就是程式設計。然而，別讓程式設計只成為單純的語句組裝。

當我接觸函數式程式設計之後，開始會想著，我的程式中真的有函式嗎？當接觸3D程式建模之後，我總是會想，模型中有數學嗎？

在接觸了Prolog之後，我不禁在面對程式時，又開始思考了：我的程式真的有所謂的邏輯嗎？如果有人聲稱他寫的程式中，有著（或許也只有著）某種邏輯，而實際上並沒有，那他的程式中到底剩下了什麼呢？