在我先前專欄〈用「邏輯」寫程式〉中,曾經提過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之後,我不禁在面對程式時,又開始思考了:我的程式真的有所謂的邏輯嗎?如果有人聲稱他寫的程式中,有著(或許也只有著)某種邏輯,而實際上並沒有,那他的程式中到底剩下了什麼呢?

作者簡介


Advertisement

更多 iThome相關內容