小语种介绍：LISP/Scheme

自从裘宗燕教授翻译了《计算机程序的构造和解释》（Structure and Intepretation of Computer Programs，SICP）第二版之后，这本MIT计算机系的编程入门教材开始越来越多地受到中国开发者的关注。同时受到关注的，还有它所介绍的函数式编程（Functional Programming），以及其中范例所使用的Scheme语言。

时光倒转到30年前，1975年，Bill Gates和Paul Allen写出了那个传奇的BASIC版本——他们后来卖给MITS、换来“第一桶金”的那个BASIC版本。同一年，Gerald Sussman——他正是SICP的作者——创造了Scheme语言。其实Scheme并不是一种新鲜的语言，准确地说，它只是LISP的一个变体、一种方言。早在1958年，John McCarthy就开始研究一种“用于处理列表数据”的语言——这也是LISP名字的由来（LISt Processing）。“列表处理”乍看上去是一个相当特定的问题，但实际上这类问题有着深远而重要的内涵，稍后我们就会看到这里的故事。

与LISP的其他方言相比，Scheme最大的特点或许在于：它是可以被编译成机器码的。也就是说，它的运行效率更高。除此之外，Scheme在语言层面上可说是中规中矩。LISP素来奉仰的哲学思想是“微核心+高扩展性”，Scheme也将这一特点发挥到了极致。Scheme内置的关键字（keyword）少得可怜，就连大于小于、加减乘除等操作都是以函数的形式出现。甚至可以夸张一点说，只要有define关键字与括号，就可以写出所有程序。不过，这种风格的一个副作用是会在程序中出现大量的括号，所以也有人把LISP戏称为“一大堆烦人的、教人看不懂的括号”（Lots of Irritating, Spurious Parentheses）。譬如说，下面的程序是用来求一个值的平方：

(define (square x)

      (* x x))

(display (square 3))

对于我们这些从C语言开始入门、习惯了过程式编程（相对于“函数式编程”而言）的程序员，初接触LISP/Scheme之时，受到的第一个触动大概就是：Scheme不区分数据与操作。仍然以“求平方”的例子，“x的平方”可以表述为“以1为基数，将‘乘以x’计算两次”。如果用C++语言，这个逻辑可以这样实现：

int square(int x) {

      return 1 * x * x;

}

而在Scheme中，我们还可以这样实现：

(define (twice func base arg)

      (func base (func base arg)))

(define (square x)

      (twice * 1 x))

这种实现的特点在哪里？最大的特点就是：一个操作（乘法运算）被当作参数传递。按照程序设计的“黑话”，如果一个程序单元可以被作为参数和返回值传递，那么这个单元就被称为“一等公民”（first class）。在C/C++/Java等语言中，虽然也可以通过函数指针、functor等形式传递“操作”，但毕竟是经过了包装；而在Scheme中，可以将另一个函数直接作为参数传入函数，也可以作为返回值传回另一个函数，函数（也即“操作”）完全被作为一等公民对待。

这样做的好处是什么？在上面的例子中，我们把“两次执行某操作”的逻辑也抽象出来，得到了twice函数。如果我们想要实现“以0为基数将加法操作执行两遍”（也就是“乘以2”），只需要这样写：

(define (double x)

      (twice + 0 x))

这里的twice函数是“对别的函数进行操作的函数”，它的结果取决于传入什么函数给它作为参数。像这种“函数的函数”，在函数式编程的术语中被称为“高阶函数”（high-order）。能够很自然地实现高阶函数，是Scheme的第二个重要特点。在前面已经提到过，LISP这个名字代表“列表处理”，其实处理列表数据的能力正是来自对高阶函数的运用。譬如说，我们有下面这样一个列表：

{1, 2, 3, 4, 5}

针对这个列表，我们要做两件事：

<!---->1.      <!---->将每个元素翻倍，得到新的列表：{2, 4, 6, 8, 10}

<!---->2.      <!---->对每个元素求平方，得到新的列表：{1, 4, 9, 16, 25}

用Java语言，我们可以这样实现：

List<int> doubleList(List<int> src) {

      List<int> dist = new ArrayList<int>();

      for(int item : src) {

            dist.add(item * 2);<o:p></o:p>

}

return dist;

}

List<int> squareList(List<int> src) {

      List<int> dist = new ArrayList<int>();

      for(int item : src) {

            dist.add(item * item);<o:p></o:p>

}

return dist;

}

问题一目了然：除了加粗的两行代码之外，这两个方法几乎是完全重复的。细想之下，其实这两个方法做的事情非常相似：遍历一个列表，按照“某种规则”将原列表的每个元素映射到新的列表中。因为这个“某种规则”是针对元素的映射操作，所以为了抽象这种列表操作，我们必须实现一个高阶函数，将实际的映射操作以参数的形式传入。于是，在能够方便实现高阶函数的Scheme中，以上逻辑实现起来相当容易：

(define (double-list src)<o:p></o:p>

      (map double src))<o:p></o:p>

(define (square-list src)<o:p></o:p>

      (map square src))<o:p></o:p>

由于高阶函数在操作逻辑抽象方面的强大与便利，很多人开始寻求在“主流”的过程式语言中将操作当作一等公民对待，进而实现高阶函数。譬如说，C#以delegate的形式允许将方法作为参数或返回值传递，并且在List<T>类型中加入了find等高阶操作；Java世界的FunctionalJ（http://functionalj.sourceforge.net/）则在Java5提供的泛型基础上提供了filter、map等常用的列表操作。前面的例子如果用FunctionalJ来实现，就可以写成：

// double and square are Function instances

List<int> doubleList(List<int> src) {

      return Functions.map(double, src);

}

List<int> squareList(List<int> src) {

return Functions.map(square, src);

}

“不区分数据与操作”这句话说起来很简单，其实背后蕴含着一个重要的哲学问题，即“什么是时间”的问题。按照过程式编程的理念，“时间”是操作内部的一个变量，程序以局部变量的形式记录系统在各个时间点的瞬时状态；而按照函数式编程的理念，“时间”是操作外部的变量，以参数的形式传入函数，函数内部则没有局部状态，更没有赋值操作。或者更简单一点说，在任何时候用同样的参数调用同一个函数，必定会得到同样的结果。这种性质被称为“引用透明”。如果操作不具备引用透明性，就不能将它作为参数或返回值传递，因为调用环境和顺序都可能改变高阶函数的结果。

具备引用透明性的程序还有一项额外的好处：它们天生地具有线程安全性。不论有多少条线程、以什么顺序访问，只要程序具有引用透明性，就不需要额外的线程同步机制来保证结果正确。在同时面向众多用户的服务器端应用、尤其是web应用中，这一点显得特别重要。Rod Johnson在他的《J2EE Development without EJB》一书中提倡“无状态的Java服务器端应用”，企业应用的开发者们也从函数式编程的思想中受益匪浅。

据说LISP当初的发明颇有些无心插柳的味道：McCarthy只实现了一个基于lambda运算的抽象语法就把它扔到一边，而他的学生们却发现在这样极简的语法中写程序别有一番乐趣。有人说计算机科学家是一群喜欢归约的人，LISP的发明却是从实践的角度证明：基本上所有的程序结构都可以归约为lambda运算。按照Alonzo Church发明的丘奇代数（Church Calculus）理论，一切可以有效计算的函数——包括定值函数——都可以用lambda运算来定义。譬如说，数据“0”和操作“加1”可以用lambda运算定义如下：

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

在此基础上，就可以用lambda运算定义整个自然数系。这是一个极端的例子。在别的很多地方，LISP/Scheme也能够以类似的方式剖析我们习以为常的概念，让我们获得更加深入的洞见。譬如在SICP第二章“构造数据抽象”中，我们亲眼看到：平时所说的“面向过程编程”与“面向对象编程”，在很大程度上无非是使用同一组lambda运算的不同语法糖而已。熟悉面向对象的程序员在学习Scheme时，常常会因为跨越了“数据”与“操作”的鸿沟而获得一些全新的理解。再加上Scheme的语法极其简单，最常用的关键字大概不超过5个，所以作为教学语言有着得天独厚的优势——不少学校采用Java作为大学生的编程入门语言，当你看着这些可怜的学生在两个月之后还在与“匿名内部类”之类诡异的语法和“IO流装饰器”之类复杂的类库纠缠不清时，你不难理解我的意思。

但这种简单性也成为Scheme在企业应用中推广的最大障碍：企业应用需要的不是许多种优雅的可能性，而是一种可行的解决方案。虽然PLT等Scheme实现版本提供了XML、servlet等工具库，但过于灵活的语法、最佳实践的缺乏、以及没有大厂商的支持，都让Scheme终于无法成为企业应用的主流。不过，尽管几乎没有真正的应用，来自函数式编程的理念还是启发着企业应用的开发者们。譬如WebWork2.2引入的continuation特性，就是来自函数式编程的概念。

最后——但并非最不重要的——应该说明：虽然很少在企业应用中见到踪影，但LISP/Scheme在科学计算、人工智能、数学建模等领域的运用非常广泛，所以把它称作“小语种”多少有些不太公平。整体而言，LISP/Scheme强于算法逻辑的编写，而不善于I/O操作。我们当然可以说这是它失意于企业应用领域的原因，但又何尝不可以是它的结果呢？