LISP

Lisp（过去拼写为LISP）是具有悠久历史的计算机编程语言家族，有独特的完全用圆括号的前缀符号表示法。它起源于1958年，是现今第二悠久而仍广泛使用的高阶程式语言，只有FORTRAN编程语言比它更早一年。Lisp编程语族已经演变出许多种方言，现代最著名的通用编程方言是Scheme、Common Lisp和新近的Clojure。

## 简介

Lisp最初是为计算机程序创建的实用数学表示法，当时借鉴过阿隆佐·邱奇的lambda表示法。它很快成为人工智能研究中最受欢迎的编程语言。作为早期的高阶编程语言之一，Lisp开创了计算机科学领域的许多概念，包括树结构、自动内存管理、动态类型、条件表达式、高阶函数、递回、自主 (编译器)、读取-求值-输出循环（REPL）。

Lisp的名称源自“列表处理器”（list processor）的缩写。链接列表是Lisp的主要数据结构之一，Lisp编程代码也同样由列表组成。因此，Lisp程序可以把源代码当作数据结构进行操作，而使用其中的宏系统，开发人员可将自己定义的新语法或领域专用的语言，嵌入在Lisp编程中。

代码和数据的可互换性为Lisp提供了立即可辨识的语法。所有的Lisp程序代码都写为S-表达式或以括号表示的列表。函数调用或语义形式也同样写成列表，首先是函数或操作符的名称，然后接着是一或多个参数：例如，取三个参数的函数`f`即为(f arg1 arg2 arg3)。

## 历史

<image>

在1958年，约翰·麦卡锡在麻省理工学院发明了Lisp程式语言。在1960年，他在《ACM通讯》发表了论文《符号表达式的递回函数及其机器计算，第一部分》。在这篇论文中阐述了只要透过一些简单的运算子，以及借鉴自阿隆佐·邱奇的用于匿名函数的表示法，就可以建立一个可用于算法中的具图灵完备性的语言。Lisp还采纳了在1955年至1956年间创建的资讯处理语言所提出的列表处理与递归概念。

约翰·麦卡锡在最初定义的Lisp之中，先将程序表达为M-表达式（元表达式），再将它转换成S-表达式（符号 (编程)表达式），举例来说M-表达式的

```APL
car[cons[A;B]]
```

等同于S-表达式的(car (cons A B))。S-表达式可以将复杂结构表示为列表，在Lisp被实现了之后，编程者一般只使用S-表达式，而弃用M-表达式，这使得程式具备了同像性，即程式与资料由同样的结构储存。M-表达式曾短暂存续于Horace Enea的MLisp和沃恩·普拉特的CGOL之中。

第一个Lisp实作是在IBM 704机器上使用打孔卡写出的。史帝芬·罗素在阅读完约翰·麦卡锡的论文后，认为其中的`eval`函数可以用机器码来实作，从而创造了一个能工作的Lisp解释器。解释器可以用来运行Lisp程序，或者更恰当的说为：“求值Lisp表达式”

```
.---.---.  .-----.---.  .---.---.  .-----.---.  .---.---.
|-1 |   |->|APVAL|   |->|   |   |->|PNAME|   |->|   | / |
`---'---'  `-----'---'  `---'---'  `-----'---'  `---'---'
  ^                       |                       |
  |                     .-V-.---.               .-V-.---.
  |                     |   | / |               |   | / |
  |                     `---'---'               `---'---'
  |                       |                       |
  '-----------------------'                     .-V-----.
                                                | NIL???|
                                                `-------'
```

```
.---.---.  .-----.---.  .---.---.  .-----.---.  .---.---.
|-1 |   |->|EXPR |   |->|   |   |->|PNAME|   |->|   | / |
`---'---'  `-----'---'  `---'---'  `-----'---'  `---'---'
  .-----------------------'                       |
.-V----.---.  .---.---.  .---.---.              .-V-.---.
|LAMBDA|   |->|   |   |->|   | / |              |   | / |
`------'---'  `---'---'  `---'---'              `---'---'
                |          |                      |
              .---.---.  .----.---.             .-V-----.
              | X | / |  |COND|   |-> - - -     | FF????|
              `---'---'  `----'---'             `-------'
```

```
.----.-.---.  .--------------.
| -1 |1|   |->| 000000000017 |
`----'-'---'  `--------------'
```

在1960年发表的LISP I中，研究生Daniel Edwards开发了垃圾回收程序，使得在通用计算机上运行Lisp变得可行。在1962年，Timothy Hart与Michael Levin在麻省理工学院以Lisp自身，实做出第一个完整的Lisp编译器。在1963年，Timothy Hart提议向LISP 1.5增加宏。

在1975年，杰拉德·萨斯曼和盖伊·史提尔二世开发了Scheme，它是使用词法作用域和尾调用优化的第一个Lisp方言。在1980年代至1990年代期间，盖伊·史提尔二世、Scott Fahlman、Richard P. Gabriel、David A. Moon和Daniel Weinreb等人，在将当时新近的Lisp方言，其多数是Maclisp的后继者比如ZetaLisp和NIL，统一成单一语言上进行了巨大的努力。新语言Common Lisp，在某种程度上兼容于它所替代的方言。在1994年，ANSI出版了Common Lisp标准《ANSI X3.226-1994信息技术编程语言Common Lisp》。此外还有嵌入到编辑器Emacs中的Emacs Lisp，它非常流行并建立了自己的标准。

### 联系于人工智能

自从创始以来，Lisp就密切联系于人工智能研究社群，特别是在PDP-10系统之上。在1970年杰拉德·萨斯曼和特里·威诺格拉德使用Lisp实现了编程语言Planner (编程语言)，它被用在著名的AI系统SHRDLU之中。

### 谱系和方言

在它六十余年的历史中，Lisp产生了在S-表达式语言的核心主旨上的很多变体。此外，每个给定方言又可能有多种实现，例如Common Lisp就有十余种以上的实现。在一种标准化了的方言之内，符合标准的实现支持相同的核心语言，但是有着不同的扩展和函数库。

在方言间的差异可能是非常显眼的，例如定义一个函数

```
   |  .----.---.  .---.---.  .---.---.
uᵢ `->| -1 |   |->|IND|   |->|   |   |--> - - -
      `----'---'  `---'---'  `---'---'
                               |
                               V
                              vᵢ
```

Common Lisp使用Maclisp在1969年介入的关键字`defun`，而Scheme使用它在1975年介入的`define`。Richard P. Gabriel和Kent Pitman在1998年的一篇论文中，按采用统一的还是分立的函数与值命名空间，将Lisp家族语言划分为Lisp1和Lisp2（或写为Lisp-1和Lisp-2）。

#### 历史上的重要方言

- LISP I，是第一个实现。
- LISP 1.5，是第一个广泛发行的版本，由McCarthy和其他人在MIT开发。如此命名是因为它包含了对最初的LISP I解释器的改进，但不是LISP 2规划的那种重大重构。LISP 1.5现在有于Scheme之上的非完全实现。
- Stanford LISP 1.6，是斯坦福大学中心和研究所开发的LISP 1.5后继者，广泛的发行于运行TOPS-10操作系统的PDP-10系统。罗宾·米尔纳的可计算函数逻辑 ML运行在Stanford LISP 1.6下。它被Maclisp和InterLisp所淘汰。
- MACLISP，由MIT的MAC计划开发，它是LISP 1.5的直接后代。它运行在PDP-10和Multics系统上。MACLISP后来被称为Maclisp，也通常叫做MacLisp。在MACLISP中的“MAC”，既无关于Apple的Macintosh，又无关于McCarthy。
- Interlisp，由BBN科技开发，用于运行TENEX (操作系统)操作系统的PDP-10系统之上，后来InterLisp-D被Xerox Lisp机器接纳并昵称为“西海岸Lisp”。还有为基于6502的Atari 8位机家族计算机发行的叫做“InterLISP 65”的小型版本。在很长一段时间内，Maclisp和InterLisp相互之间是强有力的竞争者。
- Franz Lisp，起源于加利福尼亚大学伯克利分校的计划，后来由Franz Inc开发。这个名字是Franz Liszt的幽默变形，它不牵涉到Franz Inc后来销售的Allegro Common Lisp。
- XLISP，由David Betz开发，AutoLISP基于了它。
- Standard Lisp和Portable Standard Lisp，是曾被广泛使用和移植的犹他大学开发的版本，特别是用它写成了计算机代数系统Reduce (computer algebra system)。
- Lisp Machine Lisp，Symbolics称其变体版本为ZetaLisp，它用在Lisp机器之上，是Maclisp的直接后代。Lisp Machine Lisp对Common Lisp有巨大影响。
- Le Lisp，是一个法国Lisp方言。最早的图形用户界面建造器之一（叫做SOS界面）是用Le Lisp写成的。
- Scheme（1975年版），最初是在Maclisp上运行的解释器。
- Common Lisp（1984年版），是通过合并对Maclisp的不同尝试（ZetaLisp、Spice Lisp、NIL (编程语言)和S-1 Lisp）而创建的方言，也具有来自Scheme方言的实质影响。这个版本的Common Lisp在广泛的平台上都能获得到，从而被众人接受为业界标准，直至ANSI Common Lisp（ANSI X3.226-1994）出版。最广泛传播的Common Lisp子方言，是Steel Bank Common Lisp（SBCL）、CMU Common Lisp（CMU-CL）、Clozure OpenMCL、GNU CLISP和Allegro Common Lisp；所有这些实现都坚持了后来的ANSI CL标准。
- Dylan，在它的第一个版本中是Scheme和Common Lisp对象系统的混合。
- EuLisp，尝试开发一个新的高效和整洁的Lisp。
- ISLISP，尝试开发一个新的高效和整洁的Lisp。标准化为ISO/IEC 13816:1997，后来修订为ISO/IEC 13816:2007：《信息技术 – 编程语言，它们的环境和系统软件接口 – 编程语言 ISLISP》。
- IEEE Scheme，IEEE标准1178–1990（停用日期：2019-11-07）。
- ANSI Common Lisp（1994年版），是美国国家标准协会（ANSI）的Common Lisp标准，由X3J13委员会创建，其章程是：开始于以《Common Lisp语言》作为基础文档，致力于通过公开的达成共识过程，找到Common Lisp实现的程序可移植性和兼容性这个共通问题的解决方案。尽管形式上是ANSI标准，ANSI Common Lisp的实现、销售、使用和影响一直都是世界范围的。
- ACL2，是Common LISP的一个应用式（免于副作用）变体。ACL2既是可以建模计算机系统的编程语言，也是帮助证明这些模型性质的工具。
- 面向游戏汇编Lisp，是一个视频游戏编程语言，由Andy Gavin和Jak and Daxter团队在顽皮狗开发。它是使用Allegro Common Lisp写成并被用于整个Jak and Daxter系列游戏的开发。

### 2000年迄今

在1990年代衰退之后，Lisp在2000年之后因一些关注而逐渐复苏。当其他人认为Lisp已经过时陈旧，受到保罗·格雷厄姆和埃里克·雷蒙等人关于Lisp的著作的启发，很多新的Lisp编程者经常将其描述为令人大开眼界的经验，并声称在本质上比较其它编程语言更有生产效率。这种意识的提高可对比于“人工智能冬季”和Lisp在1990年代中期的短暂增长。

Common Lisp开源社群建立了至今仍活跃的支援基础有：CLiki，它是收集Common Lisp相关资讯的维基；Planet Lisp，它是收集了各种Lisp相关博客的内容；Common-lisp.net，它是开源专案的托管站点；Quicklisp，它是含括了许多函式库的装载管理器。在Common-lisp.net上，推荐了6种开源和2种商业Common Lisp实现。

Scheme社群基于广泛接纳的R5RS语言标准，开发了一些活跃至今的实作如Chicken、Gambit、Gauche (Scheme实现)和STklos等。Scheme实现要求建立了很多准标准函式库和Scheme扩展功能。随着Scheme实作用户社群增长，始自2003年的语言标准化过程在2007年产生了R6RS标准，在2013年又通过了R7RS-small最终草案，它已经有了一些实现支持。使用Scheme介绍计算机科学课程的学校似乎有所减少，麻省理工学院的计算机科学入门课程，已经不再使用Scheme。

Clojure是在2007年出现的新近Lisp方言，它编译至Java虚拟机并特别关注并发性。现今与Lisp有关的大多数新活动，包括开发新的跨平台函式库和应用，都集中在Scheme、Common Lisp、Emacs Lisp、Racket和Clojure的实作上。

近年来又有了几种新的Lisp方言：Arc、Hy、LFE语言等等。此外，在2012年出现的Julia语言所采用的语法解析器，是用Scheme方言Femtolisp实现的。

## 主要方言

Common Lisp和Scheme是Lisp发展的两大主流的代表。这些语言体现了显著不同的设计选择。

Common Lisp是Maclisp的后继者。对它有重要影响的是Lisp Machine Lisp、Maclisp、NIL (编程语言)、S-1 Lisp、Spice Lisp和Scheme。它拥有用于编程Lisp机器的大型Lisp方言Lisp Machine Lisp的很多特征，但设计上能高效的实现在任何个人计算机或工作站上。Common Lisp是通用编程语言，因而拥有一个大型语言标准，包括很多内建数据类型、函数、宏和其他语言元素，以及一个对象系统，即Common Lisp对象系统。Common Lisp还从Scheme借鉴了特定特征，比如词法作用域和词法闭包。Common Lisp实现目标定为不同的平台，比如：LLVM、Java虚拟机、x86-64、PowerPC、Alpha、ARM、Motorola 68000和MIPS，和不同的操作系统，比如：Windows、macOS、Linux、Solaris、FreeBSD、NetBSD、OpenBSD、Dragonfly BSD和Heroku。

Scheme是一个静态作用域和适当尾递归的Lisp编程语言方言。它的设计有着非常清晰和简单的语义，和很少的形成表达式的不同方式。它的设计大约比Common Lisp早上一个年代，Scheme是一个相当极简主义的设计。它拥有非常小的标准特征集合，但具有在Common Lisp中未规定的特定实现特征，比如尾递归优化和完全续体。在Scheme中能方便的表达广阔的编程范型，包括指令式、函数式和消息传递风格。Scheme通过一系列的标准，即第n次修订的算法语言Scheme报告，和一系列Scheme实现要求而持续的演化。

Clojure是Lisp的一个新近方言，其目标主要是Java虚拟机、通用语言运行库（CLR）和编译成JavaScript，它被设计为一个务实的通用编程语言。Clojure受到了Haskell的相当大的影响，因而非常强烈的强调了不可变性。Clojure提供了对Java框架和库的访问，具有可选的类型提示和类型推论，这样到Java的调用就可以避免反射并确使了快速的原始操作。Clojure设计上不后向兼容于其他Lisp方言。

进一步的，Lisp方言在很多应用中被用作脚本语言，其中最周知的是在Emacs编辑器中的Emacs Lisp，在AutoCAD中的AutoLISP和后来的Visual Lisp，Audacity中的Nyquist (编程语言)，和LilyPond中GNU Guile。有用的Scheme解释器潜在有很小的大小，使得它特别流行于嵌入式脚本。例子包括SIOD和TinyScheme，二者都曾经以共用名字“Script-fu”成功的嵌入到了GIMP图像处理软件中。LIBREP是John Harper最初基于Emacs Lisp语言开发的Lisp解释器，它已经嵌入到了Sawfish窗口管理器。

### 标准化的方言

Lisp有官方标准化和业界标准的方言：IEEE Scheme、ANSI Common Lisp、ISO ISLISP、R5RS Scheme和R7RS-small Scheme。

## 语法和语义

注意：本文的例子是用Common Lisp书写，但是其中的多数在Scheme中也是有效的，示例采用的Common Lisp实现是SBCL。

### 符号表达式

Lisp是一个面向表达式编程语言。不同于多数其他语言，在表达式和语句之间不做区分。所有代码和数据都写为表达式。当求值一个表达式的时候，它产生一个值（在Common Lisp中可能有多个值），它可以接着被嵌入到其他表达式中。每个值都可以是任何数据类型的。

McCarthy的1958年论文介入两种类型的语法：符号 (编程)表达式即S-表达式或sexps，它镜像了代码和数据的内部表示；和元表达式即M-表达式，它是与S-表达式对应的用类似数学符号表达的函数。M-表达式从未得到青睐，几乎所有今天的Lisp都使用S-表达式来操纵代码和数据二者。

大量而单一的使用圆括号，是Lisp与其他编程语言家族最直接明显的差别。为此学生们一直将Lisp戏称为：“迷失在愚蠢的括号中”（Lost In Stupid Parentheses），或“大量烦人的多余括号”（Lots of Irritating Superfluous Parentheses）。但是S-表达式语法也承担了Lisp多数能力：语法极其正规，利于计算机操纵。然而Lisp的语法不局限于传统的括号表示法，它可以扩展为包括可替代表示法。例如，XMLisp是Common Lisp扩展，它采用元对象协议，集成了S-表达式和可扩展标记语言（XML）。

有赖于表达式给予了语言巨大的灵活性。由于Lisp函数都写为列表，它们可以完全就像数据那样处理。这允许了轻易的书写能操纵其他程序的程序，即进行元编程。很多Lisp方言使用宏系统来利用这个特征，它确使了语言扩展而几乎没有限制。

### 列表

书写Lisp列表，是以空白来分隔其元素，并包围以圆括号。例如，(1 2 foo)是其元素为三个原子1、2和的一个列表。这些值是隐含的有类型的：它们分别是两个整数和叫做“符号”的Lisp专有数据类型，但不需要显式的声明。

空列表也表示为特殊原子。这是Lisp中既是原子又是列表的唯一实体。

表示式被写为使用前缀表示法的列表。在列表中第一个元素是一个函数的名字、一个宏的名字、一个lambda表达式或特殊算符的名字（见后）。列表的余下部分是实际参数。例如，函数list将它的实际参数作为一个列表返回，所以表达式：

```Lisp
* (list 1 2 (quote foo))
(1 2 FOO)
```

在前面例子中的之前的`quote`是特殊算符，它不求值就返回它的实际参数。任何未引述的表达式，在外围表达式被求值之前，都递归的被求值。例如：

```Lisp
* (list 1 2 (list 3 4))
(1 2 (3 4))
```

注意第三个实际参数是一个列表；列表是可以嵌套的。

### 算符

对算术算符的对待都是类似的。表达式：

```Lisp
* (+ 1 2 3 4)
10
```

其在中缀表示法下的等价形式为：1 + 2 + 3 + 4。

Lisp没有在Algol派生语言中实现的那样的算符概念。在Lisp中算术算符是可变参数函数（或多元函数），能够接受任何数目的实际参数。C-风格的`++`增加算符，有时在名字`incf`之下实现，给出的语法是：

```Lisp
* (setq x 0)            
0

* (incf x)  
1
```

等价于`(setq x (+ x 1))`，它返回`x`的新值。

特殊算符（有时叫做特殊形式）提供了Lisp的控制结构。例如，特殊算符接受三个实际参数。如果第一个实际参数为非`nil`，它求值为第二实际参数；否则它求值为第三个实际参数。因此表达式：

```Lisp
* (if nil
    (list 1 2 "foo")
    (list 3 4 "bar"))
(3 4 "bar")
```

当然，如果在的位置替换上非平凡的表达式会更有用处。

Lisp还提供逻辑算符`and`、`or`和`not`。`and`和`or`算符进行短路求值，并分别返回它们的第一个`nil`或非`nil`实际参数：

```Lisp
* (or (and "zero" nil "never") "James" 'task 'time)
"James"
```

### Lambda表达式和函数定义

另一个特殊算符lambda，被用来绑定变量到值，接着对表达式求进行求值。这个算符还被用于建立函数：给lambda的实际参数是一个形式参数列表，和这个函数要求值的一个或多个表达式，它的返回值是其求值的最后一个表达式的值。表达式：

```Lisp
* (lambda (arg) (+ arg 1))
#<FUNCTION (LAMBDA (ARG)) {5344B3FB}>
```

求值为一个函数，它接受一个实际参数，绑定它到并返回比这个实际参数大`1`的数。对待Lambda表达式于命名函数没有区别；它们以相同方式调用。如下表达式：

```Lisp
* ((lambda (arg) (+ arg 1)) 5)
6
```

这里我们做了一次函数应用：我们通过传递给它值`5`而执行了这个匿名函数。

命名函数是通过使用`defun`宏，将一个lambda表达式存储在一个符号之中而建立的：

```Lisp
* (defun foo (a b c d) (+ a b c d))
FOO
```

(defun f (a) b...)在全局环境中定义一个名为f的新函数。它在概念上类似于表达式：

```Lisp
* (setf (fdefinition 'f) #'(lambda (a) (block f b...)))
#<FUNCTION (LAMBDA (A)) {5344BA1B}>
```

这里的setf是一个宏，用来设置第一个实际参数fdefinition 'f为一个新的函数对象。fdefinition是对命名为f的函数的全局函数定义。是特殊算符function的简写，它返回指定函数在当前词法环境下的一个函数对象。

### 作用域

按照变量的作用域，可将Lisp家族划分为两大支系，分别使用动态作用域，或使用静态（也叫做词法）作用域。Scheme、Common Lisp和Clojure缺省使用静态作用域，而AutoLISP、PicoLisp和newLISP使用动态作用域。Emacs Lisp自从Emacs版本24.1起使用动态和词法作用域二者。

### 原子

在最初的LISP中，有两种基础数据类型：原子和列表。列表是元素的一个有限有序序列，这里的每个元素要么是一个原子要么是一个列表，而原子要么是一个数要么是一个符号。符号实质上是唯一性命名的项目，在源代码中写为字母数字串，并被要么用作一个变量名字要么符号处理中的一个数据项目。例如，列表(FOO (BAR 1) 2)包含三个元素：符号FOO、列表(BAR 1)和数`2`。

在原子和列表之间的本质区别是原子是不可变的和唯一性的。出现在源代码中不同位置的两个原子，如果以完全相同方式写成则表示相同的对象，而每个列表都是一个分立的对象，它们可以独立于其他列表而改变，并可以通过比较算符而区分于其他列表。

随着后来的Lisp介入了更多的数据类型，和编程风格的演化，原子的概念失去了重要性。很多方言出于遗产兼容性而保留了谓词`atom`，定义它为对不是`cons`的任何对象都为真。

### cons和列表

<image>

Lisp列表被实现为单向链表。这个链表的每个单元都叫做`cons`（在Scheme中叫做`pair`），它构成自两个指针，分别叫做`CAR与CDR`和`CAR与CDR`。

在众多可以用`cons`单元构建的数据结构中，最基本一个叫做“适当列表”（proper list）。适当列表要么是特殊的（空列表）符号，要么是一个`cons`，它的指向一个数据项（它可以是另一个`cons`结构比如一个列表），而指向另一个适当列表。

如果一个给定`cons`被接受为一个链表的头部，那么它的`car`指向这个列表的第一个元素，而它的`cdr`指向这个列表的余下部分。为此，在提及作为链表（而非树等）一部分的`cons`的时候，和函数也分别叫做first和rest。

因此，Lisp列表不是原子对象，它们类似C++或Java中的容器类的实例。一个列表就是链接的`cons`的一个聚集。引用一个给定列表的变量，简单的就是到列表中第一个`cons`的指针。遍历一个列表可以通过逐一`cdr`这个列表来进行，就是说连续的选取`cdr`来访问这个列表的每个`cons`；或者通过使用任何一个将一个函数映射在一个列表之上的高阶函数。

由于`cons`和列表在Lisp系统中是普遍性的，经常有人误解它们是Lisp的唯一数据结构。事实上，除了最简单者之外的所有Lisp都有其他数据结构，比如向量（数组数据结构）、散列表、结构等等。

#### S-表达式表示列表

圆括号的S-表达式表示了链表结构。有多种方式将相同的列表表示为一个S-表达式。`cons`可以用“点对表示法”写为(a . b)，这里的a是`car`而b是`cdr`。更长的适当列表可以用点对表示法写为(a . (b . (c . (d . nil))))。这通常简写为列表表示法的(a b c d)。“不适当列表”（improper list），可以用这二种表示法的组合来书写，比如列表(a b c . d)有三个`cons`，最后的`cdr`是d，它就是完全特殊形式下的(a . (b . (c . d)))。

#### 列表处理过程

Lisp提供很多内建的过程，用来访问和控制列表。列表可以直接用list过程创建，它接受任何数目的实际参数，并返回这些实际参数的列表：

```Lisp
* (list 1 2 'a 3)
(1 2 A 3)

* (list 1 '(2 3) 4)
(1 (2 3) 4)
```

由于列表是从cons对构造而来，可以使用cons过程来在一个列表的前端增加一个元素。注意由于列表构造方法，cons在处理列表实际参数上是不对称的：

```Lisp
* (cons 1 '(2 3))
(1 2 3)
 
* (cons '(1 2) '(3 4))
((1 2) 3 4)
```

append过程将两个（或更多）列表相互附加。由于Lisp列表是链表，附加两个列表有渐进时间复杂度 $O(n)$：

```Lisp
* (append '(1 2) '(3 4))
(1 2 3 4)
 
* (append '(1 2 3) '() '(a) '(5 6))
(1 2 3 A 5 6)
```

#### 共享结构

Lisp列表，作为单向链表，可以相互共享结构。就是说，两个列表可以有相同的尾部，或者最终的`cons`序列。例如，在执行下列Common Lisp代码之后：

```Lisp
* (setf foo (list 'a 'b 'c))
(A B C)

* (setf bar (cons 'x (cdr foo)))
(X B C)
```

尾部(b c)在两个列表中都是相同的结构。它不是复件；对于两个列表指向b和c的`cons`单元都在相同的内存位置。

共享结构而非复制可以得到相当客观的性能提升。但是这种技术可能以未预期的方式，交互于改变作为实际参数传递给它的列表的那些函数。改变一个列表，比如替代c为goose，将会影响另一个列表：

```Lisp
* (setf (third foo) 'goose)
GOOSE

* bar
(X B GOOSE)
```

不仅变更`foo`，还变更了`bar`，这可能是未预期的结果。这是缺陷的来源，为此改变它们的实际参数的那些函数被文档标示为破坏性的（destructive）。

函数式编程爱好者避免破坏性函数。在青睐函数式风格的Scheme方言中，破坏性函数的名字都标记了警告性感叹号，或者叫做“bang”，比如set-car!（读作set car bang），它替换一个`cons`的`car`。在Common Lisp方言中，破坏性函数是司空见惯的，与set-car!等价的是rplaca，它的名字表示“replace car”。这个函数是不常见的，因为Common Lisp包括了一个特殊设施setf，用来轻易的定义和使用破坏性函数。在Common Lisp中常见的风格是在构建原型的时候写函数式代码（没有破坏性调用），接着将破坏性调用作为优化增加于可以安全的进行它们的地方。

### 自求值形式和引述

Lisp求值用户录入的表达式。符号和列表求值为某个其他（通常更简单的）表达式，例如：一个符号求值为它指名的变量的值；(+ 2 3)求值为5。但是，多数其他形式求值为其自身：如果录入5到Lisp中，它返回5。

任何表达式都可以加上防止被求值的标记，这对于符号和列表是需要的。特殊算符quote承担了这个角色，它也简写为（一个单引号）。例如，通常如果录入了符号，它返回对应变量的值（没有这个变量则为一个错误）。要引用这个文字 (计算机编程)符号，录入要么(quote foo)，要么更常见的'foo。

Common Lisp和Scheme二者还支持“反引述”（backquote）算符（在Scheme中叫做准引述（quasiquote），这时录入字符（重音符）。它几乎同于普通引述，除了它允许表达式被求值，并将它们的值插入到引述列表之中，这些表达式标记了（逗号）表示去引述（unquote），或（逗号-at）表示拼接算符（unquote-splicing）。如果变量snue有值(bar baz)，则`(foo ,snue)求值为(foo (bar baz))，而`(foo ,@snue)求值为(foo bar baz)。反引述经常用于定义宏展开。

自求值形式和引述形式是Lisp中文字 (计算机编程)的等价者。在程序代码中可以修改（可变）文字的值。例如，如果一个函数返回一个引述形式，而调用这个函数的代码修改这个形式，这可以改变这个函数在后续调用时的行为：

```lisp
* (defun should-be-constant ()
    '(one two three))
SHOULD-BE-CONSTANT

* (let ((stuff (should-be-constant)))
    (setf (third stuff) 'bizarre))
BIZARRE

* (should-be-constant)
(ONE TWO BIZARRE)
```

像这样修改一个引述形式通常被认为是不良风格，并且被ANSI Common Lisp定义为是危险的。它会导致在编译文件中的未定义的行为，因为文件编译器可以合并类似的常量并将它们放置到写保护内存中，等等。

Lisp的引述形式化已经被Douglas Hofstadter（在《Gödel, Escher, Bach》中）和其他人注解为自引用的哲学想法的例子。

### 控制结构

Lisp最初有很少的控制结构，但是在语言演化期间却增加了很多。Lisp最初的条件算符是cond，它或被视为后来的if-then-else结构的先驱。

Scheme方言的编程者经常使用尾递归表达循环。Scheme在学术计算机科学中的通行性，导致了一些学生相信尾递归是在Lisp中书写迭代的唯一的或最常用的方式，但是这是不正确的。所有常见的Lisp方言都有指令式风格的迭代构造，从Scheme的循环到Common Lisp的复杂的loop表达式。此外，使之成为客观而非主观事物的关键要点，是Scheme对尾递归的处理提出了特殊要求，Scheme通常鼓励使用尾递归的原因，是语言定义明确的支持了这种实践。与之相反，ANSI Common Lisp不要求常称为尾递归消除的这种优化。因此，不鼓励将尾递归风格作为使用更传统的迭代构造（比如、dolist或loop）的替代品。在Common Lisp中不只是风格偏好的问题，而是潜在的效率问题，这是因为在Common Lisp中明显的尾递归可能未被编译为简单的`jump`；并且也是程序正确性问题，这是因为在Common Lisp中尾递归可能增加栈的使用而有堆栈溢出风险。

一些Lisp控制构造是特殊算符，等价于其他语言的语法关键字。使用这些算符的表达式与函数调用有着相同的表面外观，但是不同之处在于参数不是必须求值的，或者在迭代表达式的情况下，可以被求值多于一次。

对比于多数其他主要编程语言，Lisp允许使用语言自身实现控制结构。一些控制结构被实现为Lisp宏，想知道它们是如何工作的编程者甚至可以通过宏展开来研究。

Common Lisp和Scheme二者都有非局部控制流程算符。在这些算符中的不同是在这两种方言之间最深的差异。Scheme使用call/cc过程支持可重入的续体，它允许一个程序保存（并在将来恢复）执行中的特定位置。Common Lisp不支持可重入的续体，但是支持处理逃脱续体的一些方式。

相同的算法在Lisp中经常可以用要么指令式要么函数式风格来表达。如上所述，Scheme趋于青睐函数式风格，使用尾递归和续体来表达控制流程。但是，指令式风格仍是很有可能的。很多Common Lisp编程者偏好的风格，可能让使用结构化编程语言比如C的编程者看着更加熟悉，而Scheme编程者偏好的风格更加密切类似于纯函数式编程语言比如Haskell。

由于Lisp在列表处理上的早期遗产，它拥有与在序列上迭代有关的一组广泛的高阶函数。在其他语言中需要显式循环（比如C中的循环）的很多情况下，在Lisp和很多函数式编程语言中，相同的任务可以通过高阶函数来完成。

一个好的例子是在Scheme中叫做而在Common Lisp中叫做mapcar的函数。给定一个函数和一个或多个列表，mapcar按顺序将这个函数依次应用到这些列表的元素之上，并将结果收集入一个新的列表：

```Lisp
* (mapcar #'+ '(1 2 3 4 5) '(10 20 30 40 50))
(11 22 33 44 55)
```

这个`mapcar`函数将函数应用于每个对应的元素对之上。

### 程序代码的列表结构

在Lisp和其他语言之间的基本区别是，在Lisp中一个程序的文本表示，简单的是人类可读的描述，它同于底层Lisp系统使用的内部数据结构（链表、符号、数、字符等)。

Lisp利用这一点来实现了一个非常强力的宏系统。就像其他宏语言比如C，一个宏返回可以接着被编译的代码。但是不同于C的宏，Lisp的宏是函数因而可以利用Lisp的全部能力。

进一步的，因为Lisp代码作为列表有着相同的结构，宏可以使用语言中任何列表处理函数来建造。简要的说，Lisp可以在数据结构上做的任何事情，Lisp宏都可以在代码上做。相反的，在多数其他语言中，解析器的输出是纯粹的内部于语言实现的而不能被编程者操纵。

这个特征可以在语言中开发高效语言。例如，Common Lisp对象系统可以使用宏清晰的实现为一个语言扩展。这意味着如果一个应用需要不同的继承机制，它可以使用不同的对象系统。这直接的对立于多数其他语言；例如，Java不能支持多重继承并且没有增加它的合理方式。

在简单的Lisp实现中，这个列表结构被直接的解释来运行这个程序；一个函数是在文字上的一段列表结构，它被解释器在执行它的时候遍历。但是，多数后来的Lisp系统还包括一个编译器。编译器将列表结构转换成机器代码或字节码用于执行。这个代码可以像用常规语言比如C编译的代码一样快速。

宏在编译步骤之前展开，因而提供一些有价值的选项。如果一个程序需要一个预先计算了的表格，那么一个宏可以在编译时间建立这个表格，所以编译器只需要输出这个表格，而不需要在运行时间调用代码来建立这个表格。一些Lisp实现甚至拥有一种`eval-when`机制，允许代码在编译时间期间出现（在一个宏需要它的时候），而不出现在发行的模块中。

### 求值和读取–求值–打印循环

Lisp语言经常被以交互式命令行来使用，它还可以结合入集成开发环境（IDE）。用户在命令行录入表达式，或指示IDE将它们传送给Lisp系统。Lisp读取录入的表达式，求值它们，并打印结果。为此，Lisp命令行被叫做读取﹣求值﹣输出循环（REPL）。

REPL的基本操作描述如下。这是一个简化的描述，省略了很多真实Lisp的元素，比如引述和宏。

read函数接受文本的S-表达式作为输入，并将它们解析为内部数据结构。例如，如果你在提示符下录入文本(+ 1 2)，read将它转换成有三个元素的一个链表：符号、数`1`和数`2`。恰巧这个列表也是一段有效的Lisp代码，就是说它是可以被求值的。这是因为`car`这个列表指名了一个函数即加法运算。

注意将被读作一个单一符号。123将被读作数一百二十三。"123"将被读作字符串`"123"`。

eval函数求值数据，返回零或多个其他Lisp数据作为结果。求值不必然意味着解释；一些Lisp系统编译所有的表达式为机器代码。但将求值描述为解释是很简单的：要求值其`car`指名一个函数的一个列表，eval首先求值在它的`cdr`中的每个实际参数，接着应用这个函数于这些实际参数。在这个案例中，这个函数是加法，而应用它于实际参数列表(1 2)产生答案3。这是这个求值的结果。

符号求值为符号`foo`的值。数据比如字符串`"123"`求值为相同的字符串。列表(quote (1 2 3))求值为列表`(1 2 3)`。

print函数的工作是将输入表示给用户。对于简单结果比如3这是平凡的。求值为一段列表结构的一个表达式会要求print遍历这个列表并将结果输出为一个S-表达式。

要实现一个Lisp REPL，必需的只是实现这三个函数和一个无限循环函数。实现eval函数会很复杂是自然的，因为它必须也要实现所有特殊算符比如或lambda。它们完成后，一个基本的REPL就是一行代码：(loop (print (eval (read))))。

Lisp REPL典型的也提供输入编辑、输入历史、错误处理和到调试器的接口。

Lisp通常使用及早求值。在Common Lisp中，实际参数以应用式次序（最左最内为先）求值，而在Scheme中实际参数的次序是未定义的，为编译器优化留下了余地。

## 语言创意和七个原始运算

艾兹赫尔·戴克斯特拉在他的1972年图灵奖演讲中说道：

LISP具有一些非常基本的原理作为基础，它已经展示出卓越的稳定性。除此之外，LISP已经承载了相当可观的在某种意义上我们最复杂的计算机应用。LISP被玩笑的描述为“滥用计算机的最明智方式”。我认为这个描述是一种巨大的赞美，因为它传达了解放的全部意味：它辅助大量我们最有天赋的人类同胞去思考在以前不可能的想法。

Lisp是将程序代码的结构忠实而直接的表示为标准数据结构的第一个语言，这种品质后来被称为“同像性”。故而Lisp函数可以在Lisp程序中被操纵、更改、甚至创建，而不用低层操纵。这通常被认为是语言表达能力方面的主要优势之一，使得语言适合于语法宏和元循环求值。

条件表达式是麦卡锡用Fortran写一个象棋程序时发明的，他提议将其包含在ALGOL中但未被采纳。Lisp中的条件表达式使用了一般性的`cond`结构，ALGOL 60采纳了约翰·巴科斯提议的if–then–else条件语句并使之流行起来。

Lisp深刻影响了艾伦·凯，他是在Xerox PARC开发Smalltalk的研究组的领导者；反过来Lisp又受到Smalltalk的影响，其后来的方言在1970年代接纳了面向对象编程特征，包括有继承的类、封装的实例、消息传递等。Flavors (编程语言)对象系统介入了多重继承和混入的概念。Common Lisp对象系统（CLOS）提供了多重继承、具有多分派的多方法、和头等泛化函数，从而产生了一种灵活而强力形式的动态分派。CLOS充当了很多后来的包括Scheme在内的Lisp的对象系统的模板，它经常通过Gregor Kiczales等人发展出的元对象协议来实现，这是一种反射式元循环设计，其中的对象系统依据自身来定义。由于这些特征的融合，Lisp成为Smalltalk之后第二个具有元对象系统的语言。多年以后艾伦·凯宣称，只有Smalltalk和Lisp可以视为完全意义上的面向对象编程系统。

Lisp介入了自动垃圾回收的概念，即系统巡视堆来寻找无用的内存。现代复杂的垃圾回收算法比如分代垃圾回收的进步，受到了它在Lisp中使用的激励。

很大程度上由于它对于包括早期微处理器在内的早期计算机硬件的资源需求，Lisp未能像Fortran和ALGOL后裔C语言那样在人工智能社区之外得以流行。由于它适合于复杂和动态的应用，Lisp在2010年代享有了一定程度的大众关注的复兴。

保罗·格雷厄姆辨识出Lisp区别于其他现存的语言如Fortran的九个重要特征：

- 条件不受限于跳转。
- 头等函数。
- 递归。
- 将变量统一当作指针，将类型留给值。
- 垃圾回收。
- 程序完全构成自表达式 (计算机科学)而没有语句。
- 符号 (编程)数据类型，区别于字符串数据类型。
- 代码的表示法构成自符号树（使用很多圆括号）。
- 完全的语言可以获得于装载时间、编译时间和执行时间。

保罗·格雷厄姆从约翰·麦卡锡的最初论文中提炼出如下7个原始运算：

### quote

`(quote x)`返回`x`，通常简记为`'x`：

```lisp
* (quote a)
A

* 'a
A

* (quote (a b c))
(A B C)
```

将`quote`写成`'`只是一种语法糖。

### atom

`(atom x)`当`x`是一个`atom`或者空的`list`时返回原子`t`，否则返回`NIL`。在Common Lisp中通常习惯用原子`t`列表示真，而用空列表`()`或`NIL`列表示假。例如：

```lisp
* (atom 'a)
T

* (atom '(a b c))
NIL

* (atom '())
T
```

`atom`是需要求出实际参数值的算符，下面展示`quote`算符的作用，即通过引述一个列表，避免它被求值（`eval`）。一个未被引述的列表达式作为实际参数，`atom`会将其视为代码，例如：

```lisp
* (atom (atom 'a))
T
```

这是因为`(atom 'a)`已求值出结果`t`，把它代入`(atom (atom 'a))`，成为`(atom t)`，从而这个列表达式的结果是`t`。

反之一个被引述的列表，仅仅被视为列表，例如：

```lisp
* (atom '(atom 'a))
NIL
```

引用看上去有些奇怪，因为很难在其它语言中找到类似的概念，但正是这一特征构成了Lisp最为与众不同的特点：代码和数据使用相同的结构来列表示，只是用`quote`来区分它们。

### eq

`(eq x y)`当`x`和`y`指向相同的对象的时候返回`t`，否则返回`NIL`，例如：

```lisp
* (eq 'a 'a)
T

* (eq 'a 'b)
NIL

* (eq '() '())
T

* (eq '(a b c) '(a b c))
NIL
```

值得注意的是在Common Lisp中，原子对象在内存中只会有一份拷贝，所以`(eq 'a 'a)`返回`t`。

### car

`(car x)`要求`x`是一个列表，它返回`x`中的第一个元素，例如：

```lisp
* (car '(a b))
A
```

### cdr

`(cdr x)`同样要求`x`是一个列表，它返回`x`中除第一个元素之外的所有元素组成的列表，例如：

```lisp
* (cdr '(a b c))
(B C)
```

### cons

`(cons x y)`预期`y`的值是一个列表，并且返回包含`x`的值和随后`y`的值的那些元素的一个列表，例如：

```lisp
* (cons 'a 'b)
(A . B)

* (cons 'a (cons 'b 'c))
(A B . C)

* (cons 'a  (cons 'b ()))
(A B)

* (cons 'a (cons 'b (cons 'c ())))
(A B C)
```

### cond

`(cond (p<sub>1</sub> e<sub>1</sub>) ...(p<sub>n</sub> e<sub>n</sub>))`的求值规则如下：对“条件列表达式`p`”依次求值，直到有一个返回`t`。如果能找到这样的`p`列表达式，相应的“结果列表达式`e`”的值，作为整个`cond`列表达式的返回值。例如：

```lisp
* (cond ((eq 'a 'b) 'first)  ((atom 'a)  'second))
SECOND
```

## 对象系统

已经有各种对象系统和模型建造在Lisp之上、旁边或其中，包括：

- Common Lisp对象系统（CLOS），是ANSI Common Lisp内在的一部分。CLOS衍生自New Flavors和CommonLOOPS。ANSI Common Lisp是第一个标准化的面向对象编程语言（1994, ANSI X3J13）。
- ObjectLisp或Object Lisp，用于Lisp机器公司和早期版本的Macintosh Common Lisp。
- LOOPS（Lisp面向对象编程系统）和后来的CommonLOOPS。
- Flavors (编程语言)，建造于MIT，它的后代是New Flavors（由Symbolics.com开发）。
- KR（知识表达），它是用来辅助书写Common Lisp的GUI库Garnet的基于约束满足的对象系统。
- 知识工程环境（KEE）使用叫做UNITS的对象系统并集成入了推理机和推理维护（ATMS）。

## 范例

### Hello World!

这个Hello World!例子展示Lisp的三种主要方言，在基本输出和函数定义上的用法：

Scheme｜Common Lisp｜Clojure

```scheme
;; 显示过程在屏幕中打印字符串
;; 并返回未规定值
(display "Hello, world!")

;; 定义过程hello-world
(define (hello-world)
  (display "Hello, world!"))
 
;; 调用过程hello-world
(hello-world)
```

```lisp
;; 格式化函数在第一个参数是t时, 
;; 在屏幕中打印字符串，并返回NIL
(format t "hello, world!")

;; 定义函数hello-world
(defun hello-world ()
  (format t "hello, world!"))

;; 调用函数hello-world
(hello-world)
```

```clojure
;; 打印函数在屏幕中打印字符串
;; 并返回nil
(print "hello, world!")

;; 定义函数hello-world
(defn hello-world []
  (print "hello, world!"))

;; 调用函数hello-world
(hello-world)
```

### 阶乘

Lisp语法自然的适合于递归。数学问题比如递归定义集合的枚举，在这种表示法中表达是很容易的。例如，要求值一个数的阶乘：

```Lisp
(defun factorial (n)
  (if (zerop n) 1
    (* n (factorial (1- n)))))
```

下面的版本在底层Lisp系统进行尾递归优化时比前面版本取用更少的堆栈空间：

```Lisp
(defun factorial (n &optional (acc 1))
  (if (zerop n) acc
    (factorial (1- n) (* acc n))))
```

对比上述例子，下面的指令式版本使用了Common Lisp的loop宏：

```Lisp
(defun factorial (n)
  (loop for i from 1 to n
    for fac = 1 then (* fac i)
    finally (return fac)))
```

### 反转列表

下列函数反转一个列表。它与Lisp内建的`reverse`函数做同样的事情：

```Lisp
(defun -reverse (list)
  (let ((return-value))
    (dolist (e list) (push e return-value))
    return-value))
```

## 外部链接

历史

- History of LISP at the Computer History Museum

图书和教程

- Casting SPELs in Lisp , a comic-book style introductory tutorial
- On Lisp , a free book by Paul Graham
- Practical Common Lisp , freeware edition by Peter Seibel
- Land of Lisp , Official Website for the book
- mal - Make a Lisp

资源

- Awesome Lisp Languages
- CLiki: the Common Lisp wiki
- Lisp FAQ Index
- Planet Lisp

## 基本资料

- 日语原文：Lisp
- 域：Common Lisp的标志
- 编程范型：多范型：函数式
- 发行时间：1958年
- 设计者：约翰·麦卡锡
- 开发者：史帝芬·罗素、Timothy P. Hart、Michael I. Levin
- 类型系统：动态类型、强类型
- 受影响于：IPL