2008年12月9日星期二

4个程序员的一天

你,一个DotNet程序员,刚刚加入一个新项目组。除了你之外,其他的成员包括:Ceer,一直从事C项目的程序员,他刚刚转入C#不到一个月; Jally,整天抱着本Design Pattern(没错,就是GoF的那本)在啃的前Java程序员;以及Semon,你对他完全不了解,只是听PM介绍说他是搞Scheme的(传说中的第二古老的语言LISP的方言之一)。不过你也没在意,毕竟计算机这玩意,老东西是不吃香的。


周一,刚打开电脑,老板就跑到你们组的办公座面前:“好吧,伙计们,现在有个function需要你们来搞定。具体是这样的:用户输入2个数,并输入一个操作符。你根据输入的情况来得出相应的运算结果。“


Example: Foo(+, 1, 2) = 3; Foo(*, 3, 6) = 18; Foo(/, 2, 4) = 0.5


Ceer最先作出反应:简单嘛,判断一下输入的操作符就好了。说着,他很快在白板上写出如下代码:

public class CStyle_Calculator

{

static public double Foo(char op, double x, double y)

{

switch(op)

case '+': return x + y; break;

case '-': return x - y; break;

case '*': return x * y; break;

case '/': return x / y; break;

default: throw new Exception(”What the Hell you have input?");

}

}



Jally只看了一遍,就捂着鼻子连连摇头:好一股的代码臭味【注1】。还不如看我用OO的方法来解决:

public interface I操作符 //谁说代码不能写中文的?恩恩

{

double 运算(double x, double y);

}



public class OO_Calculator

{

private I操作符 m_op;

public OO_Calculator(I操作符 op)

{

this.m_op = op; //依赖注入【注2】

}



public double Foo(double x, double y)

{

return this.m_op.运算(x, y);

}

}



public class 加法:I操作符

{

public double 运算(double x, double y)

{

return x + y;

}

}



public class 减法:I操作符

{

public double 运算(double x, double y)

{

return x - y;

}

}



public class 乘法:I操作符

{

public double 运算(double x, double y)

{

return x * y;

}

}



public class 除法:I操作符

{

public double 运算(double x, double y)

{

return x / y;

}

}



public class TheMainClass

{

static public void Main()

{

I操作符 我的加法 = new 加法();

OO_Calculator 我的加法器 = new OO_Calculator(我的加法);

double sum = 我的加法器.Foo(3, 4);

System.Console.WriteLine(sum);

//sum = 7



//其他3个我就不废话了

}

}


你看着Jally把白板写得密密麻麻之后,耸耸肩,暗叹,你们这些用java的废柴,就一个运算器还搞出Interface这些东西,烦不烦啊。 让你们见识见识DotNet的强大吧. 那个运算符我直接用delegate传进去不就好了么.

public delegate double TheOperator(double x, double y);



public class Operators

{

static public double Add(double x, double y)

{

return x + y;

}



static public double Sub(double x, double y)

{

return x - y;

}



//乘,除法 我也懒得废话了

}



public class DotNet_Calculator

{

public double Foo(TheOperator op, double x, double y)

{

return op(x, y);

}

}



public class TheMainClass

{

static public void Main()

{

TheOperator myAdd = new TheOperator(Operators.Add);

TheOperator mySub = new TheOperator(Operators.Sub);



DotNet_Calculator dc = new DotNet_Calculator();

double sum = dc.Foo(myAdd, 2, 4); //sum = 6

System.Console.WriteLine(sum);

double sub = dc.Foo(mySub, 3, 7); //sub = -4

System.Console.WriteLine(sub);

}

}

//dot net 下面还可以用CodeDom动态构造C#代码,然后在内存编译运行。

//如果觉得专门写个Operators很烦的话,可以试试C#2.0的匿名方法


很好,当你写完代码之后,挑衅的看着Jally,Ceer却开始抱怨起来:”这不就是C里面的函数指针么,我也会...“

“然则DotNet下面的Delegate是类型安全滴...”你继续洋洋得意.



而Semon,看了看你们3位华丽的代码,啥也没说,只是在键盘上敲下了2行代码


(define (Foo op x y)

(op x y))


然后就下班了...


【注: scheme的代码稍微解释下:(+ 1 2) = 3, (* 3 4) = 12.】

至于Semon的解法:

(define (Foo op x y)

(op x y))


看明白了么,上面的代码只有一个作用:第一行是函数头,定义了一个叫Foo的函数。该函数接受3个参数op, x, y。

第二行定义了函数的行为:把第一个参数op当作运算符,计算后面2个参数。

所以:(Foo + 1 2) = 3. (Foo / 12 6) = 2.


好了好了,不编故事了。

我只是想简单的让大家在繁忙的工作之余,也瞅瞅Function Programming(函数编程)世界的美妙。函数编程,最大的特点是它是将函数作为语言里1st class的元素来对待的。一个函数可以接受另一个函数作为参数,也可以把一个函数作为结果来返回。这样的函数我们称为Higher-order function。


那么,Function Programming和我们传统的面向对象有啥区别捏? 恩,这个嘛,扯得远可以扯到图灵机和冯·诺以曼这2种体系的差异...@_@不过那个太学术性,俺就不说了。不过有句话可以较好的概括FP和OO的区别(好吧,这个也是抄“紫皮书”上面的):


“Pascal是为了建造金字塔...Lisp是为了建造有机体...”“作为Lisp的内在数据结构,表对于这种可用性起着重要的提升作用...”“采用100函数在一个数据结构上操作,远远优于采用10个操作在十个数据结构上工作”“金字塔矗立在那里千年不变,而有机体则必须演化,否则就会消亡”。


而另一个总结得比较好的话是:(同样是抄来的)


一个对象:一组相同的运算上面,外加不同的数据。(想想你的object,是不是这样的?)

一个Closure:一组相同的数据,外加不同的操作。(Delegate就是这样的思想,有兴趣的话也可以去看看Ruby)


基本上,恩,没啥说的了。 如果你感兴趣的话,可以去看MIT SICP的课程(有在线版的,MIT也作为Open Course开设了的)


参考文献:

Java 语言中的函数编程(偶FP的入门贴。查叔叔,我膜拜您)

http://www.hibernate.org.cn/viewtopic.php?t=7569&postdays=0&postorder=asc&start=0


Lambda Calculus

http://www.mactech.com/articles/mactech/Vol.07/07.05/LambdaCalculus/


Java 语言中的函数编程

http://www-128.ibm.com/developerworks/cn/java/j-fp/


【注1】

见Bob大叔的《ASD》一书


【注2】

Flower的依赖注入模式,Ioc容器啥的是这里来的

伟大的树形结构

一篇介绍Ant、Xml与Lisp相似,来讲述Lisp语言的特质,数据与指令;另外,那篇文章也谈到以xml可以作为语言间相互转换的中间语言,当时非常震惊于lisp语言的神奇,称其为与C语言并立的语言高峰。后来随着不断地回味这其中的门道,个人觉得这之间其实不用讲那么玄乎,其实最根本的地方就是树形特征在它们里面暗藏着,使得他们可以存在某种形式的映射关系。即不管是lisp还是c、java、xml其实是一种树形化表示方式,在这种表示方式下,我们采用了不同的解释就可以让它转化为不同的东西。而两种树形化语言间,由于存在某种程度上的映射关系,那么可以表示树形化的xml就,可以作为中间一级的介质存在。另外,由于树形数据在计算机编程中广泛性,我们有理由相信lisp类似列表的树形表示,它的生命力很顽强的。因为只要c语言能够表示的,lisp就可以通过一定的树形化映射表示过去。

谈到对树形化结构的佩服,就谈一点在个人具体工作中,遇到的一个关于树形化的应用。也是现在比较火热的基于Web的B/S系统。在几年的工作经历中,由于特殊的软件产品,曾接触到ActiveX控件对Javascript暴露的方法接口和事件接口,以达到“胖”客户端的目的。在ActiveX的设计中有良有莠,其中有一些接口和事件采用了参数列表的做法,有些接口和事件采用了对象化的做法。在维护的过程发现,由于业务的新变化,经常可能需要扩展新的数据,如果接口使用参数列表的做法,每次为了保持兼容性,我们就不得不开辟新的接口;但是,对象化的接口每次加入新的东西,几乎是对Javascript是透明的,原来的javascript可以照原来的协议进行访问、访问老属性,新功能版本的Javascript工作在新的协议上、即访问新的属性。

在经过几番教训和磨砺后,大家讨论觉得对象化ActiveX控件对脚本暴露的方法和事件是一个获得比较好扩展性、兼容性的做法。在以后的工作过程中,经常以这样的观点去靠、去分析已经实现ActiveX代码,发现在所有对象化接口和事件中,另外一个做的非常好的就是对象化其实是一个递归的过程,即对象化的属性也可以是对象化的.这样对象化自身看来就像一个背袋,可以不断地扩展,往背袋里面装载了东西,它可以是原来版本已经有,也可以是后来加入的。背袋提供了类似容器一样的扩展性,对于背袋的外层用户来说,如果是旧版本它可以按照老的工作协议从背袋中取数据,如果是新版本则可以按照新的工作协议。
在这个对象化的最后,你也可以看到一颗树的产生,它由自动化接口IDispatch作为树的主干存在,原始类型以及自动化接口自身可以作为叶子存在,形式化可描述为IDispatch* = {IDispatch*|other variant Type}。后来也思考到由于Javascript之于对象化的Activex接口和事件有天生的兼容性和扩展性,那么强类型语言之于二进制的数据呢?我们是不是也可以做到,修改接口协议之后获得自动的兼容性呢?我们知道是数据结构决定了操作,或者操作上的某种特性的要求也会支持去创造出新的数据结构。对于二进制数据,如果在操作上是普通的移位,而不是象良性树形化数据,我们可以按照节点去操作,那么二进制的扩展性就不是很好。因为插入新数据后,简单地移位后会导致后面的发生变化。我们在二进制协议设计中也通常使用TLV代表一个存储域,其实它就可以看做是一种类似树形的节点,那么我们看看在TLV结构下的节点操作吧,我们可以做到每次我二进制的移动位置量是由TLV中的L决定,这样移动量是一个节点,相当于节点操作,而Value的取法仅决定于工作协议,没有严格与TLV中Length相绑定滚系。 在这种二进制TLV的组织中和“正确”编解码中,那么我们也可以获得类似树形化数据的扩展性,随便添加枝叶,但是对已有的接口程序不会存在不良影响。

2008年11月26日星期三

函数式编程另类指南

程序员拖沓成性,每天到了办公室后,泡咖啡,检查邮箱,阅读 RSS feed,到技术站点查阅最新的文章,在编程论坛的相关版面浏览公共讨论,并一次
次地刷新以免漏掉一条信息。然后是午饭,回来后盯了IDE没几分钟,就再次检查邮箱,倒咖啡。最后在不知不觉中,结束了一天。
不平凡的事是每隔一段时间会跳出一些很有挑战性的文章。如果没错,这些天你至少发现了一篇这类文章——很难快速通读它们,于是就将之束之高阁,直到突然
你发现自己已经有了一个长长的链接列表和一个装满了PDF文件的目录,然后你梦想着到一个人迹罕至的森林里的小木屋苦读一年以期赶上,要是每天清晨你沿
着那里的林中小溪散步时会有人带来食物和带走垃圾就更好了。
虽然我对你的列表一无所知,但我的列表却是一大堆关于函数式编程的文章。而这些基本上是最难阅读的了。它们用枯燥的学院派语言写成,即使“在华尔街行业
浸淫十年的专家(veterans)”也不能理解函数式编程(也写作FP)都在探讨些什么。如果你去问花旗集团(Citi Group)或德意志银行
(Deutsche Bank)的项目经理[1],为什么选择了 JMS 而不 Erlang,他们可能回答不能在产业级的应用中使用学院派语言。问题
是,一些最为复杂的,有着最严格需求的系统却是用函数式编程元素写成。有些说法不能让人信服。
的确,关于函数式编程的文章和论文难于理解,但他们本来不必这么晦涩。这一知识隔阂的形成完全是历史原因。函数式编程的概念本身并不困难。这篇文章可以
作为“简易的函数式编程导引”。是一座从我们命令式(imperative)的思维模式到函数式编程的桥梁。去取杯咖啡回来继续读下去吧。可能你的同事
很快就会开始取笑你对函数式编程发表的观点了。
那么什么是函数式编程呢?它怎么产生?它可以被掌握吗(Is it edible)?如果它真如其倡导者所言,为什么没有在行业中得到更广泛的使用?为
什么好像只有那些拿着博士学位的人才使用它?最要紧的是,为什么它就 TMD 这么难学?这些 closure, continuation,
currying,惰性求值和无副作用等等究竟是些什么东西?没有大学参与的项目怎么使用它?为什么它看上去这么诡异于和我们命令式思想友好,圣洁和亲
近的一切的一切?我们将于不久扫清这些疑问。首先让我来解释形成实际生活和学界文章之间巨大隔阂的缘起,简单得像一次公园的散步。
信步游园
启动时间机器,我们散步在两千多年以前的一个被遗忘了太久的春季明媚的日子,那是公元前380年。雅典城墙外的橄榄树树荫里,柏拉图和一个英俊的奴隶小
男孩朝着学院走去。“天气真好”,“饮食不错”,然后话题开始转向哲思。
“瞧那两个学生,”为了使问题更容易理解,柏拉图仔细地挑选着用词,“你认为谁更高呢?”
小男孩看着那两个人站着的水漕说,“他们差不多一样高”。
柏拉图说:“你的差不多一样是什么意思?”。“我在这里看他们是一样高的,不过我肯定如果走近些就会看出他们高度的差别。”
柏拉图笑了,他正把这个孩子带到正确的方向。“那么你是说,我们这个世界没有完全的等同了?”
小男孩想了一会儿回答,“对,我不这样认为,任何事物总有一些区别,即使我们看不到它。”
这句话非常到位!“那么如果这世上没有完全的相等,你又是如何理解‘完全’相等这个概念的呢?”
小男孩迷惑得说:“我不知道。”最初尝试着理解数学的本源(nature)时也会产生这种疑惑。
柏拉图暗示这个世上的万物都只是一个对完美的近似。他还认识到我们即使没有接触到完美但依然可以理解这一概念。所以他得出结论,完美的数学形式只能存在
于另一个世界,我们通过和那个世界的某种联系在一定程度上知晓他们。很明显我们不能看到完美的圆,但我们可以理解什么是完美的圆并用数学公式将它表达出
来。那么,什么是数学?为什么宇宙可以用数学定理描述?数学可以描述宇宙中的所有现象吗?[2]
数学哲学是一个很复杂的课题。像大多数哲学学科一样它更倾向于提出问题而不是给出解答。这些意见中很多都循回绕转于一个事实,即数学实际上是一个谜语:
我们设置了一系列基本的不冲突的原理和一些可以施加于这些原理的操作规则,然后我们就能堆砌这些规则以形成更复杂的规则。数学家把这种方法叫做“形式系
统”或“演算”。如果愿意,我们可以很快写出一个关于 Tetris(译者注:一种通常被称为俄罗斯方块的游戏)的形式系统。实际上,工作中的
Tetris 实现就是一个形式系统,只是被指定使用了个不常见的表现形式。
人马座的那个生物文明也许不能理解我们的 Tetris 和圆的范式,因为可能他们唯一的感知输入是气味香橙的橘子。他们也许永远不会发现
Tetris 范式,但很可能会有一个圆的范式。我们也可能将无法阅读它,因为我们的嗅觉没有那么复杂,可是一旦我们理解(pass)了那一范式的表示
形式(通过这种传感器和标准解码技术来理解这种语言),其底层的概念就可被任何智能文明所理解。
有趣的是如果从来没有智能文明存在,Tetris 和圆的范式仍然严密合理,只是没有人注定将会发现他们。如果产生了一种智能文明,他就会发现一些形式
系统来帮助描述宇宙的规律。但他还是不大可能发现 Tetris 因为宇宙中再没有和它相似的事物。在现实世界中这类无用的形式系统或迷题的例子数不胜
数,Tetris 只是其中的一个典型。我们甚至不能确定自然数是否是对客观世界的完整近似,至少我们可以简单的想像一个很大的数它不能用宇宙中任何东
西描述,因为它以近乎无穷。
历史一瞥[3]
再次启动时间机器,这一次的旅行近了很多,我们回到 1930 年代。大萧条正在蹂躏着那个或新或就的时代。空前的经济下挫影响着几乎所有阶层的家庭生
活,只有少数人还能够保持着饥谨危机前的安逸。一些人就如此幸运地位列其中,我们关心的是普林斯顿大学的数学家们。
采用了歌特式风格设计建造的新办公室给普林斯顿罩上天堂般的幸福光环,来自世界各地的逻辑学家被邀请到普林斯顿建设一个新的学部。虽然彼时的美国民众已
难能弄到一餐的面包,普林斯顿的条件则是可以在高高的穹顶下,精致雕凿的木质墙饰边上整日的品茶讨论或款款慢步于楼外的林荫之中。
阿隆左·丘奇就是一个在这种近于奢侈的环境中生活着的数学家。他在普林斯顿获得本科学位后被邀留在研究生院继续攻读。阿隆左认为那里的建筑实属浮华,所
以他很少一边喝茶一边与人讨论数学,他也不喜欢到林中散步。阿隆左是一个孤独者:因为只有一个人时他才能以最高的效率工作。虽然如此,他仍与一些普林斯
顿人保持的定期的联系,其中包括阿兰·图灵,约翰·冯·诺依曼,和 kurt Grodel。
这四个人都对形式系统很感兴趣,而不太留意现实世界,以便致力于解决抽象的数学难题。他们的难题有些共同之处:都是探索关于计算的问题。如果我们有了无
限计算能力的机器,哪些问题可以被解决?我们可以使他们自动地得以解决吗?是否还是有些问题无法解决,为什么?不同设计的各种机器是否具有相同的计算能
力?
通过和其它人的合作,阿隆左·丘奇提出了一个被称为 lambda 演算的形式系统。这个系统本质上是一种虚拟的机器的编程语言,他的基础是一些以函数
为参数和返回值的函数。函数用希腊字母 lambda 标识,这个形式系统因此得名[4]。利用这一形式系统,阿隆左就可以对上述诸多问题推理并给出结
论性的答案。
独立于阿隆左,阿兰·图灵也在进行着相似的工作,他提出了一个不同的形式系统(现在被称为图灵机),并使用这一系统独立得给出了和阿隆左相似的结论。后
来被证明图灵机和 lambda 演算能力等同。
我们的故事本可以到此结束,我会就此歇笔,而你也将浏览到下一个页面,如果第二次世界大战没有在那时打响。整个世界笼罩在战争的火光和硝烟之中,美国陆
军和海军前所未有的大量使用炮弹,为了改进炮弹的精确度,部队组织了大批的科学家持续地计算微分方程以解出弹道发射轨迹。渐渐意识到这个任务用人力手工
完成太耗精力后,人们开始着手开发各种设备来攻克这个难关。第一个解出了弹道轨迹的机器是 IBM 制造的 Mark I —— 它重达5吨,有75万
个组件,每秒可以完成三次操作。
竞争当然没有就此结束,1949年,EDVAC(Electronic Discrete Variable Automatic Computer,
爱达瓦克)被推出并获得了极大的成功。这是对冯·诺依曼架构的第一个实践实例,实际上也是图灵机的第一个现实实现。那一年好运与阿隆左 ·丘奇无缘。
直到1950年代将尽,一位 MIT 的教授John McCarthy(也是普林斯顿毕业生)对阿隆左·丘奇的工作产生了兴趣。1958年,他公开了
表处理语言 Lisp。Lisp 是对阿隆左·丘奇的 lambda 演算的实现但同时它工作在冯·诺依曼计算机上!很多计算机科学家认识到了
Lisp 的表达能力。1973年,MIT人工智能实验室的一组程序员开发了被称为Lisp机器的硬件-阿隆左 lambda 演算的硬件实现!
函数式编程
函数式编程是对阿隆左·丘奇理论的实践应用。但也并非全部 lambda 演算都被应用到了实践中,因为 lambda 演算不是被设计为在物理局限下
工作的。因此,象面向对象的编程一样,函数式编程是一系列理念,而不是严格的教条。现在有很多种函数式编程语言,他们中的大多数以不同方式完成不同任
务。在本文中我将就最广泛使用的源自函数式编程的思想作一解释,并将用Java语言举例。(的确,你可以用Java写出函数式的程序如果你有显著的受虐
倾向)。在下面的小节中,我将会把Java作为一种函数式语言,并对其稍加修改使它成为一种可用的函数式语言。现在开始吧。
lambda 演算被设计用来探询关于计算的问题,所以函数式编程主要处理计算,并惊人地用函数来完成这一过程。函数是函数式编程的基本单位,函数几乎
被用于一切,包括最简单的计算,甚至变量都由计算取代。在函数式编程中,变量只是表达式的别名(这样我们就不必把所有东西打在一行里)。变量是不能更改
的,所有变量只能被赋值一次。用 Java 的术语来说,这意味着所有单一变量都被声明为 final(或 C++ 的 const)。在函数式编程中
没有非 final 的变量。
final int i = 5;
final int j = i + 3;
因为函数式编程中所有变量都是 final 的,所以可以提出这样两个有趣的表述:没有必要总是写出关键字 final,没有必要把变量再称为变量。那
么现在我们对Java作出两个修改:在我们的函数式 Java 中所有变量默认都是 final的,我们将变量(variable)称为符号
(symbol)。
就此你也许会质疑,用我们新创造的语言还能写出有些复杂度的程序吗?如果每个符号都是不可变更(non-mutalbe)的,那么就无法改变任何状态!
其实事实并非完全如此。在阿隆左研究其 lambda 演算时,他并不想将某个状态维护一段时间以期未来对其进行修改。他关注的是对数据的操作(也通常
被称为”演算体 caculating stuff”)。既然已被证明lambda演算与图灵机等价,它可以完成所有命令式编程语言能够完成的任务。那
么,我们怎么才能做到呢?
答案是函数式程序能保存状态,只是它并非通过变量而是使用函数来保存状态。状态保存在函数的参数中,保存在堆栈上。如果你要保存某个状态一段时间并时不
时地对其进行一些修改,可以写个递归函数。举个例子,我们写个函数来翻转 Java 的字符串。记住,我们声明的每个变量默认都是 final 的。
[5]
String reverse(String arg) {
if(arg.length == 0) {
return arg;
}
else {
return reverse(arg.substring(1, arg.length)) + arg.substring(0,1);
}}
这个函数很慢因为它不断地调用自己[6],它还也是个嗜内存魔因为要持续分配对象。不过它的确是在用函数式风格。你可能会问,怎么有人会这样写程序?好
的,我这就慢慢讲来:
函数式编程的优点
你可能会认为我根本无法对上面那个畸形的函数给出个合理的解释。我开始学习函数式编程时就是这么认为的。不过我是错了。有很好的理由使用这种风格,当然
其中一些属主观因素。例如,函数式程序被认为更容易阅读。因为每个街区的孩子都知道,是否容易理解在旁观者的眼中,所以我将略去这些主观方面的理由。幸
运的是,还有很多的客观理由。
单元测试
因为函数式编程的每一个符号都是 final 的,没有函数产生过副作用。因为从未在某个地方修改过值,也没有函数修改过在其作用域之外的量并被其他函
数使用(如类成员或全局变量)。这意味着函数求值的结果只是其返回值,而惟一影响其返回值的就是函数的参数。
这是单元测试者的梦中仙境(wet dream)。对被测试程序中的每个函数,你只需在意其参数,而不必考虑函数调用顺序,不用谨慎地设置外部状态。所
有要做的就是传递代表了边际情况的参数。如果程序中的每个函数都通过了单元测试,你就对这个软件的质量有了相当的自信。而命令式编程就不能这样乐观了,
在 Java 或 C++ 中只检查函数的返回值还不够——我们还必须验证这个函数可能修改了的外部状态。
调试
如果一个函数式程序不如你期望地运行,调试也是轻而易举。因为函数式程序的 bug 不依赖于执行前与其无关的代码路径,你遇到的问题就总是可以再现。
在命令式程序中,bug 时隐时现,因为在那里函数的功能依赖与其他函数的副作用,你可能会在和 bug 的产生无关的方向探寻很久,毫无收获。函数式
程序就不是这样——如果一个函数的结果是错误的,那么无论之前你还执行过什么,这个函数总是返回相同的错误结果。
一旦你将那个问题再现出来,寻其根源将毫不费力,甚至会让你开心。中断那个程序的执行然后检查堆栈,和命令式编程一样,栈里每一次函数调用的参数都呈现
在你眼前。但是在命令式程序中只有这些参数还不够,函数还依赖于成员变量,全局变量和类的状态(这反过来也依赖着这许多情况)。函数式程序里函数只依赖
于它的参数,而那些信息就在你注视的目光下!还有,在命令式程序里,只检查一个函数的返回值不能够让你确信这个函数已经正常工作了,你还要去查看那个函
数作用域外数十个对象的状态来确认。对函数式程序,你要做的所有事就是查看其返回值!
沿着堆栈检查函数的参数和返回值,只要发现一个不尽合理的结果就进入那个函数然后一步步跟踪下去,重复这一个过程,直到它让你发现了 bug 的生成
点。
并行
函数式程序无需任何修改即可并行执行。不用担心死锁和临界区,因为你从未用锁!函数式程序里没有任何数据被同一线程修改两次,更不用说两个不同的线程
了。这意味着可以不假思索地简单增加线程而不会引发折磨着并行应用程序的传统问题。
事实既然如此,为什么并不是所有人都在需要高度并行作业的应用中采用函数式程序?嗯,他们正在这样做。爱立信公司设计了一种叫作 Erlang 的函数
式语言并将它使用在需要极高抗错性和可扩展性的电信交换机上。还有很多人也发现了 Erlang 的优势并开始使用它。我们谈论的是电信通信控制系统,
这与设计华尔街的典型系统相比对可靠性和可升级性要求高了得多。实际上,Erlang 系统并不可靠和易扩展,Java 才是。Erlang 系统只是
坚如磐石。
关于并行的故事还没有就此停止,即使你的程序本身就是单线程的,那么函数式程序的编译器仍然可以优化它使其运行于多个CPU上。请看下面这段代码:
String s1 = somewhatLongOperation1();
String s2 = somewhatLongOperation2();
String s3 = concatenate(s1, s2);
在函数编程语言中,编译器会分析代码,辨认出潜在耗时的创建字符串s1和s2的函数,然后并行地运行它们。这在命令式语言中是不可能的,因为在那里,每
个函数都有可能修改了函数作用域以外的状态并且其后续的函数又会依赖这些修改。在函数式语言里,自动分析函数并找出适合并行执行的候选函数简单的像自动
进行的函数内联化!在这个意义上,函数式风格的程序是“不会过时的技术(future proof)”(即使不喜欢用行业术语,但这回要破例一次)。硬
件厂商已经无法让CPU运行得更快了,于是他们增加了处理器核心的速度并因并行而获得了四倍的速度提升。当然他们也顺便忘记提及我们的多花的钱只是用在
了解决平行问题的软件上了。一小部分的命令式软件和 100% 的函数式软件都可以直接并行运行于这些机器上。
代码热部署
过去要在 Windows上安装更新,重启计算机是难免的,而且还不只一次,即使是安装了一个新版的媒体播放器。Windows XP 大大改进了这一
状态,但仍不理想(我今天工作时运行了Windows Update,现在一个烦人的图标总是显示在托盘里除非我重启一次机器)。Unix系统一直以来
以更好的模式运行,安装更新时只需停止系统相关的组件,而不是整个操作系统。即使如此,对一个大规模的服务器应用这还是不能令人满意的。电信系统必须
100%的时间运行,因为如果在系统更新时紧急拨号失效,就可能造成生命的损失。华尔街的公司也没有理由必须在周末停止服务以安装更新。
理想的情况是完全不停止系统任何组件来更新相关的代码。在命令式的世界里这是不可能的。考虑运行时上载一个Java类并重载一个新的定义,那么所有这个
类的实例都将不可用,因为它们被保存的状态丢失了。我们可以着手写些繁琐的版本控制代码来解决这个问题,然后将这个类的所有实例序列化,再销毁这些实
例,继而用这个类新的定义来重新创建这些实例,然后载入先前被序列化的数据并希望载入代码可以恰到地将这些数据移植到新的实例。在此之上,每次更新都要
重新手动编写这些用来移植的代码,而且要相当谨慎地防止破坏对象间的相互关系。理论简单,但实践可不容易。
对函数式的程序,所有的状态即传递给函数的参数都被保存在了堆栈上,这使的热部署轻而易举!实际上,所有我们需要做的就是对工作中的代码和新版本的代码
做一个差异比较,然后部署新代码。其他的工作将由一个语言工具自动完成!如果你认为这是个科幻故事,请再思考一下。多年来 Erlang工程师一直更新
着他们的运转着的系统,而无需中断它。
机器辅助的推理和优化
函数式语言的一个有趣的属性就是他们可以用数学方式推理。因为一种函数式语言只是一个形式系统的实现,所有在纸上完成的运算都可以应用于用这种语言书写
的程序。编译器可以用数学理论将转换一段代码转换为等价的但却更高效的代码[7]。多年来关系数据库一直在进行着这类优化。没有理由不能把这一技术应用
到常规软件上。
另外,还能使用这些技术来证明部分程序的正确,甚至可能创建工具来分析代码并为单元测试自动生成边界用例!对稳固的系统这种功能没有价值,但如果你要设
计心房脉冲产生器 (pace maker)或空中交通控制系统,这种工具就不可或缺。如果你编写的应用程序不是产业的核心任务,这类工具也是你强于竞
争对手的杀手锏。
高阶函数
我记得自己在了解了上面列出的种种优点后曾想:“那都是非常好的特性,可是如果我不得不用天生就不健全的语言编程,把一切变量声明为
final 产生的代码将是垃圾一堆。” 这其实是误解。在如Java 这般的命令式语言环境里,将所有变量声明为 final 没有用,但是在函数式
语言里不是这样。函数式语言提供了不同的抽象工具它会使你忘记你曾经习惯于修改变量。高阶函数就是这样一种工具。
函数式语言中的函数不同于 Java 或 C 中的函数,而是一个超集——它有着 Java 函数拥有的所有功能,但还有更多。创建函数的方式和 C
中相似:
int add(int i, int j) {
return i + j;
}
这意味着有些东西和同样的 C 代码有区别。现在扩展我们的 Java 编译器使其支持这种记法。当我们输入上述代码后编译器会把它转换成下面的
Java代码(别忘了,所有东西都是 final 的):
class add_function_t {
int add(int i, int j) {
return i + j;
}
}
add_function_t add = new add_function_t();
这里的符号 add 并不是一个函数。这是一个有一个成员函数的很小的类。我们现在可以把 add 作为函数参数放入我们的代码中。还可以把它赋给另一
个符号。我们在运行时创建的 add_function_t 的实例如果不再被使用就将会被垃圾回收掉。这些使得函数成为第一级的对象无异于整数或字符
串。(作为参数)操作函数的函数被称为高阶函数。别让这个术语吓着你,这和 Java 的 class 操作其它 class(把它们作为参数)没有什
么区别。我们本可以把它们称为“高阶类”但没有人注意到这个,因为 Java 背后没有一个强大的学术社区。
那么怎样,何时应该使用高阶函数呢?我很高兴你这样问。如果你不曾考虑类的层次,就可能写出了一整团堆砌的代码块。当你发现其中一些行的代码重复出现,
就把他们提取成函数(幸运的是这些依然可以在学校里学到)。如果你发现在那个函数里一些逻辑动作根据情况有变,就把他提取成高阶函数。糊涂了?下面是一
个来自我工作的实例:假如我的一些 Java 代码接受一条信息,用多种方式处理它然后转发到其他服务器。
class MessageHandler {
void handleMessage(Message msg) {
// …
msg.setClientCode(”ABCD_123″);
// …
sendMessage(msg);
}
// …
}
现在假设要更改这个系统,现在我们要把信息转发到两个服务器而不是一个。除了客户端的代码一切都像刚才一样——第二个服务器希望这是另一种格式。怎么处
理这种情况?我们可以检查信息的目的地并相应修改客户端代码的格式,如下:
class MessageHandler {
void handleMessage(Message msg) {
// …
if(msg.getDestination().equals(”server1″) {
msg.setClientCode(”ABCD_123″);
} else {
msg.setClientCode(”123_ABC”);
}
// …
sendMessage(msg);
}
// …
}
然而这不是可扩展的方法,如果加入了更多的服务器,这个函数将线性增长,更新它会成为我的梦魇。面向对象的方法是把MessageHandler作为基
类,在导出类中专业化客户代码操作:
abstract class MessageHandler {
void handleMessage(Message msg) {
// …
msg.setClientCode(getClientCode());
// …
sendMessage(msg);
}
abstract String getClientCode();
// …
}
class MessageHandlerOne extends MessageHandler {
String getClientCode() {
return “ABCD_123″;
}
}
class MessageHandlerTwo extends MessageHandler {
String getClientCode() {
return “123_ABCD”;
}
}
现在就可以对每一个服务器实例化一个适合的类。添加服务器的操作变得容易维护了。但对于这么一个简单的修改仍然要添加大量的代码。为了支持不同的客户代
码我们创建了两个新的类型!现在我们用高阶函数完成同样的功能:
class MessageHandler {
void handleMessage(Message msg, Function getClientCode) {
// …
Message msg1 = msg.setClientCode(getClientCode());
// …
sendMessage(msg1);
}
// …
}
String getClientCodeOne() {
return “ABCD_123″;
}
String getClientCodeTwo() {
return “123_ABCD”;
}
MessageHandler handler = new MessageHandler();
handler.handleMessage(someMsg, getClientCodeOne);
没有创建新的类型和新的class层次,只是传入合适的函数作为参数,完成了面向对象方式同样的功能,同时还有一些额外的优点。没有使自己囿于类的层次
之中:可以在运行时传入函数并在任何时候以更高的粒度更少的代码修改他们。编译器高效地为我们生成了面向对象的“粘合”代码!除此之外,我们还获得了所
有函数式编程的其他好处。当然函数式语言提供的抽象不只这些,高阶函数只是一个开始:
currying
我认识的大多数人都读过“四人帮”的那本设计模式,任何自重的程序员都会告诉你那本书是语言中立的(agnostic),模式在软件工程中是通用的,和
使用的语言无关。这个说法颇为高贵,故而不幸的是,有违现实。
函数式编程极具表达能力。在函数式语言中,语言既已达此高度,设计模式就不再是必需,最终你将设计模式彻底消除而以概念编程。适配器
(Adapter)模式就是这样的一个例子。(究竟适配器和 Facade 模式区别在哪里?可能有些人需要在这里再多费些篇章)。一旦语言有了叫作
currying 的技术,这一模式就可以被消除。
currying.
适配器模式最有名的是被应用在 Java 的“默认”抽象单元——class 上。在函数式编程里,模式被应用到函数。模式带有一个接口并将它转换成另
一个对他人有用的接口。这有一个适配器模式的例子:
int pow(int i, int j);
int square(int i)
{
return pow(i, 2);
}
上面的代码把一个整数幂运算接口转换成为了一个平方接口。在学术文章里,这个雕虫小技被叫作currying(得名于逻辑学家Haskell
Curry,他曾将相关的数学理论形式化 )。因为在函数式编程中函数(反之如class)被作为参数来回传递,currying 很频繁地被用来把函
数调整为更适宜的接口。因为函数的接口是他的参数,使用 currying 可以减少参数的数目(如上例所示)。
函数式语言内建了这一技术。不用手动地创建一个包装了原函数的函数,函数式语言可以为你代劳。同样地,扩展我们的语言,让他支持这个技术:
square = int pow(int i, 2);
这将为我们自动创建出一个有一个参数的函数 square。他把第二个参数设置为 2 再调用函数 pow。这行代码会被编译为如下的 Java 代
码:
class square_function_t {
int square(int i) {
return pow(i, 2);
}
}
square_function_t square = new square_function_t();
正如你所见,通过简单地创建一个对原函数的包装,在函数式编程中,这就是 currying —— 快速简易创建包装的捷径。把精力集中在你的业务上,
让编译器为你写出必要的代码!什么时候使用 currying?这很简单,任何时候你想要使用适配器模式(包装)时。
惰性求值
惰性(或延迟)求值这一技术可能会变得非常有趣一旦我们采纳了函数式哲学。在讨论并行时已经见过下面的代码片断:
String s1 = somewhatLongOperation1();
String s2 = somewhatLongOperation2();
String s3 = concatenate(s1, s2);
在一个命令式语言中求值顺序是确定的,因为每个函数都有可能会变更或依赖于外部状态,所以就必须有序的执行这些函数:首先是
somewhatLongOperation1,然后 somewhatLongOperation2,最后 concatenate,在函数式语言里
就不尽然了。
前面提到只要确保没有函数修改或依赖于全局变量,somewhatLongOperation1 和 somewhatLongOperation2
可以被并行执行。但是如果我们不想同时运行这两个函数,还有必要保证有序的执行他们呢?答案是不。我们只在其他函数依赖于s1和s2时才需要执行这两个
函数。我们甚至在concatenate调用之前都不必执行他们——可以把他们的求值延迟到concatenate函数内实际用到他们的位置。如果用一
个带有条件分支的函数替换concatenate并且只用了两个参数中的一个,另一个参数就永远没有必要被求值。在 Haskell 语言中,不确保一
切都(完全)按顺序执行,因为 Haskell 只在必要时才会对其求值。
惰性求值优点众多,但缺点也不少。我们会在这里讨论它的优点而在下一节中解释其缺点。
优化
惰性求值有客观的优化潜力。惰性编译器看函数式代码就像数学家面对的代数表达式————可以注销一部分而完全不去运行它,重新调整代码段以求更高的效
率,甚至重整代码以降低出错,所有确定性优化(guaranteeing optimizations)不会破坏代码。这是严格用形式原语描述程序的巨
大优势————代码固守着数学定律并可以数学的方式进行推理。
抽象控制结构
惰性求值提供了更高一级的抽象,它使得不可能的事情得以实现。例如,考虑实现如下的控制结构:
unless(stock.isEuropean()) {
sendToSEC(stock);
}
我们希望只在祖先不是欧洲人时才执行sendToSEC。如何实现 unless?如果没有惰性求值,我们需要某种形式的宏(macro)系统,但
Haskell 这样的语言不需要它。把他实现为一个函数即可:
void unless(boolean condition, List code) {
if(!condition)
code;
}
注意如果条件为真代码将不被执行。我们不能在一个严格(strict)的语言中再现这种求值,因为 unless 调用之前会先对参数进行求值。
无穷(infinite)数据结构
惰性求值允许定义无穷数据结构,对严格语言来说实现这个要复杂的多。考虑一个 Fibonacci 数列,显然我们无法在有限的时间内计算出或在有限的
内存里保存一个无穷列表。在严格语言如 Java 中,只能定义一个能返回 Fibonacci 数列中特定成员的 Fibonacci 函数,在
Haskell
中,我们对其进一步抽象并定义一个关于 Fibonacci 数的无穷列表,因为作为一个惰性的语言,只有列表中实际被用到的部分才会被求值。这使得可
以抽象出很多问题并从一个更高的层次重新审视他们。(例如,我们可以在一个无穷列表上使用表处理函数)。
缺点
当然从来不存在免费的午餐。惰性求值有很多的缺点,主要就在于,懒。有很多现实世界的问题需要严格求值。例如考虑下例:
System.out.println(”Please enter your name: “);
System.in.readLine();
在惰性求值的语言里,不能保证第一行会在第二行之前执行!那么我们就不能进行输入输出操作,不能有意义地使用本地(native)接口(因为他们相互依
赖其副作用必须被有序的调用),从而与整个世界隔离。如果引入允许特定执行顺序的原语又将失去数学地推理代码的诸多好处(为此将葬送函数式编程与其相关
的所有优点)。幸运的是,并非丧失了一切,数学家为此探索并开发出了许多技巧来保证在一定函数设置下(function setting)代码以一特定
的顺序执行。这样我们就赢得了两个世界。这些技术包括 continuation, monad 和 uniqueness typing
(一致型别)。我只会在本文中解释continuation,把 monad 和 uniqueness typing 留到将来的文章中。有趣的是,
除了确保函数求值顺序, continuation 在很多别的情况下也很有用。这点等一会儿就会提到。
Continuations
Continuations 对于程序设计的意义,就像《达芬奇密码》对人类历史的意义:即对人类最大秘密的惊人揭示。也许不是,但他在概念上的突破性
至少和揭示了负数的平方根意义等同。
我们在学习函数时,只是学到了一半的事实,因为我们基于一个错误的假定:函数只能将结果返回到它的调用函数。在这个意思上continuation 是
广义的函数。函数不必要返回到其调用函数而可以返回到程序的任何地方。我们把”continuation” 作为参数传给一个函数,它指定了这个函数返
回的位置。这个描述可能听起来更加复杂。看一下下面的代码:
int i = add(5, 10);
int j = square(i);
函数 add 在其被调用的位置将结果 15 赋给了 i,接下来 i 的值被用来调用 square。注意所有的惰性求值编译器都不能调整这几行代码
因为第二行依赖着第一行的成功求值。下面用 continuation 风格又称 CPS (Continuation Programming
Style) 来重写这段代码,这里函数 add 会将结果返回到 square 而不是原来的调用函数。
int j = add(5, 10, square);
这个例子中 add 有了另一个参数 —— 一个 add 必须在它求值结束时用其返回值调用的函数。这里 square 是 add 的一个
continuation。这两种情况下,j 都将等于 255。
这就是强制使惰性语言有序地求值两个表达式的第一个技巧。考虑下面这个(熟悉的)IO代码:
System.out.println(”Please enter your name: “);
System.in.readLine();
这两行不相依赖所以编译器会自由的重新调整他们的执行顺序。然而,如果我们用 CPS 来重写这段代码,就会有一个依赖,编译器会因此而强制对这两行代
码有序执行!
System.out.println(”Please enter your name: “,
System.in.readLine);
这里 println 需要用自己的返回结果作为参数去调用 readLine 并将 readLine 返回值作为自己的返回值。这样就能确保这两行
被有序执行而且 readLine 一定被执行(因为整个计算期望最后的结果为结果)。Java 的 println 返回 void 但如果它返回的
是一个抽象值(readLine所期待的),我们就解决了这个问题!当然这样的链接函数调用很快就会使代码难以读懂,不过这个可以避免。比如我们可以给
语言添加些语法甜点(syntactic sugar)就可以简单的按顺序输入表达式,然后由编译器自动为我们链接这些函数调用。这样就可以如愿地使用
期望的求值顺序并保留一切函数式编程的好处(包括数学地对我们程序进行推理的能力)!如果还是有迷惑,记住函数是只有一个成员的类的实例。重写上述代码
使得 println 和 readLine 成为类的实例,这样就对一切都清楚了。
如果我在此结束本节,那将仅仅涉及到 continuation 最浅显的应用。用 CPS 重写整个程序,那里所有的函数都增加一个额外的
continuation 参数并把函数结果传给它。也可以通过简单地把函数当作 continuation 函数(总是返回到调用者的函数)的特殊实
例来将程序转为 CPS 风格。这种转换很容易被自动化(事实上,许多编译器就是这么做的)。
一旦我们将一个程序转为了CPS,那么很明显每个指令都将有些 continuation, 这是一个该指令在执行结束时会用其执行结果调用的函数,通
常的程序中,这是一个它要返回的地址。从上面的例子中随便举个例子,比如 add(5, 10)。在用CPS风格写的程序里,add 的
continuation很明显——这是一个 add 在其执行结束时会调用的函数。那么如果在非CPS的程序里,它是什么呢?当然我们可以把程序转
为 CPS ,但有这个必要吗?
其实没有必要。仔细看一下我们的 CPS 转换过程。如果尝试为它写一个编译器,然后经过长期的思考后,你意识到这个 CPS 的版本根本不需要栈!没
有函数会以传统的意义“返回”,它只是用结果调用了另一个函数。我们无需在调用时将函数参数压栈再于调用结束时弹出栈,而只是简单的把他们保存在一大块
内存中,然后使用跳转指令。不再需要原来的参数——他们不会再次被用到,因为没有函数会返回!
所以,用 CPS 风格写成的程序没有堆栈,但每个函数却有一个额外的参数可被调用。不是 CPS 风格的程序没有可以被调用的这个参数,但却有栈。栈
中存放着什么?只是参数和一个指向函数返回地址的指针。你看到光了吗?栈中只是放着 continuation 的信息! 栈中指向返回指令的指针本质
上和 CPS 程序里将被调用的函数是等价的。如果你想探究 add(5,10) 的 continuation,只要简单地检查它在堆栈的执行点!
这的确很简单。continuation 和栈上指向返回地址的指针是等价的,只是 continuation 是被显式传递,所以不必和函数被调用点
是同一位置。如果还记得 continuation 就是一个函数,并且在我们的语言里,函数被编译为一个类的实例,你就会理解指向栈中返回指令的指针
实际就是传递给 continuation 的参数,因为我们的函数(就像一个类的实例)只是一个指针。这意味着给定程序中任意时间和任意位置,你都可
以去请求一个当前的 continuation (current continuation)(它就是当前的栈的信息)。
好的,这样我们就知道了什么是 current continuation。他有什么意义?一旦我们得到了当前的 continuation 并将它保
存在某处,我们就最终将程序当前的状态保存了下来——及时地冷冻下来。这就像操作系统将其置为休眠状态。一个 continuation 对象里保存了
在我们获得它的地方重新启动程序的必要信息。操作系统在每次发生线程间的上下文切换时也是如此。唯一的区别是它保留着全部控制。请求一个
continuation 对象(在Scheme里,可以调用 call-with-current-continuation 函数)后,你就会获得
一个包括了当前 continuation
的对象——堆栈(或者在CPS情况下则是下一个要调用的函数)。可以把这个对象保存在一个变量(或者是磁盘)里。当你用这 continuation
“重启”程序时,就会转回到处你取得这个对象的那个状态。这就象切换回一个被挂起的线程或唤醒休眠着的操作系统,区别是用 continuation,
你可以多次地重复这一过程。当操作系统被唤醒时,休眠信息就被销毁了。但如果那些信息没有被销毁,你也就可以一次次地将它唤醒到同一点,就象重返过去一
样。有了 continuation 你就有了这个控制力!
Continuation 应该在什么情况下使用呢?通常在尝试模拟一个本质上是无状态的应用时可以简化你的任务。Continuation 很适合在
Web应用程序中使用。微软公司的 ASP.NET 技术极尽苦心地模拟状态以便你在开发 Web 应用时少费周折。可如果 C# 支持了
continuation,ASP.NET 的复杂度就可以减半——你只需要保存一个 continuation,当用户下次发出 web 请求时重启
它即可。对程序员来说,web 应用程序将不再有中断——程序只是简单的从下一行重启!利用 continuation 这一抽象解决问题真是令人难以
置信的便利。考虑到越来越多的胖客户端应用程序正在向服务器端转移,将来 continuation 也会变得越来越重要。
模式匹配
模式匹配不是什么新的创新的特性。事实上,它和函数式编程的关系不大。把产生模式匹配归因于函数式编程的唯一的原因是函数式语言一度提供了模式匹配,然
而现在的命令式语言还做不到。
让我们用一个例子深入了解一下模式匹配。这是一个Java的Fibonacci函数:
int fib(int n) {
if(n == 0) return 1;
if(n == 1) return 1;
return fib(n - 2) + fib(n - 1);
}
让我们从Java衍生出的语言来支持模式匹配:
int fib(0) {
return 1;
}
int fib(1) {
return 1;
}
int fib(int n) {
return fib(n - 2) + fib(n - 1);
}
两者有什么区别?编译器为我们实现了分支。这有什么大不了?的确没什么。有人注意到很多函数包括了复杂的 swith 语句(尤其是在函数式程序中)所
以认为这种抽象形式很好。我们把一个函数定义分离成多个,然后把模式置于参数中(有点象重载)。当这个函数被调用时,编译器使其比较参数和其运行时的定
义然后选择其中正确的一个。这一般是通过选择可选的最特定的定义来完成。例如,int fib(int n) 可以以 n 等于 1 被调用,但是实际
上 fib(n) 没有被调用,因为 fib(1) 更加特定。
模式匹配通常要比我这个例子复杂,比如,高级模式匹配系统可以让我们这样做:
int f(int n < 10) { ... }
int f(int n) { ... }
模式匹配什么时候适用?情况太多了!每当你有一个嵌套着 if 的复杂的数据结构,这时就可以用模式匹配以更少的代码完成得更好。一个很好的例子闪现在
我脑海,这就是所有 Win32 平台都提供了的标准的 WinProc 函数(即使它通常被抽象了)。通常模式匹配系统能检测集合也可以应付简单的
值。例如,当传给函数一个数组后,就可以找出所有首元素为 1 第三个元素大于 3 的所有数组。
模式匹配还有一个好处即如果需要增加或修改条件,那么不必对付一个巨大的函数。只需增加或修改适合的定义即可。这消除了“四人帮”(GoF)书中的一大
类设计模式。条件越复杂,模式匹配就越有用。一旦习惯了它,你就会担心没有了模式匹配的日子如何打发。
Closures
到此我们已经讨论了纯的函数式语言——实现了lambda演算又不包括与丘奇形式系统矛盾的语言——环境里的特性,可是还有很多在lambda演算框架
之外的函数语言的有用特征。虽然一个公理系统的实现可以让我们象数学表达式那样思考程序但它未必是实际可行的。许多语言选择去合并一些函数式的元素而没
有严格的坚持函数式的教条。很多象这样的语言(如Common Lisp)不要求变量是 final 的——可以即处对其修改。他们还不要求函数只依赖
于其参数——允许函数访问外部状态。但这些语言也的确包含着函数式的特征——如高阶函数,在非纯粹的函数式语言里传递函数作为参数和限制在
lambda 演算系统中的作法有些不同,它需要一种常被称为词法(lexical)closure 的有趣特性。下面我给出几个例子。记住,这里变量
不再是final的,函数可以引用其作用域外的变量:
Function makePowerFn(int power) {
int powerFn(int base) {
return pow(base, power);
}
return powerFn;
}
Function square = makePowerFn(2);
square(3); // returns 9
函数 make-power-fn 返回了一个函数,它有一个参数,并对这个参数进行一定阶的幂运算。如果对 square(3) 求值会有什么结果?
变量 power 不在 powerFn 的作用域中,因为 makePowerFn 已经返回它的栈桢而不复存在。那么square如何工作?一定是
这个语言以某种方式将power的值保存了起来以便 square 使用。如果我们再新建一个函数cube,用来计算参数的立方又会怎样?运行环境必须
存储两个power的拷贝,每个我们用 make-power-fn 生成的函数都用一个拷贝。保存这些值的现象就被称为 closure。
closure 不只保存宿主函数的参数。例如,closure可能会是这样:
Function makeIncrementer() {
int n = 0;
int increment() {
return ++n;
}
}
Function inc1 = makeIncrementer();
Function inc2 = makeIncrementer();
inc1(); // returns 1;
inc1(); // returns 2;
inc1(); // returns 3;
inc2(); // returns 1;
inc2(); // returns 2;
inc2(); // returns 3;
运行时已保存了n,所以递增器可以访问它,而且运行时为每个递增器都保存了一个 n 的拷贝,即使这些拷贝本应在 makeIncrementer
返回时消失。这些代码被如何编译?closure 在底层是如何工作的?很幸运,我们可以去幕后看看。
一点常识会很有帮助,首先会注意到的是局部变量的生命期不再由简单的作用域限定而是不确定的。那么显然可以由此得出结论它们不再被保存在栈上——反之必
须被保存在堆上[8]。这样一来,closure 的实现就象我们前面讨论的函数一样了,只是它还有一个指向周围变量的引用。
class some_function_t {
SymbolTable parentScope;
// …
}
当一个 closure 引用了一个不在其作用域的变量时,它会在其祖先作用域中查找这个引用。就是这样!Closure 将函数式和面向对象的世界紧
密结合。当你创建了一个包含了一些状态的类并把它传到别处时,考虑一下 closure。Closure 就是这样在取出作用域中的变量的同时创建“成
员变量”,所以你不必亲自去做这些!
下一步的计划?
关于函数式编程,本文作了浅显地讨论。有时候一次粗浅的射猎可能会进展为重大的收获与我也受益匪浅。将来我还计划写写 category 理
论,monad,函数式数据结构,函数式语言中的类型(type)体系,函数式并发,函数式数据库等等还有很多。如果我得以(在学习的过程中)写出了上
述诸多主题中的一半,我的生命就会完整了。还有,Google 是我们的朋友。
评论?
如果你有任何问题,意见或建议,请发到邮箱 coffee…@gmail.com。很高兴收到你的反馈
===========================
[1] 我在2005年找工作时常常提出这个问题,当时我得到的是数量可观的一脸茫然。想像一下,这些人至少每人会得到30万美元,如果他们理解了他们
可以得到的大部分工具。
[2] 这像是个悖论。物理学家和数学家被迫确认他们还不完全清楚是否宇宙万物遵循着可以被数学描述的规则。
[3] 我一直厌恶提供了一堆枯燥的日期,人名和地点的纪年式历史课。对我而言,历史是改变了这个世界的人的生活,是他们行为之后的个人动机,是他们得
以影响亿万生灵的体制。所以这个关于历史的小节注定无法完整,只讨论了于此关系及其密切的人物与事件。
[4] 我在学习函数式编程的时候,很不喜欢术语 lambda,因为我没有真正理解它的意义。在这个环境里,lambda 是一个函数,那个希腊字母
只是方便书写的数学记法。每当你听到 lambda 时,只要在脑中把它翻译成函数即可。
[5] 有趣的是 Java 的字符串是不可变更的,探讨这一离经叛道的设计的原因也非常有趣,不过在这里会分散我们对原目标的注意力
[6] 大多数函数式编程语言的编译器能通过将递归尽可能转为迭代来进行优化,这被称为尾递归。
[7] 相反未必成立,虽然有时可以证明两端代码等价,但这不是所有情况下都成立。
[8] 这实际上不比存储在栈上慢,因为一旦引入了垃圾回收器,内存分配就成为了一个O(1)的操作。
Tags: No Tags
Filed under: 科学, IT相关 — indigo @ 9:56 pm +356Key +Del.icio.us

Lamda演算简介

Wikipedia(维基百科全书)中关于lambda演算的解释如下:

The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. It was introduced by Alonzo Church and Stephen Cole Kleene in the 1930s; Church used the lambda calculus in 1936 to give a negative answer to the Entscheidungsproblem. The calculus can be used to cleanly define what a computable function is. The question of whether two lambda calculus expressions are equivalent cannot be solved by a general algorithm, and this was the first question, even before the halting problem, for which undecidability could be proved. Lambda calculus has greatly influenced functional programming languages, especially Lisp.

Lambda演算是一个形式系统,它被设计出来用来研究函数定义,函数应用和递归。它是在二十世纪三十年代由Alonzo Church 和 Stephen Cole Kleene发 明的。Church在1936年使用lambda演算来证明了判定问题是没有答案的。Lambda演算可以用来清晰的定义什么是一个可计算的函数。两个 lambda演算表达式是否相等的问题不能够被一个通用的算法解决,这是第一个问题,它甚至排在停机问题之前。为了证明停机问题是没有答案的,不可判定性 能够被证明。Lambda演算对于函数式编程语言(例如lisp)有重大的影响。

同时,数理逻辑中对于lambda演算的介绍就简单得多:

λ-演算可以说是最简单、最小的一个形式系统。它是在二十世纪三十年代由Alonzo Church 和 Stephen Cole Kleene发 明的。至今,在欧洲得到了广泛的发展。可以说,欧洲的计算机科学是从λ-演算开始的,而现在仍然是欧洲计算机科学的基础,首先它是函数式程序理论的基础, 而后,在λ-演算的基础上,发展起来的π-演算、χ-演算,成为近年来的并发程序的理论工具之一,许多经典的并发程序模型就是以π-演算为框架的。

这里不由得想起一位我尊敬的老师的博士毕业论文就是关于π-演算的,可惜这位老师已经去别的学校了。

Lambda演算表达了两个计算机计算中最基本的概念“代入”和“置换”。“代入”我们一般理解为函数调用,或者是用实参代替函数中的形参;“置换”我们 一般理解为变量换名规则。后面会讲到,“代入”就是用lambda演算中的β-归约概念。而“替换”就是lambda演算中的α-变换。

Lambda演算系统的形式化定义

维基百科全书上面的对于lambda演算的定义不是很正规,但是说明性的文字较多。而数理逻辑中的定义很严密,不过没有说明不容易理解。我尽可能把所有资料结合起来说明lambda演算系统的定义。

字母表

lambda演算系统中合法的字符如下:

1. x1,x2,x3,…变元(变元的数量是无穷的,不能在有限步骤内穷举,这个很重要,后面有定理是根据这一点证明的)

2. à 归约

3. = 等价

4. λ,(,) (辅助工具符号,一共有三个,λ和左括号右括号)

所有能够在lambda演算系统中出现的合法符号只有以上四种,其他符号都是非法的。例如λx.x+2,如果没有其他对于+符号的说明,那么这就是一个非法的λ演算表达式。

λ-项

λ-项在一些文章中也称为λ表达式(lambda expression),它是由上面字母表中的合法字符组成的表达式,合法的表达式组成规则如下:

1. 任一个变元是一个项

2. 若M,N是项,则(MN)也是一个项 (function application,函数应用)

3. 若M是一个项,而x是一个变元,则(λx.M)也是一个项 (function abstraction,函数抽象)

4. 仅仅由以上规则归纳定义得到的符号串是项

说明1:λ-项是左结合的,意思就是若f x y都是λ-项,那么f x y=(f x) y

说明2:(λx.M)这样的λ-项被称为函数抽象,原因是它常常就是一个函数的定义,函数的参数就是变量x,函数体就是M,而函数名称则是匿名的。用一个 不恰当的比喻来说,我们通常认为的函数f(x)=x+2,可以被表达为λx.x+2。因为+是未定义的,所以这个比喻只是为了方便理解而已。

说明3:MN这样的λ-项被称为函数应用,原因是它表达了将M这个函数应用到N这个概念。沿用上面的例子f(x)=x+2,那么f(2)=2+2;同样的 λx.x+2表达了f(x)的概念,那么(λx.x+2)2表达了f(2)的概念。其中M=λx.x+2,N=2,所以MN=(λx.x+2)2。

说明4:注意说明3只是为了方便理解,但是还存在很多与直观理解不符合的地方。例如xy也是一个合法的λ-项,它们也是MN形式的,不过x和y都仅仅是一个变量而已,谈不上函数代入。

上面是λ-项的形式化定义,有一些是可以与函数理论直观联系的,而另一些只是说明这个λ-项是合法的,不一定有直观的字面意义。

公式

若M,N是λ-项,则MàN,M=N是公式。

λ-项中的变量自由出现法则

在一个λ-项中,变量要么是自由出现的,要么是被一个λ符号绑定的。还是以函数的方式来理解变量的自由出现和绑定。例如f(x)=xy这个函数,我们知道 x是和函数f相关的,因为它是f的形参,而y则是和f无关的。那么在λx.xy这个λ-项中,x就是被λ绑定的,而y则是自由出现的变量。

直观的理解,被绑定的变量就是作为某个函数形参的变量,而自由变量则是不作为任何函数形参的变量。

Lambda变量绑定规则:

1. 在表达式x中,如果x本身就是一个变量,那么x就是一个单独的自由出现。

2. 在表达式λ x. E中,自由出现就是E中所有的除了x的自由出现。这种情况下在E中所有x的出现都称为被表达式中x前面的那个λ所绑定。

3. 在表达式(MN )中,变量的自由出现就是M和N中所有变量的自由出现。

另一种关于变量的自由出现的规则也许更直接:

1. free(x) = x

2. free(MN) = free(M) free(N)

3. free(lx " M) = free(M) – {x}

为什么要花大力气来给出变量自由出现的规则,是因为后面的很多地方要用到变量的自由出现的概念。例如α-变换和β-归约。

例子:分析λf.λx.fx中变量的自由出现和绑定状况。

λf.λx.fx =λf.E, E=λx.fx

E=λx.A, A=A1A2, A1=f, A2=x

所以在A中f和x都是自由出现的,

所以E中x是绑定λ x

所以整个公式中f是绑定第一个λ f的。

λ x的控制域

来看两个λ-项,λx.xx和λx.(xx)有何不同?根据左结合的法则,λx.xx=(λx.x)x,其中第一个x是被λ绑定的,而第二个x则是自由出现的。而λx.(xx)中两个x都是被λ绑定的。这表明了两个λ-项中λx的控制域是不同的。

我们知道谓词演算中量词也是有控制域的,λx的控制域与它们类似,这里就不给出详细的定义了。其实也很直观。

α-变换(α-conversion)

α-变换规则试图解释这样一个概念,λ演算中约束变量的名称是不重要的,例如λx.x和λy.y是相同的函数。因此,将某个函数中的所有约束变量全部换名是可以的。但是,换名需要遵循一些约束。

首先是一个说明:如果M,N是λ-项,x在M中有自由出现,若以N置换M中所有x的自由出现(M中可能含有x的约束出现),我们得到另一个λ-项,记为M[x/N]。

α-变换规则如下:

λx.M=λy.M[x/y] 如果y没有在M中自由出现,并且只要y替换M中的x,都不会被M中的一个λ绑定。

例子:λx.( λx.x)x = λy(λx.x)y

α-变换主要用来表达函数中的变量换名规则,需要注意的是被换名的只能是M(函数体)中变量的自由出现。

β-归约

β-归约表达的是函数应用或者函数代入的概念。前面提到MN是合法的λ-项,那么MN的含义是将M应用到N,通俗的说是将N作为实参代替M中的约束变量,也就是形参。β-归约的规则如下:

(λx.M)N à M[x/N] 如果N中所有变量的自由出现都在M[x/N]中保持自由出现

β-归约是λ演算中最重要的概念和规则,它是函数代入这个概念的形式化表示。

一些例子如下:

(lx.ly.y x)(lz.u) ly.y(lz.u)

(lx. x x)(lz.u) (lz.u) (lz.u)

(ly.y a)((lx. x)(lz.(lu.u) z)) (ly.y a)(lz.(lu.u) z)

(ly.y a)((lx. x)(lz.(lu.u) z)) (ly.y a)((lx. x)(lz. z))

(ly.y a)((lx. x)(lz.(lu.u) z)) ((lx. x)(lz.(lu.u) z)) a

需要多加练习才能习惯这种归约。

η-变换(η-conversion)

η-变换表达了“外延性”(extensionality)的概念,在这种上下文中,两个函数被认为是相等的“当且仅当”对于所有的参数,它们都给出同样的结果。我理解为,对于所有的实参,通过β-归约都能得到同样的λ-项,或者使用α-变换进行换名后得到同样的λ-项。

例如λx.fx与f相等,如果x没有在f中自由出现。

λ演算的公理和规则组成

这一段来自《数理逻辑与集合论》(第二版 清华大学出版社)。还修正了其中的一个错误。

1. (λx.M)N à M[x/N] 如果N中所有变量的自由出现都在M[x/N]中保持自由出现

2. MàM

3. MàN, NàL => MàL (原书中此处错误)

4. MàM’=>ZMàZM’

5. MàM’=>MZàM’Z

6. MàM’=>λx. M àλx. M’

7. MàM’=>M=M’

8. M=M’=>M’=M

9. M=N,N=L=>M=L

10. M=M’ => ZM = ZM’

11. M=M’ => MZ = M’Z

12. M=M’ =>λx. M =λx. M’

如果某一公式MàN或者M=N可以用以上的公理推出,则记为λ├MàN和λ├M=N。

范式

如果一个λ-项M中不含有任何形为((λx.N1)N2)的子项,则称M是一个范式,简记为n.f.。如果一个λ-项M通过有穷步β-归约后,得到一个范式,则称M有n.f.,没有n.f.的λ-项称为n.n.f.。

通俗的说法是,将一个λ-项进行β-归约,也就是进行实参代入形参的过程,如果通过有穷步代入,可以得到一个不能够再进行代入的λ-项,那么这就是它的范式。如果无论怎样代入,总存在可以继续代入的子项,那么它就没有范式。

例子

M = λx.(x((λy.y)x))y,则Mà y((λy.y)y) à yy。M有一个n.f.。

例子

M =λx.(xx) λx.(xx),则Màλx.(xx) λx.(xx)=M。注意到M的归约只有唯一的一个可能路径,所以M不可能归约到n.f.。所以M是n.n.f.。

注意这个λx.(xx) λx.(xx)在λ演算的协调性研究中是一个比较经典的项。((λ x. x x) (λ x. x x))被称为Ω, ((λ x. x x x) (λ x. x x x))被称为 Ω2。

不动点理论

Λ表示所有的λ-项组成的集合。

定理:对于每一个F∈Λ,存在M∈Λ,使得λ├FM=M。

证明:定义w=λx.F(xx),又令M=ww,则有λ├M=ww=(λx.F(xx))w=F(ww)=FM。

证明是非常巧妙的,对于每个F,构造出的这个ww刚好是可以通过一次β-归约得到F(ww)=FM,如果再归约一次就得到F(FM),这样可以无限次的归约下去得到F(F(F(F…(FM)…)))。

Church-Rosser定理及其等价定理

这两个定理告诉我们这样一个事实:如果M有一个n.f.,则这个n.f.是唯一的,任何β-归约的路径都将终止,并且终止到这个n.f.。

Church-Rosser定理:如果λ├M=N,则对某一个Z,λ├MàZ并且λ├NàZ。

与之等价的定理如下,

Diamond Property定理:如果MàN1,MàN2,则存在某一Z,使得N1àZ,N2àZ。

后记

最后两个定理的证明没有怎么看懂,所以没有在笔记中记下。另外,前天在网上订购的《程序设计语言:概念和结构》第二版刚刚拿到手,其中有关于λ演算的一章。应该也对我大有帮助,待看完再说。

学习λ演算的初衷是了解一些程序设计的最基本原理,没想到最后还是绕到形式系统和数理逻辑这儿来了。不过,形式化表达的λ演算更清晰。

国内大学虽然也开程序设计的课程,不过好像都是pascal,c/c++之类,关于程序设计的本质基础的程序好像并不多。随着大学扩招,中国有望在很短的 时间内成为世界上程序员最多的国家,如果仅仅只学命令式和面向对象的程序设计,一定是不够的。函数式和逻辑式程序设计语言也是要学学的啊。

文中肯定有很多错漏,希望看出来的人给我留言。

参考文献

School of Computer Science and Software Engineering, Faculty of Information Technology, Monash University, Australia 3800

这个大学的FP课程中的Lambda演算相关部分

http://www.csse.monash.edu.au/~lloyd/tildeFP/Lambda/Ch/

wikipedia中lambda演算相关介绍

http://en.wikipedia.org/wiki/Lambda_calculus

《数理逻辑与集合论》第二版 清华大学出版社

lambda演算

Lambda
首先介绍 Lambda。许多非常精彩、非常重要、也非常困难的概念,随着时间发展,慢慢变成了日常生活中丝毫不引起人注意的事情。比如火和轮子这样关系到人类文明进程的重大发明,数字"零"的发现,等等。计算机科学里面也是如此。计算机科学发展的幼儿时期,数理逻辑中的 s-m-n 定理和通用图灵机等的发现,都被认为是重要成果,可是今天,许多熟悉电脑的中学生都知道,用软件模拟通用计算机是可能的。关于 Lambda 演算的理论也差不多是这样。

如果不是专门研究 Lambda 演算的理论,Lambda 对于今天的程序员来说,几乎是个透明而不可见的概念。实在是太普通,都很难把它说的有趣一点,或者看上去深奥一点。因为所谓Lambda,其实就是表达了区区一个"函数"的概念而已。不过,在 Scheme 里面,Lambda 还是表达了两个值得注意的重要特征。第一个,就是广泛的允许匿名对象的存在。这很难说和正宗的 Lambda 演算的理论有特别的联系,它更像是由 Lambda 演算的理论所衍生出来的编程风格。第二个特征,就是所谓的高阶函数。这个特征和 Lambda 演算理论息息相关。高阶函数是 Lambda 演算理论的精髓,是由 Lisp 首先介绍到程序语言这个世界的。也是大量的现代语言,比如流行的 Python 当中一个似乎是不那么引人注目的特征。

下面我们分头介绍这两个和 Lambda 演算理论紧密相关的 Scheme 特征。

高阶函数
Python 发明人 Guido van Rossum 和 Fred Drake 编写的 Python Tutorial 第 4.6 节列举了下面的例子。

>>> fib

>>> f = fib
>>> f(100)
1 1 2 3 5 8 13 21 34 55 89

对于事先不了解 Lambda 演算理论的读者朋友来说,第一次看到上面例子的时候,哪会想到背后深刻的理论基础和悠久的历史发展呢?这似乎就是公路上数不清的普通的轮子当中的普通的又一个而已,谁会想起生活在石器时代的我们的先祖们第一次看到这个滚动的玩意儿的时候是怎样的兴奋呢?不过,计算机科学就是不一样,如果你当真想亲眼看到有人对"轮子"发出由衷的赞叹的话,可以找一个 C 或者 Pascal 语言的程序员来碰碰运气。不过,如果你的运气实在不好,也许会听到类似下面的话的哦。"轮子?没有我家的小叫驴好呀!"

玩笑说了这么多,我们下面讲点干巴巴的"理论"。^_^

高阶函数有两点内容。第一是让函数对象成为程序语言当中所谓"第一等公民"。我们所说程序语言当中的"第一等公民",指的是可以对这样的数据对象进行赋值、传递等操作。就像我们可以对整数型变量所做的那样。如果函数对象也是程序语言当中的第一等公民,我们就可以像上面列举的 Python 的例子那样,把函数对象在变量之间进行赋值和传递等操作。

高阶函数的第二点内容是像下面这样。既然函数本身,就像整数或者浮点数那样,成了我们所谓"第一等公民",我们当然就希望可以像以前能够做的那样,在我们需要的时候,把所有这些"第一等公民",拿在手上揉来揉去、捏来捏去,无论它们是整数型数据、或者是浮点型数据、还是函数型数据。我们要把它们这样变换过来,再那样变换过去。把这些"第一等公民"放到我们的变换函数里面,对它们进行任意的、我们所需要的各种各样的操作。换句话说,我们可以像对待整数和浮点型数据那样,把函数本身也作为某个函数的输入数据和输出数据。也就是说,我们的函数可以对函数本身进行操作。这些可以操作别的函数的函数的地位不就是更高级了吗?这就是所谓"高阶"这个词的由来。

匿名函数
除了高阶函数这个本质性的东西以外,Lambda 在 Scheme 里面还代表了一种原则。这个原则就是把程序语言中的对象和对象的名字分离开,并且允许存在匿名对象。对于和 Lambda 直接相关的"函数"这个概念来说,就是允许存在匿名函数。函数可以没有名字,在我们需要的时候,又可以给它加上名字。这更多的是一种需要程序语言提供支持的编程风格。这个所需要的支持,就是对上面所说"高阶函数"的支持。确实有一些程序语言在实现高阶函数的时候,却没能够提供对匿名函数的支持。这的确是一个有趣的现象。当然,在这样的语言中加上对匿名函数的支持是轻而易举的。

把数据对象和变量名称剥离开来的原则,对于程序员来说,是非常大的解脱。就像 Lisp 和 Scheme 程序员视为当然的自动内存管理一样,这也是一个 Lisp 和 Scheme 程序员享受了很久的东西,可是 Lisp 这个圈子外的程序员直到最近,才开始接触到这些概念。要知道, Lisp 据说是自 Fortran 以来,第二个最古老的语言哦。像自动内存管理这样的技术,直到上世纪九十年代中后期,才开始被 Lisp 圈子外的程序员所了解。而这其实是 Lisp 程序员自上世纪六十年代以来,就一直在享受的东西。

在以后的例子里面将会具体的看到用 Lambda 定义匿名函数的例子。到时候,我们将有机会看到这样的匿名函数对于编程来说,是多么方便。

2008年11月24日星期一

你是如何成为 Lisp 程序员的?

问题之:你是如何成为 Lisp 程序员的?

答:我成为 Lisp 程序员的道路曲折而漫长。我曾于 2007 年 10 月 3 日在自己的日记中总结了自己的学习经历,现抄录于此。

最早在 2000 年 5 月,斯托曼院士访华时告诉我,Lisp (或者它的现代变种 Scheme)是功能最强大的编程语言,他本人就是一位高级的 Lisp 程序员,他还精通 C,GNU Emacs 就是采用 C 和 Lisp 两者开发的。我当时已经掌握了 C,但不会用 Lisp,但是我完全相信他说的都是真的。于是,一心想成为编程高手的我,决定学习和掌握这门编程语言。我从 2000 年下半年开始学习 Lisp。下面总结的学习经历大致按照时间先后顺序排出:

有必要先说明一点,在我遇到斯托曼院士之前,我在上大学时曾经阅读过一本关于人工智能的著作,《Artificial Intelligence --- Making machines "think"》,
作者是 Neill Graham,这本书的最后一章(第14章)是关于 Lisp 语言的简介,
所以我对人工智能和 Lisp 的概念并不完全陌生。这本书前面的章节都很好理解,但是在这最后一章,我遇到了很大困难。我花了许多时间试图明白其中的道理,不过最后成效不彰,现在回想起来,究其缘故,最主要的就是我没有一个适当的上机练习环境,在读了许多书中的东西后,当时我感觉似乎明白了其道理,但是实际上并没有真正理解清楚。不过,有两点在我看来无疑是确定的:一、Lisp 早已经成为人工智能研究项目的首选(或者说是默认的)编程工具,在人工智能领域没有其他语言能撼动其领导地位。二、对于具有表结构的数据操作,对于列表(list)头元素(pair 的 car 的部分)的处理采用递归方式比较好,而对于众多的体元素(pair 的 cdr 的部分)则采用迭代的方式处理效率更好。

斯托曼院士回国后,我首先在计算机上尝试用 Emacs Lisp 编程,
它是嵌入在 GNU Emacs 文本编辑器中的解释器。在庞大的 Lisp 家谱中,
Emacs Lisp 不是 Common Lisp,而是早期的 MacLisp 的一个直系后代,
同时在一些方面作了简化和强化。同时我开始阅读 Robert Chassell 所著 《Introduction to Emacs Lisp Programming》,Robert Chassell 是斯托曼院士早年结识的战友,也是自由软件基金会的合创人之一,他很早就使用 GNU Emacs,而且使用 Emacs Lisp 程序定制 GNU Emacs,斯托曼友善地把 Robert Chassell 介绍给我认识。 这本书既是自由文档(可以从 GNU 的网站自由下载),又是自由软件基金会出版社(GNU Press)的出版物。等我读完了这本书之后,我觉得这本书实在太美妙了,作者的文笔十分了不起(即使对于想学习英文写作的人,帮助也应该很大),把这本书介绍给其他人是完全值得的。我于是找了两位翻译人员(毛文涛博士和吕芳女士),把它译成了中文,我则担任了全书的编辑和审校工作。中文版质量很高,我很满意,它作为一本很伟大的编程入门书籍十分适合广大读者自学(我认为读者应该搞到一本阅读)。我至今还想自己动手翻译这本书的第三版,可惜如今我很难再找到当年那么多的时间做编辑和审校之类的工作了。

阅读完这本书之后,我意识到如果想使用 Emacs Lisp 开发非玩具级别的实际应用程序,那么根据作者的推荐,自由软件基金会出版的《GNU Emacs Lisp Reference Manual》是必不可少的工具书,我打印了这份文档的第 2.4 版本,厚厚的共四本。后来这份文档正式出版,从 GNU 网站上订购的图书升级到了 2.6 版本,针对的是 GNU Emacs version 21。我不太认同 Eric Raymond 在他的名著 《The Art of Unix Programming》中对 Emacs Lisp 的评论,他以为 Emacs Lisp 只能为 Emacs 编辑器本身编写控制程序,而赶不上其他脚本语言全面。实际上,我认为只要熟悉了 Emacs Lisp 的细节,其他任何脚本语言能完成的工作,都可以使用 Emacs Lisp 程序完成。我亲眼看见斯托曼院士在 GNU Emacs 内完成电子邮件的编辑、收发等工作,不用 Eric Raymond 开发的 fetchmail 程序一样干得很好。我自己也利用 Emacs Lisp 编写过 CGI 应用程序,效果也不错。

Bob Glickstein 曾经写过一本《Writing GNU Emacs Extensions》,可以配合 Robert Chassell 的书与《GNU Emacs Lisp Reference Manual》,作为补充读物。

读了 Robert Chassell 的书之后,我开始花时间阅读 David Touretzky 博士所著的 《Common Lisp: A Gentle Introduction to Symbolic Computation》,这本书可以从互联网上自由下载,读者可以自行在万维网上 google 得到它。 这也是一本伟大的 Lisp 著作,内容已经是基于 Common Lisp 的,但是作者并没有特意强调这一点。我把下载的 PDF 文件打印出来,自己动手把打印出的文档纸张装订成了两卷手册。 我从这本书中得到的最大收获是我充分认识到 Lisp 中的一切都是对象:数字原子(numeric atoms)和符号原子(symbolic atoms)都是对象。数字原子求值返回它自身的值,而符号原子则有名称(name)、类型(type)、值(value)、秉性表(plist)和绑定表(bindlist)。这五个字段可以放入一个数据结构中,并在实现中以 C 语言的 struct 表达。

在阅读这些材料的同时,我又从网上找到了 Gary Knott 教授编写的一份文档,《Interpreting Lisp》,这份文档篇幅不长,从来没有正式出版成书。在这份文档中,作者利用 C 语言编写了一个微小的 Lisp 实现,非常接近于最初的 Lisp 实现。最可贵的是他将实现的源代码和盘托出。从这本书中,我清晰地看到了如何构造 Lisp 对象的结构,我开始认识到内存垃圾收集算法的重要性。在理解了 David Touretzky 博士所著的 《Common Lisp: A Gentle Introduction to Symbolic Computation》介绍的 Lisp 对象的结构基础上,我明白了书中图示的 Lisp 对象中若仅在结构设计时安排五个字段是不够的,还需要有供垃圾回收(GC,Garbage CCollector)模块操作的字段才行。

在 2001-2002 期间,我开始接触 Scheme。在此之前的 2000 年 8 月,Rorbert Chassell 曾来中国访问,我们在西安时,他向我介绍了 Scheme 是我应该关注的语言。Scheme 于 1985 年诞生于 MIT,发明人有两位:一位是 Gerald Sussman 教授,他是自由软件基金会的董事会成员之一,另一位是 Guy J.Steele 博士,下面即将更多地提到。我首先使用了 Dorai Sitaram 所著的教材《Teaching Yourself Scheme in Fixnum Days》,这份文档可以从网络自由下载,不过坦率地说,这本书教材不太适合初学者,阅读它的人至少应该具有很多基础知识或者经验才行。我并没有从这本书从获得太多的帮助,对 Scheme 的基本概念也没有搞清楚,特别是连续(Continuation)之类的概念没有理解。不过,收获还是有很多,我意识到 Scheme 是一个非常优美的 Lisp 变种,它继承了源自 Algol60 和早期 Lisp 两者的特点。这份教材的最后还列举出了一个具体的编程实例,讲授如何利用 Scheme 编写 CGI 程序。现在我看来,在 CGI 编程等领域, Perl 和 PHP 等脚本语言获得广泛应用简直就是钻了 Lisp 社团不善营销的空子。

到了 2001 夏天,我从美国获得了《Structure and Interpretation of Computer Programs》的教师手册,是我的朋友 James Gray 帮我买的,他是我一个很好的朋友,不过我这里要善意地埋怨一下,他做事有些马大哈,我原来希望他给我搞到这本书的学生用书,没有想到他却寄来了教师手册,我想他在买书时没有仔细区分一下,而此著作的教师手册和学生用书的封面都采用了同一图案,作者和 MIT 出版社的编辑的确很优秀,他们在营销本书时非常成功,后来专门还开设了一个网站推广本书和相关的教学材料,网上公布了教材的全部内容,加上两位作者课堂教学的视频录像。 教师手册价格比较便宜,James 在购买时要么没有仔细辨认清楚,要么就是帮我省钱,才寄来了这本教师手册。我当时没有学生手册,也就没有继续学习 Scheme。不过话说回来,James 寄给我的教师手册我一直都留在我手头,后来对于我在黑客道教学中讲授 Scheme 帮助极大,在这里还是应该深深地感谢 James Gray。

不久(2003年),我买了一本 Patrick Winston 教授所著的《Common Lisp》第三版, 作者是麻省理工学院人工智能实验室的主任(斯托曼早年就是他手下的兵),在美国的人工智能研究领域名气很大,我就是冲着他的名气才买此书的。阅读完之后,我觉得这位教授名副其实,而不像我在国内见到的一些人徒有虚名,拿不出真东西。这是一本介绍 Common Lisp 的极好教材。后来 Hans Hagen (ConTeXt 排版软件包的主要作者之一)告诉我这本书的合著者 Berthold Klaus Paul Horn 在 TeX 社团名气也很大,的确如此,从本书的排版质量即可看出许多名堂来,排版样式一看就是典型的 TeX 风格。 作为中文 TeX 用户俱乐部(CTUG)的主席,我已经知道,国内学术界(我指的是数学界和计算机科学技术界)很少有人精通 TeX 排版系统,鲜有人能使用它排版自己的讲义或著作。

读了这本书之后,我感觉自己必须阅读 Common Lisp 的语言参考手册,许多问题必须在看到语言规范(这是基本的尺度)之后才能搞清楚。 Guy L. Steele 博士写过这样的手册,而且他写了两次,第一个版本是在 Common Lisp 标准化之前完成的,第二个版本是在标准化完成之后写成的,但是网上有人评论说有些该写的东西没有写进去,此书是否会有第三版不得而知。Guy L. Steele 博士是非常著名的语言手册的作者,他已经为 C、Common Lisp、Java 等编程语言都写过的语言参考手册,都非常成功,这些参考手册都是一版再版,销路极好,比位于瑞士的国家标准化组织(ISO)发布的非常昂贵的标准文档销路好许多。他写的这些语言参考手册已经成为编写这些语言编译器作者们的大救星。

大约在同时,我下载了 《On Lisp》,这是 Paul Graham 博士编写的一本优秀著作,从中我得到了许多 Lisp 概念的细节,特别是 Lisp 的 macro 机制,
以及黑客们如何利用 Lisp 思考问题。作者介绍的自底向上(bottom up)的方法论对我触动很大,而作者的讲解是非常富于启发性的(作者曾专程赴意大利的美术学院学习过油画创作,所以具有很高的艺术修养)。从那时开始,混合编程(Hybrid Programming)的思想在我头脑中开始成型,我坚信 Lisp 将会成为一种非常长寿的编程语言,这使我联想起斯托曼院士当年在四川九寨沟就 GNU Emacs 开发对我讲过的话。在 GNU Emacs 和 Lisp 背后隐含的方法论是永远不会过时的。

2004 年,我真正找到了 Lisp 编程的感觉,觉得自己开始进入状态,
并开始使用 Scheme 开发真正的应用程序,我编写的程序是一个网络应用程序,即一个网络留言板(Web-based bulletin System),在万维网上可以运行,
CGI 的模块是采用 Scheme 写的,Apache 在服务器上通过 Scheme 的 CGI 程序接上了 PostgreSQL 数据库。我使用的是 PLT Scheme 的 103 版本,我非常喜欢这个版本,既简单又很干净,我用 C 语言和 PostgreSQL 提供的 libpg 编写了一个 DA (database adaptor),让 Scheme 程序可以访问 PostgreSQL 数据库。

完成了这个项目之后,好事成双,我得到了渴望已久的《Structure and Interpretation of Computer Programs》(简称 SICP,或者“紫皮书”),作者就是 Harold Abelson 教授和 Gerald Sussman 教授。正是这一年,我开始利用自己头脑中形成的数学观点,特别是在我的泛系尺度论中表达的思想,来认真学习 Scheme,并且主动地从中国古代的阴阳太极图模型来理解当今电子计算机系统上的计算模型。这一过程延续了很长时间,直到 2005 年的冬天才最终获得成功! 这期间的许多思想写入了我的著作《自由软件:新的游戏规则》第三卷内篇的第二章“论尺度”。今后我还准备花更多的时间把它扩展开来,形成一部单行本的著作《泛系尺度论》,在这个单行本中,我将利用更长的篇幅把中国古代的哲理思想、现代数学思想和计算机编程融为一体,对整个计算理论提出自己完整的一家之言。在黑客道九个段位中,初段就是讲“计算的本质”,里面就纳入了我的思想方法和编程经验。

2004-2005 年期间,我仔细地研究了 R5RS 文档中除了第七章之外的所有内容,
收获巨大。对于第七章的内容,当时仍然有些疑惑,因为这些材料需要理解大量的关于 lambda calculi 的细节和大量的预备知识,我当时还没有找到充分的材料钻研。另外,在研究 PLT Scheme 的源代码时,内存垃圾回收算法对我而言,仍然是一大疑难问题,显然,对于内存垃圾回收技术,我还需要学习更多的背景材料。

到了 2005 年的年底,我把 R5RS 翻译成了中文。在完成翻译的过程中,我知道了如何利用形式语言和扩展的巴科斯-劳尔范式(EBNF)来定义一门编程语言的形式句法和语义规则,以及如何正确理解和读懂它。

2005-2006期间,我学习了其他许多关于 Lisp 编程的书籍,包括 Paul Graham 博士的《ANSI Common Lisp》、 Matthew Flatt 等人合著的 《How to Design
Programs》, Brian Harvey 和 Matthew Wright 合著的 《Simply Scheme ---
Introducing Computer Science》(此书的封面设计别出心裁,非常值得回味)、
Daniel Friedmann 和 Matthias Felleisen 合著的 《The Little Schemer》 和
《The Seasoned Schemer》。另外我花了相当多的时间仔细阅读 《The Scheme Programming Language, 3e》,这是 R. Dybvig 教授的代表作,他是 Chez Scheme 实现的设计大师。年底我得到了 《Hackers and Painters》(“黑客和画家”),这是 Paul Graham 博士所著的散文集,与 Robert Chassell 一样,他也是一位伟大的作家,他的行文非常容易阅读,而且这本书中的内容如同其书名副标题一样,的确收入了许多伟大的想法,这些想法对于创新公司利用 Lisp 开发创新项目是非常富有启发性的。

2006 年 7 月 15 日,我的学生千俊哲从南韩的汉城大学带来了他学习的两本著作的复印件:George Springer 和 Daniel P. Friedman 合著的《Scheme and the Art of Programming》,以及 Mark Watson 的 《Programming in Scheme: Learn Scheme through Artificial Intelligence Programs》。前一本的难度在紫皮书之下,比较好读,其中许多程序如同棋谱一样,展现了许多高级编程技巧,值得反复思考,我立即在 PLT Scheme 实现上验证了书中的大部分代码;后一本则介绍如何使用 MIT Scheme 来设计人工智能程序,非常精彩。

2006 年 7 月送走了千俊哲之后的夏天,我一直在瑞士苏黎世度假(八月下旬我还去了西班牙马德里参加了国际数学家大会),苏黎世中央图书馆(ZB,Zentralbibliothek Zuerich)是一所了不起的图书馆,现有藏书一百二十万种。据说列宁当年在欧洲流亡时曾来到苏黎世,就睡在这个图书馆里读书学习。八月份时,大多数瑞士人也在休假,图书馆的人不多,非常安静。我在这段时间从图书馆中找到了非常多的背景材料,包括 H.P. Barendregt 所著的数学经典教材 《The Lambda Calculus --- Its Syntax and Semantics》,这本书于 1981 年由 North Holland 出版社出版,对这一数学分支作了详尽的介绍,我认为对于这一主题,今后再也无人可以写得比这本著作更好了。 另外,我找到了第一本关于 lambda calculus 的著作,是由这个理论的创始人 Alonzo Church 教授创作的,《The Calculi of Lambda-conversion》 简直是无价之宝,在这本小册子中,作为数学家,作者清晰而精炼地阐明了 lambda calculi 的全部内容。任何一位想掌握 lambda calculus 的人都应该仔细阅读本书。在图书馆中还找到了 《An Introduction to Lmabda Calculi for Computer Scientists》, 作者是 Chris Hankin。 Matthias Felleisen 和 Matthew Flatt 合写的 《Programming Language and Lambda Calculi》也打印出来了,并仔细阅读了两遍,这两人是 PLT Scheme 研发小组的核心成员。 在苏黎世中央图书馆的书架上,我还看到了 SCIP 紫皮书的第一版的德文本,书中的内容与英文版第二版大同小异,但是我敏锐地发现,第一版的第四章中没有收入 eval 和 apply 两个高阶算子构成的太极推手图,第二版中则出现了。

我花时间研究了 《Lisp 1.5 Programmer's Manual》,这是世界上第一份真正意义上正式发布过的 Lisp 稳定实现版本的手册,作者就是 John McCarthy 等人,极具学术权威性,我认为任何一位 Lisp 程序员都应该阅读这本手册。时隔多年后,我又开始阅读关于人工智能方面的著作,《Lisp, Lore and Logic》是 W. Richard Stark 写的,《Artificial Intelligence, theory and practice》 是 Thomas Dean 等人写的,他们都已经使用 Common Lisp 来说明问题。阅读时,我参考了前面已经提到的 Partrick Winston 教授编写的经典教材 《Artificial Intelligence, 3e》。

2007 年初,我开始关注 Scheme 社团中尚处于起草状态中的 R6RS,这个文件将成为新的 Scheme 语言规范。我现在仍然认为 Common Lisp 太复杂、太庞大,回厂大修似乎也不太可能,因为工业界已经很好地接受了 Common Lisp,而 Scheme 将是未来的主流。我开始按照这一规范来开发自己的 Scheme 实现版本,这一实现版本称为 MNM Scheme。

2007年6月至7月间,我在瑞士苏黎世的 Campus Zollikerberg 打印了 R5.97RS,
我花了许多时间理解这一新的规范,特别是它与前一个版本(R5RS)的差异。
同时,我重新思考了 PLT Scheme 实现的源代码和涉及模块(modules)、名称空间(namespaces)、盒子(box)类型、define-values 和其他附加在 R5RS 规范之上的特性与实现风格。

从苏黎世中央图书馆借到的另外一本具有重大价值的著作就是 Richard Jones 和 Rafael Lins 合著的《Garbage Collection》,这本书极大地帮助我理解了内存垃圾回收算法设计的细节。我从此开始真正明白了 Scheme 实现工作中的最后一个阴暗角落。对于一切 Lisp 对象,内存垃圾收集的算法设计时其实不存在理论上的最优算法,算法的效率受到多种因素的影响,而 Lisp 的设计者可以根据自己的设计思想来决定应该怎样回收内存垃圾。

这时的我已经成长为熟练的 C++ 程序员,站在 C++ 程序员的立场看,一切 Lisp 对象都有类型,我可以用 C++ 语言内置的类(class)来刻画它们(即声明各种用户自定义的类),一切 Lisp 对象从存储空间分配和回收的角度来看具有共性,所以,这可以利用 C++ 的模板来表达 Lisp 对象的存储管理结构,而各个 Lisp 对象占有的存储空间大小,则可以利用类的构造函数(constructor)和析构函数(destructor)对内存分配和内存垃圾回收在模板的支持下进行统一的操作。

源自 Lisp 发展起来的 GC 是一项“古老”的技术,实际上它已经广泛地被采用了,Java 这门当今新的商业编程语言中就有,而且 Java 的 GC 算法设计得非常好,我决定在我的 Scheme 实现中参考它。2007 年 9 月,我在从香港飞往苏黎世的飞机上,我阅读了美国著名的程序员 Bruce Eckel 所著的 《Thinking in Java》的第四版原著,从作者的介绍中,我结合从《Garbage Collection》中获得的知识,我理解了 Java 的内存垃圾回收算法的总体思路,并构思了如何利用他们的算法来改进我的设计。 而在我离开苏黎世回国的同一天(2007年9月26日),R6RS 技术委员会的全体编辑成员决定冻结对草案的讨论,正式发布了这一规范,从那一天起,我实现 MNM Scheme 的步伐也大大加快了。(不过,请读者留意在委员会举办的投票时,也有许多人投了反对票,并给出了反对意见,这些意见与支持的意见一起,都是极有研究价值的。)

Scheme 的实现版本非常多,而且自己能否动手实现一个是考验一个计算机专业人士学术修养深浅的好指标(这也是我在黑客道中把第五段的教学内容定为“解释器的原理与构造”的原因之一)。迄今优秀的 Scheme 实现有: PLT Scheme、MIT Scheme、Chez Scheme 等等。我认为 PLT Scheme 是非常优秀的实现版本,它是按照 GPL 发布的自由软件,值得在这里推荐给广大读者。毫不客气地讲,我的 MNM Scheme 也应该算一个。

Common Lisp 的实现版本很多,抛开 Franz Lisp 等商业版本不谈,自由软件社团中最有名的两个实现分别是:Bruno Haible 等人从 1992 年以来一直维护和开发的 CLISP,以及卡耐基梅隆大学的小组开发 CMU Common Lisp。这两个 Common Lisp 实现都很好,我个人比较喜欢使用 CLISP。目前最好的 Common Lisp 编程著作可推荐 Peter Seibel 写的 《Practical Common Lisp》,这位作者的天分显然比我高,他原来是 Java 和 Perl 程序员,2004年才开始学习 Common Lisp,他花了一年的时间学习它,就完全学会了,而且在学习的同时,边练习、边写书,结果很丰硕,写出的这本书就是读者能看到的结果,这本书得到了广泛的认可,它出版后获得了美国出版界计算机图书创作的震撼大奖。他在一次采访中提出了一个新的说法:时代的发展需要“第二代 Lisp 程序员”,而且每个程序员都应该学习 Lisp。(让我再次回忆起斯托曼院士在 2000 年时对我说过的话。)

正如读者在上面所读到的,成为一位了解 Lisp 一切内幕的程序员可真不容易,但是我很高兴,因为我已经成功地逾越过了这个初看起来曾经非常高的门槛,我现在已经是这样一位程序员了。学习 Lisp 给我带来了巨大的乐趣,如果没有这种在编程中产生的乐趣相伴,我绝对不会花这么长的时间来学习它。今天,我由衷地自豪,因为如果按照 Peter Seibel 的说法和衡量标准,我已经是第二代优秀的 Lisp 程序员群体中的一分子。

2008年11月23日星期日

Common Lisp -- 梦想与现实的交汇

Beating the Averages
作者和Morris(是的,就是搞出第一个蠕虫病毒的那个家伙)在1995用Lisp搞了个C2C平台,在打败了所有竞争对手后,被Yahoo收购,成为现 在Yahoo Store的雏形。当得知Yahoo收购消息后,作者做的第一件事就是招了几十个程序员,因为谁也无法相信这样强大的C2C平台只是由四个Lisp黑客构建的。文章中,作者提出编程语言的表达能力是有区别的,而程序员每天写的代码量却和使用的语言基本无关,所以如果你使用的语言表达能力是别人的30倍,你的开发时间将是别人的30分之一!这就是很多竞争对手都认为作者拥有秘密武器--每次他们发布了新的功能,作者都可以在第一时间做到同样的事,作者的秘密武器就是Lisp。文章还揭示了为啥Lisp没有成为主流语言的原因--编程语言不仅是工具,还是程序员思考问题的方式,改变思考方式不是一件容易的事!然 而,作者的成功正是利用了这一点。
如果你喜欢这篇文章,可以考虑购买Hacker and Painter一书,是作者散文的合集,其中大部分可以在上面的网站上在线阅读。

The Nature of Lisp
这篇文章中,作者以广为人知的XML为引子,首先问为啥XML能作为一种通用的数据描述语言,因为XML具有树状结构,而几乎所有的信息都可以用某种树状结构来表现。接着作者启发道,程序能不能用XML表示呢?其实是可以的,因为几乎所有的编译器把原文件变成一种叫抽象语法树(AST)的东西,所以XML可以表现几乎所有的语言的语法!接着作者用Ant的例子引出Executable XML的概念。而后开始转到Lisp上,说其实Lisp和XML是同一个东西,所不同的是Lisp早发明30年,而且比较简洁。然而,Executable XML的实现是需要借助其他语言的,用SAX或者DOM接口操纵XML。而Lisp可以用macro直接操纵自己的语法树,这才是Lisp的威力所在!
Lisp和XML一样可以表达几乎任何语言的语法,用macro可以很方便地模拟语言的语义,Lisp可以变成你想要的任何语言!Lisp, one language to rule them all! Lisp编程就是构建一层层的DSEL,直到抽象层次升高到可以直接描述问题领域。Lisp is not a language, but a language to build languages, it's meta-language!

为啥MIT的人工智能会那么强?因为他们从60年代开始,在所有其他人都还在使用Fortran和汇编的时候,已经开始用Lisp编程了!GEB中提到,大脑的底层是神经元,在这个层面是完全无法理解智能的(至于存不存在的话是哲学问题),慢慢地升高层次,当突破某个临界点后,突然间,智能就出现了!所以,几乎所有的AI程序都是用Lisp写的,就是因为如果你无法构建高级的抽象,永远在神经元层次编程的话,可能就永远写不出AI程序了。对,我说的是“可能”,我所知道的有两种例外:
1。你的大脑就是一个Lisp编译器,你用Lisp思考,大脑帮你编译成别的语言,可能在Lisp发明之前的AI程序就是这么写的。这可能也就是冯诺依曼为啥只用汇编的原因,因为他的脑袋瓜实在是太厉害了,因为他不是人类:)
2。你在无意识中已经开发了一个Lisp解释器

2008年7月28日星期一

Alan Kay 推荐计算机专业的学生学习 Lisp

Alan Kay 推荐计算机专业的学生学习 Lisp
Smalltalk之父,Java思想的先驱.

Alan Kay于1970年加入Xerox公司的Palo Alto研究中心。
早在70年代初期,Alan Kay等人开发了世界上第二个面向对象语言Smalltalk,因此,Alan Kay被誉为Smalltalk之父。2003年,Alan Key因为在面向对象程序设计上的杰出贡献,获得了有计算机界的诺贝尔奖之称的ACM Turing Award。
Alan Kay成名于Smapltalk和OOP,而Java虽然在语言上类似于C,但是在语义上非常接近Smalltalk,很多Java中的设计思想在Alan Kay的文献中找到根源,所以也有些人将Alan Kay尊为Java思想的先驱。不过Alan Kay认为Java的成功不是由于Java本身的内在价值,而是其商业化的成功。
Alan Kay欣赏的是Lisp,他认为Lisp是软件的麦克斯韦方程,其中的许多想法是软件工程和计算机科学的一部分。

2008年7月19日星期六

Lisp发布新方言Arc

Arc 语言是 Graham 设计的一种全新的 Lisp 方言,被实现为一个对 MzScheme 的扩展程序。

与其它方言不同,这个语言具有十分清晰和“现代化”的语法,以至于无法被直接实现为一组 Scheme 的卫生宏。

按照作者的话说,Arc 是一种适合“探索性编程”(exploratory programming)的语言,适合乐于思考但不想被现有语言的语法、特性等不足限制思考的程序员使用,在构建大型程序方面并无很大优势。

语法方面,使用了整合 cond 能力的 if,类似 Lua 的 for 语句,省略了转换函数(相对于 Lisp)的宏定义 mac,被替换为方括号的 lambda,字符串、列表、散列的取值语法即函数调用语法。并简化了大量常用语法。

语义方面,增加了对于 Lisp 来说不存在的算符这一概念。

little b:用于构建复杂系统的Lisp方言

little b 编程语言刚刚发布了新版本。该项目的初衷是为生物学家提供一个开源的、模块化的、重用能力强的编程语言。

在 Common Lisp 的基础上,little b 提供了优秀的模块化系统和一个完整的、超越当前大多数自命为“面向对象语言”所能提供的面向对象系统。

关于这一点,可以从其 class 定义语法中看出端倪。此外,little b 还整合了 Prolog 的规则推理机制,数学系统中常见的符号计算等功能。

语法方面,大多数语法设计都集中在了 OOP 系统上(花括号用于创建对象,方括号用于指定对象的域,奢侈的设计);支持中缀算符。这里有一个使用 little b 快速建模生物化学系统的例子。"

2008年7月9日星期三

Lisp: 50 周年(转)

Lisp's 50th Birthday Celebration
Richard P. Gabriel

In October 1958, John McCarthy published one in a series of reports about his then ongoing effort for designing a new programming language that would be especially suited for achieving artificial intelligence. That report was the first one to use the name LISP for this new programming language. 50 years later, Lisp is still in use. During the past five decades, it has been changed and turned, which led to dialects differing in many respects from the original design, but the central corner stones remained the same, making it one of the oldest programming language still in use today, second only to Fortran.

1958 年 10 月,John MaCarthy 发表了一系列关于他正在致力于设计一个特别适合人工智能研究的新编程语言的报告中的一篇。那篇报告里首次将这种新编程语言命名为 LISP。50 年后,Lisp 仍然在使用。在过去的 50 年里,它有许多变化和调整,并产生出一些在许多方面与其最初设计截然不同的方言,但是它的中心思想仍然不变,使其成为今天仍在使用的最古老的语言之一,仅次于 Fortran。

The final design for the first incarnation of Lisp was published in an issue of the Communications of the ACM in 1960. That version of Lisp pioneered numerous languages features that are nowadays taken for granted. To name but a few: Lisp introduced a conditional expression, which was taken over in other languages as the ubiquitous if statement; it introduced recursion and first-class functions, the essential ingredients of functional and many other programming languages; it introduced reference semantics for variables, without which object-oriented programming would not exist; it introduced symbolic expressions, a generic and uniform representation for data (later reinvented as XML) and programs, the latter enabling program transformations from within an application; it introduced garbage collection for the very first time in programming languages; and it even already had a combination of metadata and dynamic dispatch in the form of symbols and property lists.

第一个 Lisp 的最终实现发表在 1960 年的 Communications of the ACM (CACM) 上。那一版本的 Lisp 首创了几个至今仍被采纳的语言特性:Lisp 引入了一个条件表达式,后来被其他语言拿去作一般性的 if 语句了;它引入了递归和第一类 (first-class) 函数,函数型和许多其他编程语言的核心成分;它引入了变量的引用语义,没有它的话就没有面向对象编程语言;它引入了符号表达式,通用和统一的数据和程序的表示形式 (后来被重新发明成 XML),后者使得程序可以在应用里进行转换;它很早就在编程语言里引入了垃圾收集机制;并且它甚至已经有了一个元数据组合以及基于符号和属性列表的动态派发机制。

Lisp is clearly one of the most influential programming languages in the history of computer science: Timothy Hart added macros to Lisp in the 1960's; Warren Teitelman invented an advice facility for Lisp in the 1960's as the very first precursor to aspect-oriented programming; Carl Hewitt used Lisp as a platform to develop backtracking (essential for logic programming) and the actor model; Alan Kay acknowledges the heavy influence of Lisp on Smalltalk, the first explicit object-oriented programming language; Brian Smith developed the concept of computational reflection using Lisp as a starting point; Paul Graham used Lisp to develop the first continuation-based web application; and even today Lisp is on the forefront for the upcoming Web 3.0.

Lisp 无疑是计算机科学史上最具影响力的编程语言之一:Timothy Hart 在 1960 年代为 Lisp 增加了宏;Warren Teitelman 在 1960 年代发明了一个 advice 机制,成为了面向方面 (aspect-oriented) 编程的最早先驱;Carl Hewitt 将 Lisp 作为一个开发回溯 (逻辑编程的本质) 和其他 actor 模型的平台;Alan Kay 承认了 Lisp 对于 SmallTalk 的重要影响,后者是第一个明确的面向对象编程语言;Brian Smith 开发了第一个基于续延 (continuation-based) 的 Web 应用;而且直到今天 Lisp 仍处在即将到来的 Web 3.0 的前沿。

We would like to celebrate Lisp's 50th birthday. OOPSLA 2008 is an excellent venue for such a celebration, because object-oriented programming benefitted heavily from Lisp ideas and because OOPSLA 2008 takes place in October, exactly 50 years after the name Lisp has been used publicly for the first time.

John McCarthy has already agreed to give a talk about the early history of Lisp, returning to OOPSLA after his successful keynote talk at OOPSLA 2007. Guy Steele and Richard Gabriel will repeat their HOPL-II talk about the Evolution of Lisp from 1992, using a particularly unusual set of slides. Pascal Costanza will talk about the recent developments in the Lisp community, which has seen a surprising resurrection after its wake from the AI Winter. We will invite other influential Lispers, covering important aspects in the development of Lisp during the past five decades. Finally, we will have an open panel discussion about the next 50 years of Lisp.

OOPSLA 2008 will take place in Nashville, Tennessee, USA from October 19 to October 23. OOPSLA is the major annual conference on object-oriented programming worldwide and continues to attract several hundreds of the brightest minds in this field both from industry and academia since over 20 years. Find more information about OOPSLA 2008 at http://oopsla.org

2008年5月11日星期日

Scheme语言深入

一、关于符号类型

符号类型又称引用类型,在概要一文中本人介绍得非常的模糊,使很多初学者不理解。符号类型在Scheme语言中是最基础也是最重要的一种类型,这是因为Scheme语言的祖先Lisp语言的最初目的就是符号处理,在Scheme语言中几乎所有的东西都可以看做是符号或做为符号列表来处理,这也是我们把符号类型做为第一个问题研究的原因。

与符号类型相关的关键字有四个,分别是:quote, quasiquote, unquote和unquote-splicing,如下所示:

规范用法:(quote obj)
简化用法:'obj (注意,'为右单引号,"双引号下面的那个符号。)
意义:符号类型的定义,(quote obj)本身就是一个值,虽然它不如数字123这样直观。

规范用法:(quasiquote obj)
简化用法:`obj (注意,`为左单引号,~波浪号下面的那个符号。)
意义:"类似符号"类型的定义,最好称之为逆符号类型,它可以将符号类型转换为具有实际意义的东西。

规范用法:(unquote obj)
简化用法:,obj (注意,,逗号,<小于号下面的那个符号。)
意义:"非符号"类型的定义,非符号类型出现在符号类型或逆符号类型定义中间,它不直接做为符号类型使用,而是将运算结果做为符号类型的一部分。

规范用法:(unquote-splicing obj)
简化用法:,@obj
意义:非符号类型的拼接,注意:,@ 两个符号做为一个操作符来使用)。当非符号类型是一些复杂算法时,需要用它来做一下拼接,以达到符号类型的目的。
上面所说的所有规范用法和简化用法的功能都是相同的。

符号类型的意义在于,一个说明,英文单词zebra指的是活生生的斑马,而'zebra或(quote zebra)指的是由字母z、e、b、r、a构成的这串符号(不是字符串),就象我们定义变量(define x 100),这时x指的就是100这个数值,而'x或(quote x)则代表字母x构成的这个符号。

首先看一段代码:

guile> (define s '(good morning))
guile> s
(good morning)
guile> (symbol? s)
#f
guile> (list? s)
#t
guile> (symbol? (list-ref s 1))
#t



从此示例中可以看出,用quote定义的列表的类型仍是列表,而列表中的某一值的类型则是符号类型。还可以看出有点类似于如下:

(+ 1 (+ 2 (+ 3 (+ 4 5)))) ==> (+ 1 2 3 4 5)
(list 'a 'b 'c 'd 'e) ==> '(a b c d e)



两者有异曲同工之妙,减少了多余的操作符,使表达式更直观,更容易理解。

从 '(1 2 3 4 5) ==> (1 2 3 4 5) 可以看出,由符号类型的定义来形成列表,这是Scheme语言继承自LISP语言的传统。

下面是在guile中的用法示例:

guile> `(1 ,(+ 1 1) 3)
(1 2 3)
guile> (quasiquote (1 (unquote (+ 1 1)) 3))
(1 2 3)
;;;第一个是简化用法,第二个是标准用法。
guile> `(1 ,@(map + '(1 3) '(2 4)) 9)
(1 3 7 9)
guile> (quasiquote (1 (unquote-splicing (map + (quote (1 3)) (quote (2 4)))) 9))
(1 3 7 9)
;;;第一个是简化用法,第二个是标准用法(注意:,@ 两个符号做为一个操作符来使用)。



从示例中我们可以看出,这些应用多数与列表有关,而处理列表是Scheme语言的关键所在。符号类型的用法对深入理解Scheme语言也非常关键,因为Scheme语言本身就可以理解为是这种符号类型的列表,处理符号类型就是处理Scheme语言本身。






回页首




二、关于尾递归

数列问题是研究递归的非常好的范例,在王垠的主页中有关于用菲波那契数列来说明非尾递归与尾递归之间区别和尾递归的好处的一个例子,见 http://learn.tsinghua.edu.cn/homepage/2001315450/wiki/TailRecursion.html 。我们这里用更简单一点的问题,求累计的问题来说明,即求自然数1+2+3+4+ ... +n的和。事实上就是设计一个过程,给它一个参数n,求1+2+3+ ... +n的和,我们首设计一个suma过程,代码如下:

#! /usr/local/bin/guile -s
!#
(define suma
(lambda (n)
(if (= n 1)
1
(+ n (suma (- n 1))))))
(display "(suma 100) ==> ")
(display (suma 100)) (newline)
(display "(suma 818) ==> ")
(display (suma 818)) (newline)
运行这段代码,会出现如下结果:
(suma 100) ==> 5050
(suma 818) ==> 334971


说明:
以(suma 5)为例,表达式展开后:
(suma 5)
(+ 5 (suma 4))
(+ 5 4 (suma 3))
(+ 5 4 3 (suma 2))
(+ 5 4 3 2 (suma 1))
(+ 5 4 3 2 1) ==> 15


如果n为1000的话则会最终形成(+ 1000 999 ... 3 2 1)这样长度惊人的表达式,结果直接导致guile的崩溃。

为什么会是818呢?因为819是会溢出的,出错,得不到结果,这可能大出乎我们意料之外,因为如果用C来写这样功能的程序代码,可能会求到6位数而不出问题。这一过程是用非尾递归来完成的,它的扩张呈指数级增长。代码的迅速膨胀,使guile没有处理到1000就崩溃了。

我们再来看看采用尾递归的情况,代码如下:

#! /usr/local/bin/guile -s
!#
(define sumb
(lambda (n)
(let f ((i n) (a 1))
(if (= i 1)
a
(f (- i 1) (+ a i))))))
(display "(sumb 100) ==> ")
(display (sumb 100)) (newline)
(display "(sumb 1000) ==> ")
(display (sumb 1000)) (newline)
运行结果如下:
(sumb 100) ==> 5050
(sumb 1000) ==> 500500


还是以n为5的情况来说明: (sumb 5)
(f 5 1)
(f 4 6)
(f 3 10)
(f 2 13)
(f 1 15) ==> 15


这样的话,始终是依次计算,不会出现列表膨胀,所以n为1000时也不会出错,计算速度也很快。

此结果大超出了非尾递归的818限制,参数是10000也没问题,因它采用尾递归,代码根本没有膨胀,而是依次计算。首先是在过程内部绑定了一个过程f,它有两个参数,一个i的值来自sum过程的参数n,另一个参数a定义值为1,当i值不等于时,仍调用f,第一个参数(也就是i)减1,第二个参数(也就是a)的值在原来的基础上加上i,当i的值为1是返回a,也就此sum过程的结果。理解这些后,你会发现事实上尾递归是在过程的绑定和过程的参数上做文章,用参数来保存运算结果,递归调用绑定的过程,最终达到运算目的。






回页首




三、关于过程参数的问题

过程的多参数问题对初学者不太好理解,一般情况下我们处理过程时,过程参数的数量是固定的,当过程的参数数量不固定时怎么办呢?对了,时刻记住列表,把过程的参数做为一个列表来处理,如求和过程:(sum arg1 arg2 ...),(初学者可能对如何实现定义这样的过程无从下手不知所措),我们如何来求这些参数的和呢?看下面的代码:

guile> (define sum (lambda args (apply + args)))
guile> sum
#
guile> (sum 1 2 3 4 5)
15



从中可以看出,lambda的格式有所变化,由原来的((lambda arg1 arg2 ...) body ...)变成了(lambda args body ...),也就是将原来的多个项组成的列表,改成了用一个名称args来标识的列表,其本质并没有变,变的是我们的方法,由原来的单项处理变成了统一处理的列表。

这里还用到了for-each过程,通过下面代码来看一下for-each过程的一般用法:

guile> (define newdisplay (lambda (x) (begin (display x)(newline))))
guile> newdisplay
#
guile> (define tt (lambda args (for-each newdisplay args)))
guile> tt
#
guile> (tt 'abc 'efg 'tomson)
abc
efg
tomson



for-each过程的一般用法是(for-each 过程 列表),此中的过程可以是我们自定义的,也可以是系统提供的,还可以是lambda 表达式。

栈结构是一种简单而又有意义的数据结构,我们可以用列表来模拟一个简单的栈,下面是代码:

#! /usr/local/bin/guile -s
!#
(define stack '())
(define push!
(lambda (x)
(set! stack (cons x stack))))
(define pop!
(lambda ()
(let ((temp (car stack)))
(set! stack (cdr stack))
temp)))
(push! 9)
(push! 8)
(push! 7)
(display stack) (newline)
(display (pop!)) (newline)
(display stack) (newline)



结果如下:

(7 8 9)
7
(8 9)



这里面我们定义了一个变量stack来表示栈,定义一个过程push!向栈内压数据,同时还定义了一个过程pop!来从栈内弹出数据,完成了基本的栈功能。这段代码的缺点是要定义一个外部的变量来表示栈,同时还有两个过程,如果创建多个栈的话就需要更多的过程和变量了,这在某些情况下是不可想象的,如果程序中要用100个栈,我们就不得不100次复制和更改上面的代码。如何解决这一问题呢?看下面的代码:

#! /usr/local/bin/guile -s
!#
(define make-stack
(lambda ()
(let ((st '()))
(lambda (process arg)
(case process
((push!) (begin
(set! st (cons arg st))
st))
((pop!) (let ((temp (car st)))
(set! st (cdr st))
temp))
((view) (display st))
(else "error!"))))))
(define s (make-stack))
(display (s 'push! 9)) (newline)
(display (s 'push! 8)) (newline)
(display (s 'push! 7)) (newline)
(display (s 'pop! 0)) (newline)
(s 'view 0) (newline)



结果如下:

(9)
(8 9)
(7 8 9)
7
(8 9)



在上面代码中定义的make-stack过程,它的形式是一种特殊的情况,在lambda表达式里面又嵌有lambda表达式,在使用这类过程时,先要调用这一过程定义一个变量(这个变量其实就是第二个lambda表达式),然后将这个变量再做为一个过程来直接调用(事实上也就是生成了一个过程),就像代码中的(s 'push 9) 。

我们首先绑定了一个变量st为空值做为栈的基础,与栈有关的操作都围绕它展开,这样的话前面提到代码重复问题就不会出现了,你可以定义任意多个栈。这段代码里还用到了case结构,它有点像C语言中的switch语句,用它判断第二个lambda表达式的第一个参数,也就是要对栈的操作,在调用时要用符号变量来使用,否则会出错,因为'push结果就是push,所以在过程定义中直接使用push,而调用时用'push。从这段代码中你会意识到变量和符号的重要性了。

这段代码中我们仍用上面代码的形式,用列表来模拟栈,因为这更能体现栈的原理和列表这一Scheme语言的基础数据类型的做用。细心的读者朋友会发现我们对栈进行pop操作时的调用是(s 'pop! 0),而正确的操作应该是(s 'pop!),'view也同样;这是因为我们第二个lambda表达式是lambda (process arg),为了不出错,不得不用这样的调用,如果将第二个lambda表达式改为lambda (process . arg)就可以避免这种尴尬情况了,但结果可能并不是我们想要的,栈会变成((7) (8) (9))这种情况。

如何更好的实现一个栈呢?对了,改变现有的形式,使用list(不用原始的cons)或vector来模拟,将 lambda (process arg) 改成 (process . arg) 或 (process . args) (注意,这两者可不一样啊!),这就要看你对栈结构的理解和编码水平了,相信参照这一代码你会模拟出更实用更快捷的栈结构来的。(本文代码中有一个用list来模拟栈结构的稍完整的代码) 这里我们还会发现一个小小的惯例,如果过程要更改变量的值,那么它的过程名后一定要加一个!;而如果过程是一个判断,结果为逻辑值时,它的过程名后一定要加一个?,这会使别人很快理解你的代码。






回页首




四、关于continuation

Scheme语言相对Lisp语言的重要特征是提出并实现了continuation,这是让初学者最难理解,也是最让程序员心动的特征。那么Continuation到底是什么呢?在运算Scheme表达式过程中,我们必须跟踪两个东西:1、运算什么?2、什么与值相关?看一看下面表达式的计算: (if (null? x) (quote ()) (car x)) 。其中首先要运算的是(null? x),然后在这个值的基础上再运算(quote ())或(cdr x),要运算的是(null? x)而与值相关的是(quote ())和(car x);这里把与值相关的称为运算的continuation。我们看(null? x)表达式中与值相关的东西就有三个,1、表达式本身,结果为#t或#f;2、过程null?,它是一个lambda表达式;3、变量x,它应用当有一个值。那么上面的表达式里面有几个continuation呢?答案是六个,上面的表达式本身,我们说过的三个,car也是一个lambda表达式,还有它后面的x,也和值相关;而(car x)没有计算在内,因为它与上面表达式结果之一是相同的。

在任何表达式中,Continuation可以用一个叫call-with-current-continuation的过程来得到,多数情况下它被简化为call/cc。在guile的1.6.4或以前版本中,简化代码如下所示:

(define call/cc call-with-current-continuation)



而在其它的Scheme语言的实现版本中完全可以不用这样定义,而直接使用call/cc。

call/cc过程的唯一个参数应该是一个过程(或lambda表达式),而且这个过程只能有一个参数,continuation就绑定在这个参数上。看下面的代码:

guile> (define call/cc call-with-current-continuation)
guile> call/cc
#
guile> (call/cc (lambda (k) 5))
5
;;;此时过程参数k未用到,所以取过程的返回值5做为结果
guile> (call/cc (lambda (k) (* 5 (k 8))))
8
;;;此时过程参数k绑定为8,所以其结果为8
guile> (+ 2 (call/cc (lambda (k) (* 5 (k 8)))))
10
;;;此时结果在我们意料之中了



可以利用call/cc这一特点,让它从一个循环中跳出来,这有点像C语言中的break,看下面的代码:

guile> (call/cc (lambda (return)
(for-each (lambda (x) (if (< x 0) (return x)))
'(99 88 77 66 55))
#t))
#t



其结果为#t,因为for-each运算过程中未出现过(< x 0)的情况,所以(lambda (return ) ...)的结果为#t,call/cc取此值为最终结果。

guile> (call/cc (lambda (return)
(for-each (lambda (x) (if (< x 0) (return x)))
'(11 22 33 44 -55 66 77))
#t))
-55



其结果为-55,因为当遇到小于0的数时,return就绑定x,call/cc就返回此值,即从for-each处理过程中跳出来,这是call/cc的重要功能之一,也是最基本的功能。

call/cc 还可以这样操作:

guile> (define foo #f)
guile> (call/cc (lambda (bar) (set! foo bar) 123))
123
guile> (foo 456)
456
guile> (foo 'abc)
abc



上面的操作中,call/cc绑定了lambda表达式的参数bar,而后我们又设定foo的值为bar,此时foo即为一个灵活的continuation;最后我们又让lambda表达式的值为123,所以整个call/cc表达式的值为123,如果我们不加这个123而直接结束这个表达式的话,此表达式就没有结果,不返回任何值。

当foo成为一个continuation后,我们可以象调用过程那样来调用它(当然它并不是过程),其后面绑定的值即为此continuation的结果,如上面的代码运行所示。

这段代码的前提是有call/cc的定义,如果你直接运行guile后就输入上面的代码是肯定会出错的。

在赵蔚的文章 http://www.ibm.com/developerworks/cn/linux/l-scheme/part2/index.shtml中提到过由David Madore先生提出的"阴阳迷题",下面我们通过对它的研究来理解一下continuation,代码如下所示(为解释方便,稍做改动):

(let* ((yin ((lambda (foo) (display "@") foo) (call/cc (lambda (bar) bar))))
(yang ((lambda (foo) (display "*") foo) (call/cc (lambda (bar) bar)))))
(yin yang))



我们进行一些简化,将其中的lambda表达式定义为过程,使其看起来更清晰:

(define bar (lambda (bar) bar))
(define foox (lambda (foo) (display "@") foo))
(define fooy (lambda (foo) (display "*") foo))



则上面的繁琐的表达式可以变成为:

(let* ((yin (foox (call/cc bar)))
(yang (fooy (call/cc bar))))
(yin yang))



将let*改变成let,使其进一步简化为:

(let ((yin (foox (call/cc bar))))
(let ((yang (fooy (call/cc bar))))
(yin yang)))



最后将let去掉,继而成为:

((foox (call/cc bar)) (fooy (call/cc bar)))



经过这一翻简化处理(对初学者是有必要的),相信我们对Scheme语言会有新的认识。需要说明的是每一次简化后,都要运行一下,保证它的结果如下所示,否则说明我们简化过程中有错误:

@*@**@***@****@*****@******@*******@********@*********@********** ......



在理解continuation之前,这一结果是我们无论如何也想不到的,如果你有足够奈心的话,你会发现它会按这一规律无限的延长,在我的老机上从11:20一直到15:20仍无迹象表明要停止。

为什么会出现这一结果呢?首先看看我们为了简化而定义的三个过程bar、foox和fooy,bar是Scheme语言中最简单的过程,只有一个参数,并且返回这个参数;foox和fooy比它们只多了一步,执行完一个display过程后再返回这个参数;这样简单的两个过程确出现如此复杂的结果,原因全在call/cc身上。

首先,看(call/cc bar)表达式,它形成了一个灵活的continuation,用它来做foox的参数,表达式(foox (call/cc bar))则形成一个新的灵活的continuation,即显示一个@字符同时也是一个continuation。

再看,表达式((call/cc bar) (foox bar))的结果与表达式((foox bar) (foox bar))的结果相同,均为显示两个@字符,同时返回一个过程#,这就让我们在某种程度上理解了表达式(call/cc procedure?)的结果为#t了,因为(procedure? procedure?)也为#t;而(call/cc boolean?)则不然,因为(boolean? boolean?)为#f。

从上面我们可以看出表达式((call/cc bar) (foox (call/cc bar)))实际则是与表达式((foox (call/cc bar)) (foox (call/cc bar))),运行一下会发现,两者确实相同,显示@字符,无穷无尽,看来(call/cc bar)这个参数起到了关键作用。那么再看我们的阴阳表达式((foox (call/cc bar)) (fooy (call/cc bar))),前者(foox (call/cc bar))为一个显示字符@的continuation,我们表示为*cc;后者(fooy (call/cc bar))为一个显示字符*的continuation,我们表示为*cc;则在@cc的调动指挥下,每次*cc再加下一个(fooy (call/cc bar)),形成**cc,再加后,如此形成我们前面的效果。过程如下所示:

@cc *cc
@cc **cc
@cc ***cc
@cc ****cc 一直至无穷尽



前一段时间,"晕"这个字总会出现在网友的聊天中,相信现在不"晕"了。我们给上面的代码改动一下:

#! /usr/local/bin/guile -s
!#
(define call/cc call-with-current-continuation)
(define n 0)
(define bar (lambda (bar) bar))
(define foo (lambda (foo) (display n) (newline) (set! n (+ n 1)) foo))
((call/cc bar) (foo (call/cc bar)))



这样形成了,0 1 2 3 4 ......无限制的循环,由此我们解决了一个不用循环语句来形成循环的问题。






回页首




五、关于记录类型

在guile中提供了很多复杂的复合类型,如record,struct,hashtable,array等等,record类型是其中较简单的一种,我们这里称之为记录类型,这种类型有点像C语言中的结构,更像C++中的类。通过它我们可以了解一些面向对象思想在Scheme语言中的应用。记录类型包括九个相关过程,以下是简单介绍:

record? 记录类型的判断过程
make-record-type 创建记录类型,两个参数,类型的名称和类型的成员名称列表
record-constructor 创建记录类型构建过程,一个参数,类型
record-predicate 创建记录类型的判断过程,用此过程某一变量是否为已创建的记录类型
record-accessor 创建记录类型的get系列过程,两个参数,类型和表示成员名称的符号
record-modifier 创建记录类型的set系列过程,同上
record-type-descriptor 一般不用,可忽略
record-type-name 取得记录类型的名字,返回字符串
record-type-fields 取得记录类型的成员名字列表

要想知道如何定义一个记录类型和上面提到的相关过程的用法,具体代码是必不可少的,下面是一个简单的示例:

#! /usr/local/bin/guile -s
!#
(define girl (make-record-type "girl" '(name info)))
;;定义record类型girl,包含两个成员name和info,其中name为一字符串,info为一过程用来显示信息
(define girl-init! (record-constructor girl))
;;定义girl的初始化过程
(define girl-name-get (record-accessor girl 'name))
;;定义取得girl类型的name成员的值的过程
(define girl-name-set! (record-modifier girl 'name))
;;定义设定girl类型的name成员的值的过程
(define girl-info-get (record-accessor girl 'info))
;;定义取得girl类型的info成员的值的过程
(define girl-info-set! (record-modifier girl 'info))
;;定义设定girl类型的info成员的值的过程
(define hi
(lambda (name)
(display "Hi! I'm ")
(display name)
(display ".")))
;;定义hi过程,显示"Hi! I'm " 加字符串 name 加 "."
(define g (girl-init! "Lucy" hi))
;;定义一个girl类型的变量g,其成员name值为"Lucy",成员info值为上面定义的hi过程
((girl-info-get g) (girl-name-get g)) (newline)
;;取得girl类型变量g的info成员,做为过程来执行它,取得girl类型变量g的name成员做为此过程的参数



这段代码的运行结果为: Hi! I'm Lucy.

代码中的注释相信大家都能看懂,需要说的是当我们用定义一个用make-record-type创建的记录类型后,就可以用record?来判断此类型是否为记录类型了,即 (record? girl) ==> #t 。

还有就是可以用代码 (define girl? (record-predicate girl)) 来定义一个此记录类型girl的判断过程girl?,也就是 (girl? g) ==> #t 。

还有就是下面的结果也应该在我们的想象之中:

(record-type-name girl) ==> "girl"
(record-type-fields girl) ==> (name info)



从这个简单的例子来看,记录类型已经具备了面向对象的编程思想所要求的一些必备的东西,而且更具有Scheme语言自己的特色。相信在我的这个例子基础上你可以创建一个更优秀的girl来。






回页首




六、关于宏定义

Scheme语言中的宏定义类似于自己定义一个Scheme语言关键字,可以实现不同的功能,很多关键字都可以通过宏定义来实现,我们在多数参考资料中都可以看到这样的例子。

在多数Scheme语言的实现中,都提供了不同形式的宏定义功能,在guile中提供了用defmacro或define-macro来定义宏,defmacro的格式为:

(defmacro name (args ...) body ...)



它等同于

(define-macro (name args ...) body ...)



我们来看一个简单的宏定义:

#! /usr/local/bin/guile -s
!#
(define-macro (defobj name)
`(begin
(define ,(string->symbol (string-append "make-" name))
(lambda ()
(display "make object ok!\n")))
(define ,(string->symbol (string-append name "?"))
(lambda (obj)
(if (eq? obj 'name)
#t
#f)))))
(defobj "foo")
(make-foo)
(display (foo? 'name)) (newline)
这段程序的运行结果如下:
make object ok!
#t



从这段代码中你可能看到了逆符号(quasiquote)以及相关的操作的重要性了,这里我们定义了一个宏defobj,当运行完(defobj "boy")这个宏时,产生了两个过程定义即make-foo和foo?,从这一点上来看,高性能的宏定义可以大大减轻我们代码的重复使用的麻烦。还有就是guile系统中很多宏定义都是按上面的宏定义方式来进行的。

在Scheme语言中,R5RS中的宏定义是通用的标准,guile中通过调用syncase模块来实现这一功能,你需要在代码中加入:(use-modules (ice-9 syncase)) 来调用ice-9目录下的syncase模块。

下面的R5RS格式的宏定义实现了前面提到的sum功能和一个列表定义功能,它都有多参数的特点,这在R5RS宏观定义中很容易实现:

#! /usr/local/bin/guile -s
!#
(use-modules (ice-9 syncase))
(define-syntax sum
(syntax-rules ()
((_ exp1 exp2 ...)
(+ exp1 exp2 ...))))
(display (sum 1 2 3 4 5)) (newline)
(define-syntax ourlst
(syntax-rules ()
((_ exp)
(cons exp '()))
((_ exp1 exp2 ...)
(cons exp1 (ourlst exp2 ...)))))
(display (ourlst 1 2 3 4 5)) (newline)



上面代码的结果如下:

15
(1 2 3 4 5)



在sum宏定义中,如果附合规则(_ exp1 exp2 ...)或(sum exp1 exp2 ...)将按(+ exp1 exp2 ...)的方式来处理,其中exp1、exp2表示Scheme表达式,而省略号 ... 则表示更多的表达式。也就是说 (sum 1 2 3 4 5)将按(+ 1 2 3 4 5)来处理,其结果为15。在ourlst宏中则有两个规则,第一是只有一个参数的情况,第二是多参数的情况,在多参数情况下还用到了递归,相信大家都能理解。

这是按R5RS标准来实现的最简单的两个宏(当然还有我在概要一文中提到的糟糕的start宏),相信通过这两个宏的定义,您会理解并能进行宏定义了。






回页首




七、关于模块

上面提到的syncase模块是如何实现的呢?多数Scheme语言的实现版本都提供了一套模块系统,guile也不例外,看一看下面的简单的模块定义:

;;;file : tt.scm , a module test here .
(define-module (ice-9 tt)
:export (newdisplay))
(define newdisplay
(lambda (str)
(display str)
(newline)))



将其以tt.scm文件名保存。这段代码中,首先用define-module表示定义一个模块,而(ice-9 tt)则指明了模块的具体位置和名称,最后:export指出模块中要导出的过程等的名称,这们这里只有一个newdisplay,可以用列表来形成多个导出过程名。而下面的代码则和我们普通的过程定义代码相同,简单的定义了一个名为newdisplay的过程,功能是在要显示的东西后面加一个换行符。

我们再编写一段代码来测试一下这个模块:

#! /usr/local/bin/guile -s
!#
(use-modules (ice-9 tt))
(newdisplay "test use tt modules")



这段代码中用usemodules来调用我们上面定义的tt模块,以test_tt.scm文件名保存,运行后会出现错误信息: ERROR: no code for module (ice-9 tt) 。

这是因为,默认情况下,模块所在目录为/usr/local/share/guile/1.6/ice-9 或 /usr/share/guile/1.6/ice-9 。执行命令: cp tt.scm /usr/local/share/guile/1.6/ice-9/ ,将模块文件复制到相应目录,再执行test_tt.scm文件,其输出结果如下:(输出字符串自动换行了)

test use tt modules



这说明我们成功的定义了一个模块。我们在宏定义时用的syncase模块实际上就是在/usr/local/share/guile/1.6/ice-9目录中的syncase.scm文件,研究一下此目录中的scm文件会发现很多定义模块的技巧。






回页首




八、关于eval

在概要一文中还没有提到的是eval这个过程的用法,利用它可以实现用Scheme语言本身来解释Scheme表达式的功能,这对一个学习编译系统和Scheme语法功能的实现非常重要。下面是在guile中运行eval过程来解释Scheme表达式的情况:

guile> (primitive-eval '(+ 2 3))
5
guile> (eval '(+ 1 2) (interaction-environment))
3



这里面包含了两个版本的eval过程,首先是原始的guile内部使用的primitive-eval,它可以直接解释运行Scheme表达式;第二个是正常的eval过程,它需要两个参数,一个是要解释运行的要Scheme表达式,第二个是表达式运行的环境,可以由interaction-environment过程来获得,如此则eval过程正常运行。

可以想象用C语言来写C语言编译器对初学者来说的难度,但掌握Scheme语法和eval的用法后,你会发现用Scheme语言来写一个Scheme语言解释器并不是很难,这可能成为你理解编译原理的重要一步。

我们在感觉到Scheme语言的简单易用的同时,还应该意识到它是一门富于挑战意义的语言,相信现在我们能够真正理解Scheme挑战意义的所在了吧。(本文涉及到了Scheme语言中大多数的稍复杂一些的内容,还请热爱Scheme语言的朋友们多多指正。)

Scheme 语言概要

作为Lisp 变体,Scheme 是一门非常简洁的计算语言,使用它的编程人员可以摆脱语言本身的复杂性,把注意力集中到更重要的问题上,从而使语言真正成为解决问题的工具。本文分为上、 下两部分来介绍 scheme 语言。

一.Scheme语言的特点

Scheme语言是LISP语言的一个方言(或说成变种),它诞生于1975年的MIT,对于这个有近三十年历史的编程语言来说,它并没有象C++,java,C#那样受到商业领域的青睐,在国内更是显为人知。但它在国外的计算机教育领域内却是有着广泛应用的,有很多人学的第一门计算机语言就是Scheme语言。

它是一个小巧而又强大的语言,作为一个多用途的编程语言,它可以作为脚本语言使用,也可以作为应用软件的扩展语言来使用,它具有元语言特性,还有很多独到的特色,以致于它被称为编程语言中的"皇后"。

下面是洪峰对Scheme语言的编程特色的归纳:

词法定界(Lexical Scoping)
动态类型(Dynamic Typing)
良好的可扩展性
尾递归(Tail Recursive)
函数可以作为值返回
支持一流的计算连续
传值调用(passing-by-value)
算术运算相对独立
本文的目的是让有编程基础(那怕是一点点)的朋友能尽快的掌握Scheme语言的语法规则,如果您在读完本文后,发现自己已经会用Scheme语言了,那么我的目的就达到了。






回页首




二.Scheme语言的标准与实现

R5RS (Revised(5) Report on the Algorithmic Language Scheme)

Scheme语言的语法规则的第5次修正稿,1998年制定,即Scheme语言的现行标准,目前大多数Scheme语言的实现都将达到或遵循此标准,并且几乎都加入了一些属于自己的扩展特色。

Guile (GNU's extension language)

Guile是GNU工程的一个项目,它是GNU扩展语言库,它也是Scheme语言的一个具体实现;如果你将它作为一个库打包,可以把它链接到你的应用程序中去,使你的应用程序具有自己的脚本语言,这个脚本语言目前就是Scheme语言。

Guile可以在LINUX和一些UNIX系统上运行,下面是简单的安装过程:

下载guile-1.6.4版,文件名为guile-1.6.4.tar.gz,执行下面的命令:

tar xvfz guile-1.6.4.tar.gz
cd guile-1.6.4
./configure
make
make install



如此,即可以执行命令guile,进入guile>提示符状态,输入调试Scheme程序代码了,本文的所有代码都是在guile下调试通过。

其它实现

除了Guile外,Scheme语言的实现还有很多,如:GNU/MIT-Scheme, SCI,Scheme48,DrScheme等,它们大多是开源的,可以自由下载安装使用,并且跨平台的实现也很多。你会发现既有象basic的Scheme语言解释器,也有将Scheme语言编译成C语言的编译器,也有象JAVA那样将Scheme语言代码编译成虚拟机代码的编译器。






回页首




三.基本概念

注释

Scheme语言中的注释是单行注释,以分号[;]开始一直到行尾结束,其中间的内容为注释,在程序运行时不做处理,如:

; this is a scheme comment line.



标准的Scheme语言定义中没有多行注释,不过在它的实现中几乎都有。在Guile中就有多行注释,以符号组合"#!"开始,以相反的另一符号组合"!#"结束,其中内容为注释,如:

#!
there are scheme comment area.
you can write mulity lines here .
!#



注意的是,符号组合"#!"和"!#"一定分做两行来写。

Scheme用做脚本语言

Scheme语言可以象sh,perl,python等语言那样作为一种脚本语言来使用,用它来编写可执行脚本,在Linux中如果通过Guile用Scheme语言写可执行脚本,它的第一行和第二行一般是类似下面的内容:

#! /usr/local/bin/guile -s
!#


这样的话代码在运行时会自动调用Guile来解释执行,标准的文件尾缀是".scm"。

块(form)

块(form)是Scheme语言中的最小程序单元,一个Scheme语言程序是由一个或多个form构成。没有特殊说明的情况下 form 都由小括号括起来,形如:

(define x 123)
(+ 1 2)
(* 4 5 6)
(display "hello world")



一个 form 也可以是一个表达式,一个变量定义,也可以是一个过程。

form嵌套

Scheme语言中允许form的嵌套,这使它可以轻松的实现复杂的表达式,同时也是一种非常有自己特色的表达式。下图示意了嵌套的稍复杂一点的表达式的运算过程:




变量定义

可以用define来定义一个变量,形式如下:
(define 变量名 值)

如: (define x 123) ,定义一个变量x,其值为123。

更改变量的值

可以用set!来改变变量的值,格式如下:
(set! 变量名 值)

如: (set! x "hello") ,将变量x的值改为"hello" 。

Scheme语言是一种高级语言,和很多高级语言(如python,perl)一样,它的变量类型不是固定的,可以随时改变。






回页首




四.数据类型

1. 简单数据类型

逻辑型(boolean)

最基本的数据类型,也是很多计算机语言中都支持的最简单的数据类型,只能取两个值:#t,相当于其它计算机语言中的 TRUE;#f,相当于其它计算机语言中的 FALSE。

Scheme语言中的boolean类型只有一种操作:not。其意为取相反的值,即:

(not #f) => #t
(not #t) => #f



not的引用,与逻辑非运算操作类似

guile> (not 1)
#f
guile> (not (list 1 2 3))
#f
guile> (not 'a)
#f



从上面的操作中可以看出来,只要not后面的参数不是逻辑型,其返回值均为#f。

数字型(number)

它又分为四种子类型:整型(integer),有理数型(rational),实型(real),复数型(complex);它们又被统一称为数字类型(number)。

如:复数型(complex) 可以定义为 (define c 3+2i)
实数型(real)可以定义为 (define f 22/7)
有理数型(rational)可以定义为 (define p 3.1415)
整数型(integer) 可以定义为 (define i 123)

Scheme语言中,数字类型的数据还可以按照进制分类,即二进制,八进制,十进制和十六进制,在外观形式上它们分别以符号组合 #b、 #o、 #d、 #x 来作为表示数字进制类型的前缀,其中表示十进制的#d可以省略不写,如:二进制的 #b1010 ,八进制的 #o567,十进制的123或 #d123,十六进制的 #x1afc 。

Scheme语言的这种严格按照数学定理来为数字类型进行分类的方法可以看出Scheme语言里面渗透着很深的数学思想,Scheme语言是由数学家们创造出来的,在这方面表现得也比较鲜明。

字符型(char)

Scheme语言中的字符型数据均以符号组合 "#\" 开始,表示单个字符,可以是字母、数字或"[ ! $ % & * + - . / : %lt; = > ? @ ^ _ ~ ]"等等其它字符,如:
#\A 表示大写字母A,#\0表示字符0,
其中特殊字符有:#\space 表示空格符和 #\newline 表示换行符。

符号型(symbol)

符号类型是Scheme语言中有多种用途的符号名称,它可以是单词,用括号括起来的多个单词,也可以是无意义的字母组合或符号组合,它在某种意义上可以理解为C中的枚举类型。看下面的操作:

guile> (define a (quote xyz)) ; 定义变量a为符号类型,值为xyz
guile> a
xyz
guile> (define xyz 'a) ; 定义变量xyz为符号类型,值为a
guile> xyz
a



此处也说明单引号' 与quote是等价的,并且更简单一些。符号类型与字符串不同的是符号类型不能象字符串那样可以取得长度或改变其中某一成员字符的值,但二者之间可以互相转换。

2. 复合数据类型

可以说复合数据类型是由基本的简单数据类型通过某种方式加以组合形成的数据类型,特点是可以容纳多种或多个单一的简单数据类型的数据,多数是基于某一种数学模型创建的。

字符串(string) 由多个字符组成的数据类型,可以直接写成由双引号括起的内容,如:"hello" 。下面是Guile中的字符串定义和相关操作:

guile> (define name "tomson")
guile> name
"tomson"
guile> (string-length name) ; 取字符串的长度
6
guile> (string-set! name 0 #\g) ; 更改字符串首字母(第0个字符)为小写字母g (#\g)
guile> name
"gomson"
guile> (string-ref name 3) ; 取得字符串左侧第3个字符(从0开始)
#\s



字符串还可以用下面的形式定义:

guile> (define other (string #\h #\e #\l #\l #\o ))
guile> other
"hello"



字符串中出现引号时用反斜线加引号代替,如:"abc\"def" 。

点对(pair)

我把它译成"点对",它是一种非常有趣的类型,也是一些其它类型的基础类型,它是由一个点和被它分隔开的两个所值组成的。形如: (1 . 2) 或 (a . b) ,注意的是点的两边有空格。

这是最简单的复合数据类型,同是它也是其它复合数据类型的基础类型,如列表类型(list)就是由它来实现的。

按照Scheme语言说明中的惯例,以下我们用符号组合 "=>" 来表示表达式的值。

它用cons来定义,如: (cons 8 9) =>(8 . 9)

其中在点前面的值被称为 car ,在点后面的值被称为 cdr ,car和cdr同时又成为取pair的这两个值的过程,如:

(define p (cons 4 5)) => (4 . 5)
(car p) => 4
(cdr p) => 5



还可以用set-car! 和 set-cdr! 来分别设定这两个值:

(set-car! p "hello")
(set-cdr! p "good")



如此,以前定义的 p 又变成了 ("hello" . "good") 这个样子了。

列表(list)

列表是由多个相同或不同的数据连续组成的数据类型,它是编程中最常用的复合数据类型之一,很多过程操作都与它相关。下面是在Guile中列表的定义和相关操作:

guile> (define la (list 1 2 3 4 ))
guile> la
(1 2 3 4)
guile> (length la) ; 取得列表的长度
4
guile> (list-ref la 3) ; 取得列表第3项的值(从0开始)
4
guile> (list-set! la 2 99) ; 设定列表第2项的值为99
99
guile> la
(1 2 99 4)
guile> (define y (make-list 5 6)) ;创建列表
guile> y
(6 6 6 6 6)



make-list用来创建列表,第一个参数是列表的长度,第二个参数是列表中添充的内容;还可以实现多重列表,即列表的元素也是列表,如:(list (list 1 2 3) (list 4 5 6))。

列表与pair的关系

回过头来,我们再看看下面的定义:

guile> (define a (cons 1 (cons 2 (cons 3 '()))))
guile> a
(1 2 3)



由上可见,a本来是我们上面定义的点对,最后形成的却是列表。事实上列表是在点对的基础上形成的一种特殊格式。

再看下面的代码:

guile> (define ls (list 1 2 3 4))
guile> ls
(1 2 3 4)
guile> (list? ls)
#t
guile> (pair? ls)
#t



由此可见,list是pair的子类型,list一定是一个pair,而pair不是list。

guile> (car ls)
1
guile> (cdr ls)
(2 3 4)



其cdr又是一个列表,可见用于pair的操作过程大多可以用于list。

guile> (cadr ls) ; 此"点对"对象的cdr的car
2
guile> (cddr ls) ; 此"点对"对象的cdr的cdr
(3 4)
guile> (caddr ls) ; 此"点对"对象的cdr的cdr的car
3
guile> (cdddr ls) ; 此"点对"对象的cdr的cdr的cdr
(4)



上在的操作中用到的cadr,cdddr等过程是专门对PAIR型数据再复合形成的数据操作的过程,最多可以支持在中间加四位a或d,如cdddr,caaddr等。

下图表示了由pairs定义形成的列表:




这个列表可以由pair定义为如下形式:

(define x (cons 'a (cons 'b (cons 'c (cons 'd '())))))



而列表的实际内容则为:(a b c d)

由pair类型还可以看出它可以轻松的表示树型结构,尤其是标准的二叉树。

向量(vector)

可以说是一个非常好用的类型 ,是一种元素按整数来索引的对象,异源的数据结构,在占用空间上比同样元素的列表要少,在外观上:

列表示为: (1 2 3 4)
VECTOR表示为: #(1 2 3 4)
可以正常定义:(define v (vector 3 4 5))
也可以直接定义:(define v #(3 4 5))

vector是一种比较常用的复合类型,它的元素索引从0开始,至第 n-1 结束,这一点有点类似C语言中的数组。

关于向量表(vector)的常用操作过程:

guile> (define v (vector 1 2 3 4 5))
guile> v
#(1 2 3 4 5)
guile> (vector-ref v 0) ; 求第n个变量的值
1
guile> (vector-length v) ; 求vector的长度
5
guile> (vector-set! v 2 "abc") ; 设定vector第n个元素的值
guile> v
#(1 2 "abc" 4 5)
guile> (define x (make-vector 5 6)) ; 创建向量表
guile> x
#(6 6 6 6 6)



make-vector用来创建一个向量表,第一个参数是数量,后一个参数是添充的值,这和列表中的make-list非常相似。

我们可以看出,在Scheme语言中,每种数据类型都有一些基本的和它相关的操作过程,如字符串,列表等相关的操作,这些操作过程都很有规律,过程名的单词之间都用-号隔开,很容易理解。对于学过C++的朋友来说,更类似于某个对象的方法,只不过表现的形式不同了。

3. 类型的判断、比较、运算、转换与方法

类型判断

Scheme语言中所有判断都是用类型名加问号再加相应的常量或变量构成,形如:

(类型? 变量)



Scheme语言在类型定义中有比较严格的界定,如在C语言等一些语言中数字0来代替逻辑类型数据False,在Scheme语言中是不允许的。

以下为常见的类型判断和附加说明:

逻辑型:

(boolean? #t) => #t
(boolean? #f) => #t 因为#t和#f都是boolean类型,所以其值为#t
(boolean? 2) => #f 因为2是数字类型,所以其值为 #f



字符型

(char? #\space) => #t
(char? #\newline) => #t 以上两个特殊字符:空格和换行
(char? #\f) => #t 小写字母 f
(char? #\;) => #t 分号 ;
(char? #\5) => #t 字符 5 ,以上这些都是正确的,所以返回值都是 #t
(char? 5) => #f 这是数字 5 ,不是字符类型,所以返回 #f



数字型

(integer? 1) => #t
(integer? 2345) => #t
(integer? -90) => #t 以上三个数均为整数
(integer? 8.9) => #f 8.9不整数
(rational? 22/7) => #t
(rational? 2.3) => #t
(real? 1.2) => #t
(real? 3.14159) => #t
(real? -198.34) => #t 以上三个数均为实数型
(real? 23) => #t 因为整型属于实型
(number? 5) => #t
(number? 2.345) => #t
(number? 22/7) => #t



其它型

(null? '()) => #t ; null意为空类型,它表示为 '() ,即括号里什么都没有的符号
(null? 5) => #f
(define x 123) 定义变量x其值为123
(symbol? x) => #f
(symbol? 'x) => #t ; 此时 'x 为符号x,并不表示变量x的值



在Scheme语言中如此众多的类型判断功能,使得Scheme语言有着非常好的自省功能。即在判断过程的参数是否附合过程的要求。

比较运算

Scheme语言中可以用<,>,<=,>=,= 来判断数字类型值或表达式的关系,如判断变量x是否等于零,它的形式是这样的:(= x 0) ,如x的值为0则表达式的值为#t,否则为#f。

还有下面的操作:

(eqv? 34 34) => #t
(= 34 34) => #t



以上两个form功能相同,说明 eqv? 也可以用于数字的判断。

在Scheme语言中有三种相等的定义,两个变量正好是同一个对象;两个对象具有相同的值;两个对象具有相同的结构并且结构中的内容相同。除了上面提到的符号判断过程和eqv?外,还有eq?和equal?也是判断是否相等的过程。

eq?,eqv?,equal?

eq?,eqv?和equal?是三个判断两个参数是否相等的过程,其中eq?和eqv?的功能基本是相同的,只在不同的Scheme语言中表现不一样。

eq?是判断两个参数是否指向同一个对象,如果是才返回#t;equal?则是判断两个对象是否具有相同的结构并且结构中的内容是否相同,它用eq?来比较结构中成员的数量;equal?多用来判断点对,列表,向量表,字符串等复合结构数据类型。

guile> (define v (vector 3 4 5))
guile> (define w #(3 4 5)) ; w和v都是vector类型,具有相同的值#(3 4 5)
guile> (eq? v w)
#f ; 此时w和v是两个对象
guile> (equal? v w)
#t ; 符合equal?的判断要求



以上操作说明了eq? 和equal? 的不同之处,下面的操作更是证明了这一点:

guile> (define x (make-vector 5 6))
guile> x
#(6 6 6 6 6)
guile> (eq? x x) ; 是同一个对象,所以返回#t
#t
guile> (define z (make-vector 5 6))
guile> z
#(6 6 6 6 6)
guile> (eq? x z) ; 不是同一个对象
#f
guile> (equal? x z) ; 结构相同,内容相同,所以返回#t
#t



算术运算

Scheme语言中的运算符有:
+ , - , * , / 和 expt (指数运算)
其中 - 和 / 还可以用于单目运算,如:

(- 4) => -4
(/ 4) => 1/4



此外还有许多扩展的库提供了很多有用的过程,

max 求最大 (max 8 89 90 213) => 213
min 求最小 (min 3 4 5 6 7) => 3
abs 求绝对值 (abs -7) ==> 7



除了max,min,abs外,还有很多数学运算过程,这要根据你用的Scheme语言的运行环境有关,不过它们大多是相同的。在R5RS中规定了很多运算过程,在R5RS的参考资料中可以很容易找到。

转换

Scheme语言中用符号组合"->"来标明类型间的转换(很象C语言中的指针)的过程,就象用问号来标明类型判断过程一样。下面是一些常见的类型转换过程:

guile> (number->string 123) ; 数字转换为字符串
"123"
guile> (string->number "456") ; 字符串转换为数字
456
guile> (char->integer #\a) ;字符转换为整型数,小写字母a的ASCII码值为96
97
guile> (char->integer #\A) ;大写字母A的值为65
65
guile> (integer->char 97) ;整型数转换为字符
#\a
guile> (string->list "hello") ;字符串转换为列表
(#\h #\e #\l #\l #\o)
guile> (list->string (make-list 4 #\a)) ; 列表转换为字符串
"aaaa"
guile> (string->symbol "good") ;字符串转换为符号类型
good
guile> (symbol->string 'better) ;符号类型转换为字符串
"better"







回页首




五.过程定义

过程(Procedure)

在Scheme语言中,过程相当于C语言中的函数,不同的是Scheme语言过程是一种数据类型,这也是为什么Scheme语言将程序和数据作为同一对象处理的原因。如果我们在Guile提示符下输入加号然后回车,会出现下面的情况:

guile> +
#



这告诉我们"+"是一个过程,而且是一个原始的过程,即Scheme语言中最基础的过程,在GUILE中内部已经实现的过程,这和类型判断一样,如boolean?等,它们都是Scheme语言中最基本的定义。注意:不同的Scheme语言实现环境,出现的提示信息可能不尽相同,但意义是一样的。

define不仅可以定义变量,还可以定义过程,因在Scheme语言中过程(或函数)都是一种数据类型,所以都可以通过define来定义。不同的是标准的过程定义要使用lambda这一关键字来标识。

Lambda关键字

Scheme语言中可以用lambda来定义过程,其格式如下:
(define 过程名 ( lambda (参数 ...) (操作过程 ...)))

我们可以自定义一个简单的过程,如下:

(define add5 (lambda (x) (+ x 5)))



此过程需要一个参数,其功能为返回此参数加5 的值,如:

(add5 11) => 16



下面是简单的求平方过程square的定义:

(define square (lambda (x) (* x x)))



与lambda相同的另一种方式

在Scheme语言中,也可以不用lambda,而直接用define来定义过程,它的格式为:
(define (过程名 参数) (过程内容 …))

如下面操作:

(define (add6 x) (+ x 6))
add6
# 说明add6是一个过程,它有一个参数x
(add6 23) => 29



再看下面的操作:

guile> (define fun
(lambda(proc x y)
(proc x y)))
guile> fun
#
guile> (fun * 5 6)
30
guile> (fun / 30 3)
10



更多的过程定义

上面定义的过程fun有三个参数,其中第一个参数proc也是一个操作过程(因为在Scheme语言中过程也是一种数据,可以作为过程的参数),另外两个参数是数值,所以会出现上面的调用结果。

guile> (define add
(lambda (x y)
(+ x y)))
guile> add
#
guile> (fun add 100 200)
300



继续上面操作,我们定义一个过程add,将add作为参数传递给fun过程,得出和(fun + 100 200)相同的结果。

guile> ((lambda (x) (+ x x)) 5)
10



上面的 (lambda(x) (+ x x)) 事实上是简单的过程定义,在后面直接加上操作参数5,得出结果10,这样实现了匿名过程,直接用过程定义来操作参数,得出运算结果。

通过上面的操作,相信你已初步了解了过程的用法。既然过程是一种数据类型,所以将过程作为过程的参数是完全可以的。以下过程为判断参数是否为过程,给出一个参数,用 procedure? 来判断参数是否为过程,采用if结构(关于if结构见下面的介绍):

guile> (define isp
(lambda (x)
(if (procedure? x) 'isaprocedure 'notaprocedure)))
guile> isp
#
guile> (isp 0)
notaprocedure
guile> (isp +)
isaprocedure



上面的过程就体现了Scheme语言的参数自省(辨别)能力,'0'是数字型,所以返回notaprocedure;而'+'是一个最基础的操作过程,所以返回isaprocedure。

过程的嵌套定义

在Scheme语言中,过程定义也可以嵌套,一般情况下,过程的内部过程定义只有在过程内部才有效,相当C语言中的局部变量。

如下面的代码的最终结果是50:

(define fix
(lambda (x y z)
(define add
(lambda (a b) (+ a b)))
(- x (add y z))))
(display (fix 100 20 30))



此时过程add只在fix过程内部起做用,这事实上涉及了过程和变量的绑定,可以参考下面的关于过程绑定(let,let* 和letrec)的介绍。

过程是初学者难理解的一个关键,随着过程参数的增加和功能的增强,过程的内容变得越来越复杂,小括号也会更多,如果不写出清晰的代码的话,读代码也会成为一个难题。

熟悉了 scheme 基本概念、数据类型和过程(函数)后, 下一部分我们来学习 scheme 的结构、递归调用和其他扩展功能。
一.常用结构

顺序结构

也可以说成由多个form组成的form,用begin来将多个form放在一对小括号内,最终形成一个form。格式为:(begin form1 form2 …)

如用Scheme语言写成的经典的helloworld程序是如下样子的:

(begin
(display "Hello world!") ; 输出"Hello world!"
(newline)) ; 换行



if结构

Scheme语言的if结构有两种格式,一种格式为:(if 测试 过程1 过程2),即测试条件成立则执行过程1,否则执行过程2。例如下面代码:

(if (= x 0)
(display "is zero")
(display "not zero"))



还有另一种格式:(if 测试 过程) ,即测试条件成立则执行过程。例如下面代码:

(if (< x 100) (display "lower than 100"))



根据类型判断来实现自省功能,下面代码判断给定的参数是否为字符串:

(define fun
(lambda ( x )
(if (string? x)
(display "is a string")
(display "not a string"))))



如执行 (fun 123) 则返回值为"not a string",这样的功能在C++或JAVA中实现的话可能会很费力气。

cond结构

Scheme语言中的cond结构类似于C语言中的switch结构,cond的格式为:

(cond ((测试) 操作) … (else 操作))



如下是在Guile中的操作:

guile> (define w (lambda (x)
(cond ((< x 0) 'lower)
((> x 0) 'upper)
(else 'equal))))
guile> w
#
guile> (w 9)
upper
guile> (w -8)
lower
guile> (w 0)
equal



上面程序代码中,我们定义了过程w,它有一个参数x,如果x的值大于0,则返回符号upper,如x的值小于0则返回符号lower,如x 的值为0则返回符号equal。

下载已做成可执行脚本的 例程。

cond可以用if形式来写,上面的过程可以如下定义:

guile> (define ff
(lambda (x)
(if (< x 0) 'lower
(if (> x 0) 'upper 'zero))))
guile> ff
#
guile> (ff 9)
upper
guile> (ff -9)
lower
guile> (ff 0)
zero



这在功能上是和cond一样的,可以看出cond实际上是实现了if的一种多重嵌套。

case结构

case结构和cond结构有点类似,它的格式为:

(case (表达式) ((值) 操作)) ... (else 操作)))

case结构中的值可以是复合类型数据,如列表,向量表等,只要列表中含有表达式的这个结果,则进行相应的操作,如下面的代码:

(case (* 2 3)
((2 3 5 7) 'prime)
((1 4 6 8 9) 'composite))



上面的例子返回结果是composite,因为列表(1 4 6 8 9)中含有表达式(* 2 3)的结果6;下面是在Guile中定义的func过程,用到了case结构:

guile> (define func
(lambda (x y)
(case (* x y)
((0) 'zero)
(else 'nozero))))
guile> func
#
guile> (func 2 3)
nozero
guile> (func 2 0)
zero
guile> (func 0 9)
zero
guile> (func 2 9)
nozero



可以下载另一个脚本文件 te.scm,参考一下。

and结构

and结构与逻辑与运算操作类似,and后可以有多个参数,只有它后面的参数的表达式的值都为#t时,它的返回值才为#t,否则为#f。看下面的操作:

guile> (and (boolean? #f) (< 8 12))
#t
guile> (and (boolean? 2) (< 8 12))
#f
guile> (and (boolean? 2) (> 8 12))
#f



如果表达式的值都不是boolean型的话,返回最后一个表达式的值,如下面的操作:

guile> (and (list 1 2 3) (vector 'a 'b 'c))
#(a b c)
guile> (and 1 2 3 4 )
4
guile> (and 'e 'd 'c 'b 'a)
a



or结构

or结构与逻辑或运算操作类似,or后可以有多个参数,只要其中有一个参数的表达式值为#t,其结果就为#t,只有全为#f时其结果才为#f。如下面的操作:

guile> (or #f #t)
#t
guile> (or #f #f)
#f
guile> (or (rational? 22/7) (< 8 12))
#t
guile> (rational? 22/7)
#t
guile> (real? 22/7)
#t
guile> (or (real? 4+5i) (integer? 3.22))
#f



我们还可以用and和or结构来实现较复杂的判断表达式,如在C语言中的表达式:

((x > 100) && (y < 100)) 和 ((x > 100) || (y > 100))



在Scheme中可以表示为:

guile> (define x 123)
guile> (define y 80)
guile> (and (> x 100) (< y 100))
#t
guile> (or (> x 100) (> y 100))
#t



Scheme语言中只有if结构是系统原始提供的,其它的cond,case,and,or,另外还有do,when,unless等都是可以用宏定义的方式来定义的,这一点充分体现了Scheme的元语言特性,关于do,when等结构的使用可以参考R5RS。






回页首




二.递归调用

用递归实现阶乘

在Scheme语言中,递归是一个非常重要的概念,可以编写简单的代码很轻松的实现递归调用,如下面的阶乘过程定义:

(define factoral (lambda (x)
(if (<= x 1) 1
(* x (factoral (- x 1))))))



我们可以将下面的调用(factoral 4),即4的阶乘的运算过程图示如下:




以下为factoral过程在Guile中的运行情况:

guile> (define factoral (lambda (x) (if (<= x 1) 1 (* x (factoral (- x 1))))))
guile> factoral
#
guile> (factoral 4)
24



另一种递归方式

下面是一另一种递归方式的定义:

(define (factoral n)
(define (iter product counter)
(if (> counter n)
product
(iter (* counter product) (+ counter 1))))
(iter 1 1))
(display (factoral 4))



这个定义的功能和上面的完全相同,只是实现的方法不一样了,我们在过程内部实现了一个过程iter,它用counter参数来计数,调用时从1开始累计,这样它的展开过程正好和我们上面的递归过程的从4到1相反,而是从1到4。

循环的实现

在Scheme语言中没有循环结构,不过循环结构可以用递归来很轻松的实现(在Scheme语言中只有通过递归才能实现循环)。对于用惯了C语言循环的朋友,在Scheme中可以用递归简单实现:

guile> (define loop
(lambda(x y)
(if (<= x y)
(begin (display x) (display #\\space) (set! x (+ x 1))
(loop x y)))))
guile> loop
#
guile> (loop 1 10)
1 2 3 4 5 6 7 8 9 10



这只是一种简单的循环定义,过程有两个参数,第一个参数是循环的初始值,第二个参数是循环终止值,每次增加1。相信读者朋友一定会写出更漂亮更实用的循环操作来的。






回页首




三.变量和过程的绑定

let,let*,letrec

在多数编程语言中都有关于变量的存在的时限问题,Scheme语言中用let,let*和letrec来确定变量的存在的时限问题,即局部变量和全局变量,一般情况下,全局变量都用define来定义,并放在过程代码的外部;而局部变量则用let等绑定到过程内部使用。

用let可以将变量或过程绑定在过程的内部,即实现局部变量:

guile> let
#



从上面的操作可以看出let是一个原始的宏,即guile内部已经实现的宏定义。

下面的代码显示了let的用法(注意多了一层括号):

guile> (let ((x 2) (y 5)) (* x y))
10



它的格式是:(let ((…)…) …),下面是稍复杂的用法:

guile> (let ((x 5))
(define foo (lambda (y) (bar x y)))
(define bar (lambda (a b) (+ (* a b) a)))
(foo (+ x 3)))
45



以上是Guile中的代码实现情况。它的实现过程大致是:(foo 8) 展开后形成 (bar 5 8),再展开后形成 (+ (* 5 8) 5) ,最后其值为45。

再看下面的操作:

guile> (let ((iszero?
(lambda(x)
(if (= x 0) #t #f))))
(iszero? 9))
#f
guile> (iszero? 0) ;此时会显示出错信息



let的绑定在过程内有效,过程外则无效,这和上面提到的过程的嵌套定是一样的,上面的iszero?过程在操作过程内定义并使用的,操作结束后再另行引用则无效,显示过程未定义出错信息。

下面操作演示了let*的用法:

guile> (let ((x 2) (y 5))
(let* ((x 6)(z (+ x y))) ;此时x的值已为6,所以z的值应为11,如此最后的值为66
(* z x)))
66



还有letrec,看下面的操作过程:

guile> (letrec ((even?
(lambda(x)
(if (= x 0) #t
(odd? (- x 1)))))
(odd?
(lambda(x)
(if (= x 0) #f
(even? (- x 1))))))
(even? 88))
#t



上面的操作过程中,内部定义了两个判断过程even?和odd?,这两个过程是互相递归引用的,如果将letrec换成let或let*都会不正常,因为letrec是将内部定义的过程或变量间进行相互引用的。看下面的操作:

guile> (letrec ((countdown
(lambda (i)
(if (= i 0) 'listoff
(begin (display i) (display ",")
(countdown (- i 1)))))))
(countdown 10))
10,9,8,7,6,5,4,3,2,1,listoff



letrec帮助局部过程实现递归的操作,这不仅在letrec绑定的过程内,而且还包括所有初始化的东西,这使得在编写较复杂的过程中经常用到letrec,也成了理解它的一个难点。

apply

apply的功能是为数据赋予某一操作过程,它的第一个参数必需是一个过程,随后的其它参数必需是列表,如:

guile> (apply + (list 2 3 4))
9
guile> (define sum
(lambda (x )
(apply + x))) ; 定义求和过程
guile> sum
#
guile> (define ls (list 2 3 4 5 6))
guile> ls
(2 3 4 5 6)
guile> (sum ls)
20
guile> (define avg
(lambda(x)
(/ (sum x) (length x)))) ; 定义求平均过程
guile> avg
#
guile> (avg ls)
4



以上定义了求和过程sum和求平均的过程avg,其中求和的过程sum中用到了apply来绑定"+"过程操作到列表,结果返回列表中所有数的总和。

map

map的功能和apply有些相似,它的第一个参数也必需是一个过程,随后的参数必需是多个列表,返回的结果是此过程来操作列表后的值,如下面的操作:

guile> (map + (list 1 2 3) (list 4 5 6))
(5 7 9)
guile> (map car '((a . b)(c . d)(e . f)))
(a c e)



除了apply,map以外,Scheme语言中还有很多,诸如:eval,delay,for-each,force,call-with-current-continuation等过程绑定的操作定义,它们都无一例外的提供了相当灵活的数据处理能力,也就是另初学者望而生畏的算法,当你仔细的体会了运算过程中用到的简直妙不可言的算法后,你就会发现Scheme语言设计者的思想是多么伟大。






回页首




四.输入输出

Scheme语言中也提供了相应的输入输出功能,是在C基础上的一种封装。

端口

Scheme语言中输入输出中用到了端口的概念,相当于C中的文件指针,也就是Linux中的设备文件,请看下面的操作:

guile> (current-input-port)
# ;当前的输入端口
guile> (current-output-port)
# ;当前的输出端口



判断是否为输入输出端口,可以用下面两个过程:input-port? 和output-port? ,其中input-port?用来判断是否为输入端口,output-port?用来判断是否为输出端口。

open-input-file,open-output-file,close-input-port,close-output-port这四个过程用来打开和关闭输入输出文件,其中打开文件的参数是文件名字符串,关闭文件的参数是打开的端口。

输入

打开一个输入文件后,返回的是输入端口,可以用read过程来输入文件的内容:

guile> (define port (open-input-file "readme"))
guile> port
#
guile> (read port)
GUILE语言



上面的操作打开了readme文件,并读出了它的第一行内容。此外还可以直接用read过程来接收键盘输入,如下面的操作:

guile> (read) ; 执行后即等待键盘输入
12345
12345
guile> (define x (read)) ; 等待键盘输入并赋值给x
12345
guile> x
12345



以上为用read来读取键入的数字,还可以输入字符串等其它类型数据:

guile> (define name (read))
tomson
guile> name
tomson
guile> (string? name)
#f
guile> (symbol? name)
#t



此时输入的tomson是一个符号类型,因为字符串是用引号引起来的,所以出现上面的情况。下面因为用引号了,所以(string? str)返回值为#t 。

guile> (define str (read))
"Johnson"
guile> str
"Johnson"
guile> (string? str)
#t



还可以用load过程来直接调用Scheme语言源文件并执行它,格式为:(load "filename"),还有read-char过程来读单个字符等等。

输出

常用的输出过程是display,还有write,它的格式是:(write 对象 端口),这里的对象是指字符串等常量或变量,端口是指输出端口或打开的文件。下面的操作过程演示了向输出文件temp中写入字符串"helloworld",并分行的实现。

[root@toymouse test]# guile
guile> (define port1 (open-output-file "temp")) ; 打开文件端口赋于port1
guile> port1
#
guile> (output-port? port1)
#t ; 此时证明port1为输出端口
guile> (write "hello\\nworld" port1)
guile> (close-output-port port1)
guile> (exit) ; 写入数据并关闭退出
[root@toymouse test]# more temp 显示文件的内容,达到测试目的
"hello
world"



在输入输出操作方面,还有很多相关操作,读者可以参考R5RS的文档。






回页首




五.语法扩展

Scheme语言可以自己定义象cond,let等功能一样的宏关键字。标准的Scheme语言定义中用define-syntax和syntax-rules来定义,它的格式如下:

(define-syntax 宏名
(syntax-rules()
((模板) 操作))
. . . ))



下面定义的宏start的功能和begin相同,可以用它来开始多个块的组合:

(define-syntax start
(syntax-rules ()
((start exp1)
exp1)
((start exp1 exp2 ...)
(let ((temp exp1)) (start exp2 ...))) ))



这是一个比较简单的宏定义,但对理解宏定义来说是比较重要的,理解了他你才会进一步应用宏定义。在规则 ((start exp1) exp1) 中,(start exp1) 是一个参数时的模板,exp1是如何处理,也就是原样搬出,不做处理。这样 (start form1) 和 (form1) 的功能就相同了。

在规则 ((start exp1 exp2 ...) (let ((temp exp1)) (start exp2 ...))) 中,(start exp1 exp2 …) 是多个参数时的模板,首先用let来绑定局部变量temp为exp1,然后用递归实现处理多个参数,注意这里说的是宏定义中的递归,并不是过程调用中的递归。另外在宏定义中可以用省略号(三个点)来代表多个参数。

在Scheme的规范当中,将表达式分为原始表达式和有源表达式,Scheme语言的标准定义中只有原始的if分支结构,其它均为有源型,即是用后来的宏定义成的,由此可见宏定义的重要性。附上面的定义在GUILE中实现的 代码。






回页首




六. 其它功能

1. 模块扩展

在R5RS中并未对如何编写模块进行说明,在诸多的Scheme语言的实现当中,几乎无一例外的实现了模块的加载功能。所谓模块,实际就是一些变量、宏定义和已命名的过程的集合,多数情况下它都绑定在一个Scheme语言的符号下(也就是名称)。在Guile中提供了基础的ice-9模块,其中包括POSIX系统调用和网络操作、正则表达式、线程支持等等众多功能,此外还有著名的SFRI模块。引用模块用use-modules过程,它后面的参数指定了模块名和我们要调用的功能名,如:(use-modules (ice-9 popen)),如此后,就可以应用popen这一系统调用了。如果你想要定义自己的模块,最好看看ice-9目录中的那些tcm文件,它们是最原始的定义。

另外Guile在面向对象编程方面,开发了GOOPS(Guile Object-Oriented Programming System),对于喜欢OO朋友可以研究一下它,从中可能会有新的发现。

2. 如何输出漂亮的代码

如何编写输出漂亮的Scheme语言代码应该是初学者的第一个问题,这在Guile中可以用ice-9扩展包中提供的pretty-print过程来实现,看下面的操作:

guile> (use-modules (ice-9 pretty-print)) ; 引用漂亮输出模块
guile> (pretty-print '(define fix (lambda (n)
(cond ((= n 0) 'iszero)
((< n 0) 'lower)
(else 'upper))))) ; 此处是我们输入的不规则代码
(define fix
(lambda (n)
(cond ((= n 0) 'iszero)
((< n 0) 'lower)
(else 'upper)))) ; 输出的规则代码



3. 命令行参数的实现

在把Scheme用做shell语言时,经常用到命令行参数的处理,下面是关于命令行参数的一种处理方法:

#! /usr/local/bin/guile -s
!#
(define cmm (command-line))
(display "应用程序名称:")
(display (car cmm))
(newline)
(define args (cdr cmm))
(define long (length args))
(define loop (lambda (count len obj)
(if (<= count len)
(begin
(display "参数 ")
(display count)
(display " 是:")
(display (list-ref obj (- count 1)))
(newline)
(set! count (+ count 1))
(loop count len obj)))))
(loop 1 long args)



下面是运行后的输出结果:

[root@toymouse doc]# ./tz.scm abc 123 ghi
应用程序名称:./tz.scm
参数 1 是:abc
参数 2 是:123
参数 3 是:ghi



其中最主要的是用到了command-line过程,它的返回结果是命令参数的列表,列表的第一个成员是程序名称,其后为我们要的参数,定义loop递归调用形成读参数的循环,显示出参数值,达到我们要的结果。

4. 特殊之处

一些精确的自己计算自己的符号

数字 Numbers 2 ==> 2
字符串 Strings "hello" ==> "hello"
字符 Charactors #\\g ==> #\\g
辑值 Booleans #t ==> #t
量表 Vectors #(a 2 5/2) ==> #(a 2 5/2)



通过变量计算来求值的符号

如:



x ==> 9
-list ==> ("tom" "bob" "jim")
factoral ==> #
==> #



define 特殊的form

(define x 9) ,define不是一个过程, 它是一个不用求所有参数值的特殊的form,它的操作步骤是,初始化空间,绑定符号x到此空间,然后初始此变量。

必须记住的东西

下面的这些定义、过程和宏等是必须记住的:

define,lambda,let,lets,letrec,quote,set!,if,case,cond,begin,and,or等等,当然还有其它宏,必需学习,还有一些未介绍,可参考有关资料。

走进Scheme语言的世界,你就发现算法和数据结构的妙用随处可见,可以充分的检验你对算法和数据结构的理解。Scheme语言虽然是古老的函数型语言的继续,但是它的里面有很多是在其它语言中学不到的东西,我想这也是为什么用它作为计算机语言教学的首选的原因吧。