Lisp(历史上是Lisp,“列表处理”的缩写)是一个具有悠久历史的编程语言家族,具有独特的,完全括号前缀表示法。[3]Lisp最初是在1960年指定的,是继Fortran和COBOL之后仍在普遍使用的第三古老的高级编程语言。[4][5] Lisp从早期开始就发生了变化,在它的历史上存在过许多方言。今天,最著名的通用Lisp方言是Common Lisp、Scheme、Racket和Clojure[6][7][8]。
Lisp最初是作为计算机程序的实用数学符号而创建的,受Alonzo Church的λ演算符号的影响(尽管最初不是派生自)[9]。它很快成为人工智能(AI)研究的一种受欢迎的编程语言。[10]作为最早的编程语言之一,Lisp在计算机科学中开创了许多思想,包括树数据结构、自动存储管理、动态类型、条件、高阶函数、递归、自托管编译器、[11]和read-eval-print循环[12]。
LISP这个名字来源于“列表处理器”。[13]链表是Lisp的主要数据结构之一,Lisp源代码就是由链表组成的。因此,Lisp程序可以将源代码作为数据结构来操作,从而产生宏系统,允许程序员在Lisp中创建新的语法或新的特定于领域的语言。
代码和数据的可互换性使Lisp具有可立即识别的语法。所有的程序代码都被写成s表达式,或者用圆括号括起来的列表。函数调用或语法形式写成一个列表,函数或操作符的名称在前面,参数在后面;例如,接受三个参数的函数f将被称为(f arg1 arg2 arg3)。
John McCarthy于1958年在麻省理工学院(MIT)时开始开发Lisp。麦卡锡在1960年4月的《美国计算机协会通讯》上发表了一篇论文,题为“符号表达式的递归函数及其机器计算,第一部分”。[14]他展示了用几个简单的运算符和从丘奇那里借来的匿名函数的符号,就可以建立一个图灵完备的算法语言。
信息处理语言(Information Processing Language)是第一种人工智能语言,出现于1955年或1956年,它已经包含了Lisp中使用的许多概念,比如列表处理和递归。
麦卡锡最初的表示法是用括号括起来的“m -表达式”,这将被翻译成s -表达式。例如,m表达式car[cons[A,B]]等价于s表达式(car (cons A B))。Lisp实现后,程序员迅速选择使用s表达式,m表达式被抛弃。随着Horace Enea的MLisp[15]和Vaughan Pratt的CGOL的短暂尝试,m表达式再次出现。
Lisp最初是由Steve Russell在IBM 704计算机上使用打孔卡实现的。[16]罗素读了麦卡锡的论文,并意识到(令麦卡锡吃惊的是)Lisp的eval函数可以用机器代码实现。
麦卡锡认为:[17]
史蒂夫·拉塞尔说,为什么我不编写这个eval…我对他说,哦,哦,你把理论和实践混淆了,这个计算是用来阅读的,不是用来计算的。但他还是照做了。也就是说,他将我论文中的eval编译成IBM 704机器码,修复错误,然后把它宣传为Lisp解释器,它确实是。所以在那个时候,Lisp基本上有了今天的形式……
结果是一个可以工作的Lisp解释器,它可以用来运行Lisp程序,或者更确切地说,“计算Lisp表达式”。
IBM 704的两个汇编语言宏成为分解列表的基本操作:car(寄存器号的地址部分的内容)和cdr(寄存器号的递减部分的内容),[18]其中“Register”指的是计算机中央处理器(CPU)的寄存器。Lisp方言仍然分别使用car和cdr (/k [k] r/和/k [k] d] r/)来返回列表中的第一项和列表的其余部分。
1962年,蒂姆·哈特和迈克·莱文在麻省理工学院实现了第一个用Lisp语言编写的完整的Lisp编译器,并且可以通过简单地使用现有的Lisp解释器解释编译器代码来编译,产生的机器码输出能够以比解释器快40倍的速度执行。[19]该编译器引入了Lisp的增量编译模型,编译函数和解释函数可以自由混合。哈特和莱文的备忘录中使用的语言比麦卡锡早期的代码更接近现代Lisp风格。
1962年之前,垃圾收集程序是由麻省理工学院的研究生丹尼尔·爱德华兹开发的。[20]
在20世纪80年代和90年代,人们做出了巨大的努力,将新的Lisp方言(主要是Maclisp的继承者,如ZetaLisp和NIL (Lisp的新实现)统一为一种语言。新的语言,Common Lisp,在某种程度上与它所取代的方言兼容(《Common Lisp The language》一书中提到了各种结构的兼容性)。1994年,ANSI发布了公共Lisp标准,“ANSI X3.226-1994信息技术编程语言公共Lisp”。