Prolog
Prolog(Programming in Logic的縮寫)是一種邏輯程式設計語言。它建立在邏輯學的理論基礎之上, 最初被運用於自然語言等研究領域。現在它已廣泛的應用在人工智能的研究中,它可以用來建造專家系統、自然語言理解、智能知識庫等。[1][2][3][4][5]
編程範型 | 邏輯式 |
---|---|
設計者 | Alain Colmerauer,羅伯特·科瓦爾斯基 |
釋出時間 | 1972年 |
副檔名 | .pl , .pro , .P |
主要實作產品 | |
B-Prolog, Ciao語言, ECLiPSe, GNU Prolog, Poplog Prolog, P#, Quintus Prolog, SICStus, Strawberry, SWI-Prolog, Tau Prolog, tuProlog, WIN-PROLOG, XSB, YAP | |
衍生副語言 | |
ISO Prolog, Edinburgh Prolog | |
啟發語言 | |
PLANNER | |
影響語言 | |
CHR、Clojure、Datalog、Erlang、KL0、KL1、Mercury、Oz、Strand、Visual Prolog、XSB | |
歷史
編輯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
編輯/* 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.
外部連結
編輯- 實現
參見
編輯