-
楼主 / webdriver
- 时间: 2014-10-17 13:14
-
-
- 时间: 2014-10-17 13:43傻瓜函数式编程
2006年6月19日，星期一
开篇
我们这些码农做事都是很拖拉的。每天例行报到后，先来点咖啡，看看邮件还有RSS订阅的文章。然后翻翻新闻还有那些技术网站上的更新，再过一遍编程论坛口水区里那些无聊的论战。最后从头把这些再看一次以免错过什么精彩的内容。然后就可以吃午饭了。饭饱过后，回来盯着IDE发一会呆，再看看邮箱，再去搞杯咖啡。光阴似箭，可以回家了……
（在被众人鄙视之前）我唯一想说的是，在这些拖拉的日子里总会时不时读到一些不明觉厉的文章。如果没有打开不应该打开的网站，每隔几天你都可以看到至少一篇这样的东西。它们的共性：难懂，耗时，于是这些文章就慢慢的堆积成山了。很快你就会发现自己已经累积了一堆的收藏链接还有数不清的PDF文件，此时你只希望隐入一个杳无人烟的深山老林里什么也不做，用一年半载好好的消化这些私藏宝贝。当然，我是说最好每天还是能有人来给送吃的顺带帮忙打扫卫生倒垃圾，哇哈哈。
--- 太形象了 （读者评）
我不知道你都收藏了些什么，我的阅读清单里面相当大部分都是函数式编程相关的东东：基本上是最难啃的。这些文章充斥着无比枯燥的教科书语言，我想就连那些在华尔街浸淫10年以上的大牛都无法搞懂这些函数式编程（简称FP）文章到底在说什么。你可以去花旗集团或者德意志银行找个项目经理来问问1：你们为什么要选JMS而不用Erlang？答案基本上是：我认为这个学术用的语言还无法胜任实际应用。可是，现有的一些系统不仅非常复杂还需要满足十分严苛的需求，它们就都是用函数式编程的方法来实现的。这，就说不过去了。
关于FP的文章确实比较难懂，但我不认为一定要搞得那么晦涩。有一些历史原因造成了这种知识断层，可是FP概念本身并不难理解。我希望这篇文章可以成为一个“FP入门指南”，帮助你从指令式编程走向函数式编程。先来点咖啡，然后继续读下去。很快你对FP的理解就会让同事们刮目相看了。
什么是函数式编程（Functional Programming，FP）？它从何而来？可以吃吗？倘若它真的像那些鼓吹FP的人说的那么好，为什么实际应用中那么少见？为什么只有那些在读博士的家伙想要用它？而最重要的是，它母亲的怎么就那么难学？那些所谓的closure、continuation，currying，lazy evaluation还有no side effects都是什么东东（译者：本着保留专用术语的原则，此处及下文类似情形均不译）？如果没有那些大学教授的帮忙怎样把它应用到实际工程里去？为什么它和我们熟悉的万能而神圣的指令式编程那么的不一样？
我们很快就会解开这些谜团。刚才我说过实际工程和学术界之间的知识断层是有其历史原因的，那么就先让我来解释一下这个问题。答案，就在接下来的一次公园漫步中： -
-
- 时间: 2014-10-17 13:43公园漫步
时间机器启动……我们来到公元前380年，也就是2000多年前的雅典城外。这是一个阳光明媚的久违的春天，柏拉图和一个帅气的小男仆走在一片橄榄树荫下。他们正准备前往一个学院。天气很好，吃得很饱，渐渐的，两人的谈话转向了哲学。
“你看那两个学生，哪一个更高一些？”，柏拉图小心的选择用字，以便让这个问题更好的引导眼前的这个小男孩。
小男仆望向水池旁边的两个男生，“他们差不多一样高。”。
“‘差不多一样高’是什么意思？”柏拉图问。
“嗯……从这里看来他们是一样高的，但是如果走近一点我肯定能看出差别来。”
柏拉图笑了。他知道这个小孩已经朝他引导的方向走了。“这么说来你的意思是世界上没有什么东西是完全相同的咯？”
思考了一会，小男孩回答：“是的。万物之间都至少有一丁点差别，哪怕我们无法分辨出来。”
说到点子上了！“那你说，如果世界上没有什么东西是完全相等的，你怎么理解‘完全相等’这个概念？”
小男仆看起来很困惑。“这我就不知道了。”
这是人类第一次试图了解数学的本质。柏拉图认为我们所在的世界中，万事万物都是完美模型的一个近似。他同时意识到虽然我们不能感受到完美的模型，但这丝毫不会阻止我们了解完美模型的概念。柏拉图进而得出结论：完美的数学模型只存在于另外一个世界，而因为某种原因我们却可以通过联系着这两个世界的一个纽带来认识这些模型。一个简单的例子就是完美的 圆形。没有人见过这样的一个圆，但是我们知道怎样的圆是完美的圆，而且可以用公式把它描述出来。
如此说来，什么是数学呢？为什么可以用数学法则来描述我们的这个宇宙？我们所处的这个世界中万事万物都可以用数学来描述吗？2 数理哲学是一门很复杂的学科。它和其他多数哲学一样，更着重于提出问题而不是给出答案。数学就像拼图一样，很多结论都是这样推导出来的：先是确立一些互不冲突的基础原理，以及一些操作这些原理的规则，然后就可以把这些原理以及规则拼凑起来形成新的更加复杂的规则或是定理了。数学家把这种方法称为“形式系统”或是“演算”。如果你想做的话，可以用形式系统描述俄罗斯方块这个游戏。而事实上，俄罗斯方块这个游戏的实现，只要它正确运行，就是一个形式系统。只不过它以一种不常见的形式表现出来罢了。
如果半人马阿尔法上有文明存在的话，那里的生物可能无法解读我们的俄罗斯方块形式系统甚至是简单的 圆形的形式系统，因为它们感知世界的唯一器官可能只有鼻子（译者：偶的妈你咋知道？）也许它们是无法得知俄罗斯方块的形式系统了，但是它们很有可能知道圆形。它们的圆形我们可能没法解读，因为我们的鼻子没有它们那么灵敏（译者：那狗可以么？）可是只要越过形式系统的表示方式（比如通过使用“超级鼻子”之类的工具来感知这些用味道表示的形式系统，然后使用标准的解码技术把它们翻译成人类能理解的语言），那么任何有足够智力的文明都可以理解这些形式系统的本质。
有意思的是，哪怕宇宙中完全不存在任何文明，类似俄罗斯方块还有圆形这样的形式系统依旧是成立的：只不过没有智慧生物去发现它们而已。这个时候如果忽然一个文明诞生了，那么这些具有智慧的生物就很有可能发现各种各样的形式系统，并且用它们发现的系统去描述各种宇宙法则。不过它们可能不会发现俄罗斯方块这样的形式系统，因为在它们的世界里没有俄罗斯方块这种东西嘛。有很多像俄罗斯方块这样的形式系统是与客观世界无关的，比如说自然数，很难说所有的自然数都与客观世界有关，随便举一个超级大的数，这个数可能就和世界上任何事物无关，因为这个世界可能不是无穷大的。 -
- 时间: 2014-10-17 13:43历史回眸3
再次启动时间机……这次到达的是20世纪30年代，离今天近了很多。无论新旧大陆，经济大萧条都造成了巨大的破坏。社会各阶层几乎每一个家庭都深受其害。只有极其少数的几个地方能让人们免于遭受穷困之苦。几乎没有人能够幸运的在这些避难所里度过危机，注意，我说的是几乎没有，还真的有这么些幸运儿，比如说当时普林斯顿大学的数学家们。
新建成的哥特式办公楼给普林斯顿大学带来一种天堂般的安全感。来自世界各地的逻辑学者应邀来到普林斯顿，他们将组建一个新的学部。正当大部分美国人还在为找不到一片面包做晚餐而发愁的时候，在普林斯顿却是这样一番景象：高高的天花板和木雕包覆的墙，每天品茶论道，漫步丛林。 一个名叫阿隆佐·邱奇(Alonzo Church)的年轻数学家就过着这样优越的生活。阿隆佐本科毕业于普林斯顿后被留在研究院。他觉得这样的生活完全没有必要，于是他鲜少出现在那些数学茶会中也不喜欢到树林里散心。阿隆佐更喜欢独处：自己一个人的时候他的工作效率更高。尽管如此他还是和普林斯顿学者保持着联系，这些人当中有艾伦·图灵、约翰·冯·诺伊曼、库尔特·哥德尔。
这四个人都对形式系统感兴趣。相对于现实世界，他们更关心如何解决抽象的数学问题。而他们的问题都有这么一个共同点：都在尝试解答关于计算的问题。诸如：如果有一台拥有无穷计算能力的超级机器，可以用来解决什么问题？它可以自动的解决这些问题吗？是不是还是有些问题解决不了，如果有的话，是为什么？如果这样的机器采用不同的设计，它们的计算能力相同吗？
在与这些人的合作下，阿隆佐设计了一个名为lambda演算的形式系统。这个系统实质上是为其中一个超级机器设计的编程语言。在这种语言里面，函数的参数是函数，返回值也是函数。这种函数用希腊字母lambda（λ），这种系统因此得名4。有了这种形式系统，阿隆佐终于可以分析前面的那些问题并且能够给出答案了。
除了阿隆佐·邱奇，艾伦·图灵也在进行类似的研究。他设计了一种完全不同的系统（后来被称为图灵机），并用这种系统得出了和阿隆佐相似的答案。到了后来人们证明了图灵机和lambda演算的能力是一样的。
如果二战没有发生，这个故事到这里就应该结束了，我的这篇小文没什么好说的了，你们也可以去看看有什么其他好看的文章。可是二战还是爆发了，整个世界陷于火海之中。那时的美军空前的大量使用炮兵。为了提高轰炸的精度，军方聘请了大批数学家夜以继日的求解各种差分方程用于计算各种火炮发射数据表。后来他们发现单纯手工计算这些方程太耗时了，为了解决这个问题，各种各样的计算设备应运而生。IBM制造的Mark一号就是用来计算这些发射数据表的第一台机器。Mark一号重5吨，由75万个零部件构成，每一秒可以完成3次运算。
战后，人们为提高计算能力而做出的努力并没有停止。1949年第一台电子离散变量自动计算机诞生并取得了巨大的成功。它是冯·诺伊曼设计架构的第一个实例，也是一台现实世界中实现的图灵机。相比他的这些同事，那个时候阿隆佐的运气就没那么好了。
到了50年代末，一个叫John McCarthy的MIT教授（他也是普林斯顿的硕士）对阿隆佐的成果产生了兴趣。1958年他发明了一种列表处理语言（Lisp），这种语言是一种阿隆佐lambda演算在现实世界的实现，而且它能在冯·诺伊曼计算机上运行！很多计算机科学家都认识到了Lisp强大的能力。1973年在MIT人工智能实验室的一些程序员研发出一种机器，并把它叫做Lisp机。于是阿隆佐的lambda演算也有自己的硬件实现了！ -
- 时间: 2014-10-17 13:43函数式编程
函数式编程是阿隆佐思想的在现实世界中的实现。不过不是全部的lambda演算思想都可以运用到实际中，因lambda演算在设计的时候就不是为了在各种现实世界中的限制下工作的。所以，就像面向对象的编程思想一样，函数式编程只是一系列想法，而不是一套严苛的规定。有很多支持函数式编程的程序语言，它们之间的具体设计都不完全一样。在这里我将用Java写的例子介绍那些被广泛应用的h函数式编程思想（没错，如果你是受虐狂你可以用Java写出函数式程序）。在下面的章节中我会在Java语言的基础上，做一些修改让它变成实际可用的函数式编程语言。那么现在就开始吧。
Lambda演算在最初设计的时候就是为了研究计算相关的问题。所以函数式编程主要解决的也是计算问题，而出乎意料的是，是用函数来解决的！（译者：请理解原作者的苦心，我想他是希望加入一点调皮的风格以免读者在中途睡着或是转台……）。函数就是函数式编程中的基础元素，可以完成几乎所有的操作，哪怕最简单的计算，也是用函数完成的。我们通常理解的变量在函数式编程中也被函数代替了：在函数式编程中变量仅仅代表某个表达式（这样我们就不用把所有的代码都写在同一行里了）。所以我们这里所说的‘变量’是不能被修改的。所有的变只能被附一次初值。在Java中就意味着每一个变量都将被声明为final（如果你用C++，就是const）。在FP中，没有非final的变量。
final int i = 5;
final int j = i + 3;
既然FP中所有的变量都是final的，可以引出两个规定：一是变量前面就没有必要再加上final这个关键字了，二是变量就不能再叫做‘变量’了……于是现在开始对Java做两个改动：所有Java中声明的变量默认为final，而且我们把所谓的‘变量’称为‘符号’。
到现在可能会有人有疑问：这个新创造出来的语言可以用来写什么有用的复杂一些的程序吗？毕竟，如果每个符号的值都是不能修改的，那么我们就什么东西都不能改变了！别紧张，这样的说法不完全正确。阿隆佐在设计lambda演算的时候他并不想要保留状态的值以便稍后修改这些值。他更关心的是基于数据之上的操作（也就是更容易理解的“计算”）。而且，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。同时它也会大量的消耗内存，因为它会不断的分配创建内存对象。无论如何，它是用函数式编程思想写出来的。这时候可能有人要问了，为什么要用这种奇怪的方式编写程序呢？嘿，我正准备告诉你。 -
- 时间: 2014-10-17 13:44
-
- 时间: 2014-10-17 13:44单元测试
因为FP中的每个符号都是final的，于是没有什么函数会有副作用。谁也不能在运行时修改任何东西，也没有函数可以修改在它的作用域之外修改什么值给其他函数继续使用（在指令式编程中可以用类成员或是全局变量做到）。这意味着决定函数执行结果的唯一因素就是它的返回值，而影响其返回值的唯一因素就是它的参数。
这正是单元测试工程师梦寐以求的啊。现在测试程序中的函数时只需要关注它的参数就可以了。完全不需要担心函数调用的顺序，也不用费心设置外部某些状态值。唯一需要做的就是传递一些可以代表边界条件的参数给这些函数。相对于指令式编程，如果FP程序中的每一个函数都能通过单元测试，那么我们对这个软件的质量必将信心百倍。反观Java或者C++，仅仅检查函数的返回值是不够的：代码可能修改外部状态值，因此我们还需要验证这些外部的状态值的正确性。在FP语言中呢，就完全不需要。 -
- 时间: 2014-10-17 13:44调试查错
如果一段FP程序没有按照预期设计那样运行，调试的工作几乎不费吹灰之力。这些错误是百分之一百可以重现的，因为FP程序中的错误不依赖于之前运行过的不相关的代码。而在一个指令式程序中，一个bug可能有时能重现而有些时候又不能。因为这些函数的运行依赖于某些外部状态， 而这些外部状态又需要由某些与这个bug完全不相关的代码通过某个特别的执行流程才能修改。在FP中这种情况完全不存在：如果一个函数的返回值出错了，它一直都会出错，无论你之前运行了什么代码。
一旦问题可以重现，解决它就变得非常简单，几乎就是一段愉悦的旅程。中断程序的运行，检查一下栈，就可以看到每一个函数调用时使用的每一个参数，这一点和指令式代码一样。不同的是指令式程序中这些数据还不足够，因为函数的运行还可能依赖于成员变量，全局变量，还有其他类的状态（而这些状态又依赖于类似的变量）。FP中的函数只依赖于传给它的参数，而这些参数就在眼前！还有，对指令式程序中函数返回值的检查并不能保证这个函数是正确运行的。还要逐一检查若干作用域以外的对象以确保这个函数没有对这些牵连的对象做出什么越轨的行为（译者：好吧，翻译到这里我自己已经有点激动了）。对于一个FP程序，你要做的仅仅是看一下函数的返回值。
把栈上的数据过一遍就可以得知有哪些参数传给了什么函数，这些函数又返回了什么值。当一个返回值看起来不对头的那一刻，跳进这个函数看看里面发生了什么。一直重复跟进下去就可以找到bug的源头！ -
- 时间: 2014-10-17 13:45并发执行
不需要任何改动，所有FP程序都是可以并发执行的。由于根本不需要采用锁机制，因此完全不需要担心死锁或是并发竞争的发生。在FP程序中没有哪个线程可以修改任何数据，更不用说多线程之间了。这使得我们可以轻松的添加线程，至于那些祸害并发程序的老问题，想都不用想！
既然是这样，为什么没有人在那些高度并行的那些应用程序中采用FP编程呢？事实上，这样的例子并不少见。爱立信开发了一种FP语言，名叫Erlang，并应用在他们的电信交换机上，而这些交换机不仅容错度高而且拓展性强。许多人看到了Erlang的这些优势也纷纷开始使用这一语言。在这里提到的电信交换控制系统远远要比华尔街上使用的系统具有更好的扩展性也更可靠。事实上，用Erlang搭建的系统并不具备可扩展性和可靠性，而Java可以提供这些特性。Erlang只是像岩石一样结实不容易出错而已。
FP关于并行的优势不仅于此。就算某个FP程序本身只是单线程的，编译器也可以将其优化成可以在多CPU上运行的并发程序。以下面的程序为例：
String s1 = somewhatLongOperation1();
String s2 = somewhatLongOperation2();
String s3 = concatenate(s1, s2);
如果是函数式程序，编译器就可以对代码进行分析，然后可能分析出生成字符串s1和s2的两个函数可能会比较耗时，进而安排它们并行运行。这在指令式编程中是无法做到的，因为每一个函数都有可能修改其外部状态，然后接下来的函数又可能依赖于这些状态的值。在函数式编程中，自动分析代码并找到适合并行执行的函数十分简单，和分析C的内联函数没什么两样。从这个角度来说用FP风格编写的程序是“永不过时”的（虽然我一般不喜欢说大话空话，不过这次就算个例外吧）。硬件厂商已经没办法让CPU运行得再快了。他们只能靠增加CPU核的数量然后用并行来提高运算的速度。这些厂商故意忽略一个事实：只有可以并行的软件才能让你花大价钱买来的这些硬件物有所值。指令式的软件中只有很小一部分能做到跨核运行，而所有的函数式软件都能实现这一目标，因为FP的程序从一开始就是可以并行运行的。 -
- 时间: 2014-10-17 13:45热部署
在Windows早期，如果要更新系统那可是要重启电脑的，而且还要重启很多次。哪怕只是安装一个新版本的播放器。到了XP的时代这种情况得到比较大的改善，尽管还是不理想（我工作的时候用的就是Windows，就在现在，我的系统托盘上就有个讨厌的图标，我不重启机子就不消失）。这一方面Unix好一些，曾经。只需要暂停一些相关的部件而不是整个操作系统，就可以安装更新了。虽然是要好一些了，对很多服务器应用来说这也还是不能接受的。电信系统要求的是100%的在线率，如果一个救急电话因为系统升级而无法拨通，成千上万的人就会因此丧命。同样的，华尔街的那些公司怎么也不能说要安装软件而在整个周末停止他们系统的服务。
最理想的情况是更新相关的代码而不用暂停系统的其他部件。对指令性程序来说是不可能的。想想看，试着在系统运行时卸载掉一个Java的类然后再载入这个类的新的实现，这样做的话系统中所有该类的实例都会立刻不能运行，因为该类的相关状态已经丢失了。这种情况下可能需绞尽脑汁设计复杂的版本控制代码，需要将所有这种类正在运行的实例序列化，逐一销毁它们，然后创建新类的实例，将现有数据也序列化后装载到这些新的实例中，最后希望负责装载的程序可以正确的把这些数据移植到新实例中并正常的工作。这种事很麻烦，每次有新的改动都需要手工编写装载程序来完成更新，而且这些装载程序还要很小心，以免破坏了现有对象之间的联系。理论上是没问题，可是实际上完全行不通。
FP的程序中所有状态就是传给函数的参数，而参数都是储存在栈上的。这一特性让软件的热部署变得十分简单。只要比较一下正在运行的代码以及新的代码获得一个diff，然后用这个diff更新现有的代码，新代码的热部署就完成了。其它的事情有FP的语言工具自动完成！如果还有人认为这只存在于科幻小说中，他需要再想想：多年来Erlang工程师已经使用这种技术对它们的系统进行升级而完全不用暂停运行了。
ZT: 傻瓜函数式编程
