Lisp语言的发展

Lisp语言的发展

国家智能计算机研究开发中心 刘晓华

--------------------------------------------------------------------------------

一、引言

Lisp是一个优美的高级语言,它的发展经历了漫长的复杂的历程。在Lisp作为高级语言

出现以前,大约经过了两年的酝酿(1956～1958),形成了Lisp的许多基本设计思想。1958年

秋进入Lisp的实现与初步应用时期,这一时期(1958～1962),Lisp的发展基本上是单线的。

1962年以后Lisp的发展变成多线,在这一段时期(1962～1984),不同的机构团体提出许多不

同的思想,形成了"百家争鸣"的局面。直到Common Lisp(1984)出现以后,Lisp的发展才进入

标准化时代。不同寻常的发展过程使得Lisp成为继Fortran语言之后第二个历史最长使用最

广泛的语言。

二、Lisp前期和早期(1956～1962)

Lisp前期(1956～1958)始于John McCarthy的一种愿望:为IBM 704计算机提供一个代数

表处理语言,以便适用于人工智能(AI)的研究。这种愿望是1956年夏在Dartmouth举行的AI研

究计划讨论会上他受到Newell,Shaw和Simon描述的IPL2——表处理语言的启发而萌发的。

但他并不想直接采用IPL2,原因有两个:①IPL2是用来实现逻辑定理证明的,而且依赖于Ran

d公司的JOHNNIAC机器;②Fortran语言结构用来进行表处理也是很有吸引力的(后面我们将

会谈到)。这种愿望最终变成现实:IBM公司慷慨承担了在MIT成立New England Computatio

n Center和开发一个证明平面几何定理的程序,当时John McCarthy是这个项目的顾问。

John McCarthy选择表作为程序句子的基本表示单位。表结构不仅能表示符号信息,而

且适合逻辑推理,即适合进行符号处理。尽管有其他一些采用传统表示方法的符号处理系统

,但McCarthy放弃了传统的中缀表示方法而采用了前缀形式,因而能很快地决定机器下一步

应该采取的动作。这个特征可能是Lisp在和其他语言的竞争中取得成功的原因。但是如何

在机器上存储表结构和对表结构进行操作,这是一个技术问题，而且和具体的机器有关,如机

器字及其bit数。

最初,提出了对表结构进行操作的基本操作。这些操作都是针对寄存器的字或地址进行

的。cwr表示取寄存器中字的内容,car表示取寄存器中地址的内容,还定义了cdr、cpr和ct

r三个类似的函数,cons最初是定义为一个例程而不是一个函数。这些思想几乎都是在Dart

month的New England Computation Center形成的,但是没有在机器上实现。

同时进行的另一部分工作,是在Fortran中实现一个表处理语言,当时IBM有一个平面几

何证明的项目。在McCarthy的建议下,N.Rochester和H.Gelerneter等决定在Fortran中增加

关于表处理的功能,提出了FLPL语言(Fortran表处理语言),把cons处理为一个函数。尽管F

LPL能容易地处理表达式和编写平面几何证明程序,但缺少条件表达式和递归功能。

McCarthy在1957～1958年间提出了条件表达式,并首先用于Fortran程序。到1958年夏

天,这些思想基本成熟,并且超过了FLPL:(1)用条件表达式定义递归函数,把各种情形组合在

一个公式中;(2)引入church的入概念,函数可以作为表的参数。通过修补Fortran来进行表

处理,无论从技术上还是策略上都很困难,因此需要一个崭新的表处理语言。

Lisp语言终于诞生。1985年秋天,MIT的McCarthy(电子工程系)和Marvin Minsky(数学

系)领导的小组着手实现一个Lisp编译器,以便为Lisp程序提供一个运行环境。Lisp程序是

用一个类似于Fortran的M表达式编写的,通过手工方式将各种各样的函数汇编成汇编语言,

在Lisp"环境"下运行。这时的Lisp除了提供一些基本功能外还实现了输入(READ)和输出(P

RINT)Lisp表结构。

刚出世的Lisp实际上是一个很脆弱的婴儿,需要不断吸取氧分才能茁壮成长。Lisp虽然

提供递归函数计算,但它不是一个通用图灵机,应该更加简朴巧致地描述可计算函数,便于实

现。出于Lisp设计的初衷(用于人工智能、包括定理证明、符合数学法则、函数可能作为变

量、表达式可以替换)。引入了Lisp表达式计值的函数eval和LABEL符号(表示一个函数作为

表的参数)。至此,Lisp的核心已经较为完备。Lisp作为一个高级编程语言(称作Lisp1.5),

也显示了其他语言所不具备的特征:Lisp程序可以作为Lisp数据被eval解释和用语言本身来

编写自己的编译器。

Lisp早期也出现了几个Lisp的版本。最早是在IBM 704机上实现的。John McCarthy和

Steve Russell在Stanford大学的PDP-1上实现了PDP-1Lisp。T.R.Hart和T.G.Evans在Univ

ac M 460实现了Lisp1.5,它的最低层是用机器语言代码写的。后来,R.Saunders等人又在I

BM的Q-32机器上实现了Lisp1.5。

三、Lisp中期(1962～1984):百家争鸣

这一段时期,Lisp的发展呈现多样化,形成了许多Lisp方言,支持Lisp的机器也越来越多

。不同的机构团体在开发Lisp方言的时候,或多或少对Lisp的发展做出了自己的贡献。

1.从Lisp1.5到PDP-6Lisp

在1963年,还是高中生的L.Peter Deutsh在PDP-1上实现了一个与Lisp1.5相似的Lisp,

称作基本PDP-1 Lisp。1964年,Lisp1.5运行在MIT的兼容的分时系统IBM 7094机上。这两个

Lisp对PDP-6 Lisp的发展产生了主要的影响。PDP-6 Lisp是由DEC和MIT在1964年在PDP-6上

联合开发的。至此形成了Lisp的两支主流。PDP-6 Lisp最后发展成为Maclisp。基本PDP-1

sp发展成为Interlisp。Maclisp和Interlisp成为60年代后期至80年代早期两个最主要的L

isp方言。

2.Maclisp

Maclisp是MIT AI实验室主要的Lisp方言。它是在PDP-10上开发的,也能用于Honeywell

6180(操作系统是Multics)。它采用纯表(lisp)风格,注重产生式质量(production quali

ty),扩展了Lisp1.5的功能:引入LEXPR,计算如(A+B+C)之类的操作数个数不定的函数,增加

了数组的处理,引入了简单谓词操作(如MEMBER和出错函数ERR),允许用户发出错信号(sign

al)。

Maclisp的另一个重要发展是由MIT的MAC计划促成的,这时不再强调语言设计而是注重

满足用户的需要。在这期间,Maclisp吸取了其他Lisp方言和其他编程语言的特征。在70年

代初期,Maclisp的主要开发者John L.White把快速数学编译器LISCOM中的技术应用到Lisp编

译器中,产生了一个新的Maclisp编译器NCOMPLR,成为一个比较的标准(衡量其他Lisp编译器

生成的执行代码的运行速度快慢的尺度)。由于MIT AI实验室的视觉和机器人需要进行大量

的数值计算,Maclisp改变了Lisp1.5数值计算效率低的问题,使得编译Maclisp的数值性能几

乎能和Fortran编译器相媲美,也增加了对任意精度及其整数的处理。

Maclisp引入了读表(read table)概念。读表为程序和数据提供了一个可编程的输入语

法。它的文法分析器也可由用户重新编程,大大改善了Lisp1.5的输入功能。

Maclisp从其他Lisp方言吸收的东西并不多,主要借用了Interlisp NIL的处理方法:(C

AR NIL)→NIL和(CDR NIL)→NIL。

Maclisp的发展到70年代中期开始受阻。目标机PDP-10的1M内存限制了Lisp程序的大小

。Maclisp经过几年较有力的发展后,它的用户到1980年开始减少,资金短缺使MIT的人材流

向一些新的机构。

3.Interlisp

Interlisp是由基本PDP-1 Lisp演变而成的。在Bolt Beranek and Newman(BBN),在PD

P-1上实现了一个向上兼容的Lisp版本,即基本PDP-1 Lisp的后继。最后又由A.Hartley和M

urphy在PDP-10上实现了这个Lisp(称为BBN Lisp),由BBN和Xerox Palo Alto研究中心共同

维护,并将其更名为Interlisp。

Interlisp把许多基本思想引入到Lisp编程风范和方法当中。这些思想都体现在编程工

具里,如拼写校正器、文件包、DWIM、CLISP、结构编辑器和MASTERSCOPE。Warren Teitel

man的1966年的博士论文首先提出了这些思想。

拼写校正器和DWIM(Do What I Mean)能够弥补人的缺陷,自动或交互式正用户拼写和配

对符号不匹配的错误。CLISP(Comersational Lisp)是InterLisp的类似ALgol的英语自然风

格的文法。程序员可以像Algol一样编写Lisp程序或定义函数。结构编辑器编辑的源文件是

一个驻于内存的Lisp数据结构,对该文件的任何修改,包括自动修改部分,都会被保存起来,

文件仅仅是一个后援拷贝。MASTERSCOPE能够确定大系统中函数的相关信息(如调用关系)建

立一个数据库。这些工具相互之间能协调工作,构成了InterLisp的集成开发环境。Interl

isp的块编辑(多个函数定义在一个块区)提高了函数调用的速度。这些思想在现在使用的L

isp环境中也得到了充分体现。

尽管Interlisp沿袭了Lisp1.5文法,但也提出了自己的处理方法。像Maclisp一样,它修

改了lisp1.5的函数调用机制,允许函数参数个数可变,函数参数什么时候计值也由LAMBDA和

NLAMBDA以及它们的确定辐度(spread函数参数数目固定)和不确定辐度(mospread函数参数

数目不定)属性来决定。MacLisp和Interlisp关于函数参数处理除了在文法形式上存在差别

外,Maclisp坚持参数数目必须严格一致,而Interlisp却采取一种灵活机制:多余的参数被抛

弃,缺少的参数补全并以NIL作为它们的值。

Interlisp对lisp的另一个重要贡献是栈的处理方法,它引入Spaghettie栈,把栈组织成

一个树结构,解决了变量作用域和动态定义函数的生命期问题。

Interlisp和Maclisp共生于同一时期。尽管相互之间有取长补短之处,但两个团体之间

由于编程哲学(philosophy)上的分歧,使得他们没有能在MacLisp和Interlisp之间达成共识

。MacLisp本身的缺陷致使它到 1980年时开始衰退,而InterLisp能运行于PDP-10系列、VA

X系列和Dmachines等多种机器,且具有良好的集成环境而受到Lisp用户的青睐。

4.Lisp 机:1973～1980

Lisp机提供了Lisp运行的硬件支撑环境。其思想源于L.P.Deutsch。1973年,Xerox公司

开发了基于Interlisp的Lisp机:Alto。这个机器不能够充分发挥Interlisp的优势。1976年

,Xerox生产的Dorado取代了Alto,具有向上兼容性,其速度很快,但没有进入计算机市场。7

0年代后期在Dolphin机上运行Interlisp,其性能比Alto好,但不能够成为一台真正的Lisp机

。到1980年,Xerox生产了另一台Lisp机:Dandelion,其速度比Dolphin快,但比Dorado慢。

1974年,R.Greenblatt负责MIT的Lisp机计划,研制一台基于MacLisp能向上兼容的Lisp

机CONS(其改进型机器叫CADR)。它的目的是提高Lisp程序运行性能,提供类型检查和graba

ge收集(遗憾的是没有实现)的硬件支持,能够运行大规模Lisp程序(突破MacLisp的缺陷)。

虽然MIT的Lisp机基于MacLisp,但也突破了MacLisp的限制,在一定程度上受到InterLisp的

影响,如它也提供了一个正文编辑器(后来成为EMACS)调试和一个驻内存编译器。

Lisp机似乎并没有受到足够的注意。大多数用户并不看重Lisp机的硬件技术而是注重

它的软件。Lisp机公司也没有发现这一事实,导致Lisp机陷入了困境。

5.其他的Lisp方言尽管MacLisp和InterLisp成为70年代Lisp的主导潮流,仍然有一些大

学研究机构和公司先后开发了各种Lisp方言。其中使用最广泛的是Standard Lisp和Porta

ble Standard Lisp。前者是A.Hern和他的同事们共同开发的,是Lisp 1.5的子集,试图融合

其他一些Lisp方言的特征。这了提高性能,又开发一个Portable Standard Lisp(PSL)。它

是Lisp全新的实现。编译器是可重定对象的(regargetable)。这主要归功于它具有开创意义

的编译技术:①用一个系统实现语言SYSLISP对无类型的Lisp表示进行编码;②采用了一个参

数化的汇编级翻译宏c-macro。PSL编译器将Lisp翻译成一个抽象的汇编语言,然后通过c-m

acro把其转换成机器相关的格式。在PSL程序开发环境方面,70年代后期和80年代初期也开

发了一些工具,如类似Emacs的多窗口编辑器等。到80年代中期,HP公司推出了PSL的商业版

本。

PDP-10的地址空间问题使Lisp的发展受到阻碍,被后来问世的VAX系列取而代之。70年

代后期在VAX机上开发了一系列Lisp方言:VAX InterLisp、Franz Lisp、NIL和移植到VAX上

的PSL。Franz Lisp是在Berkeley开发的,用于符号代数运算,几乎全部是用C语言写的。NI

L是Jon L White等人设计的,它承袭了MacLisp,但受到了MIT的Lisp机的影响。1979年,在

Lawrrnce Livermere国家实验室制造的超计算机S-1 Mark ⅡA上实现,但不能实用,最终也

没有被广泛采用。

IBM推出了两个Lisp方言:Lisp360和Lisp370。虽然最初Lisp是在IBM/7090上实现的,但

IBM并没有成为领导Lisp的主流。主要原因是60年代早期,IBM和MIT在Lisp专利上产生了争

执,IBM寸步不让,导致MIT拒绝再用IBM机器开发Lisp而和DEC公司建立了良好的合作关系。

这使IBM的Lisp开发受到影响。

Lisp360是在IBM360机上实现的,被广泛应用于大学教学。Lisp370是在IBM370上开发的

,它有一个类似于InterLisp的开发环境。后来Lisp370称作Lisp/VM。Common Lisp出现以后

,IBM不再支持Lisp370,转向支持Common Lisp在IBM370机上的实现。

还有其他一些Lisp方言。1975年,G.J.Sussman等人受到C.Hewitt的Actor理论的影响,

设计了一个Lisp方言Scheme。在70年代中期,法国也开发了一个基于解释的Lisp方言VLisp

。这些Lisp方言几乎都没有产生过大的影响。

一直到80年代初期,开发Lisp的组织都是各唱各的戏。Lisp的发展没有形成一个统一的

标准。1981年4月,ARPA召集了一个Lisp团体会议，讨论Lisp未来的发展方向,意在阻止Lisp

方

言各自为政的纷呈现局面。InterLisp组织提出提供一个标准语言和标准环境,使未来的Li

sp能运行在不同的计算机平台上;MacLisp组织要消除MacLisp的子孙Lisp方言之间的差别,

寻求技术上的统一。Common Lisp这一名字的提出也费了一番周折。因为它既不能偏袒任何

一个Lisp方言,又要能表达对Lisp技术统一的愿望。关于Common Lisp技术的讲座是通过一

种奇特的方式进行的。Common Lisp的技术来自于许多Lisp方言设计者的共同努力,他们分

布在美国不同地方的AI实验室和一些Lisp机器公司,频繁的技术交流是通过E-mail来完成的

。

虽然大家把主要的精力都集中Common Lisp但在Common Lisp1984年正式颁布以前,一些

Lisp方言仍然在不断发展。Portable Standard Lisp被移植到VAX、DECsystem-20、MC680

00系列机和Cray-1上。Franz Lisp也被移植到许多系统上。Zetalisp是在Lisp机上发展的

。在CMU,Scott Fahlman和他的同事设计并实现了一个类似MacLisp的Lisp方言SPICE Lisp

。不过这时Lisp方言的发展,不再是以前那样的纷繁复杂的Lisp方言的世界了。在所有这些

Lisp方言中,更多地类似于MacLisp而不是InterLisp。

四、Common Lisp和Lisp的标准化时期(1984～1992)

Common Lisp的形成经历了大约四年的历程。Common Lisp是以"Common Lisp:The Lan

guage"(1984)的发布为其诞生标志的。在此之前进行了很多Lisp语言文本和技术上的努力

。1981年夏天,B.K.Steele开始编写Common Lisp手册(基于SPICELisp手册)。30多人的Com

mon Lisp小组,一直在讨论Common Lisp的技术细节。直到1983年初,所有的技术细节才最后

确定,Common Lisp语言也大抵达到了Common Lisp小组原定的目标:①公用性:成为一种公用

的Lisp方言;②可移植性;③一致性:解释器和编译器应保证语义相同;④丰富的表达能力:吸

取各种方言的优点;⑤兼容性:与Zetalisp、MacLisp和Interlisp兼容;⑥效率:提供一个优

化编译器;⑦Common Lisp应是一个系统构造语言;⑧稳定性。

Common Lisp的出现表明Lisp世界第一次有了一个认同的标准,尽管它还不完美,却在计

算机界产生了较大的影响。AI和Lisp相互推动,Common Lisp的逐渐流行伴随着AI研究的逐

步兴起。许多公司,包括DEC、HP、IBM、Sun、Apollo等一些著名的大公司和以前一些从事

Lisp方言的公司,迅速成为Common Lisp的有力支持者。欧洲和日本一些公司 也加入了这一

行列。Lucid公司(Gabriel等创建),不依赖于任何其他Lisp方言,实现了Common Lisp。DEC

和HP最后也选择了Common Lisp。

Common Lisp并不是一个国际标准,其本身也不完美。1985年DARPA(ARPA)要求其标准化

,并提供面向对象、多任务、窗口系统、图形、外部函数接口和迭代支持。于是ANSI成立了

Common Lisp技术委员会X3J13讨论标准化问题。促成X3J13的主要原因是欧洲正在讨论它自

已的Lisp(Eulisp)在ISO下的标准化。X3J13在讨论标准化期间,Common Lisp技术也有了很

大发展。1986年提出了Common Lisp Object System(CLOS),即支持面向对象的处理,1988年

12月被X3J13毫无修改地接受了。其他的技术发展有迭代、条件系统(例外处理)、计值语义

的完善等。到1992年4月,X3J13提出了Common Lisp草案。

1987年,ISO成立了一个工作小组WG16,讨论Lisp的标准化、国际化。其目标是未来的Lis

p方言应该具有商业价值的分层的Lisp,其内部是一个Kernel Lisp。在1992年ISO也草拟了

一个Kernet Lisp草案。

五、结束语

Lisp具有其他高级语言不可比拟的特征。它具有坚固的理论基础,丰富的表达能力,较

强的可塑性,也提供了操作系统的许多设施,如命令解释器、文件管理、多任务等。所有这

些特征为符号计算和人工智能研究提供了一个方便的工具。Lisp也成为一个最主要的AI语

言。

Lisp的发展不是直线的。很多人都被吸引到Lisp语言的研究与实现上,形成了许多Lis

p方言。本文我们介绍了Lisp的进化过程,但不能够一一介绍所有的Lisp方言和它们的发展

历程。我们希望这篇文章能有助于对Lisp更广泛的认识和了解,并引起我们对Lisp语言的关

注。

（计算机世界报 1995年 第8期）