Alain Colmerauer, Prolog之父
Alain Colmerauer生于1941年1月24日,是法国计算机科学家。和他在马赛大学的助手于1962年发明了逻辑语言Prolog和Q-Systems。
在之后的30年中,Prolog经过几代的发展,作为一种程序设计语言已经相当成熟。如今,Prolog已成为人工智能领域不可缺少的一个工具,在世界任何地方都能看到它的踪迹。
Prolog诞生记 编辑本段回目录
众所周知,"Prolog"1972年诞生于法国的马赛。"Prolog"一词是"PROgrammation enLOGique"(逻辑程序设计语言)的缩写。意思是实现一个用自然语言进行人机对话的软件工具。可以说,Prolog是自然语言与自动定理证明完美结合的产物。当时。像用法语这样一类的自然语言直接与计算机进行问答与交谈的想法简直是异想天开。就在这样的情况下,Alain Colmerauer在1970年夏开始着手进行这个项目的研究。Alain有过计算机自然语言处理的经验,他想扩大他的研究领域。
1970年7月初,Robert Pasero和Philippe受Alain的邀请来到了蒙特利尔(Montreal)。Alain那时是蒙特利尔大学的计算机系副教授,正领导着一项叫做TAUM(Taduction Automatique de Universite de Montreal)的自动翻译项目。也许他们并没有意识到,他们处于事业的转折点上。当时Rober和Philippe只有25岁,他们在一个大学的计算机系任教。Alain也只有29岁,他从加拿大回到法国只有三年的时间。
在蒙特利尔大学待了两个月后,Robert和Philippe熟悉了自然语言的计算机处理技术。他们用Algol 60开发了一些不确定上下文的无关分析器,也用Q-System开发了一个法语翻译器。Q-System是Alain为翻译项目开发的一种编程语言。
与此同时,加拿大科学家Jean Trudel和Alain的一个博士生选择的研究项目是自动定理证明。他参考了Alan Robinson 1965年关于消解原理(resolution principle)的文章。在1970年,这是一篇非常难懂的文章,好在Jean曾在纽约上过Martin Davis讲授的数理逻辑课程。他已经开发了一个完整的定理证明器,那时他采用了一种新的编程风格,所有的计算都是用可变指针实现的。
1971:第一步
1971年初,大家都回到马赛。Alain获得了在计算机系任教的机会,Jean Trudel也能够开始协助他。这个项目的目标是实现基于法语文本的推理机。他们进行了分工:Jean Trudel和Philippe研究推理机部分,Robert Pasero和Alain研究自然语言部分。
他们能够使用的计算机是马赛大学计算中心的一台IBM 360-44,它配有900K的内存和不带虚拟内存的操作系统。为了充分利用所有可用的内存,他们在晚上用上了Jean Trudel开发的交互式监视器,这样,他们的工作条件就相当不错了:有几乎1M的内存可供程序执行,并能在操作员控制台上通过法语在用户和程序之间进行交互式通讯。
Jean Trudel改进了他的证明器,然后Philippe从5月开始用Algol-W写了一套证明器。不久整个小组开发出了一个原始自然语言会话系统。逻辑公式与法语的接口由50条Q-System输入规则和17条Q-System输出规则组成。推理部分是用Philippe开发的证明器来实现的。这时就可以和计算机作如下的交谈了:
用户:
Cats kill mice.
Tom is a cat who does not like mice who eat cheese.
Jerry is a mouse who eats cheese.
Max is not a mouse.
What does Tom do?
计算机:
Tom does not like mice who eat cheese
Tom Kills mice.
用户:
Who is a cat?
计算机:
Tom.
用户:
What does Jerry eat?
计算机:
Cheese.
用户:
Who does not like mice who eat cheese?
计算机:
Tom.
用户:
What does Tom eat?
计算机:
What cats who do not like mice who eat cheese eat.
正当Jean Trudel继续进行自动定理证明的研究时,他偶然看到一个非常有趣的方法:SL-消解法(Kowalski 1971)。他说服Alain邀请这个理论的发明者之一Robert Kowalski于1991年6月到马赛访问。这次会面令人终生难忘。他们第一次同一个能解释消解理论及其变化和优化的自动定理证明专家进行了探讨。
对Robert Kowalski来说,他所遇到的是一群对他的研究深感兴趣并决定把它用于自然语言处理的人。
1972:创建Prolog的应用程序
1972是丰收的一年。首先,2月份小组从一个加入法国工业部计算机研究院的信息自动化研究所那里获得了为期18个月的12.2万法郎(当时值2万美元)经费。这使他们得以购买一台电传终端(30字符/秒),并用300波特率联在Grenoble大学的IBM 360-67计算机上(该机用的是一个了不起的操作系统CP-CMS,它能管理虚拟设备)。在以后的三年里,它是小组最常用的计算机系统。每个人都使用它,包括来访问的研究人员。后来累积起来的所欠Grenoble大学的机时费他们化了几年的时间才还清。当时这笔钱使他们得以雇了一个秘书和一个研究员——博士后Henry Kanoui,他研究法语构词法。Kowalski后来获得了NATO基金会的资助。
在Philippe实现的所有消解系统中,R.Kowalski和D.Kuehner的SL-消解法是最有趣的。它的栈操作方式像标准程序设计语言中过程调用的管理模式,而且用反跟踪的方法比拷贝和保存消解式的方法来处理不确定理论更合适。SL-消解法也成为Philippe关于自动定理证明中有关形式等式处理论文的主题。形式等式的表达能力不如标准等式,但是它处理起来效率非常高。在Prolog最早的版本中就引入了Philippe论文中的否定谓词dif(≠)。4月和5月,他们再次邀请了Robert Kowalski。这以后,大家关于自动定理证明的计算知识更为丰富了。他们知道怎样将小问题(加入整数、表连接、表反转)公理化以使SL-消解证明器运算效率更高。
1972年秋,Philippe用Niklaus Wirt的Algol-W语言实现了第一个Prolog系统。同时,Alain和Robert Pasero建立了期待已久的用法语进行人机交谈的系统。Prolog是在它的开发者Philippe和用它进行编程的Alain、Robert、Pasero之间没有间断过的相互讨论中一步一步建立起来的。也正是这个时候,它有了一个确定的名字,它的命名受到了Philippe的妻子的启发。
人机对话系统是用Prolog写的第一个最大的程序。它有610条子句:Alain写了其中334条,主要是分析部分;Robert Pasero写了162条,是纯推理部分;Henry Kanoui用104条语句写了一个法语构词器,它能识别所有普遍名词的单复数和现在一般时第三人称单数的所有动词,甚至是不规则动词。下面是1972年人机交谈系统的一段对话:
Evey psychiatrist is a person.
Every person he analyzes is sick.
Jacques is a psychiatrist in Marseille.
Is Jacques a person?
Where is Jacques?
Is Jacques sick?
后面三个问题的回答是:
Yes.
In Marseille.
I don't know.
(原始的问答实际上是用法语的)
所有的推论是根据名词(he、she、they等),冠词(the、a、every等),带或不带介词(from、to等)的主语和补语作出来的。事实上,系统只认识代词、冠词和介词(词汇表是用164条子句编码的),它能认识专用名词(在词前打个星号)以及基于104条子句表示的法语构词法的动词和普通名词。
11月,他们在美国访问了许多研究所的实验室。他们随身携带着关于自然语言对话系统以及最早Prolog版本的报告。他们几乎在所到之处都留下了这些报告的副本。Jacques Cohen在波士顿迎接了他们,并把他们介绍给了MIT,在那儿他们受到了热烈欢迎。
1973:Prolog新版本
最早的Prolog版本的用户在应用中积累了大量的编程经验,对Prolog第二版的推出起了不可估量的作用。第二版完全面向计算机编程语言,不再仅仅是一种自动推理机。除了1972年的法语对话系统,另外在最初的Prolog版本上开发了两个系统:一个符号运算系统和一个叫做Sugiton的通用问题求解系统。Robert Pasero也用它继续进行法语语义研究,至1972年5月份,非常出色地完成了他的论文。
1973年2~4月,Philippe参观了爱丁堡大学人工智能学院,那里有Bernard Meltzer领导的计算逻辑系。Philippe同David Warren、Roger Boyer和Jay Moore进行了广泛的讨论。
他们用了一个极其天才的方法构造了消解系统,这种方法基于一种用结构共享技术表示在推理中生成的逻辑公式的思想。这次访问使Philippe他们看到了实验室对真正编程语言的要求,同时也坚定了他们推出Prolog第二版的决心。
1973年5~6月间,他们制订出语言的大致框架,尤其是确定了语法、推理机计算方法的基本原语,这比第一版有所简化。从6月至年底,G e rard Battani、Henry Meloni和ReneBazzoli用Fortran写了推理机,用Prolog本身写了管理程序。
1974~1975:Prolog的传播
在Grenoble大学运行的那个基于电传方式的交互式Prolog版本的需求量非常大。当时的系统部分用Fortran实现,部分用Prolog实现,它每秒大约能进行200条归约操作。在此之上开发了大量的实用系统。后来和Alain一起工作的David Warren用Prolog写了规划生成系统Warplan;Henry Kanoui和Marc Bergman用它开发了一个具有相当规模的符号处理系统Sycophante;Gerard Battani和Henry Meloni开发了语言识别系统,它能回答与IBM的操作系统CP-CMS有关的问题。
1975年初,Alain Colmerauer完全重写了管理程序,他保留了用Prolog写的中缀运算符说明,但加入了一个叫做"元构形(metamorphosis)"语法的编译器。而Rene Bazzoli的方法则是用自顶向下分析方法来读Prolog规则。David Warren后来用这类语法规则开发了他的Prolog编译版本,并和Fernando Pereira一起把一种简化的元构形语法命名为"有限子句语法(definite clause grammars)"。元构形语法能使语法规则直接参数化地表示出来。加了两个参数之后,管理程序便能将这些规则编译成Prolog子句。为了证明元构形语法具有优秀的表达能力和较高的处理效率,Alanin从Algol一直到伪汇编语言风格写过几个小型编译器,并用自动推理机实现了一个完整的人机对话系统。他的所有这些工作都成了元构形语法的理论基础。
Gerard Battani与Henry Meloni整天忙于Prolog的传播。他们把Prolog送到巴尔的摩、华沙、多伦多和加拿大的滑铁卢,还到爱丁保协助David Warren将Prolog装在PDP 10上。Alain以前的学生He le ne Le Gloan把它装到了蒙特利尔大学的机器上,巴黎的Michel Van Caneghem在IRIA也装了多套。后来,Maurice Bruynooghe在马赛待了三个月后将Prolog到了比利时。
1975年,小组准备将推理机移植到16位微机T1600上。这种机器只有64K内存,所以必须首先为它写一个专用的虚拟内存管理系统。大家搞了一个竞赛,结果Pierre Basso的程序独占鳌头,他的程序代码最短,而且能够处理32位寻址和缺页检测。接着小组的每个成员分到两页Fortran程序将它翻译成机器语言。当大家把程序连接起来的时候,竟奇迹般地运行通过了。Prolog的微机版本就这样诞生了。
事实上,由于越来越多的人对Prolog开始感兴趣,他们不断从马赛和爱丁堡拷走Prolog,Prolog的转播速度大大出乎人的预料。正如David Warren所说的,Prolog不是"传播"出去的,而是从大学里"逃离"出去的。
在之后的20年中,Prolog经过几代的发展,作为一种程序设计语言已经相当成熟。如今,Prolog已成为人工智能领域不可缺少的一个工具,在世界任何地方都能看到它的踪迹。
Prolog编辑本段回目录
编程范型 逻辑编程语言
面市時間 1972年
设计者 Alain Colmerauer
主要实作产品 BProlog,GNU Prolog, Quintus, SICStus, Strawberry, SWI-Prolog, YAP-Prolog
衍生副语言 ISO Prolog, Edinburgh Prolog
影响语言 Visual Prolog, Mercury, Oz, Erlang, Strand
Prolog(Programming in Logic的缩写)是一种逻辑编程语言。它建立在逻辑学的理论基础之上, 最初被运用于自然语言等研究领域。现在它已广泛的应用在人工智能的研究中,它可以用来建造专家系统、自然语言理解、智能知识库等。
历史
Prolog语言最早由Aix-Marseille大学的Alain Colmerauer与Phillipe Roussel等人于60年代末研究开发。1972年被公认为是Prolog语言正式诞生的年份,自1972年以后,分支出多种Prolog的方言。最主要的两种方言为Edinburgh和Aix-Marseille。最早的Prolog解释器由Roussel建造,而第一个Prolog编译器则是David Warren编写的。
Prolog一直在北美和欧洲被广泛使用。日本政府曾经为了建造智能计算机而用Prolog来开发ICOT第五代计算机系统。在早期的机器智能研究领域,Prolog曾经是主要的开发工具。
80年代Borland开发的Turbo Prolog,进一步普及了Prolog的使用。1995年确定了ISO Prolog标准
特点
有别于一般的过编程语言,prolog的程式是基于谓词逻辑的理论。最基本的写法是定立物件与物件之间的关系,之后可以用询问目标的方式来查询各种物件之间的关系。系统会自动进行匹配及回溯,找出所询问的答案。