冒號課堂
第四課 重溫范式（2）
4.2邏輯范式——當(dāng)算法失去了控制
道常無為而無不為 ——《老子·道經(jīng)》
關(guān)鍵詞： 編程范式,邏輯式編程,Prolog,算法,邏輯,控制
摘要： 再談邏輯式編程
？提問
- 衡量軟件復(fù)雜度是由代碼的長度決定的嗎？
- 為什么邏輯式的編碼一般比過程式的更簡潔？
- 邏輯式編程相比命令式編程有哪些優(yōu)勢和劣勢？
：講解
問號提出：“邏輯式編程不是也很特別嗎？前面似乎介紹得也不多。”
“那我們就用邏輯式語言Prolog再實(shí)現(xiàn)一次quicksort吧。”冒號說著將幻燈片翻頁——
/*快速排序法的Prolog實(shí)現(xiàn)*/
/* 定義劃分法 */
partition(_,[],[],[]). /* 劃分遞歸終點(diǎn) */
partition(Pivot,[X|Rest],[X|Small],Big) :-
X < Pivot, partition(Pivot,Rest,Small,Big). /* 比基準(zhǔn)小的歸入Small */
partition(Pivot,[X|Rest],Small,[X|Big]) :-
X >= Pivot, partition(Pivot,Rest,Small,Big). /* 比基準(zhǔn)大的歸入Big */
/* 定義排序法 */
qsort([],[]). /* 排序遞歸終點(diǎn) */
qsort([Pivot|Rest],Sorted) :-
partition(Pivot,Rest,Small,Big), /* 按基準(zhǔn)劃分子列 */
qsort(Small,SortedSmall), /* 對前面的子列遞歸 */
qsort(Big,SortedBig), /* 對后面的子列遞歸 */
append(SortedSmall,[Pivot|SortedBig],Sorted)./* 子列合并 */
逗號撓撓頭：“看不太懂哦，好在我記住了您的一句話：容忍無知。我忍了！”
大伙都樂了。
“本節(jié)課的焦點(diǎn)不是語言而是范式，因此對Prolog代碼不詳加解說。我只簡單地說三點(diǎn)：首先，Prolog代碼是由一系列事實(shí)（fact）、規(guī)則（rule）和查詢（query）語句組成的[1]。其次，與大多數(shù)語言不同的是，大寫字母或下劃線開頭的標(biāo)識符是變量，其他的是常量或函數(shù)。請注意，這不是約定俗成，而是語法規(guī)定。最后，符號‘:-’等價(jià)于if；逗號‘,’等價(jià)于and。比如，我們可以用Prolog來表達(dá)一個(gè)斷言：如果一個(gè)人未婚且為男士，那么他就是一光棍。”冒號轉(zhuǎn)身在黑板上寫下——
/* X is bachelor if X is unmarried and male*/
bachelor (X) :- unmarried(X) , male(X).
聽見下面一陣嘀咕聲，冒號忽地閃過一個(gè)念頭：這個(gè)例子該不會(huì)傷了某位滿足條件的同志吧？頓了一會(huì)，繼續(xù)說道：“邏輯式實(shí)現(xiàn)的排序雖不比函數(shù)式更簡潔，但比過程式來還是綽綽有余的。畢竟同屬聲明式，省去了不少有關(guān)變量賦值、迭代和流程控制方面的代碼。我們再看一個(gè)更加典型的范例。”
黑板上出現(xiàn)了一幅樹狀圖形——
冒號簡作說明：“這是一個(gè)三代家譜圖。已知每人的性別和父輩，要求判斷任意兩人之間的關(guān)系。我們先用Java來試一試——”
class Person
{
private Person parent;
private boolean isMale;
public Person(Person parent, boolean isMale)
{
this.isMale = isMale;
this.parent = parent;
}
private boolean isSibling(Person other)
{
return parent == other.parent && parent != null && this != other;
}
public String getRelation(Person other)
{
if (other == null || this == other) return null;
if (parent == other) return isMale ? "son" : "daughter";
if (other.parent == this) return isMale ? "father" : "mother";
if (parent == null) // this是老祖宗
{
if (other.parent == null) return null;
if (other.parent.parent == this) return isMale ? "grandfather" : "grandmother";
return null;
}
if (other.parent == null) // other是老祖宗
{
if (parent.parent == other) return isMale ? "grandson" : "granddaughter";
return null;
}
// 非直系
if (isSibling(other)) return isMale ? "brother" : "sister";
if (parent.isSibling(other.parent)) return "cousin";
if (parent.isSibling(other)) return isMale ? "nephew" : "niece";
if (isSibling(other.parent)) return isMale ? "uncle" : "aunt";
return null;
}
public static void main(String[] args)
{
Person a = new Person(null, true);
Person b = new Person(a, true);
Person c = new Person(a, true);
Person d = new Person(a, false);
Person e = new Person(b, false);
Person f = new Person(b, true);
Person g = new Person(c, false);
Person h = new Person(d, true);
Person i = new Person(d, false);
Person j = new Person(d, true);
// 以下省略。。。
}
}
“這段代碼很平凡，毋需多言。再來看看邏輯式語言的做法。”冒號不愿過多地糾纏于細(xì)節(jié)，隨即又換成了Prolog代碼——
/* 規(guī)則 */
/* 上下兩代直系關(guān)系 */
father(X,Y) :- parent(X,Y), male(X).
mother(X,Y) :- parent(X,Y), female(X).
child(X,Y) :- parent(Y,X).
son(X,Y) :- parent(Y,X), male(X).
daughter(X,Y) :- parent(Y,X), female(X).
/* 祖孫關(guān)系 */
grandparent(X,Y) :- parent(X,Z), parent(Z,Y).
grandfather(X,Y) :- grandparent(X,Y), male(X).
grandmother(X,Y) :- grandparent(X,Y), female(X).
grandchild(X,Y) :- grandparent(Y,X).
grandson(X,Y) :- grandparent(Y,X), male(X).
granddaughter(X,Y) :- grandparent(Y,X), female(X).
/* 平輩關(guān)系 */
/* 若X與Y有相同的父輩Z，且X不是Y，則X與Y是同胞*/
sibling(X,Y) :- parent(Z,X), parent(Z,Y), X"==Y.
brother(X,Y) :- sibling(X,Y), male(X).
sister(X,Y) :- sibling(X,Y), female(X).
cousin(X,Y) :- parent(Z,X), parent(W,Y), sibling(Z,W).
/* 上下兩代旁系關(guān)系 */
uncle(X,Y) :- parent(Z,Y), brother(X,Z).
aunt(X,Y) :- parent(Z,Y), sister(X,Z).
nephew(X,Y) :- parent(Z,X), sibling(Z,Y), male(X).
niece(X,Y) :- parent(Z,X), sibling(Z,Y), female(X).
/* 定義一個(gè)普適關(guān)系relation，方便查詢 */
relation(R, X, Y) :- relations(Rs), member(R,Rs), Q =..[R,X,Y], call(Q).
/* 事實(shí) */
/* 關(guān)系列表 */
relations([parent,father,mother,son,daughter,grandparent,grandfather,
grandmother,grandchild,grandson,granddaughter,
sibling,brother,sister,cousin,uncle,aunt,nephew,niece]).
parent(a,b). parent(a,c). parent(a,d).
parent(b,e). parent(b,f).
parent(c,g).
parent(d,h). parent(d,i). parent(d,j).
male(a).
male(b).
male(c).
female (d).
female (e).
male(f).
female (g).
male(h).
female (i).
male(j).
嘆號沒有看出名堂：“Prolog代碼并不比Java代碼簡短多少啊。”
“評價(jià)代碼的復(fù)雜度，長短只是一個(gè)因素。程序員不是打字員，花在思考上的時(shí)間和精力遠(yuǎn)遠(yuǎn)超過花在鍵盤上。”冒號指出，“就拿此例來說，Java代碼雖然并不復(fù)雜，但有不少的選擇分支語句，次序很重要。稍有不慎，就會(huì)出現(xiàn)邏輯錯(cuò)誤。另外如果我們把關(guān)系分得更細(xì)致些，比如區(qū)分叔伯舅、姑姨嬸、堂兄表妹等；再加入姻親關(guān)系，比如姑嫂婆媳、妯娌連襟等。這時(shí)你再來改寫這段代碼試試？”
引號聽得頭皮有些發(fā)麻：“那一定需要不少重重嵌套的if-else語句了。”
問號提出的問題更讓人頭痛：“如果我們不限于三代，再加上曾孫女、曾叔父之類的關(guān)系呢？”
逗號聯(lián)想到一則笑話：“話說一對父子與一對母女聯(lián)姻，作父親的娶了那位女兒，作兒子的娶了那位母親。本來關(guān)系已經(jīng)夠顛倒錯(cuò)亂了，雪上加霜的是這兩對夫婦又各自有了子女，那位父親終于精神崩潰了。”
大家哄笑著：這下徹底亂套啰。
“前面的Java代碼之所以沒有嵌套，得益于及時(shí)退出的一些return語句。如果考慮到超過三代的關(guān)系以及多重交叉的關(guān)系，許多語句都得改寫。可見上述代碼是多么地脆弱！” 冒號就棍打腿，“再看Prolog代碼，如果要求更細(xì)的血親關(guān)系、增加姻親關(guān)系或三代以上的關(guān)系，只需引入新的規(guī)則和事實(shí)即可，不會(huì)影響原有代碼。下面列出幾個(gè)示范語句——”
/* 規(guī)則 */
/* 配偶原則 */
father(X,Y) :- spouse(Z,X), mother(Z,Y).
mother(X,Y) :- spouse(Z,X), father(Z,Y).
husband(X,Y) :- spouse(X,Y), male(X).
wife(X,Y) :- spouse(X,Y), female(X).
/* 父系的堂、姑兄弟姐妹 */
paternal_cousin(X,Y) :- father(Z,X), father(W,Y), sibling(Z,W).
/* 母系的舅、姨兄弟姐妹 */
maternal_cousin(X,Y) :- mother(Z,X), mother(W,Y), sibling(Z,W).
/* 姻親關(guān)系 */
father_in_law(X,Y) :- spouse(Y,Z), father(X,Z).
mother_in_law(X,Y) :- spouse(Y,Z), mother(X,Z).
son_in_law(X,Y) :- spouse(X,Z), daughter(Z,Y).
daughter_in_law(X,Y) :- spouse(X,Z), son(Z,Y).
/* 曾祖孫關(guān)系 */
great_grandparent(X,Y) :- grandparent(Z,Y), parent(X,Z).
great_grandchild(X,Y) :- grandchild(Z,Y), child(X,Z).
/* 事實(shí) */
/* 新引入的關(guān)系 */
relations([husband,wife, paternal_cousin,maternal_cousin,
father_in_law,mother_in_law,son_in_law,daughter_in_law,
great_grandparent,great_grandchild]).
parent(pa,a).
spouse(a,as).
spouse(ds,d).
spouse(cs,c).
句號方悟其妙：“這樣的代碼既無層層嵌套，也無次序分別。比起過程式，編寫輕松得多，程序的可維護(hù)性和可擴(kuò)展性也更高。”
“此外另有妙處。邏輯式與過程式和函數(shù)式的一個(gè)不同之處是，它沒有明顯的輸入、輸出之分。上面的程序不僅可以用來判斷任意二人之間的關(guān)系，還能倒過來通過關(guān)系來找人。”冒號板書了幾行字——
輸入查詢：relation(R,a,ds) /* a與ds的關(guān)系是什么？ */
輸出結(jié)果：R=father_in_law
輸入查詢：great_grandparent (pa,X) /* pa是誰的曾祖？*/
輸出結(jié)果：X=e;X=f;X=g; X=h; X=i; X=j;
引號義務(wù)作翻譯：“這告訴我們兩件事：a與ds是翁婿關(guān)系，pa有曾孫e、f、g、h、i和j。”
“邏輯式語言著眼于關(guān)系而非函數(shù)，對付這類問題正是它的拿手好戲。”冒號聲音逐漸高亢，“大家應(yīng)該都聽說過等式‘算法+數(shù)據(jù)結(jié)構(gòu)=程序’吧？這是Pascal設(shè)計(jì)者Niklaus Wirth的一本著作的書名，它刻畫了過程式尤其是結(jié)構(gòu)化編程的思想。后來Robert Kowalski進(jìn)一步提出：算法=邏輯+控制。其中邏輯是算法的核心，控制主要用于改進(jìn)算法的效率。在邏輯式編程中，程序員只需表達(dá)邏輯，而控制交給編程語言的解釋器或編譯器去管理。”
“所以程序員的負(fù)擔(dān)大大減輕了。”問號接口道，“邏輯式編程聽起來真是不錯(cuò)，但不知Prolog程序能否與Java程序?qū)幽兀?#8221;
冒號回答：“任何程序之間的對接都是可能的，只是不同的對接方式在復(fù)雜度和效率上有所差異而已。除了通過程序之間的通訊（如socket）或可執(zhí)行文件的直接調(diào)用外，Prolog與C、C++、Java、C#、VB、Perl、JavaScript等多種語言之間，還能借助工具進(jìn)行源代碼轉(zhuǎn)換[2]或通過雙向編程接口互嵌代碼。具體到Java，一方面可以通過JNI (Java Native Interface)與Prolog引擎相連[3]，另一方面可以利用Prolog引擎的Java實(shí)現(xiàn)來完成JVM上的集成[4]。”
句號請求：“能否總結(jié)一下邏輯式編程的優(yōu)缺點(diǎn)？”
冒號欣然應(yīng)允：“由于邏輯式編程模擬人類的邏輯思維，故而在機(jī)器證明、專家系統(tǒng)、自然語言處理、博弈等人工智能領(lǐng)域如魚得水，同時(shí)在非學(xué)術(shù)領(lǐng)域的知識管理、智能決策分析等方面也能大顯身手。同為聲明式，它與函數(shù)式一樣比命令式更簡潔、更抽象、更少副作用，運(yùn)用得當(dāng)能大大提高生產(chǎn)效率，還能用于快速原型（rapid prototyping）開發(fā)。但缺點(diǎn)是運(yùn)行效率偏低，可掌控性較差，與常規(guī)的過程式思維差異較大，更適合基于規(guī)則（rule-based）而不是基于狀態(tài)（state-based）的應(yīng)用[5]。此外，相對而言邏輯式語言還不夠成熟和完善。”
逗號“抗議”道：“我怎么感覺經(jīng)過這么一反芻，胃里的負(fù)擔(dān)更重了？”
冒號略帶歉意地笑了笑：“在所有編程范式中，函數(shù)式與邏輯式與傳統(tǒng)思維方式的差別最大，此前的介紹又過于簡單，因此今天特意多談了些。既然有人提意見，那就我就適可而止了。最后請?jiān)试S我畫蛇添足：在代表計(jì)算機(jī)最高水平的人工智能領(lǐng)域中，這兩種范式發(fā)揮著舉足輕重的作用。單憑這一點(diǎn)，它們也是值得學(xué)習(xí)和借鑒的。好了，大家先休息十分鐘，出去活動(dòng)活動(dòng)筋骨吧。”
，插語
[1] 用數(shù)學(xué)邏輯的話來說，事實(shí)與規(guī)則是公理，查詢是定理。
[2] 如Prolog Café和P#能分別將Prolog代碼轉(zhuǎn)化為Java代碼和C#代碼。
[3] 比如JPL通過JNI與Prolog FLI （Foreign Language Interface）將Java與SWI-Prolog橋接起來。
[4] 比如JIProlog（Java Internet Prolog）是一個(gè)用Java實(shí)現(xiàn)的Prolog解釋器，為Java和Prolog提供雙向API。類似的還有JLog等。
[5] 交互式或事件驅(qū)動(dòng)式應(yīng)用通常是基于狀態(tài)的。
。總結(jié)
- 代碼的長度不是衡量軟件復(fù)雜度的唯一標(biāo)準(zhǔn)。其中的邏輯結(jié)構(gòu)越復(fù)雜、越微妙、受需求變化的影響越大，軟件越難控制和維護(hù)。
- 算法=邏輯+控制。邏輯式編程將算法中的控制部分大都移交給編程語言，編程人員主要關(guān)注算法的核心邏輯。這樣大大減輕了程序員的負(fù)擔(dān)，編碼也更簡潔易懂，更具可維護(hù)性和可擴(kuò)展性。
- 有別于過程式和函數(shù)式，邏輯式?jīng)]有明顯的輸入和輸出之分。
- 邏輯式編程不僅適用于人工智能方面的學(xué)術(shù)領(lǐng)域，同樣廣泛適用于各種涉及知識管理、決策分析等方面的應(yīng)用領(lǐng)域。
- 相對于命令式，邏輯式更簡潔、更抽象、更少副作用，能提高生產(chǎn)效率，還能用于快速原型開發(fā)。但在運(yùn)行效率、可掌控性、語言成熟度等方面有所欠缺。另外，因其思維方式獨(dú)特而鮮為人用，適合基于規(guī)則而非基于狀態(tài)的應(yīng)用 。
“”參考
[1] Michael Lee Scott．Programming Language Pragmatics．San Francisco：Morgan Kaufmann，2000．620-650
[2]Robert A. Kowalski．Algorithm = Logic + Control．Communications of the ACM，1979，22(7)：424-436