编程语言之Lisp
2014-03-11 15:13:08 
阿炯
LISP(全名LISt Processor，即列表处理语言)，由约翰·麦卡锡在1960年左右创造的一种基于λ演算的函数式编程语言。
LISP有很多种方言，各个实现中的语言不完全一样。1980年代Guy L. Steele编写了Common Lisp试图进行标准化，这个标准被大多数解释器和编译器所接受。还有一种是编辑器Emacs所派生出来的Emacs Lisp(而Emacs正是用Lisp作为扩展语言进行功能扩展的)非常流行，并创建了自己的标准。
LISP语言的主要现代版本包括Common Lisp和Scheme。
LISP是第一个函数型编程语言，区别于C/Java等命令型编程语言。Lisp语言形式简单、内涵深刻，Paul Graham在《Lisp之根源》中将其对编程的贡献与欧几里德对几何的贡献相提并论。
由于历史的原因，Lisp长期以来被认为主要用于AI领域，但Lisp并不是为AI而设计，而是一种通用的编程语言。Lisp的表达式是一个原子(atom)或表(list)，原子(atom)又包含符号(symbol)与数值(number)；表是由零个或多个表达式组成的串行，表达式之间用空格分隔开，放入一对括号中，如：
abc
()
(abc xyz)
(a b (c) d)
最后一个表是由四个元素构成的，其中第三个元素本身也是一个表，这种list又称为嵌套表(nested list)。正如算数表达式1+1有值2一样，Lisp中的表达式也有值，如果表达式e得出值v，我们说e返回v。如果一个表达式是一个表，那么我们把表中的第一个元素叫做操作符，其余的元素叫做自变量。
虽然Lisp与函数式编程有很大的关系，但学习Lisp绝不仅仅是学习如何用函数表达设计思想。实际上，函数式编程并非Lisp的本质，在已经掌握了lambda、高阶函数、闭包、惰性求值等函数式编程概念之后，学习Lisp仍然大大加深了对编程的理解。学习Lisp所收获的是如何“自由地”表达你的思想，这正是Lisp最大的魅力所在，也是这门古老的语言仍然具有很强的生命力的根本原因。
Scheme
Scheme是一种函数式编程语言，是Lisp的两种主要方言之一（另一种为Common Lisp）。不同于Common Lisp，Scheme遵循极简主义哲学，以一个小型语言核心作为标准，加上各种强力语言工具（语法糖）来扩展语言本身。诞生于1970年。
麻省理工学院与其他院校曾采用Scheme教授计算机科学入门课程。著名的入门教材《计算机程序的构造和解释》（SICP）利用Scheme来解释程序设计。Scheme的广泛受众被视为一个主要优势，然而不同实现之间的差异成为了它的一个劣势。Scheme最早由麻省理工学院的盖伊·史提尔二世与杰拉德·杰伊·萨斯曼在1970年代发展出来，并由两人发表的“λ论文集”推广开来。 Scheme语言与λ演算关系十分密切。小写字母“λ”是Scheme语言的标志。
Scheme的哲学是：设计计算机语言不应该进行功能的堆砌，而应该尽可能减少弱点和限制，使剩下的功能显得必要。Scheme是第一个使用静态作用域的Lisp方言，也是第一个引入“干净宏”和第一类续延的编程语言。目前Scheme由IEEE负责标准管理，并由一个专门的委员会发表的“算法语言Scheme报告，第N版”（Revisedn Report on the Algorithmic Language Scheme）进行标准化。
Scheme大体上是一个函数式编程语言，并支持其他编程范型。它的语法基于Lisp的S-表达式：函数调用在Scheme中表示为一个串列，其中第一个元素为函数名，而后的元素为函数的参数。一个Scheme程序是由嵌套串列表达而成，而串列又是Scheme的主要数据结构，这导致程序和资料在Scheme中基本上是等价的概念。因此每一个Scheme程序都可以被视为另一个Scheme程序的参数。Scheme程序可以轻易读入并分析其他Scheme程序，就是所谓的同像性。该特性被用于“代码即数据”的设计思维中，它极大提高了语言表达性和灵活性。但也有批评认为对该特性的不当使用将造成反效果，将数据当作代码需要借助eval在运行时求值，这不利于编译优化；另外代码可以被当作数据一样被修改（即所谓程序自修改）可能会造成程序逻辑混乱。
Scheme的列表与其他Lisp方言都是基于最基础的数据结构“有序对”（pair）。Scheme提供cons，car，与cdr方法操作有序对与列表。Scheme的变量都使用动态强类型系统，而函数被视为变量的一种，并可以作为参数提供给其他函数。换句话说，Scheme中的函数都是第一类对象。
Scheme的精简设计使得编程语言设计人士与爱好者特别钟爱研究它的实现，很多嵌入式系统语言与脚本语言即是基于Scheme。Scheme的实现一般小而精简，造成了很多不可互通的实现互相竞争。尽管Scheme的精简性是它的一个主要长处，但试图使用Scheme编写既复杂又便于移植的程序往往比较困难，主要原因之一，是因为Scheme没有库函数标准。而R6RS试图完成这样的工作，它定义了两套标准，核心语言以及标准库。这使得Scheme第一次有了库函数标准，也使得编译器开发者和贡献者可以实现Scheme的可移植库。
脚本语言
自由软件影像处理程序GIMP利用Scheme为脚本语言。
GNU的标准脚本语言Guile是基于Scheme的，并被用于GNOME等软件中。
Common Lisp
Common Lisp，缩写为CL（不是组合逻辑的缩写）是Lisp编程语言的一种方言，由ANSI INCITS 226-1994(R2004)（前身为ANSI X3.226-1994(R1999)），所定义的语言规范标准。Common Lisp HyperSpec是源自于ANSI Common Lisp标准的网页超链接版本。诞生于1984年。
CL语言是为标准化和改良Maclisp而开发的后继者。到20世纪80年代初，几个工作组已经在设计MacLisp各种后继者，例如：Lisp Machine Lisp（又名 ZetaLisp），Spice Lisp，NIL和S-1 Lisp。CL是为了标准化和扩展此前众多的MacLisp分支而开发，它本身并非具体的实现，而是对语言设立标准的规范。有数个实现符合Common Lisp规范，其中包括自由和开源软件，以及商业化产品。CL支持了结构化、函数式和面向对象编程等范型。相对于各种嵌入在特定产品中的语言，如Emacs Lisp和AutoLISP，Common Lisp是一种用途广泛的编程语言。不同于很多早期Lisp，Common Lisp如同Scheme，其中的变量是默认为词法作用域的。
身为一种动态编程语言，它有助于进化和增量的软件开发，并将其迭代编译成高效的运行程序。这种增量开发通常是交互持续地改善，而不需中断运行中的应用程序。它还支持在后期的分析和优化阶段添加可选的类型注记与转型，使编译器产生更有效率的代码。例如在硬件和实现的支持范围内，fixnum能保存一个未封装整数，允许比大整数或任意精度类型更高效率的运算。同样地，在每个模块或函数的基础上可声明优化，指示编译器要编译成哪一类型的安全级别。
CL包含了支持多分派和方法组合的对象系统，缩写为CLOS，它通常以元对象（Metaobject）协议来实现。
Common Lisp 拥有丰富的数据类别。
标量类型
数值类型包括整数，分数，浮点数和复数。Common Lisp使用大数（bignums）来表示任意大小和精度的数值。 分数类型确切地代表分数，很多语言并不具备这种能力。Common Lisp会自动将数值转换成适当的类型。有许多方式取舍数值，函数round将参数四舍六入为最接近的整数，逢五则取偶整数。truncate，floor和ceiling分别朝向零，向下或向上取整数。所有这些函数将舍去的小数当作次要值返回。
数据结构
Common Lisp的序列类型包括列表、向量、比特向量和字符串。有许多函数可对应不同类型的序列进行操作。
函数
Common Lisp支持第一类函数（亦即函数可当成数据类型来处理）。例如编写以其它函数当作一个函数的参数，或函数的传回值也是函数，利用函数的结合来描述常用的操作。CL库高度依赖于这样的高端函数变换。举例而言，sort函数可将关系运算符作为参数，并选用如何取键的函数作为参数。如此一来不但能对任何类型的数据排序，还能根据取用的键值对数据结构作排序。
Common Lisp中的宏是独一无二的，和C语言中的宏的机制相同，但是在宏扩展的过程中由于可以使用所有现有的Common Lisp功能，因此宏的功能就不再仅限于C语言中简单的文本替换，而是更高级的代码生成功能。宏的使用形式和函数一致，但是宏的参数在传递时不进行求值，而是以字面形式传递给宏的参数。宏的参数一旦传递完毕，就进行展开。展开宏的过程将一直进行到这段代码中的所有宏都展开完毕为止。宏完全展开完毕后，就和当初直接手写在此处的代码没有区别，也就是嵌入了这段代码上下文中，然后Lisp系统就对完整的代码上下文进行求值。Lisp宏表面上类似于函数的使用，但并不是会直接被求值的表达式，它代表程序源码的字面转换。宏将包含的代码内容当作参数，将它们绑定到宏自身的参数，并转换为新的源码形式。这个新的源码形式也能够使用一个宏，然后重复扩展，直到新的源码形式没有再用到宏。最终形式即运行时所运行的源代码。
Common Lisp与Scheme的比较
Common Lisp经常和Scheme互相比较，因为它们是最受欢迎的两种Lisp方言。Scheme早于CL，不仅来自同一个Lisp传统，而且来自同一位工程师Guy L. Steele，与Gerald Jay Sussman设计的，Guy L. Steele也担任过Common Lisp标准委员会的主席。
Common Lisp是一种普遍用途的的编程语言；相反的如Emacs Lisp和AutoLISP这两种Lisp的变体，则是嵌入特定产品作为扩展用的语言。与许多早期的Lisps不同，Common Lisp（Scheme同样）对源码直译和编译时，默认为词法变量作用域。
大部分Lisp系统（如ZetaLisp和Franz Lisp）的设计，促成了Common Lisp在解释器中使用动态作用域的变量，并在编译器中使用了词法作用域的变量。由于ALGOL 68的启发，Scheme引入了Lisp对词法作用域变量的单一使用；这被广泛认同是好主意。CL也支持动态作用域的变量，但必须将其显式声明为“特殊”。ANSI CL解释器和编译器之间的作用域界定是没有差别的。
Common Lisp有时被称为Lisp-2，而Scheme被称为Lisp-1。它指的是CL对函数和变量使用个别的名字空间（实际上CL有许多名字空间，例如go标签，block名称和loop关键字）。在涉及多个名字空间的权衡之间，CL与Scheme倡导者之间存在着长期的争议。在Scheme中（广义地）必须避免与函数名称互相冲突的变量名称；Scheme函数通常拥有名称为lis，lst或lyst的参数，以免与系统内置的list函数冲突。然而在CL中，在传递函数作为参数时一定要显式地引用函数的名称空间，这也是一个常见的事件，如前面小节中的排序编程示例。
在处理布尔逻辑值时，CL也与Scheme不同。Scheme使用特殊值#t和#f来表示逻辑真与假值。而CL遵循使用符号T和NIL的传统Lisp惯例，NIL同时也是空列表。在CL中任何非NIL值被条件处理为真，例如if；而在Scheme当中，所有非#f值被视为真。这些惯例约定允许这两种语言的一些运算符同时作为谓词（回应逻辑上的是非问题），并返回一个作用值进行进一步的计算，但在Scheme的布尔表达式中，等同于Common Lisp空列表的NIL值或'()，会被评估为真。
最后，Scheme的标准文件要求尾部调用优化，而CL标准没有。不过大多数CL实现会提供尾部调用优化，虽然通常只在程序员使用优化指令时。尽管如此，常见的CL编程风格并不偏好于Scheme中普遍使用的递归样式- 一个Scheme程序员会使用尾部递归表达式，CL用户则通常会用do，dolist，loop等迭代表达式，或使用iterate包来表达。
一些基于Unix的实现，例如CLISP，可以作为脚本解释器使用；因此系统可以像调用Perl或者Unix shell解释器一样透明地调用它。
函数不仅是 Lisp 程序的根基，它同时也是 Lisp 语言的基石。
除了少数称为特殊形式 (special form) 的操作符之外，Lisp 的核心就是一个函数的集合。如果你觉得某件事 Lisp 应该能做，你完全可以把它写出来，然后你的新函数可以享有和内置函数同等的待遇。有两点让 Lisp 函数与众不同。一是Lisp 本身就是函数的集合。这意味着我们可以自己给 Lisp 增加新的操作符。另一个就是:函数也是 Lisp 的对象。这意味着在 Lisp 里我们可以像对待其他熟悉的数据类型那样来对待函数,就像整数那样:在运行期创建一个新函数,把函数保存在变量和结构体里面,把它作为参数传给其他函数,还有把它作为函数的返回值。
定义函数
最通常的做法就是用defun宏实现函数定义，如下面定义的double函数。
> (defun double (x) (* 2 x))
DOUBLE
函数本身就是对象，defun就是构造这样的对象，然后保存它到第一个参数名下。所以我们既可以调用double，也可以持有这个名字对应的函数对象。通常可以用#'操作符得到这个对象，这个操作符能将名字映射到实际的函数对象。就像下面这样：
> #'double
#<FUNCTION DOUBLE>
也可以使用On Lisp
可以使用一种称为 λ–表达式 (lambda-expression) 的东西定义函数，它由三部分组成：lambda符号，参数列表和若干表达式主体。下面的λ–表达式是等价于double的函数：
> (lambda (x) (* 2 x))
λ–表达式也可以看作是函数的名字，如果说 double 是个正规的名字，那么lambda表达式就相当于具体的描述。通过#'可以得到相应的函数：
> #'(lambda (x) (* 2 x))
#<FUNCTION (LAMBDA (X)) {100366DEAB}>
由于 λ–表达式同时也是函数的名字,因而它也可以出现在函数调用的最前面：
> ((lambda (x) (* x 2)) 3)
6
在 Common Lisp 里,我们可以同时拥有名为 double 的函数和变量。
"拥有分开的变量和函数命名空间的 Lisp 称为 Lisp–2,在另一类 Lisp–1 下,变量和函数定义在同一命名空间里,最著名的这种 Lisp 方言是 Scheme。关于 Lisp–1 vs. Lisp–2 在网上有很多讨论,一般观点认为 Lisp–1 对于编译器来说更难实现。"
> (setq double 2)
2
> (double double)
4
当符号出现在函数调用的首位，或者前置 #’ 的时候，它被认为是函数。其他场合下它被当成变量名。
Common Lisp 还提供了两个函数用于将符号映射到它所代表的函数或者变量，以备不时之需。
symbol-value 函数以一个符号为参数，返回对应变量的值：
> (symbol-value 'double)
2
而symbol-function则可以得到一个全局定义的函数：
> (symbol-function 'double)
#<FUNCTION DOUBLE>
由于函数也是对象，变量也可以把函数当作值
(setf double-1 #'double)
其实，defun实际上是把它的第一个参数的symbol-function设置成了用它其余部分构造的函数，下面两个表达式完成的功能基本相同：
(defun double (x) (* 2 x))
(setf (symbol-function 'double) #'(lambda (x) (* 2 x)))
函数型参数
函数同为数据对象，就意味着我们可以像对待其他对象那样把它传递给其他函数。common lisp中提供了apply和funcall让我们实现对函数的调用：
(+ 1 2)
(apply #’+ ’(1 2))
(apply (symbol-function ’+) ’(1 2))
(apply #’(lambda (x y) (+ x y)) ’(1 2))
(apply #’+ 1 ’(2))
(funcall #’+ 1 2)
apply和funcall的唯一区别就是，apply必须以列表参数结尾。
作为属性的函数
函数作为 Lisp对象这一事实也创造了条件，能够编写出那种可以随时扩展以满足新需求的程序。假设需要写一个以动物种类作为参数并产生相应行为的函数。在大多数语言中，会使用 case 语句达到这个目的，Lisp 里也可以用同样的办法：
(defun behave (animal)
(case animal
(dog (wag-tail) (bark))
(rat (scurry) (squeak))
(cat (rub-legs) (scratch-carpet))))
如果把每种个体动物的行为以单独的函数形式保存，会更利于扩展：
(defun behave (animal) (funcall (get animal ’behavior)))
(setf (get ’dog ’behavior)
#’(lambda () (wag-tail) (bark)))
作用域
Common Lisp 是一种词法作用域 (lexically scope) 的 Lisp方言，词法作用域与动态作用域的区别在于语言处理自由变量的方式不同。
当一个符号被用来表达变量时，称这个符号在表达式中是被绑定（bound）的，这里的变量可以是参数，也可以来自于像let，do这样的变量绑定操作符。如果符号不受到约束，就认为它是自由的，比如：
(let ((y 7))
(defun scope-test (x)
(list x y)))
在函数表达式里，x是受约束的，而y是自由的。自由变量有意思的地方就在于，这种变量应有的值并不那么显而易见。一个约束变量的值是确信无疑的，当调用 scope-test 时，x 的值就是通过参数传给它的值。但 y 的值应该是什么呢？这要看具体方言的作用域规则。
在动态作用域的 Lisp 里，要想找出当 scope-test 执行时自由变量的值，要往回逐个检查函数的调用链。当发现 y 被绑定时，这个被绑定的值即被用在 scope-test 中。如果没有发现，那就取 y 的全局值。这样在用动态作用域的 Lisp 里，在调用的时候 y 将会产生这样的值：
> (let ((y 5)) (scope-test 3))
(3 5)
在词法作用域 的 Lisp 里，不再往回逐个检查函数的调用链，而是逐层检查定义这个函数时，它所处的各层外部环境。在一个词法作用域 Lisp 里，我们的示例将捕捉到定义 scope-test 时，变量 y 的绑定。所以可以在 Common Lisp 里观察到下面的现象：
> (let ((y 5)) (scope-test 3))
(3 7)
闭包
common lisp是词法作用域，如果定义含有自由变量的函数，系统就必须在函数定义时保存那些变量的绑定。这种函数和一组变量绑定的组合称为闭包。闭包是带有局部状态的函数。下面列举一些这样的例子：
(defun list+ (lst n)
(mapcar #’(lambda (x) (+ x n))
lst))
> (list+ ’(1 2 3) 10)
(11 12 13)
(defun make-adderb (n)
#’(lambda (x &optional change)
(if change
(setq n x)
(+ x n))))
> (setq addx (make-adderb 1))
> (funcall addx 3)
4
> (funcall addx 100 t)
100
> (funcall addx 3)
103
局部函数
在用lambda表达式时，由于它没有自己的名字，因此没办法引用自己，这就意味着在common lisp里，不能用lambda表达式定义递归函数。如果想把某个列表上的参数一一应用到某个函数上，可以这样写：
> (mapcar #'(lambda (x) (+ 2 x))
'(1 2 3 4))
(3 4 5 6)
要是想把递归函数作为第一个参数送给 mapcar 呢？如果函数已经用 defun 定义了，就可以通过名字简单地引用它：
> (mapcar #’copy-tree ’((a b) (c d e)))
((A B) (C D E))
但现在假设这个函数必须是一个闭包，它从 mapcar 所处的环境获得绑定，比如：
(defun list+ (lst n)
(mapcar #’(lambda (x) (+ x n))
lst))
mapcar 的第一个参数是 #’(lambda (x) (+ x n))，它必须要在 list+ 里定义，原因是它需要捕捉 n 的绑定。到目前为止都还一切正常，但如果要给 mapcar 传递一个函数，而这个函数在需要局部绑定的同时也是递归的呢？我们不能使用一个在其他地方通过 defun 定义的函数，因为这需要局部环境的绑定。并且也不能使用 lambda 来定义一个递归函数，因为这个函数将无法引用其自身。
Common Lisp 提供了 labels 帮助跳出这个两难的困境。除了在一个重要方面有所保留外，labels 基本可以看作是 let 的函数版本。labels 表达式里的每个绑定规范都必须符合如下形式：
(⟨name⟩ ⟨parameters⟩ . ⟨body⟩)
在 labels 表达式里，⟨name⟩ 将指向与下面表达式等价的函数：
#’(lambda ⟨parameters⟩ . ⟨body⟩)
例如：
> (labels ((inc (x) (1+ x)))
(inc 3))
> 4
尽管如此，在 let 与 labels 之间有一个重要的区别。在 let 表达式里,变量的值不能依赖于同一个 let 里生成的另一个变量，就是说，不能这样写( let*可以这样写 )：
(let ((x 10)
(y x))
y)
然后认为这个新的 y 能反映出那个新 x 的值。相反，在 labels 里定义的函数 f 的函数体里就可以引用那里定义的其他函数，包括 f 本身，这就使定义递归函数成为可能。
使用 labels 就可以写出类似 list+ 这样的函数了，但这里 mapcar 的第一个参数是递归函数：
(defun count-instances (obj lsts)
(labels ((instances-in (lst)
(if (consp lst)
(+ (if (eq (car lst) obj) 1 0)
(instances-in (cdr lst)))
0)))
(mapcar #’instances-in lsts)))
该函数接受一个对象和一个列表，然后分别统计出该对象在列表的每个元素 (作为列表) 中出现的次数，把这些次数组成列表，并返回它：
> (count-instances ’a ’((a b c) (d a r p a) (d a r) (a a)))
(1 2 1 2)
尾递归
递归函数自己调用自己。如果函数调用自己之后不做其他工作，这种调用就称为尾递归 (tail-recursive)。下面这个函数不是尾递归的：
(defun our-length (lst)
(if (null lst)
0
(1+ (out-length (cdr lst)))))
因为在从递归调用返回之后，我们又把结果传给了 1+。
尾递归是一种令人青睐的特性，因为许多 Common Lisp 编译器都可以把尾递归转化成循环。若使用这种编译器，你就可以在源代码里书写优雅的递归，而不必担心函数调用在运行期产生的系统开销。如果一个函数不是尾递归的话，常常可以把一个使用累积器 (accumulator) 的局部函数嵌入到其中，用这种方法把它转换成尾递归的形式。在这里，累积器指的是一个参数，它代表着到目前为止计算得到的值。例如 our-length 可以转换成
(defun our-length (lst)
(labels ((rec (lst acc)
(if (null lst)
acc
(rec (cdr lst) (1+ acc)))))
(rec lst 0)))
派生软件-MiniLisp
MiniLisp 是个用 1000 行 C 语言写的 Lisp 解释器，其支持：
整数、符号、cons 单元格
全局变量
局部变量
原始函数，例如 +、=、< 或 list，
用户定义的函数
宏观系统
垃圾收集器
编译
$ make
MiniLisp 已经在 Linux x86/x86-64 和 64 位 macOS 上进行了测试。代码与体系结构无关，因此应该能够在其他类 Unix 操作系统上编译和运行。
测试
MiniLisp 带有一个全面的测试套件。为了运行测试，给出 “test” 参数。
$ make test
语言特点
MiniLisp 是传统的 Lisp 解释器。它一次从标准输入中读取一个表达式，对其求值，然后打印出表达式的返回值。这是有效输入的示例。
(+ 1 2)
LISP有很多种方言，各个实现中的语言不完全一样。1980年代Guy L. Steele编写了Common Lisp试图进行标准化，这个标准被大多数解释器和编译器所接受。还有一种是编辑器Emacs所派生出来的Emacs Lisp(而Emacs正是用Lisp作为扩展语言进行功能扩展的)非常流行，并创建了自己的标准。
LISP语言的主要现代版本包括Common Lisp和Scheme。
LISP是第一个函数型编程语言，区别于C/Java等命令型编程语言。Lisp语言形式简单、内涵深刻，Paul Graham在《Lisp之根源》中将其对编程的贡献与欧几里德对几何的贡献相提并论。
由于历史的原因，Lisp长期以来被认为主要用于AI领域，但Lisp并不是为AI而设计，而是一种通用的编程语言。Lisp的表达式是一个原子(atom)或表(list)，原子(atom)又包含符号(symbol)与数值(number)；表是由零个或多个表达式组成的串行，表达式之间用空格分隔开，放入一对括号中，如：
abc
()
(abc xyz)
(a b (c) d)
最后一个表是由四个元素构成的，其中第三个元素本身也是一个表，这种list又称为嵌套表(nested list)。正如算数表达式1+1有值2一样，Lisp中的表达式也有值，如果表达式e得出值v，我们说e返回v。如果一个表达式是一个表，那么我们把表中的第一个元素叫做操作符，其余的元素叫做自变量。
虽然Lisp与函数式编程有很大的关系，但学习Lisp绝不仅仅是学习如何用函数表达设计思想。实际上，函数式编程并非Lisp的本质，在已经掌握了lambda、高阶函数、闭包、惰性求值等函数式编程概念之后，学习Lisp仍然大大加深了对编程的理解。学习Lisp所收获的是如何“自由地”表达你的思想，这正是Lisp最大的魅力所在，也是这门古老的语言仍然具有很强的生命力的根本原因。
Scheme
Scheme是一种函数式编程语言，是Lisp的两种主要方言之一（另一种为Common Lisp）。不同于Common Lisp，Scheme遵循极简主义哲学，以一个小型语言核心作为标准，加上各种强力语言工具（语法糖）来扩展语言本身。诞生于1970年。
麻省理工学院与其他院校曾采用Scheme教授计算机科学入门课程。著名的入门教材《计算机程序的构造和解释》（SICP）利用Scheme来解释程序设计。Scheme的广泛受众被视为一个主要优势，然而不同实现之间的差异成为了它的一个劣势。Scheme最早由麻省理工学院的盖伊·史提尔二世与杰拉德·杰伊·萨斯曼在1970年代发展出来，并由两人发表的“λ论文集”推广开来。 Scheme语言与λ演算关系十分密切。小写字母“λ”是Scheme语言的标志。
Scheme的哲学是：设计计算机语言不应该进行功能的堆砌，而应该尽可能减少弱点和限制，使剩下的功能显得必要。Scheme是第一个使用静态作用域的Lisp方言，也是第一个引入“干净宏”和第一类续延的编程语言。目前Scheme由IEEE负责标准管理，并由一个专门的委员会发表的“算法语言Scheme报告，第N版”（Revisedn Report on the Algorithmic Language Scheme）进行标准化。
Scheme大体上是一个函数式编程语言，并支持其他编程范型。它的语法基于Lisp的S-表达式：函数调用在Scheme中表示为一个串列，其中第一个元素为函数名，而后的元素为函数的参数。一个Scheme程序是由嵌套串列表达而成，而串列又是Scheme的主要数据结构，这导致程序和资料在Scheme中基本上是等价的概念。因此每一个Scheme程序都可以被视为另一个Scheme程序的参数。Scheme程序可以轻易读入并分析其他Scheme程序，就是所谓的同像性。该特性被用于“代码即数据”的设计思维中，它极大提高了语言表达性和灵活性。但也有批评认为对该特性的不当使用将造成反效果，将数据当作代码需要借助eval在运行时求值，这不利于编译优化；另外代码可以被当作数据一样被修改（即所谓程序自修改）可能会造成程序逻辑混乱。
Scheme的列表与其他Lisp方言都是基于最基础的数据结构“有序对”（pair）。Scheme提供cons，car，与cdr方法操作有序对与列表。Scheme的变量都使用动态强类型系统，而函数被视为变量的一种，并可以作为参数提供给其他函数。换句话说，Scheme中的函数都是第一类对象。
Scheme的精简设计使得编程语言设计人士与爱好者特别钟爱研究它的实现，很多嵌入式系统语言与脚本语言即是基于Scheme。Scheme的实现一般小而精简，造成了很多不可互通的实现互相竞争。尽管Scheme的精简性是它的一个主要长处，但试图使用Scheme编写既复杂又便于移植的程序往往比较困难，主要原因之一，是因为Scheme没有库函数标准。而R6RS试图完成这样的工作，它定义了两套标准，核心语言以及标准库。这使得Scheme第一次有了库函数标准，也使得编译器开发者和贡献者可以实现Scheme的可移植库。
脚本语言
自由软件影像处理程序GIMP利用Scheme为脚本语言。
GNU的标准脚本语言Guile是基于Scheme的，并被用于GNOME等软件中。
Common Lisp
Common Lisp，缩写为CL（不是组合逻辑的缩写）是Lisp编程语言的一种方言，由ANSI INCITS 226-1994(R2004)（前身为ANSI X3.226-1994(R1999)），所定义的语言规范标准。Common Lisp HyperSpec是源自于ANSI Common Lisp标准的网页超链接版本。诞生于1984年。
CL语言是为标准化和改良Maclisp而开发的后继者。到20世纪80年代初，几个工作组已经在设计MacLisp各种后继者，例如：Lisp Machine Lisp（又名 ZetaLisp），Spice Lisp，NIL和S-1 Lisp。CL是为了标准化和扩展此前众多的MacLisp分支而开发，它本身并非具体的实现，而是对语言设立标准的规范。有数个实现符合Common Lisp规范，其中包括自由和开源软件，以及商业化产品。CL支持了结构化、函数式和面向对象编程等范型。相对于各种嵌入在特定产品中的语言，如Emacs Lisp和AutoLISP，Common Lisp是一种用途广泛的编程语言。不同于很多早期Lisp，Common Lisp如同Scheme，其中的变量是默认为词法作用域的。
身为一种动态编程语言，它有助于进化和增量的软件开发，并将其迭代编译成高效的运行程序。这种增量开发通常是交互持续地改善，而不需中断运行中的应用程序。它还支持在后期的分析和优化阶段添加可选的类型注记与转型，使编译器产生更有效率的代码。例如在硬件和实现的支持范围内，fixnum能保存一个未封装整数，允许比大整数或任意精度类型更高效率的运算。同样地，在每个模块或函数的基础上可声明优化，指示编译器要编译成哪一类型的安全级别。
CL包含了支持多分派和方法组合的对象系统，缩写为CLOS，它通常以元对象（Metaobject）协议来实现。
Common Lisp 拥有丰富的数据类别。
标量类型
数值类型包括整数，分数，浮点数和复数。Common Lisp使用大数（bignums）来表示任意大小和精度的数值。 分数类型确切地代表分数，很多语言并不具备这种能力。Common Lisp会自动将数值转换成适当的类型。有许多方式取舍数值，函数round将参数四舍六入为最接近的整数，逢五则取偶整数。truncate，floor和ceiling分别朝向零，向下或向上取整数。所有这些函数将舍去的小数当作次要值返回。
数据结构
Common Lisp的序列类型包括列表、向量、比特向量和字符串。有许多函数可对应不同类型的序列进行操作。
函数
Common Lisp支持第一类函数（亦即函数可当成数据类型来处理）。例如编写以其它函数当作一个函数的参数，或函数的传回值也是函数，利用函数的结合来描述常用的操作。CL库高度依赖于这样的高端函数变换。举例而言，sort函数可将关系运算符作为参数，并选用如何取键的函数作为参数。如此一来不但能对任何类型的数据排序，还能根据取用的键值对数据结构作排序。
Common Lisp中的宏是独一无二的，和C语言中的宏的机制相同，但是在宏扩展的过程中由于可以使用所有现有的Common Lisp功能，因此宏的功能就不再仅限于C语言中简单的文本替换，而是更高级的代码生成功能。宏的使用形式和函数一致，但是宏的参数在传递时不进行求值，而是以字面形式传递给宏的参数。宏的参数一旦传递完毕，就进行展开。展开宏的过程将一直进行到这段代码中的所有宏都展开完毕为止。宏完全展开完毕后，就和当初直接手写在此处的代码没有区别，也就是嵌入了这段代码上下文中，然后Lisp系统就对完整的代码上下文进行求值。Lisp宏表面上类似于函数的使用，但并不是会直接被求值的表达式，它代表程序源码的字面转换。宏将包含的代码内容当作参数，将它们绑定到宏自身的参数，并转换为新的源码形式。这个新的源码形式也能够使用一个宏，然后重复扩展，直到新的源码形式没有再用到宏。最终形式即运行时所运行的源代码。
Common Lisp与Scheme的比较
Common Lisp经常和Scheme互相比较，因为它们是最受欢迎的两种Lisp方言。Scheme早于CL，不仅来自同一个Lisp传统，而且来自同一位工程师Guy L. Steele，与Gerald Jay Sussman设计的，Guy L. Steele也担任过Common Lisp标准委员会的主席。
Common Lisp是一种普遍用途的的编程语言；相反的如Emacs Lisp和AutoLISP这两种Lisp的变体，则是嵌入特定产品作为扩展用的语言。与许多早期的Lisps不同，Common Lisp（Scheme同样）对源码直译和编译时，默认为词法变量作用域。
大部分Lisp系统（如ZetaLisp和Franz Lisp）的设计，促成了Common Lisp在解释器中使用动态作用域的变量，并在编译器中使用了词法作用域的变量。由于ALGOL 68的启发，Scheme引入了Lisp对词法作用域变量的单一使用；这被广泛认同是好主意。CL也支持动态作用域的变量，但必须将其显式声明为“特殊”。ANSI CL解释器和编译器之间的作用域界定是没有差别的。
Common Lisp有时被称为Lisp-2，而Scheme被称为Lisp-1。它指的是CL对函数和变量使用个别的名字空间（实际上CL有许多名字空间，例如go标签，block名称和loop关键字）。在涉及多个名字空间的权衡之间，CL与Scheme倡导者之间存在着长期的争议。在Scheme中（广义地）必须避免与函数名称互相冲突的变量名称；Scheme函数通常拥有名称为lis，lst或lyst的参数，以免与系统内置的list函数冲突。然而在CL中，在传递函数作为参数时一定要显式地引用函数的名称空间，这也是一个常见的事件，如前面小节中的排序编程示例。
在处理布尔逻辑值时，CL也与Scheme不同。Scheme使用特殊值#t和#f来表示逻辑真与假值。而CL遵循使用符号T和NIL的传统Lisp惯例，NIL同时也是空列表。在CL中任何非NIL值被条件处理为真，例如if；而在Scheme当中，所有非#f值被视为真。这些惯例约定允许这两种语言的一些运算符同时作为谓词（回应逻辑上的是非问题），并返回一个作用值进行进一步的计算，但在Scheme的布尔表达式中，等同于Common Lisp空列表的NIL值或'()，会被评估为真。
最后，Scheme的标准文件要求尾部调用优化，而CL标准没有。不过大多数CL实现会提供尾部调用优化，虽然通常只在程序员使用优化指令时。尽管如此，常见的CL编程风格并不偏好于Scheme中普遍使用的递归样式- 一个Scheme程序员会使用尾部递归表达式，CL用户则通常会用do，dolist，loop等迭代表达式，或使用iterate包来表达。
一些基于Unix的实现，例如CLISP，可以作为脚本解释器使用；因此系统可以像调用Perl或者Unix shell解释器一样透明地调用它。
函数不仅是 Lisp 程序的根基，它同时也是 Lisp 语言的基石。
除了少数称为特殊形式 (special form) 的操作符之外，Lisp 的核心就是一个函数的集合。如果你觉得某件事 Lisp 应该能做，你完全可以把它写出来，然后你的新函数可以享有和内置函数同等的待遇。有两点让 Lisp 函数与众不同。一是Lisp 本身就是函数的集合。这意味着我们可以自己给 Lisp 增加新的操作符。另一个就是:函数也是 Lisp 的对象。这意味着在 Lisp 里我们可以像对待其他熟悉的数据类型那样来对待函数,就像整数那样:在运行期创建一个新函数,把函数保存在变量和结构体里面,把它作为参数传给其他函数,还有把它作为函数的返回值。
定义函数
最通常的做法就是用defun宏实现函数定义，如下面定义的double函数。
> (defun double (x) (* 2 x))
DOUBLE
函数本身就是对象，defun就是构造这样的对象，然后保存它到第一个参数名下。所以我们既可以调用double，也可以持有这个名字对应的函数对象。通常可以用#'操作符得到这个对象，这个操作符能将名字映射到实际的函数对象。就像下面这样：
> #'double
#<FUNCTION DOUBLE>
也可以使用On Lisp
可以使用一种称为 λ–表达式 (lambda-expression) 的东西定义函数，它由三部分组成：lambda符号，参数列表和若干表达式主体。下面的λ–表达式是等价于double的函数：
> (lambda (x) (* 2 x))
λ–表达式也可以看作是函数的名字，如果说 double 是个正规的名字，那么lambda表达式就相当于具体的描述。通过#'可以得到相应的函数：
> #'(lambda (x) (* 2 x))
#<FUNCTION (LAMBDA (X)) {100366DEAB}>
由于 λ–表达式同时也是函数的名字,因而它也可以出现在函数调用的最前面：
> ((lambda (x) (* x 2)) 3)
6
在 Common Lisp 里,我们可以同时拥有名为 double 的函数和变量。
"拥有分开的变量和函数命名空间的 Lisp 称为 Lisp–2,在另一类 Lisp–1 下,变量和函数定义在同一命名空间里,最著名的这种 Lisp 方言是 Scheme。关于 Lisp–1 vs. Lisp–2 在网上有很多讨论,一般观点认为 Lisp–1 对于编译器来说更难实现。"
> (setq double 2)
2
> (double double)
4
当符号出现在函数调用的首位，或者前置 #’ 的时候，它被认为是函数。其他场合下它被当成变量名。
Common Lisp 还提供了两个函数用于将符号映射到它所代表的函数或者变量，以备不时之需。
symbol-value 函数以一个符号为参数，返回对应变量的值：
> (symbol-value 'double)
2
而symbol-function则可以得到一个全局定义的函数：
> (symbol-function 'double)
#<FUNCTION DOUBLE>
由于函数也是对象，变量也可以把函数当作值
(setf double-1 #'double)
其实，defun实际上是把它的第一个参数的symbol-function设置成了用它其余部分构造的函数，下面两个表达式完成的功能基本相同：
(defun double (x) (* 2 x))
(setf (symbol-function 'double) #'(lambda (x) (* 2 x)))
函数型参数
函数同为数据对象，就意味着我们可以像对待其他对象那样把它传递给其他函数。common lisp中提供了apply和funcall让我们实现对函数的调用：
(+ 1 2)
(apply #’+ ’(1 2))
(apply (symbol-function ’+) ’(1 2))
(apply #’(lambda (x y) (+ x y)) ’(1 2))
(apply #’+ 1 ’(2))
(funcall #’+ 1 2)
apply和funcall的唯一区别就是，apply必须以列表参数结尾。
作为属性的函数
函数作为 Lisp对象这一事实也创造了条件，能够编写出那种可以随时扩展以满足新需求的程序。假设需要写一个以动物种类作为参数并产生相应行为的函数。在大多数语言中，会使用 case 语句达到这个目的，Lisp 里也可以用同样的办法：
(defun behave (animal)
(case animal
(dog (wag-tail) (bark))
(rat (scurry) (squeak))
(cat (rub-legs) (scratch-carpet))))
如果把每种个体动物的行为以单独的函数形式保存，会更利于扩展：
(defun behave (animal) (funcall (get animal ’behavior)))
(setf (get ’dog ’behavior)
#’(lambda () (wag-tail) (bark)))
作用域
Common Lisp 是一种词法作用域 (lexically scope) 的 Lisp方言，词法作用域与动态作用域的区别在于语言处理自由变量的方式不同。
当一个符号被用来表达变量时，称这个符号在表达式中是被绑定（bound）的，这里的变量可以是参数，也可以来自于像let，do这样的变量绑定操作符。如果符号不受到约束，就认为它是自由的，比如：
(let ((y 7))
(defun scope-test (x)
(list x y)))
在函数表达式里，x是受约束的，而y是自由的。自由变量有意思的地方就在于，这种变量应有的值并不那么显而易见。一个约束变量的值是确信无疑的，当调用 scope-test 时，x 的值就是通过参数传给它的值。但 y 的值应该是什么呢？这要看具体方言的作用域规则。
在动态作用域的 Lisp 里，要想找出当 scope-test 执行时自由变量的值，要往回逐个检查函数的调用链。当发现 y 被绑定时，这个被绑定的值即被用在 scope-test 中。如果没有发现，那就取 y 的全局值。这样在用动态作用域的 Lisp 里，在调用的时候 y 将会产生这样的值：
> (let ((y 5)) (scope-test 3))
(3 5)
在词法作用域 的 Lisp 里，不再往回逐个检查函数的调用链，而是逐层检查定义这个函数时，它所处的各层外部环境。在一个词法作用域 Lisp 里，我们的示例将捕捉到定义 scope-test 时，变量 y 的绑定。所以可以在 Common Lisp 里观察到下面的现象：
> (let ((y 5)) (scope-test 3))
(3 7)
闭包
common lisp是词法作用域，如果定义含有自由变量的函数，系统就必须在函数定义时保存那些变量的绑定。这种函数和一组变量绑定的组合称为闭包。闭包是带有局部状态的函数。下面列举一些这样的例子：
(defun list+ (lst n)
(mapcar #’(lambda (x) (+ x n))
lst))
> (list+ ’(1 2 3) 10)
(11 12 13)
(defun make-adderb (n)
#’(lambda (x &optional change)
(if change
(setq n x)
(+ x n))))
> (setq addx (make-adderb 1))
> (funcall addx 3)
4
> (funcall addx 100 t)
100
> (funcall addx 3)
103
局部函数
在用lambda表达式时，由于它没有自己的名字，因此没办法引用自己，这就意味着在common lisp里，不能用lambda表达式定义递归函数。如果想把某个列表上的参数一一应用到某个函数上，可以这样写：
> (mapcar #'(lambda (x) (+ 2 x))
'(1 2 3 4))
(3 4 5 6)
要是想把递归函数作为第一个参数送给 mapcar 呢？如果函数已经用 defun 定义了，就可以通过名字简单地引用它：
> (mapcar #’copy-tree ’((a b) (c d e)))
((A B) (C D E))
但现在假设这个函数必须是一个闭包，它从 mapcar 所处的环境获得绑定，比如：
(defun list+ (lst n)
(mapcar #’(lambda (x) (+ x n))
lst))
mapcar 的第一个参数是 #’(lambda (x) (+ x n))，它必须要在 list+ 里定义，原因是它需要捕捉 n 的绑定。到目前为止都还一切正常，但如果要给 mapcar 传递一个函数，而这个函数在需要局部绑定的同时也是递归的呢？我们不能使用一个在其他地方通过 defun 定义的函数，因为这需要局部环境的绑定。并且也不能使用 lambda 来定义一个递归函数，因为这个函数将无法引用其自身。
Common Lisp 提供了 labels 帮助跳出这个两难的困境。除了在一个重要方面有所保留外，labels 基本可以看作是 let 的函数版本。labels 表达式里的每个绑定规范都必须符合如下形式：
(⟨name⟩ ⟨parameters⟩ . ⟨body⟩)
在 labels 表达式里，⟨name⟩ 将指向与下面表达式等价的函数：
#’(lambda ⟨parameters⟩ . ⟨body⟩)
例如：
> (labels ((inc (x) (1+ x)))
(inc 3))
> 4
尽管如此，在 let 与 labels 之间有一个重要的区别。在 let 表达式里,变量的值不能依赖于同一个 let 里生成的另一个变量，就是说，不能这样写( let*可以这样写 )：
(let ((x 10)
(y x))
y)
然后认为这个新的 y 能反映出那个新 x 的值。相反，在 labels 里定义的函数 f 的函数体里就可以引用那里定义的其他函数，包括 f 本身，这就使定义递归函数成为可能。
使用 labels 就可以写出类似 list+ 这样的函数了，但这里 mapcar 的第一个参数是递归函数：
(defun count-instances (obj lsts)
(labels ((instances-in (lst)
(if (consp lst)
(+ (if (eq (car lst) obj) 1 0)
(instances-in (cdr lst)))
0)))
(mapcar #’instances-in lsts)))
该函数接受一个对象和一个列表，然后分别统计出该对象在列表的每个元素 (作为列表) 中出现的次数，把这些次数组成列表，并返回它：
> (count-instances ’a ’((a b c) (d a r p a) (d a r) (a a)))
(1 2 1 2)
尾递归
递归函数自己调用自己。如果函数调用自己之后不做其他工作，这种调用就称为尾递归 (tail-recursive)。下面这个函数不是尾递归的：
(defun our-length (lst)
(if (null lst)
0
(1+ (out-length (cdr lst)))))
因为在从递归调用返回之后，我们又把结果传给了 1+。
尾递归是一种令人青睐的特性，因为许多 Common Lisp 编译器都可以把尾递归转化成循环。若使用这种编译器，你就可以在源代码里书写优雅的递归，而不必担心函数调用在运行期产生的系统开销。如果一个函数不是尾递归的话，常常可以把一个使用累积器 (accumulator) 的局部函数嵌入到其中，用这种方法把它转换成尾递归的形式。在这里，累积器指的是一个参数，它代表着到目前为止计算得到的值。例如 our-length 可以转换成
(defun our-length (lst)
(labels ((rec (lst acc)
(if (null lst)
acc
(rec (cdr lst) (1+ acc)))))
(rec lst 0)))
派生软件-MiniLisp
MiniLisp 是个用 1000 行 C 语言写的 Lisp 解释器，其支持：
整数、符号、cons 单元格
全局变量
局部变量
原始函数，例如 +、=、< 或 list，
用户定义的函数
宏观系统
垃圾收集器
编译
$ make
MiniLisp 已经在 Linux x86/x86-64 和 64 位 macOS 上进行了测试。代码与体系结构无关，因此应该能够在其他类 Unix 操作系统上编译和运行。
测试
MiniLisp 带有一个全面的测试套件。为了运行测试，给出 “test” 参数。
$ make test
语言特点
MiniLisp 是传统的 Lisp 解释器。它一次从标准输入中读取一个表达式，对其求值，然后打印出表达式的返回值。这是有效输入的示例。
(+ 1 2)