Prolog

**Prolog**
編程範型	邏輯式
設計者	Alain Colmerauer（英語：Alain Colmerauer），羅伯特·科瓦爾斯基
釋出時間	1972年
副檔名	.pl, .pro, .P
主要實作產品
	B-Prolog（英語：B-Prolog）, Ciao語言（英語：Ciao (programming language)）, ECLiPSe（英語：ECLiPSe）, GNU Prolog（英語：GNU Prolog）, Poplog（英語：Poplog） Prolog, P#, Quintus Prolog, SICStus（英語：SICStus）, Strawberry（英語：Strawberry Prolog）, SWI-Prolog（英語：SWI-Prolog）, Tau Prolog, tuProlog（英語：tuProlog）, WIN-PROLOG（英語：Logic Programming Associates）, XSB（英語：XSB）, YAP（英語：YAP (Prolog)）
衍生副語言
	ISO Prolog, Edinburgh Prolog
啟發語言
	PLANNER（英語：PLANNER）
影響語言
	CHR（英語：Constraint Handling Rules）、Clojure、Datalog、Erlang、KL0（英語：KL0）、KL1（英語：KL1）、Mercury、Oz、Strand（英語：Strand (programming language)）、Visual Prolog、XSB（英語：XSB）
	維基教科書中有關Prolog的文字;

Prolog（Programming in Logic的縮寫）是一種邏輯程式設計語言。它建立在邏輯學的理論基礎之上，最初被運用於自然語言等研究領域。現在它已廣泛的應用在人工智能的研究中，它可以用來建造專家系統、自然語言理解、智能知識庫等。^[1]^[2]^[3]^[4]^[5]

歷史[編輯]

Prolog語言的理論基礎建立於愛丁堡大學的羅伯特·科瓦爾斯基對霍恩子句（Horn Clause）的程式性解釋，最早由艾克斯-馬賽大學的Alain Colmerauer與Phillipe Roussel等人於60年代末研究開發。1972年被公認為是Prolog語言正式誕生的年份，自1972年以後，分支出多種Prolog的方言。最主要的兩種方言為愛丁堡和艾克斯-馬賽。最早的Prolog直譯器由Roussel建造，而第一個Prolog編譯器則是David Warren編寫的。

Prolog一直在北美和歐洲被廣泛使用。日本政府曾經為了建造智能電腦而用Prolog來開發ICOT第五代電腦系統。在早期的機器智能研究領域，Prolog曾經是主要的開發工具。

80年代Borland開發的Turbo Prolog，進一步普及了Prolog的使用。1995年確定了ISO Prolog標準。

特點[編輯]

有別於一般的函數式語言，prolog的程式是基於謂詞邏輯的理論。最基本的寫法是定義物件與物件之間的關係，之後可以用詢問目標的方式來查詢各種物件之間的關係。系統會自動進行匹配及回溯，找出所詢問的答案。

Prolog代碼中以大寫字母開頭的元素是變數，字串、數字或以小寫字母開頭的元素是常數。底線（_）被稱為匿名變數。

語法範例[編輯]

事實陳述式，例如：

human(kate).
human(bill).
likes(kate,bill).

表示kate和bill是人（human），kate喜歡bill。

規則陳述式，例如：

friend(X,Y):-likes(X,Y),likes(Y,X).

表示對於兩個物件XY，如果X喜歡Y，且Y喜歡X，那麼他們是朋友。

Prolog範例[編輯]

範例如下：

Quicksort[編輯]

快速排序範例（對list作排序）：

/* quicksort2.pl    原始來源：http://en.wikipedia.org/wiki/Prolog   */
/* quicksort()中的第二個引數帶有排序好的結果　*/
/* 僅為示範，若為gprolog使用者則用內建sort等較佳 */
/* 在gprolog下之編譯例：gplc --min-size quicksort2.pl　*/
/*   執行 quicksort2 後會出現排序結果 [2,9,18,18,25,33,66,77] */

q:- L=[33,18,2,77,66,18,9,25], last(P,_), (quicksort(L,P,_), write(P), nl).    /* 加入last/2會在印P時沒複合項 */

partition([], _, [], []).			/* 此行表空集亦視為分割（分割成空集與空集）*/
partition([X|Xs], Pivot, Smalls, Bigs) :-	/* 原list分成Smalls與Bigs; 此规则保證Smalls集<Pivot且Bigs集>=Pivot */
    (   X @< Pivot ->
        Smalls = [X|Rest],
        partition(Xs, Pivot, Rest, Bigs)
    ;   Bigs = [X|Rest],
        partition(Xs, Pivot, Smalls, Rest)
    ).
 
quicksort([])     --> [].			/* 表empty list視為排序好的list */
quicksort([X|Xs]) -->			/* 此行相當於quicksort([X|Xs],Start,End) :-  此规则讓Start為sorted list */
    { partition(Xs, X, Smaller, Bigger) },	/* 由上行最左端元素為 Pivot */
    quicksort(Smaller), [X], quicksort(Bigger).	/* 此行相當於	quicksort(Smaller,Start,A),
    								A=[X|B],  注意首字母大寫者皆視為變數(list)
								quicksort(Bigger,B,End).  */
:- initialization(q).		/* 啟動q處goals */

sort[編輯]

下面簡潔的排序範例可以體會到為什麼AI領域喜用Prolog：

/* sortcsj.pl    原始參考：Computer Science  J. Glenn Brookshear   */
/* sortcsj()中的第二個引數帶有排序好的結果　*/
/* 僅為示範，若為gprolog使用者則用內建sort等較佳 */
/* 在gprolog下之編譯例：gplc --min-size sortcsj.pl　*/
/*   執行 sortcsj 後會出現排序結果 [2,9,18,18,25,33,66,77] */

q:- L=[33,18,2,77,18,66,9,25], (sortcsj(L,P), write(P), nl). 

sortcsj(L,S) :-  permutation(L,S), ordered(S).	/* L為原list, S為排序好的list, 此為permutation關係(built-in) */

ordered([]).			/* 表empty list視為排序好的list */
ordered([_|[]]).			/* 只有一元素之list視為排序好的list */
ordered([A|[B|T]]) :- A =< B, ordered([B|T]).	/* 此规则約束所謂的排序好是指前項元素小於或等於後一項元素 */

:- initialization(q).		/* 啟動q處goals */

Russell's paradox[編輯]

示範羅素悖論在Prolog下會導致堆疊溢位：

/* tstpx.pl */
/* 羅素佯謬(羅素悖論)（皇帝新腦 羅杰.彭羅斯 p.120）會導致不停機(使得gprolog產生 stack overflow) */
/* 在gprolog下之編譯例：gplc --min-size tstpx.pl　*/

q:- px(_).              /* 找尋任何可使 px() 规则成立的方式 */

px(1) :- \+ px(1).      /* 規定此规则不成立。 i.e. 此规则為假時此规则才為真 （佯謬）*/

:- initialization(q).           /* 啟動q處goal */

參考文獻[編輯]

^ Clocksin, William F.; Mellish, Christopher S. Programming in Prolog. Berlin; New York: Springer-Verlag. 2003. ISBN 978-3-540-00678-7.
^ Bratko, Ivan. Prolog programming for artificial intelligence 4th. Harlow, England; New York: Addison Wesley. 2012. ISBN 978-0-321-41746-6.
^ Covington, Michael A. Natural language processing for Prolog programmers. Englewood Cliffs, N.J.: Prentice Hall. 1994. ISBN 978-0-13-629213-5.
^ Stickel, M. E. A prolog technology theorem prover: Implementation by an extended prolog compiler. Journal of Automated Reasoning. 1988, 4 (4): 353–380. CiteSeerX 10.1.1.47.3057 . S2CID 14621218. doi:10.1007/BF00297245.
^ Merritt, Dennis. Building expert systems in Prolog. Berlin: Springer-Verlag. 1989. ISBN 978-0-387-97016-5.

外部連結[編輯]

Prolog 人工智能語言中文討論區

實現

SWI-Prolog（頁面存檔備份，存於互聯網檔案館）
Yap Prolog

參見[編輯]

[Clocksin2003-1] Clocksin, William F.; Mellish, Christopher S. Programming in Prolog. Berlin; New York: Springer-Verlag. 2003. ISBN 978-3-540-00678-7.

[Bratko2012-2] Bratko, Ivan. Prolog programming for artificial intelligence 4th. Harlow, England; New York: Addison Wesley. 2012. ISBN 978-0-321-41746-6.

[Covington1994-3] Covington, Michael A. Natural language processing for Prolog programmers. Englewood Cliffs, N.J.: Prentice Hall. 1994. ISBN 978-0-13-629213-5.

[4] Stickel, M. E. A prolog technology theorem prover: Implementation by an extended prolog compiler. Journal of Automated Reasoning. 1988, 4 (4): 353–380. CiteSeerX 10.1.1.47.3057 . S2CID 14621218. doi:10.1007/BF00297245.

[5] Merritt, Dennis. Building expert systems in Prolog. Berlin: Springer-Verlag. 1989. ISBN 978-0-387-97016-5.

[1]

[2]

[3]

[4]

[5]