发表在《程序猿》2007年7月刊上。不log上写帖子不用考虑版面限制，所以这里的帖子比发表的啰嗦点。赵健平编辑，Jacky，和刘未鹏都给了我非常多帮助，在这里一并谢了。免费的Scheme实现非常多。我用的是PLT Scheme，能够到这里下载。PLT Scheme的IDE（Dr. Scheme）支持Emacs的键盘绑定，用emacs的老大们应该喜欢。Dr.Scheme内置中文支持：

• Scheme的语法结构大道至简。Scheme的结构就两种：原子和表达式。原子是诸如数，字符串，布尔值，变量，空表这类简单数据。对非变量的原子求值，得到原子自身。对变量求值，得到变量绑定的值。比方说，对1求值得到1，但假设对变量A求值，而A和字符串”A”绑定，则得到字符串“A”。表达式的形式也仅仅有一种：列表。一对括号包括起来的就是列表。表里的元素用空格分开。列表能够嵌套。这种表达式在Lisp里叫做S-表达式，意思是符号表达式。以下是一些样例：
  • ( )： 一个空表
  • (1 2 3 4 5)：一个包括五个整数的表
  • (1 “a” 1.5 #t #f)：一个列表，依次包括整数、字符串、浮点数、为真的布尔值、和为假的布尔值
  • (1 (2 3) )：一个嵌套列表，第二个元素(2 3)也是一个表
  • (+ 2 3)：一个表达式，表示把2和3相加。Scheme里全部的操作符都是前缀操作符，即操作符在前，操作数据在后。比方说4 * (2 + 3)在Scheme里表达为(* 4  (+ 2 3))。非常多人看无论这样的方式。只是细致思考一下，能够看出前置操作符让不论什么操作符都是多维的。比方说。假设我们要把1到5的整数相加，用中缀操作符，就得写成 1 + 2 + 3 + 4 + 5。同一个加好反复了4次。而用前缀操作符，仅仅须要写一次：(+ 1 2 3 4 5)。推而广之，假设我们要把一列数加起来，就得用到循环。而在Scheme里则不须要。并且前缀操作符去掉了优先级问题：我们能够通过括号来推断每一个表达式的优先级。
  • (lambda (x y) (sqrt (* x y))。这个表达式定义了一个匿名函数，计算并返回參数x和y的几何平均值。当一个表达式以lambda开头的时后，我们就知道要定义一个函数了。
  • (define zero 0)：这个表达式把一个变量zero绑定到一个整数0。在Scheme里，全部变量本质上都是指针。指针本身没有类型，他们指向的值才有类型。换句话说，Scheme是动态类型语言。
  • (car  ‘(1 2 3 4))：这个表达式调用函数car。函数car接收一个列表參数，并返回这个參数的第一个值，也就是1。注意样例里的參数(1 2 3 4)前有一单引號。这是由于Scheme总是把一个普通列表当作表达式计算。加上单引號相当于告诉Scheme，不要对(1 2 3 4)估值，把它当成数据对待。假设不加这个单引號，Scheme会运行(1 2 3 4)。运行的规则是把该列表的第一个元素当成函数来调用。而第一个元素是1，不是函数，Scheme会抛出错误。
  • (cdr ‘(1 2 3 4))： 这个表达式调用函数cdr（读作kuder）。函数cdr也是把一个列表作为參数，并返回这个列表除去第一个元素后的子表。所以对(cdr ‘(1 2 3 4))求值，就得到(2 3 4)。
• Scheme的数据类型Scheme提供了各种通用的数据类型：整数，浮点数，复数，有理数，字符串，布尔变量，散列，数组，矢量，点对，和列表。值得一提的是点对(pair)和列表。这俩哥们儿是Scheme编程的基石。还是用样例说明比較好：
  • (1 . 2)是一个点对。一个点对包括两个指针，每一个指针指向一个值。我们用函数cons构造点对。比方说(cons 1 2)就构造出点对(1 . 2)。由于点对总是又函数cons构造，点对又叫做cons cell。点对左边的值能够用函数car取出来，右边的值能够由函数cdr取出来。以下是图示： 
    
  • 假设一个点对右边不是一个值，而是一个指针，指向另外一个列表，我们就得到了列表。比方以下的图表示列表(1 2 3 4)，实际上由点对构成：(1 . (2 . (3 . 4. ‘())。能够看出，列表本质是单向链表。

• 不要小看了列表。这个看似简单的数据类型的具有丰富的表达能力。比方我们能够把以下2x3的矩阵表达为((1 2 3) (4 5 6) (7 8 9)):而以下的树也能够用列表直观表达：(A B C (D (F H) G) E)。也就是说，每一个列表表示一个树或子树。列表的第一个元素是根。
• 函数函数在Scheme里是一等公民。定义的函数能够被当成数据传递或返回。有三种定义函数的方法：
  • 用lambda操作符定义一个匿名函数。比方(lambda (x) (* 2 x))定义了一个函数，返回參数x的倍数。操作符lambda后第一个子列表是參数列表，而第二个子列表是函数定义。这和JavaScript里的匿名函数没有本质差别：function(x){return 2 * x;}
  • 用define绑定函数名：(define 1+ (lambda (x) (+ 1 x)))。这个样例定义了递加函数，并把它绑定到函数名1+上。。Scheme对函数名没有限制。其实，Scheme对全部函数名一视同仁。规范里定义的函数没有特殊地位，我们全然能够用自己的函数定义代替。这相当于以下的JavaScript语法：var increment = function(x){return x + 1;}。
  • Scheme还提供了一条捷径，省去lambda。以下的样例用大小比較定义相等函数。函数名是same? 而參数就是后面的x和y。        (define (same? x y)             (not (or (> x y) (< x y)))这种定义方式和JavaScript里的经常使用函数定义方式一致。呵呵，能够看出JavaScript从哪里获得灵感的了吧？以下是等价的JavaScript定义：function isSame(x, y){         return !((x > y) || (x < y));}

非常多老大看不惯括号。事实上Lisp刚诞生时，John McCarthy设计了叫M-表达式的语法，与C/C++的语法相似。比方S-表达式(cdr ‘(1 2 3)用M-表达式就写成cdr[1, 2, 3]。可是Lisp的程序猿们纷纷放弃了M-表达式，选择直接使用S-表达式。S-表达式的实质是用抽象句法树(AST)表达程序，直接省去了解析这道工序。比方说，a+b*c解析成AST后，和下图一致。而该AST的表示不正好是(+ a (* b c))么？更重要的是，既然程序就是句法树，程序和数据的表示就统一了。程序即数据，数据即程序。我们遍历列表改动数据。同理，我们也能够遍列类表改动程序。正是这种统一处理带给Scheme无与伦比的威力：不管是编译时还是执行时，我们都能够改动，注入，载入，或者生成新的程序 — 这些无非是在AST里改动或加入节点而已。我们甚至能够改动或加入新的句法。 

§      定义一个函数sum-of-squares计算一列数的平方和。比方说(sum-of-squares ‘(1 2 3 4))返回的结果是30。以下是Scheme的代码。測试结果：假设哪位老大不认为这个函数定义优雅的话，最好还是试试用命令编程的方式重写。比方说用C，用Java，或者用Pascal。解剖一下上面的函数定义：

§      再来一个样例：求出两个矢量的点乘。比方说[a, b, c, d] x [e, f, g, h]就等于a*e + b*f + c*g + d*h。假设我们定义函数dot-product, 那么(dot-product ‘(1 2 3 4) ‘(5 6 7 8))就等于1x5+2x6+3x7+4x8 = 70：这次函数map同步遍历两个列表，所以定义的匿名函数也接受两个參数。Scheme里的map函数能够同一时候遍历随意多个列表。Scheme里的函数调用都是S-表达式列表。所以遍历一个列表也好，多个列表也好，都是处理一个S-表达式的尾巴，没有本质差别。哪位老大有兴趣，最好还是了解了Scheme宏的使用方法（后面会讨论）后，实现自己的map函数。

§      还不够奇妙？那写个矩阵转置函数怎么样? 所谓矩阵转置，是说把M x N的矩阵的行和列兑换，得到NxM的矩阵。比方以下的样例。给出矩阵A， A的转置矩阵A^T就等于矩阵B：  假设我们定义了函数transpose，那么用上面的样例，调用函数(transpose ‘((1 2 3) (4 5 6) (7 8 9) (10 11 12))就应该得到((1 4 7 10) (2 5 8 11) (3 6 9 12))。实现这个函数得多少代码呢？请看—一行代码，四个函数。还有比这更干净利落的么？我们详细分析一下：

§      在处理树状数据时，我们往往须要知道树的最大深度（最大深度也叫树的高度）。一个节点的深度等于该节点到根节点间的路径数。下图中的树最大深度为3， 路径是A->D->F->H。如今我们写一个函数来计算一棵树的深度。

o       应用高端函数和递归，我们的函数定义很easy：

Scheme里没有unless这个关键词，也不能后置修饰条件。只是用上宏就不一样了：測试结果：

1991年Guy Lapalme给出了Common Lisp的lisp comprehension宏定义[14]。熟悉Lisp的老大们能够看出Lisp的句法转换明显不如Scheme的方便简洁。以下是一些測试样例：

• flat-map是一个简单函数。它和函数map功能相似。只是它会展平嵌套的列表。比方说(map (lambda (x) (list x)) ‘(1 2 3))的结果是((1) (2) (3))，而把map换成flat-map得到的结果是(1 2 3)。
• (define-syntax list-of。。。定义了list comprehension的句法。当系统看见list-of时，就知道要运行list comprehension了。
• (syntax-rules (<-))表示開始定义句法转换规则。关键词syntax-rules后紧跟的列表(<-)能够包括一个或多个标识符。Scheme在句法转换时会自己主动忽略这些标识符，不会让它们同随后的变量匹配。
• 省略号…表示匹配0个或多个标识符号。比方，模式(x …)能够同(1)匹配，也能够同(1 2)匹配，也能够同(1 a 3)匹配。
• 注意定义的句法能够递归出现，比方list-of 就出如今随后的定义里。正是递归的威力让看似复杂的list comprehension变得如此easy实现。也就是说，Scheme的宏事实上是功能更为花哨的函数。