Prolog
Prolog(的缩写)是一种逻辑编程语言。它创建在逻辑学的理论基础之上, 最初被运用于自然语言等研究领域。现在它已广泛的应用在人工智能的研究中,它可以用来建造专家系统、自然语言理解、智能知识库等。[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. . Berlin; New York: Springer-Verlag. 2003. ISBN 978-3-540-00678-7.
- Bratko, Ivan. 4th. Harlow, England; New York: Addison Wesley. 2012. ISBN 978-0-321-41746-6.
- Covington, Michael A. . Englewood Cliffs, N.J.: Prentice Hall. 1994. ISBN 978-0-13-629213-5.
- Stickel, M. E. . Journal of Automated Reasoning. 1988, 4 (4): 353–380. CiteSeerX 10.1.1.47.3057
. S2CID 14621218. doi:10.1007/BF00297245.
- Merritt, Dennis.
. Berlin: Springer-Verlag. 1989. ISBN 978-0-387-97016-5.