计算机编程/函数式编程

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

想要了解更多？您可以

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

另请参阅过程式编程。

简介

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

唯一的一点是，偶尔确实会出现具有挑战性的文章。如果你查看正确的地方，你会发现每隔几天至少有一篇这样的文章。这些文章很难读懂，需要花一些时间，所以它们开始堆积起来。不知不觉中，你拥有一份链接列表和一个装满 PDF 文件的文件夹，你希望自己有一年时间住在森林中央的一间小屋里，周围方圆数英里都没有人，这样你就能赶上进度。如果有人在你每天早晨沿着河边散步时进来送食物并把垃圾拿走，那就太好了。

我不知道你的列表，但我列表中很大一部分文章都是关于函数式编程的。这些通常是最难读懂的。即使是“十年华尔街行业老手”也无法理解函数式编程（也称为FP）文章的全部内容。如果你问花旗集团或德意志银行的项目经理¹ 为什么他们选择使用 JMS 而不是 Erlang，他们会说他们无法将学术语言用于工业级应用程序。问题是，一些最复杂的系统，它们具有最严格的要求，是用函数式编程元素编写的。有些地方不对劲。

确实，FP 文章和论文很难理解，但它们并不一定如此。造成知识差距的原因纯粹是历史性的。FP 概念本身并不难。将这篇文章视为“通往 FP 的便捷指南”，是我们从命令式思维模式到 FP 世界的桥梁。喝点咖啡，继续阅读。幸运的话，你的同事很快就会开始嘲笑你关于 FP 的评论。

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

公园漫步

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

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

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

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

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

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

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

一点历史³

让我们在时间机器中换档。这次我们会走得更近一些，到1930年代。大萧条席卷了新旧世界。几乎每个社会阶层的家庭都受到了这场巨大经济衰退的影响。人们远离贫困的危险，几乎没有安全的地方。很少有人有幸身处这些避风港，但它们确实存在。我们感兴趣的是普林斯顿大学的数学家。

用哥特式风格建造的新办公室赋予了普林斯顿一种避风港的氛围。来自世界各地的逻辑学家被邀请到普林斯顿，建立一个新的系。当美国大多数人无法找到一块面包来吃晚餐时，普林斯顿却拥有高高的天花板、覆盖着精雕细刻的木头的墙壁、每天一杯茶的讨论和森林里的散步。

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

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

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

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

如果没有第二次世界大战的爆发，故事就会到此结束，我会结束这篇文章，而你会导航到另一个页面。全世界都陷入战火。美国陆军和海军比以往任何时候都更频繁地使用火炮。为了提高精度，陆军雇佣了一大批数学家来不断计算解决弹道射击表所需的微分方程。很明显，这项任务太繁重了，无法手动完成，因此开发了各种设备来克服这个问题。第一台解决弹道表的机器是 IBM 制造的 Mark I——它重达 5 吨，拥有 750,000 个零件，每秒钟可以执行 3 次操作。

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

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

函数式编程

函数式编程是阿隆佐·丘奇思想的实际实现。并非所有的 lambda 演算思想都转化为实践，因为 lambda 演算并非设计用于在物理限制下工作。因此，与面向对象编程一样，函数式编程是一组思想，而不是一组严格的准则。有许多函数式编程语言，它们中的大多数在很多方面都大不相同。在这篇文章中，我将使用用 Java 编写的示例解释函数式语言中最常用的思想（是的，如果你觉得特别受虐，你可以在 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 字符串的函数。请记住，我们声明的每个变量默认情况下都是最终的⁵。

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

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

FP 的优势

你可能在想，我绝不可能为上面那个函数的怪异行为辩解。当我学习函数式编程时，我也是这么想的。我错了。使用这种风格有很多很好的理由。其中一些是主观的。例如，人们声称函数式程序更容易理解。我会省略这些论点，因为每个街区的孩子都知道理解的难易程度是见仁见智的。幸运的是，对我有利的是，有很多客观论据。

单元测试

由于 FP 中的每个符号都是最终的，因此任何函数都无法产生副作用。你永远无法就地修改事物，也不能让一个函数修改其作用域之外的值供另一个函数使用（例如类成员或全局变量）。这意味着评估函数的唯一效果是它的返回值，而影响函数返回值的唯一因素是它的参数。

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

调试

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

一旦你重现了问题，找出根本原因就变得微不足道。这几乎是一种享受。你中断程序的执行并检查堆栈。堆栈中每个函数调用中的每个参数都可供你检查，就像在命令式程序中一样。除了在命令式程序中，这还不够，因为函数依赖于成员变量、全局变量和其他类的状态（而这些类反过来又依赖于这些东西）。函数式程序中的函数只依赖于它的参数，而该信息就在你的眼前！此外，在命令式程序中，检查函数的返回值并不能让你很好地判断该函数是否正常运行。你需要追踪其作用域之外的数十个对象，以验证它是否执行了正确的操作。在函数式程序中，你只需要查看返回值就行了！

遍历堆栈，查看传递给函数的参数及其返回值。只要返回值没有意义，你就进入有问题的函数并遍历它。你递归地重复这个过程，直到这个过程把你带到错误的源头！

并发性

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

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

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

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

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

热代码部署

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

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

在函数式程序中，所有状态都存储在堆栈中，位于传递给函数的参数中。这使得热部署变得非常容易！实际上，我们真正需要做的只是运行生产代码和新版本代码之间的差异，并部署新代码。其余的可以通过语言工具自动完成！如果你认为这是科幻小说，那就再想想。Erlang 工程师多年来一直升级实时系统，而无需停止它们。

机器辅助证明和优化

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

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

高阶函数

我记得学习上面概述的优点时，我曾想“这很好，但如果我必须用一种受限的语言编程，其中所有东西都是最终的，那将毫无用处”。这是一种误解。在像 Java 这样的命令式语言的环境中，使所有变量都成为最终的是受限的，但在函数式语言的环境中则不然。函数式语言提供了不同类型的抽象工具，使你忘记你曾经喜欢修改变量。其中一个工具是使用高阶函数的能力。

在这些语言中，函数不同于 Java 或 C 中的函数。它是一个超集——它可以做 Java 函数可以做的所有事情，以及更多。我们在 C 中创建函数的方式相同

int add(int i, int j) {
    return i + j;
}

这与等效的 C 代码有不同的含义。让我们扩展我们的 Java 编译器以支持这种表示法。当我们输入类似以下内容时，我们的编译器会将其转换为以下 Java 代码（不要忘记，所有内容都是最终的）

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

请注意，如果条件为真，则code永远不会被求值。我们无法在严格的语言中再现这种行为，因为参数将在进入unless之前被求值。

无限数据结构

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

缺点

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

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

在惰性语言中，你无法保证第一行代码会在第二行代码之前执行！这意味着，如果惰性是绝对原则，我们就无法进行 I/O，也无法以任何有意义的方式使用原生函数（因为它们需要按顺序调用，因为它们依赖于副作用），也无法与外部世界交互！如果我们引入强制代码按顺序执行的原语，我们将失去以数学方式推理代码的能力（这将带走函数式编程的所有好处）。幸运的是，并非所有东西都丢失了。数学家们开始工作，开发了一些技巧来确保代码在函数式环境中按特定顺序执行。因此我们真正获得了两全其美！这些技术包括延续、单子、唯一性类型。在这篇文章中，我们只讨论延续。我们会留出单子和唯一性类型，在下次再讨论。有趣的是，延续对除了强制特定求值顺序之外的许多事情都有用。我们也会谈到这一点。

延续

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

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

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。

这里介绍了第一个技巧，它强制惰性语言按顺序计算两个表达式。考虑以下（熟悉的）I/O 代码

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 的情况下是下一个要调用的函数）。你可以将此对象存储在变量中（或者在磁盘上）。当你选择用这个延续对象“重新启动”程序时，你将“转换”到获取延续对象时程序的状态。这与切换回挂起的线程或从休眠状态唤醒操作系统一样，只是你可以一遍又一遍地执行。当操作系统醒来时，休眠信息会被销毁。如果它没有被销毁，你将能够从同一个点醒来，就像回到过去一样。你用延续就可以控制这一切！

在哪些情况下，延续（Continuation）是有用的？通常，当你在一个本质上无状态的应用程序中模拟状态以简化你的工作时，延续就派上用场了。一个很好的延续应用例子是 Web 应用程序。微软的 ASP.NET 竭尽全力尝试模拟状态，以便你能够更轻松地编写应用程序。如果 C# 支持延续，ASP.NET 中一半的复杂性就会消失——你只需存储一个延续，并在用户再次发起 Web 请求时重新启动它。对于 Web 应用程序的程序员来说，不会有任何中断——程序会直接从下一行开始执行！延续对于某些问题来说是一个非常有用的抽象。考虑到许多传统的胖客户端正在迁移到 Web，延续在未来会变得越来越重要。

模式匹配

模式匹配并不是一个新颖的功能。事实上，它与函数式编程关系不大。它通常被归功于函数式编程的唯一原因是，函数式语言已经拥有模式匹配功能很长时间了，而现代命令式语言还没有。

让我们通过一个例子深入了解模式匹配。这是一个用 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，以便 incrementers 可以访问它。此外，它存储了多个副本，每个副本对应于每个 incrementer，即使它们应该在 makeIncrementer 返回时消失。这段代码编译成什么？闭包在幕后是如何工作的？幸运的是，我们有后台通行证。

一点常识可以走很远。第一个观察是，局部变量不再局限于简单的作用域规则，并且具有未定义的生存期。显而易见的结论是，它们不再存储在堆栈上——它们必须存储在堆上⁸。然后，闭包就像我们之前讨论过的函数一样实现，只是它额外包含一个对周围变量的引用

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

当闭包引用一个不在其局部作用域内的变量时，它会咨询这个对父作用域的引用。就是这样！闭包将函数式和面向对象的世界更紧密地联系在一起。每当你创建一个包含某些状态并将其传递到其他地方的类时，想想闭包。闭包只是一个对象，它通过从作用域中获取变量来动态创建“成员变量”，因此你不必这样做！

接下来呢？

本文只是触及了函数式编程的皮毛。有时，一个小小的触及可以发展成更大的东西，在我们这个例子中，这是一件好事。在未来，我计划撰写关于范畴论、单子、函数式数据结构、函数式语言中的类型系统、函数式并发、函数式数据库以及更多内容的文章。如果我能写（并在这个过程中学习）这些主题中的一半，我的生命将圆满。与此同时，谷歌是我们的朋友。

评论？

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

¹当我在 2005 年秋季寻找工作时，我经常问这个问题。真是有趣，我收到了多少茫然的眼神。你可能会认为，以大约 30 万美元的价格，这些人至少应该对他们可用的绝大多数工具有一个很好的理解。

²这个问题似乎很有争议。物理学家和数学家被迫承认，宇宙中的一切是否都遵循可以用数学描述的定律，目前还不清楚。

³我一直讨厌那些提供干巴巴的年代、姓名和事件的史料。对我来说，历史是关于改变世界的人的故事。它是关于他们行动背后的私人原因，以及他们影响数百万灵魂的机制。出于这个原因，这个历史部分是不完整的。只讨论了非常相关的人和事件。

⁴当我学习函数式编程时，我非常讨厌“lambda”这个词，因为我真的不明白它的真正含义。在这个上下文中，lambda 是一个函数，使用单个希腊字母只是在数学符号中更容易写。每次你听到关于函数式编程的“lambda”时，就把它在你的脑海里翻译成“函数”。

⁵有趣的是，Java 字符串本来就是不可变的。探索这种欺诈背后的原因很有趣，但这会让我们偏离目标。

⁶大多数函数式语言编译器会通过将递归函数转换为迭代的替代方案（只要可能）来优化它们。这被称为尾递归优化。

⁷反过来并不总是成立。虽然有时可以证明两段代码是等价的，但在所有情况下都不行。

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

简介