发表在《程序猿》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));
}
- 用lambda操作符定义一个匿名函数。比方(lambda (x) (* 2 x))定义了一个函数,返回參数x的倍数。操作符lambda后第一个子列表是參数列表,而第二个子列表是函数定义。这和JavaScript里的匿名函数没有本质差别:
非常多老大看不惯括号。事实上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里改动或加入节点而已。我们甚至能够改动或加入新的句法。
測试结果:
假设哪位老大不认为这个函数定义优雅的话,最好还是试试用命令编程的方式重写。比方说用C,用Java,或者用Pascal。
解剖一下上面的函数定义:
这次函数map同步遍历两个列表,所以定义的匿名函数也接受两个參数。Scheme里的map函数能够同一时候遍历随意多个列表。Scheme里的函数调用都是S-表达式列表。所以遍历一个列表也好,多个列表也好,都是处理一个S-表达式的尾巴,没有本质差别。哪位老大有兴趣,最好还是了解了Scheme宏的使用方法(后面会讨论)后,实现自己的map函数。
假设我们定义了函数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。如今我们写一个函数来计算一棵树的深度。
(cond
((条件1) (表达式1))
((条件2) (表达式 2))
。。。
((条件 n) (表达式 n))
(else (表达式 n+1)))
也就是说,当(条件 k)的计算结果为真时,(表达式 k)会被运行。运行完后,函数cond结束。最后的符号else是特殊元素,它的计算结果总是为真,这保证了当其他条件语句不为真时,else相应的表达式肯定会被运行。
#define SQAURE(x) x * x
#define SQUARE(x) (x*x)
#define SQUARE(x) ((x)*(x))
int temp;
#define SQUARE(x) ({temp = x; temp * temp})
但是这种话这个宏仅仅能接受整数,还引入一个全局变量,那我们还不如写成int square(x){return x * x;}。于是再改:
#define SAUARE(x) /
这下能够了,但我们以后不能直接申明int x了,得用XTYPE这个typedef定义的类型。一个如此简单的宏都要耗费这么多考量,那再复杂一点的呢?C++的模板好一些,只是看看Boost的实现,就知道C++模板最好留给类库程序猿[11]。幸好,Scheme的宏提供了全然不同的体验。它让我们把编程中反复出现的模式抽象出来。这类抽象往往和详细应用有关,不适合在短小篇幅内举例。因此,我们用模拟其他语言的功能来举例。但不要误解Scheme的宏仅仅适合写编译器或者DSL。
print “x > y” unless y >= x
if(! (y >= x) ){
print “x > y”
}
測试结果:
(syntax-rules ()
(模式1 模板1)
(模式2 模板2)
。。。
(模式n 模板n))
Scheme会依次用列出的模板匹配定义的表达式。匹配成功的话,就扩展模板。比方说当Scheme看到(du (display “3 > 2”) unless (> 2 3))时,就開始试着用宏定义里的模式来匹配该表达式。下划线”_”是一特殊字符,指代宏的名字。匹配的结果是 _ 与”du”匹配,expression与(display “3 > 2”)匹配,而condition与(> 2 3)匹配。匹配成功,所以这个模式相应的模板被展开为(if (not (> 2 3)) (display “3 > 2”))。运行该语句,便导致“3 > 2”被打印出来。两行程序,我们便能够体验新的编程手段。还不够酷么?
[2 * x for x in range(10) if x % 2 == 1]
Haskell里甚至支持对多个列表同一时候操作。以下的样例表示,依次取出列表[1, 3, 5]里的每一个元素x,和列表[2, 4, 6]里的每一个元素y, 把他们组对。得到的结果是新的列表[(1,2),(1,4),(1,6),(3,4),(3,6),(5,6)]
[(x,y) | x <- [1,3,5], y <- [2,4,6]]
我们用Scheme的宏能够如魔法般实现这样雅致的功能。Scheme类库Swindle里包括了花样繁复的list comprehension功能。我们这里仅仅实现一个阳春版的[12],用Philip Wadler提出的转换规则[13]:
- 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的宏事实上是功能更为花哨的函数。
flat-map f [] = []
flat-map f (x: xs) = (f x) ++ (flat-map f xs)
(a) TE[[E | v<- L: Q]] = flat-map (lambda (v). TE[[E | Q]]) TE[L]
3
1975年问世的Scheme是Lisp方言,所以我们最好还是先吹吹LISP。传说中,排资论辈,LISP和FORTRAN是都是属于古老的语言,可是fortran常常作为反面教材,LISP相比之下那自然是无限风光,倍受世人赞誉。LISP拥趸们不断“发现”Lisp里简单却深刻,浅显而强大的特性,并应用到不同地方,取得非凡成就。牛牵到哪里都是牛,上下纵横50年,就比方说如今红的发紫的Ruby,Python,和JavaScript语言,它们最为人称道的功能,居然大多源于Lisp(后面会有样例说明)。或许John K. Foderaro这位老牛的比喻和总结最能说明Lisp的价值:Lisp好比变色龙,高度适应环境的改变,由于它是一门*能够编程的编程语言*。我们不仅能够用Lisp编程,还能够对Lisp编程i。Lisp内置的抽象方法让Lisp程序员们身段灵活,长袖善舞。每当新的编程范式出现,Lisp程序猿们总能高速实现相关功能,甚至做出进一步改进。
----比方Smalltalk展示面向对象编程的潜力后,MIT媒体实验室的Cannon Howard便在1982年推出Flavors,一个功能丰富的面向对象扩展。Cannon的扩展不仅实现了 当时流行的面向对象功能,还首创了多继承,多重分派,以及被Ruby程序猿狂赞的mixini。尔后Gregor Kiczales又在集大成的CLOS里增加如今颇为眩目的面向方面(AOP)编程方法ii。---这段假设再比較说明和LISP的关系的话,我想那就更好了。
LISP吹捧完了后,如今再说说Scheme的传奇故事。1958年,John McCarthy从达特茅斯搬到MIT。当时人工智能的还有一奠基人Marvin Minsky也在MIT。牛人相见,好比姚麦组合,利刃相击,火花耀眼。著名的MIT人工智能项目在两人领导下上马i。可是在研究AI的过程中,McCarthy须要一门编程语言表达他的理论模型。而当时人见人爱的图灵机仅仅有一套笨拙的语言,不适合干净利落地表达复杂的递归函数,于是乎需求产生了,McCarthy在丘齐的lambda算子基础上顺便就设计了Lisp,其实最初Lisp是一个纯纯的理论工具,用来进行程序的推导和证明。实在须要用机器验证理论了,研究组的老大们就手工把Lisp程序翻译成IBM 740的汇编代码,再上载到IBM 740上执行。人肉编译器们甚至热衷于编译各式Lisp程序,认为跟解智力题一样好玩儿。他们还证明了能够用Lisp写出一个通用函数eval(), 用来解释执行Lisp的表达式i。但他们光顾赞叹eval()和元图灵机一样彪悍,且比图灵机构造出元图灵机的代码美妙,并没想到eval就是一个通用的Lisp解释器。幸好有天McCarthy的学生S.R. Russell灵机闪现,连夜用IBM704的机器语言实现eval()。于是世界上第一个Lisp解释器横空出世,人肉编译才渐渐失传。那时真是计算机科学研究的黄金时代啊,人们能够一夜之间改变世界,比居委会大妈在股市一夜暴富还来得轻快。顺便提一下,我们习以为常的条件推断语句,也是McCarthy在Lisp里发明的。而为了让函数应用没有副作用和实现函数闭包,McCarthy的研究小组又顺便发明了垃圾收集。这些顺便发明的产物,那一样不是如今编程语言基石,当时要是随便一样跺跺脚,如今的编程格局预计都要中个几百以下目全非脚。1975年,同是MIT的Gerald Jay Sussman和Guy Steels为了研究Carl Hewitt的面向对象模型,用Lisp编写了一个玩具语言。这个玩具语言简化了当时流行的Lisp语法,引入了词法定界(又叫静态范围)和Continuation两大革新。Sussman和Steels给这门语言取名Schemer,希望它发展成像AI里著名系统Planner一样的有力工具。可惜当时MIT用的操作系统ITS仅仅同意最长6个字节的文件名称。Sussman和Steels不得不把Schemer的最后一个字幕’r’去掉。Scheme问世便显露峥嵘:Sussman和Steels非常快发现Scheme的函数和Hewitt模型里的演员(也就是我们如今所谓的对象)没有本质差别,连句法都基本一致。其实,Sussman在教材《计算机程序设计与解释》的第二章用短短几十行代码展示了一套面向对象系统。
好了,正餐如今開始。Scheme是极度简化的语言。他的规范文档只是47页i,浓缩的就是*,吃惊吧。相比还有一大Lisp分支Common Lisp规范的上
千页文档或者Java规范的500来页文档,可见Scheme的短小精悍。只是,我们能够用Scheme写出优雅犀利的程序。Scheme规范R5RS开篇道出了Scheme的设计宗旨:设计编程语言时不应堆砌功能,而应去掉让多余功能显得必要的弱点和限制。Smalltalk的发明人Alan Kay在一次訪谈录中提到,Lisp是编程语言中的麦克斯韦方程组ii。这句评价用到Scheme上更为合适。Scheme甚至让我们写出用其它语言无法写出的程序。这个时候,通常是老大们轻蔑抛出编程语言图灵完备这样的论点的时候。所以俺最好还是小小地提醒一下:理论上,理论和实践没有区别,但实际上两者区别海了去了。不然,我们干嘛不继续用机器语言编程呢?Scheme写出的程序用汇编/C也能实现,只是这样想的老大们最好先用汇编/C写出一个Scheme的解释器。Sussman和Steeles用Scheme探索不同的编程模型时时,往往一周做出十来种不同的解释器,能够旁证Scheme的简洁和灵活。在解释是什么造就了Scheme的精练与生猛之前,我们先介绍一下Scheme的基本元素: