你，一个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容器啥的是这里来的
2008年12月9日星期二
伟大的树形结构
一篇介绍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的组织中和“正确”编解码中，那么我们也可以获得类似树形化数据的扩展性，随便添加枝叶，但是对已有的接口程序不会存在不良影响。
谈到对树形化结构的佩服，就谈一点在个人具体工作中，遇到的一个关于树形化的应用。也是现在比较火热的基于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
次地刷新以免漏掉一条信息。然后是午饭，回来后盯了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
《数理逻辑与集合论》第二版 清华大学出版社
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 定义匿名函数的例子。到时候，我们将有机会看到这样的匿名函数对于编程来说，是多么方便。
首先介绍 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 程序员群体中的一分子。
答：我成为 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解释器
作者和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解释器
订阅：
博文 (Atom)