计算机编程/函数式编程

函数式编程是一种将计算机程序视为数学函数的范式。在使用纯函数式风格编程时，我们不操作状态和变量（会改变值的元素），而是完全关注常量和函数（永远不会改变的元素）。函数式编程 (FP) 的另一个显著特征是函数被视为一等公民。用函数式风格编写的程序通常由接受其他函数作为输入的函数组成。这是 FP 语言的关键特征，因为它使得构建模块化程序变得非常容易。结果是，用 FP 语言编写的软件往往非常简洁。事实上，乌特勒支大学的一组程序员仅用 10,000 行 Haskell 代码（包括图形界面）就构建了用于“构建、编辑和分析贝叶斯网络”的工具。等效的 Java 程序则需要 200,000 行代码，是前者的 20 倍。

想要了解更多？你可以

快速浏览一下函数式编程概览，以获得快速概述
访问函数式编程语言的维基教科书，例如，Haskell（另请参阅Scheme 和 Common Lisp）。
阅读下面的文章（针对来自命令式背景的程序员）

另请参阅过程式编程。

介绍

程序员是拖延症患者。进来，喝杯咖啡，查看邮件，阅读 RSS 订阅，阅读新闻，查看技术网站上的最新文章，浏览编程论坛的指定部分的政治讨论。重复这些步骤，确保没有遗漏任何内容。去吃午饭。回来，盯着 IDE 看几分钟。查看邮件。喝杯咖啡。不知不觉，一天就过去了。

唯一的一点是，偶尔确实会弹出一些有挑战性的文章。如果你访问了正确的地方，你每隔几天就会找到至少一篇这样的文章。这些文章很难读懂，需要一些时间，所以它们开始堆积起来。不知不觉，你有一长串链接和一个装满 PDF 文件的文件夹，你希望自己有一年时间待在一个与世隔绝的森林小屋里，周围没有任何人，这样你就可以追赶进度了。如果有人每天早上在你沿着河边散步时过来送些食物并把垃圾带走，那就太好了。

我不知道你的列表，但我的列表中很大一部分是关于函数式编程的文章。这些文章通常是最难理解的。即使是“十年华尔街行业资深人士”，也无法理解函数式编程（也称为FP）文章的含义。如果你问花旗集团或德意志银行¹ 的项目经理为什么选择使用 JMS 而不是 Erlang，他们会说他们不能使用学术语言来构建工业级应用。问题是，一些最复杂的系统，具有最严格的要求，是用函数式编程元素编写的。某些事情无法解释。

FP 文章和论文确实很难理解，但这并非必然。造成知识差距的原因纯粹是历史性的。FP 概念本身并没有什么难懂之处。将这篇文章视为“FP 的易懂指南”，一座从我们命令式思维桥梁通往 FP 世界的桥梁。喝杯咖啡，继续读下去。如果幸运的话，你的同事很快就会开始因为你在 FP 方面的评论而嘲笑你。

那么什么是 FP？它是怎么产生的？它能吃吗？如果它像它的支持者声称的那样有用，为什么它在行业中没有得到更广泛的应用？为什么只有拥有博士学位的人才会使用它？最重要的是，为什么它如此难学？闭包、延续、柯里化、惰性求值和无副作用这些都是什么？它如何在不涉及大学项目的项目中使用？为什么它似乎与我们命令式思维中所有美好的、神圣的、珍贵的事物如此不同？我们很快就会澄清这一点。让我们从解释现实世界和学术文章之间巨大差距的原因开始。答案就像在公园里散步一样简单。

公园漫步

启动时光机。我们这次公园漫步发生在两千多年前，在公元前 380 年一个被遗忘的春天里一个阳光明媚的下午。在雅典城墙外，在橄榄树的阴凉下，柏拉图带着一个美丽的奴隶男孩走向学院。天气宜人，晚餐很丰盛，谈话转向哲学。

“看看这两个学生，”柏拉图一边说一边仔细地选择词语，以便使问题具有教育意义。“你认为谁更高？”奴隶男孩朝水池望去，那里站着两个人。“他们差不多高，”他说。“你说‘差不多’是什么意思？”柏拉图问道。“嗯，从这里看他们看起来一样高，但我相信如果我走近一点，就会发现他们之间有一些差异。”

柏拉图笑了。他正在引导男孩走向正确的方向。“所以你会说我们世界上没有完全相同的东西？”经过一番思考，男孩回答道：“我认为没有。所有东西至少都有点不同，即使我们看不到。”重点突出了！“那么，如果我们世界上没有完全相同的东西，你认为你是如何理解‘完美’平等的概念的？”奴隶男孩看起来很困惑。“我不知道，”他回答道。

因此，第一次试图理解数学的本质诞生了。柏拉图认为，我们世界上所有事物都只是完美的近似值。他还意识到，即使我们从未遇到过完美，我们也理解完美的概念。他得出的结论是，完美的数学形式必须存在于另一个世界，而我们通过与那个“替代”宇宙的联系而了解它们。很明显，我们无法观察到完美的圆。但我们也理解什么是完美的圆，并且可以通过方程来描述它。那么什么是数学？为什么宇宙是用数学定律来描述的？我们宇宙的所有现象都可以用数学来描述吗？²

数学哲学是一个非常复杂的学科。就像大多数哲学学科一样，它更擅长提出问题而不是提供答案。许多共识围绕这样一个事实：数学实际上是一个谜题：我们建立一组基本的、不冲突的原则，以及一组关于如何操作这些原则的规则。然后我们可以将这些规则叠加在一起，得出更复杂的规则。数学家称这种方法为“形式系统”或“演算”。如果我们想，我们就可以为俄罗斯方块编写一个形式系统。事实上，俄罗斯方块的工作实现本身就是一个形式系统，只是用一种不寻常的表示方式指定。

半人马座阿尔法星上的一群毛茸茸的生物文明将无法阅读我们关于俄罗斯方块和圆圈的形式化，因为它们唯一的感官输入可能是一种感知气味的器官。它们可能永远不会发现关于俄罗斯方块的形式化，但它们很有可能有一个关于圆圈的形式化。我们可能无法阅读它，因为我们的嗅觉没有那么灵敏，但一旦你超越了形式化的表示（通过各种感官仪器和标准的破译技术来理解语言），下面的概念是可以理解的任何智慧文明。

有趣的是，如果宇宙中从未存在过任何智慧文明，那么关于俄罗斯方块和圆圈的形式化仍然会成立，只是没有人会在那里发现它们。如果一个智慧文明出现了，它很可能会发现一些有助于描述我们宇宙定律的形式化。它们也很不可能发现俄罗斯方块，因为宇宙中没有与之相似的东西。俄罗斯方块是无数形式系统（一个谜题）的例子之一，它与现实世界无关。我们甚至不能确定自然数是否与现实世界完全相似，毕竟人们很容易想到一个如此大的数字，以至于它不能描述我们宇宙中的任何东西，因为它实际上可能被证明是有限的。

一点历史³

让我们在我们的时光机中换挡。这一次我们将前往更近的地方，即 1930 年代。大萧条正在席卷新旧世界。几乎每个社会阶层的家庭都受到了这场巨大经济衰退的影响。几乎没有多少庇护所可以让人们免受贫困的危害。很少有人有幸身处这些庇护所，但它们确实存在。我们感兴趣的是普林斯顿大学的数学家。

新建的哥特式风格的办公室为普林斯顿增添了一丝避风港的氛围。来自世界各地的逻辑学家被邀请到普林斯顿建立一个新的系。当大多数美国人找不到一块面包吃晚饭的时候，普林斯顿却拥有高高的天花板、用精雕细琢的木头覆盖的墙壁、每天喝着茶进行讨论，以及在森林中散步等条件。

一位过着如此奢华生活的数学家是一位名叫阿隆佐·丘奇的年轻人。阿隆佐获得了普林斯顿大学的理学士学位，并被劝说留在那里攻读研究生。阿隆佐觉得建筑比必要的更华丽。他很少出现在喝茶讨论数学的时候，也不喜欢在树林里散步。阿隆佐是一个独来独往的人：他独自工作时效率最高。然而，阿隆佐与其他普林斯顿居民定期联系。其中包括艾伦·图灵、约翰·冯·诺依曼和库尔特·哥德尔。

这四个人对形式系统很感兴趣。他们没有过多地关注物理世界，而是对处理抽象的数学难题更感兴趣。他们的难题有一个共同点：这些人都在努力回答关于计算的问题。如果我们拥有具有无限计算能力的机器，我们将能够解决什么问题？我们能自动解决它们吗？一些问题会永远无法解决吗？为什么？具有不同设计的各种机器在能力上是否相等？

阿隆佐·丘奇与其他男士合作开发了一个名为 lambda 演算的形式系统。该系统本质上是这些假想机器之一的编程语言。它基于将其他函数作为参数并返回函数作为结果的函数。该函数由希腊字母 lambda 标识，因此得名⁴。使用这种形式化，阿隆佐能够对上述许多问题进行推理并提供结论性答案。

艾伦·图灵独立于阿隆佐·丘奇进行类似的工作。他开发了一个不同的形式化（现在被称为图灵机），并用它独立地得出了与阿隆佐相似的结论。后来证明，图灵机和 lambda 演算在能力上是等价的。

如果不是因为第二次世界大战的爆发，故事就会在这里结束，我会总结这篇文章，然后你就会转到另一个页面。世界陷入火海。美国陆军和海军比以往任何时候都更频繁地使用炮兵。为了提高精度，陆军雇用了一大批数学家来不断计算解决弹道射击表所需的微分方程。很明显，这项任务对于人工解决来说太大了，因此开发了各种设备来克服这个问题。第一台解决弹道表的机器是由 IBM 制造的 Mark I - 它重达五吨，有 750,000 个部件，每秒可以进行三次运算。

当然，比赛还没有结束。1949 年，电子离散变量自动计算机 (EDVAC) 问世，并取得了巨大的成功。它是冯·诺依曼体系结构的第一个例子，实际上是图灵机的现实世界实现。暂时来说，阿隆佐·丘奇运气不佳。

在 1950 年代后期，麻省理工学院教授约翰·麦卡锡（也是普林斯顿大学毕业生）对阿隆佐·丘奇的工作产生了兴趣。1958 年，他公布了一种列表处理语言 (Lisp)。Lisp 是阿隆佐的 lambda 演算的实现，可以在冯·诺依曼计算机上运行！许多计算机科学家认识到 Lisp 的表达能力。1973 年，麻省理工学院人工智能实验室的一组程序员开发了他们称之为 Lisp 机器的硬件 - 实际上是阿隆佐的 lambda 演算的原生硬件实现！

函数式编程

函数式编程是阿隆佐·丘奇思想的实际应用。并非所有 lambda 演算思想都能转化为实践，因为 lambda 演算并非为在物理限制下工作而设计的。因此，与面向对象编程一样，函数式编程是一组思想，而不是一组严格的准则。存在许多函数式编程语言，它们中的大多数在许多方面都大相径庭。在本文中，我将使用用 Java 编写 (是的，如果你觉得特别虐待狂，你可以在 Java 中编写函数式程序) 的示例解释函数式语言中最广泛使用的思想。在接下来的几节中，我们将按原样使用 Java，并对其进行修改，将其转换为可用的函数式语言。让我们开始我们的探索。

lambda 演算旨在研究与计算相关的问题。因此，函数式编程主要处理计算，并且令人惊讶的是，它使用函数来进行计算。函数是函数式编程中最基本的单元。函数几乎用于所有事情，即使是最简单的计算。甚至变量也被替换为函数。在函数式编程中，变量只是表达式的别名（因此我们不必在一行中输入所有内容）。它们不能被修改。所有变量只能被赋值一次。在 Java 术语中，这意味着每个变量都被声明为final (或者如果我们使用的是 C++，则是const)。FP 中没有非最终变量。

final int i = 5;
final int j = i + 3;

由于 FP 中的每个变量都是最终的，所以可以做出两个相当有趣的陈述。始终编写关键字final 没有意义，并且将变量称为变量也没有意义。现在，我们将对 Java 进行两项修改：我们函数式 Java 中声明的每个变量默认情况下都是最终的，我们将把变量称为符号。

到目前为止，你可能想知道如何在我们新创建的语言中编写任何合理复杂的东西。如果每个符号都是不可变的，我们就无法改变任何东西的状态！这并不完全正确。当阿隆佐研究 lambda 演算时，他并不关心如何维护一段时间内的状态以便以后修改它。他感兴趣的是对数据进行操作（也通常称为“计算东西”。然而，它被证明 lambda 演算等价于图灵机。它可以做命令式编程语言可以做的所有事情。那么，我们如何才能实现相同的结果呢？

事实证明，函数式程序可以保持状态，只是它们不使用变量来做到这一点。它们使用函数来代替。状态保存在函数参数中，在堆栈上。如果你想保留一段时间的状态，并偶尔修改它，你可以编写一个递归函数。例如，让我们写一个反转 Java 字符串的函数。记住，我们声明的每个变量默认都是 final⁵。

String reverse(String arg) {
    if(arg.length == 0) {
        return arg;
    }
    else {
        return reverse(arg.substring(1, arg.length)) + arg.substring(0, 1);
    }
}

这个函数很慢，因为它反复调用自身⁶。它是一个内存占用大户，因为它反复分配对象。但它的风格是函数式的。你可能想知道为什么有人会想要以这种方式编程。嗯，我正要告诉你。

FP 的优点

你可能认为我绝不可能为上面的函数怪物找出一个合理的解释。当我学习函数式编程的时候，我也这么想。我错了。使用这种风格有很多很好的理由。其中一些是主观的。例如，人们声称函数式程序更容易理解。我将省略这些论点，因为每个人都知道理解的难易程度见仁见智。幸运的是，还有很多客观的论点。

单元测试

由于 FP 中的每个符号都是 final，所以没有任何函数能够引起副作用。你永远不能在原地修改东西，也不能一个函数修改其作用域之外的值供另一个函数使用（比如类成员或全局变量）。这意味着，评估一个函数的唯一效果是它的返回值，而影响函数返回值的唯一因素是它的参数。

这对单元测试人员来说非常有用。你可以在你的程序中测试每个函数，只需关注它的参数。你不需要担心以正确的顺序调用函数，或者正确设置外部状态。这意味着你可以减少在编写模拟、存根和其他形式的伪对象上的时间，以及减少在验证测试套件是否运行了设置和拆卸方法上的时间。你所需要做的就是传递代表边缘情况的参数。如果你的程序中的每个函数都通过了单元测试，那么你对软件质量的信心会比使用命令式语言要高得多。在 Java 或 C++ 中，检查一个函数的返回值是不够的 - 它可能会修改外部状态，我们需要验证它。在函数式语言中则不是这样。

调试

如果一个函数式程序的行为不符合预期，调试它将变得轻而易举。你将始终能够重现你的问题，因为函数式程序中的 bug 不依赖于之前执行的无关代码路径。在命令式程序中，bug 只会在某些时候出现。因为函数依赖于由其他函数的副作用产生的外部状态，你可能需要经历一系列与 bug 无关的步骤。在函数式程序中，情况并非如此 - 如果一个函数的返回值是错误的，它就始终是错误的，无论你在运行该函数之前执行了什么代码。

一旦你重现了问题，找到问题的根源就变得非常简单。这几乎是令人愉快的。你中断程序的执行，并检查堆栈。堆栈中每个函数调用中的每个参数都可供你检查，就像在命令式程序中一样。区别在于，在命令式程序中，这还不够，因为函数依赖于成员变量、全局变量和其他类的状态（而这些类又依赖于这些相同的东西）。函数式程序中的函数只依赖于它的参数，而这些信息就在你眼前！此外，在命令式程序中，检查一个函数的返回值并不能很好地告诉你该函数是否正常工作。你需要找出它作用域之外的许多对象，以验证它是否执行了正确的操作。在函数式程序中，你只需要查看返回值！

在堆栈中一步一步地走，查看传递给函数的参数及其返回值。当返回值没有意义时，你就进入有问题的函数，并一步一步地走完它。你递归地重复此过程，直到找到 bug 的根源！

并发

函数式程序已经做好了并发准备，无需任何进一步的修改。你永远不需要担心死锁和竞争条件，因为你不需要使用锁！函数式程序中没有一块数据会被同一个线程修改两次，更不用说被两个不同的线程修改了。这意味着你可以轻松地添加线程，而无需考虑困扰并发应用程序的传统问题！

如果是这样，为什么没有人使用函数式程序来开发高度并发的应用程序呢？事实证明，他们确实使用了。爱立信设计了一种名为 Erlang 的函数式语言，用于其高度容错和可扩展的电信交换机。许多人认识到 Erlang 提供的优势，并开始使用它。我们谈论的是电信和交通控制系统，它们比华尔街设计的典型系统更具可扩展性和可靠性。Erlang 系统非常坚固。

并发的故事并没有止步于此。如果你的应用程序本质上是单线程的，编译器仍然可以优化函数式程序以在多个 CPU 上运行。看看下面的代码片段

String s1 = somewhatLongOperation1();
String s2 = somewhatLongOperation2();
String s3 = concatenate(s1, s2);

在函数式语言中，编译器可以分析代码，将创建字符串s1和s2的函数归类为潜在的耗时操作，并并行运行它们。在命令式语言中这是不可能做到的，因为每个函数都可能修改其作用域之外的状态，而随后的函数可能依赖于它。在函数式语言中，自动分析函数并找到并行执行的良好候选者与自动内联一样简单！从这个意义上说，函数式程序是“面向未来的”（尽管我很讨厌流行语，但这次我忍不住）。硬件制造商无法再让 CPU 运行得更快。相反，他们增加了内核数量，并将四倍的速度提升归功于并发。当然，他们很方便地忘记了，只有在处理并行化问题的软件上，我们才能物有所值。这在命令式软件中只占一小部分，而在函数式软件中则占 100%，因为函数式程序都支持开箱即用的并行化。

热代码部署

在 Windows 的早期，为了安装更新，必须重启计算机。很多次。在安装了更新版本的媒体播放器之后。随着 Windows XP 的出现，情况有了显著改善，但它仍然不是理想的（我今天在工作中运行了 Windows Update，现在一个烦人的系统托盘图标不会消失，除非我重启）。Unix 系统已经有一段时间了，它们有一个更好的模型。为了安装更新，你只需要停止相关的组件，而不是整个操作系统。虽然这种情况已经改善，但对于一大类服务器应用程序来说，它仍然不可接受。电信系统需要 100% 的时间运行，因为如果由于升级而无法拨打紧急电话，可能会造成人员伤亡。华尔街的公司没有理由在周末停机安装软件更新。

理想的情况是在不停止系统任何部分的情况下更新代码的相关部分。在命令式世界中，这是不可能的。考虑在运行时卸载 Java 类并重新加载新的定义。如果我们这样做，类的每个实例都将变得不可用，因为它所持有的状态将丢失。我们需要求助于编写棘手的版本控制代码。我们需要序列化所有正在运行的类实例，销毁它们，创建新类的实例，尝试将序列化数据加载到它们中，并希望加载代码能够将数据正确地迁移到新实例中。最重要的是，每次我们改变一些东西时，我们都必须手动编写迁移代码。而且我们的迁移代码必须特别小心，不要破坏对象之间的关系。理论上很好，但在实践中永远不会有效。

在函数式程序中，所有状态都存储在堆栈中，存储在传递给函数的参数中。这使得热部署变得容易得多！事实上，我们真正需要做的就是运行生产代码和新版本之间的 diff，并部署新代码。剩下的可以由语言工具自动完成！如果你认为这是科幻小说，那就再想想。Erlang 工程师已经升级了运行中的系统多年，而没有停止它们。

机器辅助证明和优化

函数式语言的一个有趣的特性是它们可以用数学方法进行推理。由于函数式语言仅仅是形式系统的实现，因此所有可以在纸上进行的数学运算仍然适用于用该语言编写的程序。例如，编译器可以将代码片段转换为等效的但更有效的代码片段，并用数学证明两个代码片段是等效的⁷。关系型数据库多年来一直在执行这些优化。没有理由同样的技术不能应用于常规软件。

此外，您可以使用这些技术来证明程序的某些部分是正确的。甚至可以创建工具来分析代码并自动生成单元测试的边缘案例！此功能对于坚如磐石的系统来说非常宝贵。如果您正在设计起搏器和空中交通管制系统，这些工具几乎总是必需的。如果您正在编写非真正关键任务行业的应用程序，这些工具可以使您在竞争中占据巨大优势。

高阶函数

我记得我学到上面列出的好处时，心想“这很好，但如果我必须用一种功能受限的语言编程，而其中所有东西都是最终的，那这毫无用处。”这是一个误解。在像 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 类没有什么不同（我们可以将类实例传递给其他类）。我们可以称它们为“高阶类”，但没有人关心，因为 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);

我们没有创建新的类型，也没有创建类层次结构。我们只是将合适的函数作为参数传递。我们以面向对象对应物的优势实现了相同的功能。我们不会将自己限制在类层次结构中：我们可以在运行时传递新的函数，并在任何时候以更高的粒度、更少的代码来更改它们。实际上，编译器为我们编写了面向对象的“粘合”代码！此外，我们获得了 FP 的所有其他好处。当然，函数式语言提供的抽象不会止步于此。高阶函数只是开始。

柯里化

我遇到的大多数人读过四人帮写的 _设计模式_ 一书。任何自尊的程序员都会告诉你，这本书与语言无关，这些模式适用于一般的软件工程，无论你使用哪种语言。这是一个崇高的主张。不幸的是，它与事实相去甚远。

函数式语言表达能力极强。在函数式语言中，不需要设计模式，因为语言可能非常高级，最终你会用一些概念编程，这些概念完全消除了设计模式。一旦这样的模式是适配器模式（它与外观模式有何不同？听起来像是有人需要填写更多页面来满足他们的合同）。一旦语言支持一种称为 _柯里化_ 的技术，它就会被消除。

适配器模式在应用于 Java 中的“默认”抽象单元（类）时最为人知。在函数式语言中，该模式应用于函数。该模式采用接口，将其转换为其他人期望的另一个接口。以下是一个适配器模式的示例

int pow(int i, int j);
int square(int i)
{
    return pow(i, 2);
}

上面的代码将一个将整数升到整数次幂的函数的接口适配到一个将整数平方为整数的函数的接口。在学术界，这种微不足道的技术被称为柯里化（以逻辑学家 Haskell Curry 的名字命名，他进行了将这种技术形式化的数学特技）。因为在 FP 中，函数（与类相反）作为参数传递，所以柯里化经常被用来将函数适配到其他人期望的接口。由于函数的接口是其参数，因此柯里化用于减少参数数量（如上面的示例中）。

函数式语言内置了这种技术。您不需要手动创建一个包装原始函数的函数，函数式语言会为您做到这一点。像往常一样，让我们扩展我们的语言以支持这种技术。

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();

如您所见，我们只是为原始函数创建了一个包装器。在 FP 中，柯里化仅仅是 - 一种快速轻松地创建包装器的捷径。您专注于自己的任务，编译器会为您编写合适的代码！您什么时候使用柯里化？这应该很简单。任何时候您想使用适配器模式（包装器）。

惰性求值

惰性（或延迟）求值是一种有趣的技术，一旦我们采用函数式哲学，它就成为可能。我们已经在讨论并发时看到了以下代码片段

String s1 = somewhatLongOperation1();
String s2 = somewhatLongOperation2();
String s3 = concatenate(s1, s2);

在命令式语言中，求值的顺序将是明确的。因为每个函数都可能影响或依赖于外部状态，所以有必要按顺序执行它们：首先是 somewhatLongOperation1，然后是 somewhatLongOperation2，最后是 concatenate。在函数式语言中则不然。

正如我们之前所看到的，somewhatLongOperation1 和 somewhatLongOperation2 可以并发执行，因为我们保证没有函数影响或依赖于全局状态。但是，如果我们不想并发运行这两个函数，我们是否需要按顺序运行它们？答案是否定的。我们只需要在另一个函数依赖于 s1 和 s2 时运行这些操作。我们甚至不必在调用 concatenate 之前运行它们 - 我们可以延迟它们的求值，直到它们在 concatenate 中被需要。如果我们将 concatenate 替换为一个具有条件语句并只使用两个参数之一的函数，我们可能根本不会对其中一个参数进行求值！Haskell 是一个延迟求值语言的例子。在 Haskell 中，您不能保证任何东西都会按顺序（或完全）执行，因为 Haskell 只会在需要时执行代码。

惰性求值有很多优点和缺点。我们将在这里讨论优点，并在下一节中解释如何克服缺点。

优化

惰性求值为优化提供了巨大的潜力。一个惰性编译器对函数式代码的看法与数学家对代数表达式的看法完全相同 - 它可以消除某些东西，并完全阻止执行，重新排列代码片段以提高效率，甚至以减少错误的方式安排代码，所有这些都保证优化不会破坏代码。这是用严格的形式原语表示程序的最大好处 - 代码遵循数学定律，可以用数学方法进行推理。

抽象控制结构

惰性求值提供了更高层次的抽象，允许以其他方式不可能的方式实现事物。例如，考虑实现以下控制结构

unless(stock.isEuropean()) {
    sendToSEC(stock);
}

我们希望除非股票是欧洲股票，否则执行 sendToSEC。我们如何实现 unless？如果没有惰性求值，我们需要某种宏系统，但在像 Haskell 这样的语言中，这是不必要的。我们可以将 unless 实现为一个函数！

void unless(boolean condition, List code) {
    if(!condition)
        code;
}

请注意，如果条件为真，则代码永远不会被评估。由于参数将在unless之前进行评估，因此我们无法在严格的语言中复制此行为。

无限数据结构

惰性语言允许定义无限数据结构，这在严格的语言中要复杂得多。例如，考虑一个包含斐波那契数的列表。很明显，我们无法在合理的时间内计算一个无限列表，也无法将其存储在内存中。在像Java这样的严格语言中，我们只需定义一个斐波那契函数，它从序列中返回特定成员。在像Haskell这样的语言中，我们可以进一步抽象，并简单地定义一个无限的斐波那契数列表。由于该语言是惰性的，因此程序实际使用的列表的必要部分才会被评估。这允许抽象出许多问题，并从更高的层次（例如，我们可以对无限列表使用列表处理函数）来解决这些问题。

缺点

当然，没有免费的午餐™。（除非你幸运。）惰性求值似乎带来了一些缺点。主要是因为它很懒，有时不允许程序员也随心所欲，这意味着在某些情况下，你需要使用一些变通方法。现实世界中存在需要严格求值的问题。例如，考虑以下情况

System.out.println("Please enter your name: ");
System.in.readLine();

在惰性语言中，你无法保证第一行会在第二行之前执行！这意味着，如果惰性是绝对的原则，我们就无法进行IO，也无法以任何有意义的方式使用原生函数（因为它们需要按顺序调用，因为它们依赖于副作用），也不能与外部世界交互！如果我们要引入强制顺序代码执行的原语，我们将失去以数学方式推理代码的能力（这将带走函数式编程的所有好处）。幸运的是，并非所有希望都破灭了。数学家们开始研究并开发了许多技巧，以确保代码在函数式环境中按特定顺序执行。因此，我们真的得到了两全其美！这些技术包括延续、单子、以及唯一类型。在本文中，我们只讨论延续。我们将在以后讨论单子和唯一类型。有趣的是，延续除了强制执行特定的评估顺序之外，还有很多其他的用途。我们也会讨论这些。

延续

延续对于编程来说，就像达芬奇密码对于人类历史一样：一个关于人类历史上最伟大的掩盖的惊人启示。好吧，也许不是，但它们确实揭示了欺骗，就像负数的平方根一样。

当我们学习函数时，我们只学习了基于一个错误假设的半真半假的内容，即函数必须将其值返回给原始调用者。从这个意义上说，延续是函数的泛化。函数不一定要返回给它的调用者，它可以返回到程序的任何部分。“延续”是我们选择传递给函数的参数，它指定函数应该返回的位置。描述可能比听起来更复杂。看看下面的代码

int i = add(5, 10);
int j = square(i);

函数add返回15，以便分配给i，即add最初被调用的地方。之后，i的值被用来调用square。请注意，惰性编译器不能重新排列这些代码行，因为第二行依赖于第一行的成功评估。我们可以使用Continuation Passing Style（CPS）重写此代码块，其中函数add不返回给原始调用者，而是将结果返回给square。

int j = add(5, 10, square);

在这种情况下，add获得了另一个参数 - 一个函数，add必须在完成时用其结果调用该函数。在本例中，square是add的延续。在这两种情况下，j都将等于225。

这里包含了迫使惰性语言按顺序评估两个表达式的第一个技巧。考虑以下（熟悉的）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可以接受），我们将解决我们的问题！当然，像这样链接函数调用很快就会变得难以阅读，但这不是必需的。我们可以向语言添加语法糖，允许我们按顺序简单地键入表达式，编译器将自动为我们链接这些调用。我们现在可以按照我们希望的任何顺序评估表达式，而不会失去FP的任何好处（包括以数学方式推理程序的能力）！如果这仍然令人困惑，请记住，函数只是具有一个成员的类的实例。重写上面两行，使println和readLine成为类的实例，一切都会变得清晰。

我现在将结束本节，因为我们只触及了延续及其有用性的皮毛。我们可以用CPS编写完整的程序，其中每个函数都接受一个额外的延续参数，并将结果传递给它。我们还可以简单地将任何程序转换为CPS，方法是将函数视为延续的特例（总是返回给其调用者的函数）。这种转换很容易自动完成（实际上，许多编译器就是这么做的）。

一旦我们将程序转换为CPS，就会发现每个指令都有一个延续，一个函数，它将使用结果调用该函数，这在常规程序中将是它必须返回到的位置。让我们从上面的代码中选择任何一条指令，比如add(5, 10)。在用CPS编写的程序中，很清楚add的延续是什么 - 它是一个函数，add完成时会调用它。但在非CPS程序中呢？当然，我们可以将程序转换为CPS，但我们必须这样做吗？

事实证明我们不需要。仔细观察我们的CPS转换。如果你尝试为它编写一个编译器，并仔细考虑它，你会意识到CPS版本不需要堆栈！没有函数以传统意义上“返回”，它只是用结果调用另一个函数。我们不需要在每次调用时将函数参数压入堆栈，然后将它们弹出，我们只需将它们存储在内存的某个块中，并使用跳转指令。我们永远不需要原始参数 - 它们永远不会被再次使用，因为没有函数会返回！

因此，用CPS编写的程序没有堆栈，但有一个带有函数的额外参数要调用。没有用CPS编写的程序没有带有函数的额外参数要调用，但有堆栈。堆栈包含什么？仅仅是参数，以及指向函数应该返回的内存位置的指针。你看到灯泡了吗？堆栈只是包含延续信息！指向堆栈中返回指令的指针本质上与CPS程序中要调用的函数相同！如果你想找出add(5, 10)的延续是什么，你只需要检查它执行时的堆栈即可！

所以这很容易。延续和指向堆栈中返回指令的指针实际上是一回事，只是显式地传递了一个延续，因此它不需要与调用函数的相同位置相同。如果你记得延续是一个函数，而我们语言中的函数被编译成一个类的实例，你会意识到，指向堆栈中返回指令的指针和延续参数实际上是一回事，因为我们的函数（就像类的实例一样）只是一个指针。这意味着，在程序中的任何给定时间点，你都可以请求当前延续（它只是堆栈上的信息）。

好的，我们已经知道什么是当前延续，那它意味着什么呢？当我们获取当前延续并将它存储在某个地方时，我们最终会存储程序的当前状态 - 将其冻结在时间中。这类似于操作系统将自身置于休眠状态。延续对象包含重启程序所需的信息，从获取延续对象的位置开始。操作系统在它在线程之间切换上下文时一直这样做。唯一的区别是它保留了所有控制权。如果你请求一个延续对象（在 Scheme 中，这是通过调用 `call-with-current-continuation` 函数完成的），你将得到一个包含当前延续的对象 - 栈（或者在 CPS 情况下，下一个要调用的函数）。你可以将此对象存储在一个变量中（或者也可以存储在磁盘上）。当你选择使用这个延续对象“重启”你的程序时，你将“转换”到获取延续对象时程序的状态。这与切换回一个挂起的线程或唤醒操作系统从休眠状态相同，只是你可以反复执行。当操作系统唤醒时，休眠信息会被销毁。如果它没有被销毁，你将能够一遍又一遍地从同一个点唤醒，几乎就像回到过去。你拥有使用延续的这种控制权！

在哪些情况下延续是有用的？通常当你尝试在一个本质上是无状态的应用程序中模拟状态以简化你的生活时。延续的一个很好的应用是 Web 应用程序。微软的 ASP.NET 竭尽全力地尝试模拟状态，以便你能更容易地编写你的应用程序。如果 C# 支持延续，ASP.NET 的一半复杂性将会消失 - 你只需存储一个延续并在用户再次发出 Web 请求时重启它。对于 Web 应用程序的程序员来说，将不会有任何中断 - 程序将简单地从下一行开始！延续对于一些问题来说是一个非常有用的抽象。考虑到许多传统的胖客户端正在转向 Web，延续在未来会变得越来越重要。

模式匹配

模式匹配不是一个新的或创新的特性。事实上，它与函数式编程关系不大。它通常被归因于 FP 的唯一原因是函数式语言已经有了模式匹配一段时间了，而现代的命令式语言还没有。

让我们通过一个例子深入了解模式匹配。这是一个在 Java 中的斐波那契函数

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);
}

（不要尝试使用更高的数字，因为这个算法不适合更高的数字，因为它具有 ${\mathcal {O}}(2^{n})$ 时间复杂度；`fib(35)` 将会花费相当长的时间）

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

有什么大不了的？没什么。有人注意到大量的函数包含非常复杂的 switch 语句（这对函数式程序来说尤其如此），并决定将这些抽象出来是一个好主意。我们将函数定义拆分为多个，并将模式放在一些参数的位子上（有点像重载）。当函数被调用时，编译器在运行时将参数与定义进行比较，并选择正确的定义。这通常是通过选择最具体的可用定义来完成的。例如，`int fib(int n)` 可以用 `n` 等于 `1` 来调用，但它不会被调用，因为 `int fib(1)` 更具体。

另一个可能性，你可以在 Haskell 中找到，是按定义的顺序检查模式（函数式程序中表达式顺序为数不多的几个重要的例子之一，但你的大部分代码可以按任何你想要的顺序编写，这非常方便）。例如，函数的参数可能针对三种模式进行测试：`fun (x < 100)`、`fun (x < 1000)`、`fun (x = anything)`，当用 `x = 50` 调用时，将使用其定义的第一个实例，尽管 `x = 50` 也适合另外两个实例。（从数学意义上讲，考虑到负数，这些定义中没有一个是更具体的，因为匹配模式的集合的大小都相同。）在这个系统中，你通常按顺序排列定义，以便更具体的定义排在前面，这会自动涵盖决定使用哪个函数实例的其他方式。

模式匹配通常比我们的例子更复杂。例如，一个高级模式匹配系统将允许我们执行以下操作

int f(int n < 10) { ... }
int f(int n) { ... }

模式匹配什么时候有用？在令人惊讶的大量情况下！每当你有一个嵌套 `if` 的复杂结构时，模式匹配可以使用更少的代码来完成更好的工作。一个想到的好函数是所有 Win32 应用程序都必须提供的标准 `WndProc` 函数（即使它通常被抽象掉了）。通常情况下，模式匹配系统可以检查集合以及简单值。例如，如果你将一个数组传递给你的函数，你可以挑选出所有第一个元素等于 `1` 且第三个元素大于 `3` 的数组。

模式匹配的另一个好处是，如果你需要添加或修改条件，你不需要进入一个巨大的函数。你只需添加（或修改）相应的定义即可。这消除了对 Gang of Four 书籍中的一系列设计模式的需求。你的条件越复杂，模式匹配就能越帮助你。一旦你习惯了它，你就会开始思考没有它你曾经是如何度过每一天的。

闭包

到目前为止，我们已经在“纯粹”函数式语言的背景下讨论了这些特性 - 这些语言是 lambda 演算的实现，不包含与 Church 形式主义冲突的特性。然而，函数式语言的许多特性在 lambda 演算框架之外也很有用。虽然一个公理化系统的实现很有用，因为它允许用数学表达式来思考程序，但它可能实用也可能不实用。许多语言选择包含函数式元素，而没有严格遵守函数式教条。许多这样的语言（如 Common Lisp）不要求变量是最终的 - 你可以在适当的位置修改它们。它们也不要求函数只依赖于它们的参数 - 函数被允许访问它们边界之外的状态。但是它们确实包含函数式特性 - 比如高阶函数。在非纯语言中传递函数与在 lambda 演算的限制下传递函数略有不同，它需要对一个有趣的特性提供支持，这个特性通常被称为词法闭包。让我们看一些示例代码。记住，在这种情况下，变量不是最终的，函数可以引用其范围之外的变量

Function makePowerFn(int power) {
   int powerFn(int base) {
       return pow(base, power);
   }

   return powerFn;
}

Function square = makePowerFn(2);
square(3); // returns 9

函数 `makePowerFn` 返回一个函数，该函数接收一个参数并将它提升到某个幂。当我们尝试评估 `square(3)` 时会发生什么？变量 `power` 在 `powerFn` 的范围内不存在，因为 `makePowerFn` 已经返回，它的栈早就消失了。那么 `square` 如何工作呢？该语言必须以某种方式将 `power` 的值存储在某个地方，以便 `square` 工作。如果我们创建一个新的函数 `cube`，它将某个值提升到三次幂，会发生什么？运行时现在必须存储 `power` 的两个副本，一个用于每个使用 `makePowerFn` 生成的函数。存储这些值的现象被称为 `闭包`。闭包不仅存储宿主函数的参数。例如，闭包可以是这样的

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`，以便 `incrementer` 可以访问它。此外，它存储了各个副本，每个 `incrementer` 一个，即使它们应该在 `makeIncrementer` 返回时消失。这段代码编译成什么？闭包在幕后是如何工作的？幸运的是，我们有一个后台通行证。

一点常识可以走很远。第一个观察结果是，局部变量不再局限于简单的范围规则，并且具有未定义的寿命。显而易见的结论是，它们不再存储在栈上 - 它们必须存储在堆上8。那么，闭包的实现方式就像我们之前讨论的函数一样，只是它有一个额外的引用指向周围的变量

class some_function_t {
   SymbolTable parentScope;
   
   // ...
}

当一个闭包引用一个不在其局部范围内的变量时，它会查询这个引用以获取父范围。就是这样！闭包使函数式和面向对象的世界更接近。每次你创建一个包含某些状态的类并将其传递到其他地方时，都想想闭包。闭包只是一个对象，它通过从范围内获取它们来动态创建“成员变量”，因此你不需要这样做！

接下来是什么？

这篇文章只是触及了函数式编程的表面。有时一个小小的划痕可以发展成更大的东西，在我们的例子中，这是一件好事。在将来，我计划写一些关于范畴论、单子、函数式数据结构、函数式语言中的类型系统、函数式并发、函数式数据库等等的内容。如果我能够写出（并在这个过程中学习）这些主题中的一半，我的生活将完整无缺。同时，Google 是我们的朋友。

评论？

如果你有任何问题、评论或建议，请在 [email protected] 上留言。我很乐意听到你的反馈。

¹2005 年秋季找工作的时候，我经常问这个问题。有趣的是，很多人对此一脸茫然。你会以为，这些价值 30 万美元的人至少应该对他们能用的工具有所了解吧。

²这个问题似乎颇具争议。物理学家和数学家不得不承认，宇宙中所有事物是否都遵循可以用数学描述的规律，目前尚不清楚。

³我一直不喜欢那些枯燥地列出年代、人物和事件的历史课。对我来说，历史是关于改变世界的人们的故事。它关乎他们行动背后的个人原因，以及他们影响数百万人的机制。因此，本历史部分内容不完整。只讨论了非常重要的人物和事件。

⁴学习函数式编程时，我对 “lambda” 这个词感到很困惑，因为它让我难以理解其真正的含义。在这个语境下，lambda 指的是函数，用单个希腊字母在数学符号中更易于书写。每次你听到函数式编程中的 “lambda”，就在脑海中将其替换为 “函数”。

⁵有趣的是，Java 字符串本身就是不可变的。探索其背后的原因很有意思，但会偏离我们的目标。

⁶大多数函数式语言编译器会通过将递归函数转换为迭代形式来优化它们，只要有可能就会这样做。这被称为尾调用优化（tail call optimization）。

⁷反过来却不一定成立。虽然有时可以证明两段代码等价，但在所有情况下都无法做到。

⁸实际上，这并不比存储在栈上慢，因为一旦引入了垃圾收集器，内存分配就变成了一个 O(1) 操作。

介绍