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 */
参考文献
外部連結
- 实现
参见
- Visual Prolog
- LISP
- non-Monotonic Logic