Authorized translation from the English language edition, entitled Functional Programming For The Rest of Us, by Slava Akhmechet.
Chinese simplified language version is translated by Yifan Peng. Part of the translation is from lihaitao(lihaitao@gmail.com)
Copyright (c) 2014 Yifan Peng.
All rights reserved.

本文中文简体字版由Slava Akhmechet授权。未经书面许可，请勿复制或抄袭。

---

目录

• 简介
• 信步游园
• 历史一瞥
• 函数式编程
• 函数式编程的优点
• 高阶函数
• Currying
• 惰性求值
• Continuations
• 模式匹配
• 闭包（Closure）
• 接下来如何？

---

简介

程序员拖沓成性，每天到办公室以后，泡泡咖啡、查查邮箱、读读RSS上的回复，看看新闻，到技术网站点击一下最新的文章，然后在编程论坛的相关版面浏览公共讨论区，并不厌其烦地刷新页面，以免漏掉任何一条留言。午饭后盯着IDE没几分钟，再次检查邮箱，或者冲一杯新的咖啡。就这样不知不觉中，结束了一天。

如果你浏览的网站很对路的话，每隔几天都会发现一些很有挑战性的文章——你很难快速通读它们，于是将之束之高阁，直到有一天突然发现自己已经有了一个长长的链接列表和一个堆满了PDF文件的目录。这时你会幻想到一个人迹罕至的森林木屋，苦读一年以学会这些技术。当然，每天清晨当你沿着林中小溪散步的时候，如果有人帮你带饭、清理垃圾就更好了。

我不知道你的列表是什么，但我的列表却包含了一大堆关于函数式程序设计的文章。这些文章都很难读懂。它们用枯燥的学院派语言写成，即使“在华尔街行业浸淫十年的专家”也不能理解函数式程序设计都在探讨些什么。如果你去问花旗集团或德意志银行的项目经理¹，为什么选择了JMS 而不是Erlang，他们可能会说：不能在产业级的应用中使用学院派语言。但问题是，一些最复杂、有着最严格需求的系统却是用函数式程序设计元素写成的。所以，这些说法不能让人信服。

的确，有些关于函数式程序设计的文章和论文很难理解，但它们原本并不是这么晦涩。产生隔阂的原因完全是历史性的。函数式程序设计的概念并不难理解。本文就是“简易的函数式程序设计导论”，是一座沟通命令式（imperative）思维模式和函数式程序设计的桥梁。去冲杯咖啡回来继续读下去吧。可能你的同事很快就会开始取笑你对函数式编程发表的观点了。

那么什么是函数式程序设计呢？它是怎么产生的？它可以被驾驭吗？如果它真如其倡导者所言那么有用，为什么没有在行业中得到广泛使用呢？为什么好像只有那些博士才使用它？最重要的是，为什么它就TMD这么难学？闭包（closure）、continuation、currying、惰性赋值（lazy evaluation）、no side effects business究竟是些什么东西？一个项目如果没有大学参与，能不能使用函数式语言？为什么它看上去那么不友好、不亲切？我们马上会解答这些疑问。首先让我来解释实际应用和学术文章之间，有着产生巨大隔阂的原因。其实答案简单得就像在公园散一次步。

信步游园

启动时间机器，我们来到两千多年前的一个公园里。具体时间大约是公元前380年的一个春光明媚的周日。在雅典城外的橄榄树树荫里，柏拉图（Plato）和一个英俊的奴隶小男孩正朝着学院走去。那天天气很好，晚饭也不错。他们边走边讨论一个哲学问题。

为了使问题更有教育意义，柏拉图小心地挑选着词句：“瞧这两个学生，你认为谁更高呢？”小男孩看了看那两个站在水池中的人，说，“他们俩差不多高”。柏拉图问：“你说‘差不多’是什么意思？”。“恩……我在这儿看他们是一样高的，不过我肯定如果走近些就会看出他们的差别。”

柏拉图笑着把这个孩子引向正确的思路。“那么你是说，这个世界上没有完全相同的两个东西了？”小男孩想了一会儿回答，“对。我想即使我们看不到，任何事物之间总有一些区别。”正中下怀！“那么如果这世上没有完全相同的两个东西，你怎么理解‘完全’相等这个概念呢？”小男孩有点被问住了，说：“我不知道”。

这就是我们第一次尝试理解数学的本源。柏拉图提出，世界上所有的事情都只是趋近于完美。他同时也意识到，尽管我们无法真正碰触到完美的事情，但是我们可以理解它。因此完美的数学仅存在于另一个世界中，而我们可以通过和那个世界的某种联系在一定程度上认知它。比如，虽然我们无法看到绝对完美的圆，但是我们知道什么是圆，并且能够用公式表达它。那什么是数学呢？为什么宇宙可以用数学定理来描述？数学可以描述宇宙中的所有现象吗？²

数学哲学是一个很复杂的课题。像大多数哲学学科一样，它更倾向于提出问题而不是给出答案。很多得出的共识都围绕着一个事实：数学真的是个谜。我们首先给出一些基本的、互不冲突的原理，以及一些可以操作这些原理的规则；然后我们组合这些规则生成更复杂的规则。数学家把这种方法叫做“形式系统”或“微积分”。如果愿意，我们可以很快为俄罗斯方块写出一个形式系统。实际上，一款俄罗斯方块游戏本身就是一个形式系统，只不过游戏采用了非数学的表现形式。

半人马阿尔法行星上的毛毛生物文明不能理解我们对于俄罗斯方块或者圆的范式，因为它们唯一可以感知世界的器官可能只有嗅觉。他们也许永远不会发现俄罗斯方块的范式，但很可能会有一个圆的范式。而我们也可能无法知道如何通过嗅觉描述一个圆，因为我们的嗅觉没有那么灵敏。可是一旦我们能理解那一范式的表示形式（比如通过各种传感器和标准解码技术来理解这种语言），其底层的概念就可被任何智能文明所理解。

有趣的是，即便宇宙中从没有过智能文明，俄罗斯方块和圆的范式仍然存在，只是没有人发现它们而已。如果一种智能文明出现了，他应该能发现一些形式系统来描述宇宙的规律。但他还是不大可能搞一个俄罗斯方块， 因为宇宙中再没有和它相似的东西。在现实世界中这类无用的形式系统或迷题的例子数不胜数，俄罗斯方块只是其中一个典型的例子。我们甚至不能确定自然数是否是对客观世界的完整近似。比如我们可以很容易的想出一个特别大的数字，它无法表达我们世界中的任何事物，因为我们的世界有限的，而这个数近乎无穷。

历史一瞥³

再次启动时间机器，这次我们回到二十世纪30年代。大萧条正在蹂躏着那个新旧交替的时代。空前的经济下滑影响着几乎所有阶层的家庭。只有少数人还能够保持着饥谨危机前的安逸，比如普林斯顿大学的数学家们。

歌特式的新办公室给普林斯罩上天堂般的幸福光环。来自世界各地的逻辑学家被邀请到此成立一个新学部。那时的美国人民已很难弄到一块面包，但是在普林斯顿，你可以在高高的穹顶下、精致雕凿的木质墙饰边，整日的品茶讨论，或在楼外的林荫中款款慢步。

阿隆左·丘奇（Alonzo Church）就是其中一位享受这种近于奢华的数学家。他在普林斯顿获得本科学位后被邀继续留在研究生院攻读。阿隆左认为普林斯顿的建筑过于浮华，所以他很少一边喝茶一边与人讨论数学，他也不喜欢到林中散步。他有些孤僻，因为似乎只有独自一人时，他才能以最高的效率工作。尽管如此，他仍与另一些同样居住在普林斯顿的人保持着联系，比如阿兰·图灵（Alan Turing），约翰·冯·诺依曼（John von Neumann），和库尔特·冈特（Kurt Gödel）。

这四个人都对形式系统很感兴趣。他们致力于解决抽象的数学难题，而不太留意现实的世界。这些难题的共同之处就是计算：如果计算机能有无限的计算能力，哪些问题可以被解决？哪些问题可以被自动解决？哪些问题依旧无法解决？为什么不能被解决？基于不同设计的各种计算机是否具有相同的计算能力？

通过和其它人的合作，阿隆左·丘奇提出了一个被称为lambda演算的形式系统。这个系统本质上是一种程序设计语言。它可以运行在具有无限计算能力的机器上。lambda演算由一些函数构成，这些函数的输入输出也是函数。函数用希腊字母lambda标识，因此整个形式系统也叫lambda⁴。通过这一形式系统，阿隆左就可以对上述诸多问题进行推理并给出结论性的答案。

在同一时间，阿兰·图灵也在进行着相似的工作。他提出了一个完全不同的形式系统（现在被称为图灵机），并使用这一系统得出了和阿隆左相似的结论。事后证明，图灵机和lambda的演算能力是等价的。

我们的故事本可到此结束。如果第二次世界大战没有在那时打响，我现在就可以歇笔，而你也可以浏览下一个页面了。那时整个世界笼罩在战争的火光和硝烟之中，美国陆军和海军大量使用炮弹。为了改进炮弹的精确度，部队雇佣了大批数学家通过计算微分方程来给出弹道发射的轨迹。很显然这项工作人力浩繁，因此人们开始着手开发各种设备来攻克这个难关。第一个解出了弹道轨迹的机器是IBM的Mark I——它重达5吨，有75万个部件，每秒可以完成三次操作。

竞争当然没有就此结束。1949年，EDVAC（Electronic Discrete Variable Automatic Computer）被推出并获得了巨大的成功。这是冯·诺依曼架构的第一个具体实现，实际上也是图灵机的第一个实现。而与此同时，阿隆左·丘奇则没有那么幸运。

二十世纪五十年代，一位MIT的教授John McCarthy（也是普林斯顿毕业生）对阿隆左·丘奇的工作产生了兴趣。1958年，他发布了Lisp语言（List Processing language）。Lisp的不同之处在于，它在冯·诺依曼计算机上实现了阿隆左·丘奇的lambda演算！很多计算机科学家开始意识到Lisp的表达能力。1973年，MIT人工智能实验室的一帮程序员开发了被称为Lisp机器的硬件，于是阿隆左的lambda演算系统终于在硬件上实现了！

函数式程序设计

函数式程序设计是对阿隆左·丘奇思想的一种实现。但并非所有的lambda演算都被实现了，因为lambda演算原本不是为有物理限制的计算机设计的。因此，函数式程序设计和面向对象程序设计一样，只是一系列理念，而不是严格的使用手册。如今有很多种函数式编程语言，它们各自采用了不同的方法。在本文中，我将使用Java来编写函数式程序，并且解释函数式语言的常用特性（的确，如果你有受虐倾向，你可以用Java写出函数式程序）。在下面几章中，我将会对Java稍作修改，以使其成为一个可用的函数式编程语言。那我们开始吧。

lambda演算被设计用来解决计算问题，所以函数式程序设计主要用于处理计算。正如它的名字那样，程序用函数来完成所有操作。函数是函数式程序设计的基本单位。它几乎无处不在。即使最简单的计算也由函数构成。甚至变量（variable）都由函数取代。在函数式编程中，变量只是表达式的别名（这样我们就不必把所有东西打在一行里）。变量是不能被更改的并且只能被赋值一次。在Java中，这意味着所有变量都要被声明为final（或C++中的const）。在函数式编程中没有非final的变量。

因为函数式编程中的所有变量都是final的，所以可以提出这样两个有趣的假设：（1）没有必要总是写出关键字final，（2）没有必要再把变量称为变量。那么现在我们对Java作出两个修改：（1）在我们的函数式Java中，所有变量默认都是final的，（2）我们将变量称为符号（symbol）。

现在你可能会奇怪，用我们新创造的语言还能写出复杂的程序吗？如果每个符号都是不可变(non-mutalbe)的，我们就无法改变任何事情的状态！其实事实并非如此。在阿隆左研究lambda演算时，他并不想维护某个状态，并且在未来修改它。他关注的是如何对数据进行操作（这也通常被称为“演算体（caculating stuff）”。不管怎么说，既然lambda演算已被证明与图灵机等价，命令式程序能做的事情它应该也能做。但是我们应该怎么做呢？其实函数式程序也能保存状态，只是它使用的是函数，而不是变量。函数式程序将状态保存在函数的参数中，而这些参数又保存在“栈”上。如果你想保存某个状态并且想每隔一段时间就去修改它，你可以写个递归函数。比如，我们可以写个能够翻转Java字符串的函数。记住，我们声明的每个变量默认都是final的⁵。

这个函数很慢而且特别消耗内存⁶。它慢是因为它不停的调用自己，而它耗内存是因为它不断的分配对象。但是它确实是一个典型的函数式函数。你可能会问，怎么会有人这样写程序呢？下面就让我慢慢道来。

函数式编程的优点

你可能会认为我根本无法对上面那个变态的函数给出合理的解释。我开始学习函数式编程时，也这么想。不过事实证明我错了。有许多很好的理由来支持这样的写法，当然其中一些是主观因素。比如，有人号称函数式程序易于理解。我不会拿这些理由出来说事，因为小孩子都知道：情人眼里出西施。不过我还能找到很多客观理由。

单元测试

因为函数式编程的每一个符号都是final的，所以没有函数能产生副作用。因为你不能在某个地方修改值，也不能在一个函数中修改其作用域外别的函数使用的值（比如类成员或全局变量），所以计算（或者运行）一个函数，只能得到它的返回值，而唯一可以改变该返回值的是这个函数的参数。

对单元测试者来说，这是梦寐以求的。你可以测试程序中的每个函数，并且只关心它的输入参数。你不用理会函数的调用关系，也不用精心设置外部状态。唯一需要做的就是把需要测试的极端情况输入给函数。比起使用命令式编程，如果函数式程序中的每个函数都通过了单元测试，那么你会对整个程序的质量有更大的信心。在Java或C++中，只检查函数的返回值是不够的——我们还必须验证这个函数可能修改的外部状态。但是在函数式程序中，这种情况永远不会发生。

调试

如果一段函数式程序没有按照你所希望的那样执行，调试起来也是轻而易举。因为函数式程序中的bug与之前执行的代码无关，所以你总是可以复现遇到的问题。在命令式程序中，有些bug会时隐时现，这是由于该函数可能会依赖其他函数提供的外部状态，而那些其他的函数可能才是问题的关键。因此你必须一并检查它们。而这种调试看似和这个Bug并无直接关系。函数式程序则不同——如果一个函数的返回值错了，它永远是错的，这与你之前运行了什么代码无关。

一旦你复现了问题，寻其根源将毫不费力甚至颇有乐趣。给你的程序打个断点，然后看看栈中的情况。和命令式编程一样，你可以检查栈里每一次函数调用的参数。在命令式编程中，这是不够的，因为函数依赖于成员变量、全局变量、以及其他类的状态（这些类还可能依赖其他的成员变量、全局变量、甚至更多其他的类）。函数式程序里函数只依赖于它的参数，而那些信息就在你的面前！另外，在命令式程序里，只检查一个函数的返回值不能够让你确信这个函数已经可以正常工作了。你还需要逐个检查一堆作用域外的对象来看看它们是否也处于正常的状态。而对函数式程序，你要做的所有事就是查看其返回值！

沿着堆栈检查函数的参数和返回值，只要有返回值出现问题，就进入那个函数然后一步步跟踪下去。重复这个过程，你就能发现bug的位置。

并发

函数式程序就是为并发而生的。因为用不到锁（lock），所以永远不必担心死锁和竞争条件（race condition）。在函数式程序中，没有任何数据会被同一个线程修改两次，更不用说被两个不同的线程修改了。这意味着你可以不假思索地添加线程而不用担心困扰并发程序设计的常见问题。

如果这样，那么为什么没有人在大型并发应用中运用函数式编程呢？其实是有的。爱立信公司设计了一种函数式语言(Erlang)[http://www.erlang.org/]，用于需要极高抗错性和可扩展性的电话交换机上。其他公司也意识到了Erlang的优势，并开始使用它。我们所说的程控交换和电信通信控制系统，需要比传统的华尔街系统更易扩展和可靠。实际上，Erlang系统并不具有很高的扩展性和可靠性——Java系统才是——但是Erlang系统坚如磐石。

并发的故事并未就此结束。即使你的程序本身就是单线程的，函数式程序的编译器仍然可以对其进行优化，使其运行于多个CPU上。来看下面这段代码。

在函数式编程中，编译器可以对代码进行分析，发现生成字符串s1和s2的函数可能非常耗时，于是对其并行运行。这种情况在命令式语言中是不可能出现的，因为每一个函数都有可能修改外部状态，而后续函数有可能依赖这些外部状态。在函数式语言里，自动分析哪些函数可以并发执行就像自动内联一样简单。从这个意义上说，具有函数式风格的程序是“不会过时的技术(future proof)”(尽管我很讨厌流行用语，但这回也要破例使用一次)。硬件厂商已经无法让CPU运行得更快了。他们只能靠增加内核数量，用并发来成倍的提高速度。当然他们没有提醒我们，只有当处理并发问题的时候，我们花的钱才会物有所值。命令式程序中只有很小一部分是可以并发的，但是在函数式程序中，所有函数天生都是可并发的。

代码热部署

过去，如果要在Windows上安装更新，就必须不断地重启计算机。即使只是安装了一款新版媒体播放器，也必须重启。Windows XP大大改进了这个问题，但仍不理想（今天工作的时候，我运行了一下Windows Update，结果除非我重启系统，那个烦人的图标会一直出现在我的系统托盘上）。Unix系统一直以来有一个更好的架构：安装更新时只需停止与其相关的组件，而不是整个操作系统。即使如此，对于大型的服务器应用程序来说，这仍旧无法让人接受。程控交换系统需要100%的时间都在运行。因为如果由于升级而无法接通紧急电话，那很可能会要人命的。同样，华尔街的公司也没有理由必须在周末暂停系统来更新软件。

理想的情况是，在完全不停止系统任何组件的情况下来更新相关的代码。在命令式程序的世界里，这是不可能的。想想在Java运行过程中卸载一个类并且加载一个新的类。即使我们真的可以这样做，这个类的所有实例也都不能用了，因为这个类的状态丢失了。我们需要复杂的版本控制代码来恢复这些状态：需要把运行中实例的都序列化，销毁它们，用新的类创建新的实例，最后载入先前被序列化的数据，并祈祷着加载代码确实能将数据迁移到新的实例中。更痛苦的是，每一次改变代码的时候，我们都必须手动编写这些迁移程序。这些迁移代码不仅要迁移实例，而且还不能破坏对象间的关系。这些听来理论上可行，但实践起来可不容易。

在函数式程序中，所有的状态都存储在栈中，并且通过参数传递给函数。这使得热部署轻而易举！实际上，我们需要做的只是比较一下工作中的代码和新版本的代码，然后部署变化的部分。剩下的工作将由一个语言工具自动完成！如果你觉得这是科幻小说，我建议你再想想。这么多年来，Erlang工程师始终在运转着的系统上直接升级。

机器辅助证明和优化

函数式语言的一个有趣的特性就是它们可以用数学方式进行推理。因为函数式语言只是一个形式系统的实现，所以只要是这个形式系统能够完成的数学运算（即使只是写在纸上），用其函数式语言也可以完成。举个例子来说，编译器可以把一段代码转变成另一段运行结果相同但是更高效的代码，然后在数学上证明二者是等价的⁷。多年来关系数据库一直在进行着类似的优化。没有理由说这种技术无法应用在常规软件上。

另外，你可以通过这些技术来证明你的一部分程序理论上是正确的。甚至可以写一个工具来分析代码并自动生成单元测试的边界用例！这个功能对于需要设计一个坚如磐石的系统来说是无价的。如果你要设计一个心脏起搏器或者交通控制系统，这种代码分析工具是必不可少的。即便你的程序不是这样人命关天，这些工具也是你击败竞争对手的杀手锏。

高阶函数

我记得即使在了解了上面种种优点之后，自己旧会想“恩，这些的确不错，但是如果让我在一个什么都是final的语言中编程的话，我宁可不用它。”其实你误解了我的意思。将所有变量都声明为final确实显得蹩脚，但是只有在像Java这样的命令式语言中，才会如此；在函数式语言中则不会。函数式语言提供了不同的抽象工具来让你忘记你曾经习惯于修改变量。高级函数就是这样一种工具。

函数式语言中的函数不同于Java或C中的函数。除了Java能做的事，它的功能更宽泛。因此函数式语言中的函数是Java或C中函数的超集。我们模仿C语言来定义一个函数：

与C语言代码不同，现在我们扩展Java编译器使其支持这种记法。当我们输入上述代码后，编译器会把它转换成下面的Java代码（别忘了，所有变量都是 final 的）：

add并不是一个真正的函数。它是一个只有一个成员函数的类。现在，我们可以将add作为其他函数的参数来使用，也可以将它赋给其他的变量。在运行时，我们可以创建一个add_function_t的实例。这些实例在用过之后会被当作垃圾回收。我们把这样的对象函数称作第一级类对象，它与整数或字符串无异。我们把操作其他函数的函数（将其他函数作为参数的函数）称为高阶函数。别让这个术语吓着你，因为这和在Java中把一个类作为参数传递给另一个类，以实现类之间的操作没有任何区别。类似第一级类对象，我们把包含高阶函数的类叫做高阶类。其实没有人关心这个名字，因为Java背后没有一个强大的学术社区。

那么应该在什么时候使用高阶函数呢？又怎么用呢？我很高兴你会问到这个问题。在写一大堆代码的时候不考虑任何类层次结构。当遇到重复的代码时，把重复的部分提取成函数（幸运的是现在学校还在教这个）。当看到函数中的一段逻辑会在不同的状况下有不同的行为时，就把这个逻辑片段提取成高阶函数。有点晕？下面是我工作中遇到的一个例子。

假设有一段Java代码，它接收一段信息，将其以多种方式转换，然后转发至其他服务器上。

现在想象一下，我们要将信息转发至两个服务器。除了第二台服务器需要另一种格式的client code外，其他一切都不变。我们应该怎么办？可以根据要转发到哪台服务器来修改client code的格式，比如

但是这种方法不备可扩展性。如果更多的服务器加入，这个函数的长度将线性地增长。再更新代码时就会变得很麻烦。采用面向对象的方法，我们会定义一个父类MessageHandler，然后在派生类中具体实现生成client code的操作：

现在我们可以对每一个服务器实例化一个合适的类。添加服务器的操作变得容易维护了。但对于如此简单的修改却需要添加大量的代码。为了支持不同的client code，我们创建了两个新的类型！下面用我们修改过的、支持高阶函数的语言来实现同样的功能：

我们没有建立新的类型与类层次构，而只是把适当的函数作为参数传入，就完成了与面向对象一样的功能。这个方案有很多优势。我们不再局限于类的层次结构中：我们可以在运行时传入新的函数，并且随时以更少的代码更大的粒度修改它们：我们的编译器能够自动高效地生成面向对象的代码（将函数转换为函数类）。并且我们获得了函数式编程的所有好处。当然函数式语言提供的抽象性远不止于此，高阶函数仅仅是个开始。

Currying

我认识的很多人都读过四人帮（GOF）的《设计模式》。任何自恋的程序员都会告诉你，这本书中讨论的模式在软件工程中具有通用性，它和使用哪门语言无关。这个说法显得颇为高深，但是有违现实。

函数式编程极具表达能力。你不需要在函数式语言中使用设计模式，因为这种高级程序设计语言可以让你只进行概念编程，从而不再需要设计模式。适配器(Adapter)模式就是这样的一个例子(适配器和外观模式（Facade）有什么区别？某人可能需要在这里高谈扩论了)。一旦语言有了叫作currying的技术，我们就不再需要适配器模式了。

适配器模式最有名的应用是Java的“默认”抽象单元——类。在函数式编程里，这个模式被应用到函数上。适配器模式将一个接口转换为另一个接口。这里有一个适配器模式的例子：

上面的代码把一个整数幂运算接口转换成为了一个平方接口。在学术圈中，这样的用法被称之为currying（得名于逻辑学家Haskell Curry，他曾将相关的数学理论形式化）。因为在函数式编程中，函数——而不是类——作为参数进行传递，因此可以用currying把函数适配到其他接口。又因为函数的接口就是其参数列表，所以currying可以减少参数的数量(如上例所示)。

因为函数式语言内建了这一技术，所以不用手动地创建一个包装了原函数的类。函数式语言会为你代劳。和之前一样，我们来扩展一下我们的语言来支持这个技术：

编译器会自动为我们创建一个只有一个参数的square函数。它会在第二个参数为2的情况下调用pow函数。这段代码会编译成如下Java代码：

正如你所见，我们只是简单地包装了一下原函数。在函数式编程中，这就是currying——快速便捷的包装一个函数。你专注于你的工作，而编译器为你生成具体的代码！那么什么时候用currying？很简单：当你想用适配器模式（包装）的时候。

惰性求值

当我们采用函数式哲学以后，就可以使用惰性（或延迟）求值这一技术。在并发一节，我们已经看过如下代码：

在一个命令式语言中，求值的顺序一目了然。因为每个函数都有可能改变外部状态，所以执行顺序必须首先是somewhatLongOperation1，然后somewhatLongOperation2，最后是concatenate。在函数式语言中，则不一定非要按照这个顺序。

我们之前讲到，如果没有函数会修改或依赖于全局变量，那么somewhatLongOperation1和somewhatLongOperation2就可以并发执行。但如果我们不想并发执行它们，就必须顺序执行它们么？不一定。只有当另一个函数需要s1和s2的时候，我们才会执行这两个函数。因此在concatenate被调用之前，我们不需要执行它们——我们甚至可以将它们的求值延迟到concatenate函数中实际用到它们的位置。如果我们将concatenate替换成另外一个函数，而这个函数带有一个条件分支。如果该分支每次只会使用两个参数中的一个，。那么我们可能永远没有必要对另一个参数求值。Haskell就是这样一门支持惰性求值的语言。Haskell不能保证每一行代码都会被按顺序执行，甚至不能保证所有代码都会被执行。这是因为只有当一段代码在需要使用的时候，Haskell才会运行那段代码。

惰性求值有利有弊。我们先来说说优点，然后再讨论如何克服缺点。

优化

惰性求值具有巨大的优化潜力。惰性编译器对待函数式代码就像数学家对待代数方程式一样：一些部分可以被约分从而不必执行，一些部分的顺序可以进行调整以提升效率，代码甚至可以被重整以降低错误。所有这些优化都能确保不会破坏代码原本的逻辑。这就是严格使用形式系统来表达程序的最大好处——代码依附于数学定律，因此可以用数学进行推理。

抽象控制结构

惰性求值提供了更高一级的抽象。这种抽象使得一些原来不可能的操作变得可行。比如下面这个控制结构：

我们希望只有在stock为European的情况下才执行sendToSEC。那么应该如何实现unless？如果没有惰性求值，我们需要某种形式的宏。但是在像Haskell这样的语言中，则没必要这样做。我们可以将unless实现为一个函数：

请注意，当分支条件是true的时候，code永远不会被执行。在执行顺序严格的语言中这样的代码是无法实现的，因为在unless调用之前，参数code已经被运行了。

无限的数据结构

惰性求值允许定义无限的数据结构。在执行顺序严格的语言中，这是很难实现的。比如一个Fibonacci数列。显然我们无法在有限的时间内计算出一个无穷列表，也不能在有限的内存里保存这个列表。Java只能定义一个Fibonacci函数来返回Fibonacci数列中某个指定位置的元素。但是Haskell可以将它抽象为一个无限的Fibonacci数列。因为该语言具有延迟的特性，所以这个数列中只有实际被用到的部分才会被求值。总之，惰性求值使我们可以抽象出许多问题，并从一个更高的层面来审视它们。（例如，我们可以在一个无穷列表上使用表处理函数）。

缺点

当然天下没有免费的午餐。惰性求值也有一些缺点。最大的问题其实就是“惰性”。许多现实问题都需要严格按顺序执行。例如下面这段代码：

惰性求值语言无法保证第一行会比第二行先执行！这意味着我们没法做IO操作，没法以任何有用的方式调用本地接口（因为它们相互依赖，所以必须被顺序执行），也没法与外界交互！如果引入允许顺序执行的特性，我们又将失去能够用数学进行代码推理的好处（并为此葬送与其相关的函数式编程的所有优点）。幸运的是，不是所有优点都没了。数学家们找到了许多技巧来保证，在一定函数设置下，代码可以按顺序执行。这样我们就赢得了两个世界。这些技巧包括：continuations，monads，还有uniqueness typing。在这篇文章中，我们只会讨论continuations。monads和uniqueness typing只能留到以后讨论。有趣的是，continuations除了能让代码以特定的顺序执行以外，还有很多其他优点。这点等一会儿就会提到。

Continuations

Continuations对于程序设计的意义，就像《达芬奇密码》对人类历史的意义：揭露了人类有史以来最大的假象。恩，也许没那么牛。但它在概念上的突破性至少和开方负数的意义相同。

我们学习函数时，其实基于这样一个假设：函数只能将结果返回给调用者。在这个意义上continuation是广义的函数。一个函数不一定必须要返回到其调用者，它可以返回到程序的任何地方。continuation可以是函数的一个参数，我们通过这个参数指定函数返回位置。这个描述可能听起来很复杂，我们来看看下面的代码：

函数add返回15，并赋值给i，即原始调用add的地方。然后在调用square的时候使用i。注意，延迟特性的编译器无法重新排列这些代码，因为第二行代码依赖于第一行的执行。但是我们可以用延续传递方式（Continuation Passing Style，CPS）重写这段代码，用它来指定add函数直接返回到square，而不是原来的调用者：

这个例子中 add 有了另一个参数 —— 一个add在结束时需要调用的函数。这里square是add的continuation。这两段代码的结果都是j=225.

这个技巧可以用于迫使惰性语言顺序执行两个表达式。接下来我们看看这个（熟悉的）IO代码：

这两行代码彼此独立，所以编译器会根据自己希望的顺序去执行他们。但是，如果我们用CPS来重写这段代码，它们之间便有了依赖关系，编译器会按顺序执行它们：

这里，println需要在结束后调用readLine并且返回readLine的结果。如此这两行就能保证被有序执行，并且readLine一定会被执行（因为整个运算以最后一个值作为返回值）。Java的println会返回void，但如果假设它返回的是一个readLine能接受的抽象值，我们就解决了这个问题！当然，像这样把函数串起来，会降低代码的可读性。不过这个可以避免。我们可以在程序语言中添加一些语法规则，使我们可以像原来那样按顺序输入代码，然后编译器自动把它们串起来。这样我们就可以按希望的顺序执行代码，并且保留一切函数式编程的好处（包括按数学逻辑来解释我们的代码）。如果说到这里还有点晕的话，那么记住，一个函数就是一个只有一个成员的类实例。如果将上面的代码重写成println和readline的类实例的话，可能就清楚多了。

如果我就此结束，那将仅仅涉及到continuation的皮毛。我们可以用CPS重写整个程序，使所有函数都有一个额外的continuation参数，然后将当前函数的执行结果传进去。我们也可以将函数看成一类特殊的continuation（函数总是返回值给调用者），然后将程序转换成CPS代码。这种转换很容易被自动化（事实上，许多编译器就是这么做的）。

当我们将一个程序转换为CPS以后，每一个指令都会有continuation，一个当前函数执行后调用的函数，也就是通常的程序中的返回地址。让我从上面的代码中挑一个指令，比如add(5,10)。在CPS中，add的continuation是add调用完毕后接下来要执行的函数，但是在非CPS的程序中，continuation是什么呢？我们当然可以把它转换成CPS后来解释，但有这个必要吗？

其实没有必要。仔细看一下CPS转换过程。如果你试着去为它写一个编译器，并且好好思考如何去做的话，你会意识到CPS根本不需要栈！没有函数会像传统程序那样“返回”，它只是在执行完毕之后调用另一个函数。因此我们不用在每次调用函数时把参数都压到栈中，然后再在调用结束时把它们弹出来。我们只需要把它们存到内存块中，然后使用跳转指令。我们永远不需要原始的参数。他们不会被再次用到，因为没有函数会返回！

所以，用CPS风格写成的程序没有栈，但每个函数却有一个额外的参数来调用下一个函数。而不以CPS方式写的程序没有额外的参数，但是有栈。栈中包含了什么？一些参数和一个指向函数返回地址的内存指针。看到关系了么？栈中包含的就是continuation信息！栈中指向返回地址的指针本质上和CPS里将被调用的函数是等价的。如果你想知道add(5,10)的continuation是什么，那么你只需要检查它被执行时的栈即可。

这的确很简单。continuation和栈上指向返回地址的指针是等价的。continuation被显式传递，所以它不一定必须是函数原来被调用的地方。如果你还记得continuation就是一个函数，并且函数在我们的程序语言被编译成一个类的实例的话，你会更理解二者是一样的。这意味着给定程序中任意时间和任意位置，你都可以得到一个当前的continuation（current continuation），即当前栈的信息。

好的，这样我们就知道了什么是current continuation。有什么用呢？当我们将current continuation保存在某处时，实际上是把程序的当前状态速冻起来。这类似于操作系统进入休眠状态。一个continuation对象包含在我们获得它的地方重新启动程序的必要信息。操作系统做线程间的上下文切换时也是如此。唯一的区别是它仍然继续保持着控制权。如果你需要一个continuation对象（在Scheme中，可以调用call-with-current-continuation函数），你就会得到一个包含current continuation的对象，即栈或者是在CPS中下一个要调用的函数）。你可以将这个对象存到变量中（或者磁盘上）。当你用这个continuation对象“重启”程序的时候，就可以将程序“转换”到你取得这个对象时的那个状态。这和切换回一个被挂起的线程或者唤醒休眠着的操作系统是一回事，而且你可以一遍又一遍的这样做。当操作系统被唤醒时，休眠信息就被销毁了。但如果那些信息没有被销毁，那么你也可以从同一个点一次又一次的唤醒操作系统。这就像时间停止一样。使用continuation，你就有了这个控制力！

Continuation应该在什么情况下使用呢？一般是在我们希望在一个先天就无状态的应用中模拟状态的时候。这样可以简化任务。Continuation很适合在Web应用程序中使用。微软的ASP.NET花了很大的功夫来模拟状态，以便在开发Web应用时少费周折。如果C#支持continuation，ASP.NET就不那么复杂了——你只需要保存一个continuation，当用户再次发送web请求时，重新启动它就可以了。对于程序员来说，web应用程序将不再有中断——程序只是简单的从下一行开始执行就可以了！

对于一些问题来说，continuation是一个非常有用的抽象工具。想到很多传统复杂的客户端将走向网络，continuation在未来会变得越来越重要。

模式匹配

模式匹配不是什么新特性。事实上，它和函数式编程的关系不大。为什么总是把它当做函数式编程的一个特性呢？这是因为函数式语言已经支持模式匹配一段时间了，而现代命令式语言还不行。

用一个例子来进一步了解模式匹配。下面是Java实现的斐波那契函数：

如果用我们上文构造的并且支持模式匹配的Java来写，实现如下

两者有什么区别？编译器为我们实现了分支。

这有什么大不了的？的确没什么。有人注意到很多函数都包含非常复杂的switch语句（函数式程序中尤其如此）并且觉得这是一种很好的抽象方式。我们将函数拆分成多个，然后通过函数参数实现模式（有点象重载）。当编译器调用函数的时候，会比较传入的参数和定义中的参数，然后选择匹配的那个执行。通常来说，编译器会选择最佳匹配。比如，int fib(int n)也可以在当n为1时被匹配，但因为int fib(1)是最佳匹配，所以编译器不会选择int fib(int n)。

模式匹配通常比例子中揭示的更加复杂。比如，高级模式匹配系统允许我们这样做：

模式匹配在什么时候适用？当有一大堆case的时候！每次当你需要写一个包含嵌套if的复杂结构时，模式匹配都可以用更少的代码取得更好的效果。一个很好的例子闪现在我脑海里。这就是所有Win32平台都提供的标准WinProc函数（即使它通常被抽象了）。一般来说一个好的模式匹配系统既可以检查集合，也可以检查简单值。比如，当传给函数一个数组后，可以设计这样一个模式：当首元素为1并且第三个元素大于3的时候，该模式被匹配。

模式匹配的另一个好处就是，当你需要添加或者改变条件时，不用去检查这个庞大的函数。而只需要添加（或修改）相应的那个模式定义。这样Gof书上的一大部分设计模式就没用了。条件越复杂，模式匹配就越有用。一旦你熟悉了模式匹配，就会开始奇怪：没有它的这些年你是怎么挨过来的。

闭包（Closure）

我们已经讨论了纯函数式语言的很多功能——所谓“纯”函数式语言就是实现了lambda演算并且不包含与Church范式矛盾的特性。但是函数式语言并不仅限于lambda演算。虽然实现一个自我证明的系统非常有用，它可以让我们以数学的方式来思考程序，但是可能在实际中它没有什么用处。所以很多语言选择支持部分函数式元素，但又不严格遵守那些教条。一些语言（比如Common Lisp）不要求变量是final的。你可以随时修改变量。它们的函数也不仅依赖于函数的参数。函数可以访问外部状态。但这些语言的确包含了函数式特性，比如高阶函数。在非纯粹的函数式语言里以函数作为参数传递，和在lambda演算系统中有些不同，它需要一种被称为词法闭包（lexical closure）的有趣特性。让我们来看看这段例子代码。记住，这回变量不是final的，并且函数可以引用其作用域外的变量：

函数makePowerFn返回了一个函数。这个函数有一个参数，并对这个参数进行幂运算。如果我们对square(3)求值会发生什么？变量power其实已经不在powerFn的作用域中了，因为makePowerFn已经返回，所以它的栈已经消失了。那么square是怎么执行的？一定是这个语言以某种方式将power的值保存起来以便square使用。如果我们创建另一个函数cube，为参数的立方运算会怎么样？运行环境必须存储两个power，每个我们用makePowerFn生成的函数（square和cube）各使用一个。存储这些值的现象就叫做闭包。闭包不只保存宿主函数的参数。例如，closure可能会是这样：

运行时已经保存了n，所以递增器可以访问它。更重要的是，运行时为每个递增器都保存了一个n的拷贝，即使这些拷贝应该在makeIncrementer返回时消失。那么这些代码是被如何编译的？闭包运算又是怎么工作的？让我们去幕后看看。

一点常识会很有帮助，首先局部变量不再由简单的作用域规则限定，它们的生命周期也不确定。那么由此可以得出它们不再被保存在栈上，而是堆中·⁸(#note8)。这样一来，闭包的实现就与我们前面讨论的函数一样了，只是它还有一个指向周围变量的引用。

当闭包引用了一个不在其作用域的变量时，它便会查找其父作用域中的引用。这样闭包将函数式和面向对象程序设计相结合。每当你创建一个包含了状态的类，并且把它传到别处的时候，想想闭包吧。闭包就是一个可以在运行时创建并获取“成员变量”的对象，只是你不必亲自去做这些！

接下来如何？

这篇文章仅介绍了函数式程序设计的一些皮毛。即是所谓的抛砖引玉吧。未来我打算写一写关于分类理论（category theory），单一体（monad），函数数据结构（functional data structure），函数式程序设计中的类型系统，FP并发，函数式数据库等等。如果我能（在学习的过程中）写出这些主题的一半，我想我的人生就完整了。与此同时，Google是我们的好朋友。

意见或建议？

如果你有任何问题、意见、或建议，请发送邮件至coffeemug@gmail.com。我非常愿意听到您的反馈。

---

1. 当我2005年秋天找工作的时候，我真的常常问这个问题。让人惊讶的是，我看到了很多茫然的面孔。你得想想，这帮年薪30万美金的人对于大部分他们能接触到的工具都有一个很好的理解。
2. 这是一个有争议的问题。物理学家和数学家一直被迫承认，他们还不完全清楚宇宙万物所遵循的规则是否都可以被数学描述。
3. 我非常讨厌那种仅给出一串日期、名字、事件的历史课。对我来说，历史是那些改变历史的人的生活，是他们行动背后的动机，是他们影响世人的方式。因此，我写的这一节并不能涵盖所有的历史细节。我只介绍那些与函数式程序设计相关的人和事。
4. 我在学习函数式程序设计的时候，很不喜欢术语lambda，因为我搞不清楚它到底是什么意思。本文中，lambda就是一个函数，一个方便使用的希腊字母。当谈到函数式编程的时候，如果你听到“lambda”，在脑子里把它翻译成“函数”就行了。
5. 有趣的是，Java中的字符串就是不可变的。讨论为什么会出现这样离经叛道的设计可能更有趣，但是这会打断我们当前的话题。
6. 几乎所有的函数式语言编译器都会尽可能的将递归优化为迭代。这中优化被称为尾递归优化（tail call optimization）。
7. 相反的情况未必成立。尽管有时可以证明两段代码等价，但无法找到一种普世方法可以证明所有情况。
8. 这其实不比存在栈中慢，因为如果你引入了垃圾回收器，那么内存分配便成为了一个O(1)操作。