深入理解 Java 函数式编程系列第 1 部分 函数式编程思想概论

前言

在讨论函数式编程（Functional Programming）的具体内容之前，我们先来看看函数式编程的含义。在维基百科上，函数式编程的定义如下：“函数式编程是一种编程范式，它将计算视为数学函数的评估，避免改变状态并使用可变数据。它是一种声明式编程范式，通过表达式和声明而不是语句进行编程” （参见函数式编程）

函数式编程思想在软件开发领域由来已久。在众多的编程范式中，函数式编程虽然由来已久，但在编程范式领域乃至整个开发社区的热度一直不温不火。函数式编程有一些狂热的支持者。在他们眼里，函数式编程的思想是解决各种软件开发问题的终极方案；而另一些人则认为函数式编程的思想不容易理解，学习曲线比较慢。这是陡峭的，很难开始。大多数人更愿意接受面向对象或面向过程的编程范式。这也是函数式编程范式一直停留在小众阶段的原因。

这样的两极反应与函数式编程本身的特性是分不开的。函数式编程的思想脱胎于数学理论，也就是我们通常所说的λ演算（λ-calculus）。听到数学理论，很多人可能会觉得脑袋变大了。这确实是函数式编程学习曲线陡峭的原因之一。与数学中的函数一样，函数式编程范例中的函数具有独特的属性，通常称为无状态或引用透明性。一个函数的输出由它的输入决定，而且只由它的输入决定，同样的输入总是产生同样的输出。这使得函数式编程在处理许多与状态相关的问题时具有天然优势。函数式编程代码通常更简洁，但不一定可以理解。函数式编程解决方案有一种优雅之美。

函数式编程涵盖的内容非常广泛，从其背后的数学理论，到其中包含的基本概念，再到Haskell等函数式编程语言，以及主流编程语言对函数式编程的支持，相关专有的第三方库等。通过本系列的学习，你可以了解很多与函数式编程相关的概念。你会发现在日常开发中可以映射出很多概念。比如前端开发者一定听说过高阶组件，它类似于函数式编程中的高阶函数。流行的前端状态管理解决方案 Redux 的核心是 reduce 功能。library reselect 是 memoization 的巧妙应用。

近年来，随着多核平台和并发计算的发展，函数式编程的无状态特性在处理这些问题时具有其他编程范式无法比拟的天然优势。无论是前端还是后端开发人员，学习函数式编程的一些思想和概念，对手头的开发工作和以后的职业发展都有很大的帮助。虽然本系列的重点是 Java 平台上的函数式编程，但它对其他背景的开发人员也很有用。

下面介绍函数的基本概念。

功能

让我们从数学中的函数开始。数学中的函数是一组输入元素到一组可能的输出元素之间的映射关系，每个输入元素只能映射到一个输出元素。例如，典型的函数 f(x)=x*x 将所有实数的集合映射到它们的平方值的集合，例如 f(2)=4 和 f(-2)=4。函数允许将不同的输入元素映射到同一个输出元素，但每个输入元素只能映射到一个输出元素。比如上面的函数f(x)=x*x，2和-2都映射到同一个输出元素4，这也限制了每个输入元素对应的输出元素是固定的。每个输入元素都必须映射到某个输出元素，这意味着该函数可以应用于输入元素集中的每个元素。

在技​​术术语中，输入元素称为函数的参数。输出元素称为函数的值。输入元素的集合称为函数的域。输出元素和其他附加元素的集合称为函数的陪域。具有映射关系的输入和输出元素对的集合称为函数图。输出元素的集合称为图像。这里需要注意image和reach domain的区别。reach 字段还可能包含图像中的元素以外的元素，即没有输入元素对应的元素。

图1是一个函数对应的映射关系（图片来自维基百科上的Function词条）。输入集合X中的每个元素映射到输出集合Y中的一个元素，即f(1)=D，f(2)=C，f(3)=C。X 中的元素 2 和 3 都映射到 Y 中的 C，这是合法的。不映射 Y 中的元素 B 和 A 也是合法的。函数的域为X，到达域为Y，图为(1,D)、(2,C)、(3,C)的集合，如C、D的集合。

图 1 函数映射关系

我们通常可以把一个函数想象成一个黑盒子，而不知道它的内部实现。你只需要知道它的映射关系就可以正确使用它。函数图是描述函数的一种方式，即列出函数对应的图中所有可能的元素对。这种描述使用集合相关理论，更容易描述图1中这样一个简单的函数。对于涉及输入变量的函数，例如f(x)=x+1java方法函数，需要更复杂的集合逻辑。因为输入元素x可以是任意数，定义域是无限集，对应的输出元素集也是无限的。描述这样一个函数，用我们下面介绍的lambda演算更直观。

λ演算

Lambda 演算是数学逻辑中的一种形式系统，它使用变量绑定和替换来表达基于函数抽象和应用的计算。讨论 λ-演算离不开形式化表达。在本文中，我们尝试着重于与编程相关的基本概念，而不拘泥于数学形式表示。lambda演算实际上是对上述函数概念的简化，便于系统地学习函数。lambda 演算中的函数有两个重要的性质：

lambda 演算中的函数是匿名的，没有明确的名称。例如，函数 sum(x, y) = x + y 可以写成 (x, y)|-> x + y。由于函数本身只是通过它的映射来标识，所以函数名实际上是没有意义的。所以使用匿名函数是合理的。

lambda 演算中的所有函数只有一个输入。具有多个输入的函数可以转换为只有一个输入的函数的嵌套调用。这个过程通常被称为柯里化。例如(x, y)|-> x + y可以转化为x |-> (y |-> x + y)。右边函数的返回值是另一个函数。这个限制简化了 lambda 演算的定义。

简化函数后，我们就可以开始定义lambda演算了。λ-演算是一种基于 λ-项的语言。λ项是λ演算的基本单位。lambda 演算定义了关于 lambda 项的各种转换规则。

λ项

λ 项由以下三个规则定义：

变量 x 本身就是一个 lambda 项。

如果 M 是 λ 项且 x 是变量，则 (λx.M) 也是 λ 项。这样的 lambda 术语称为 lambda 抽象。x和M之间的点（.）用于分隔函数参数和内容。

如果 M 和 N 都是 λ 项，则 (MN) 也是 λ 项。这样的 lambda 术语称为应用程序。

所有合法的 λ 项只能通过重复应用以上三个规则来获得。需要注意的是，λ项最外面的括号可以省略，即可以直接写成λx.M和MN。当多个λ项连接在一起时，需要用括号分隔，以确定λ项的解析顺序。默认顺序是左关联的。所以 MNO 等价于 ((MN)O)。在不会产生歧义的地方可以省略括号。

通过重复应用上述三个规则，可以得到所有的 λ 项。使用变量作为 lambda 项是重复应用规则的起点。λ项λx.M定义了一个匿名函数，它将输入变量x的值代入表达式M。例如，λx.x+1是函数f(x)=x+1的lambda抽象，其中x是变量，M 是 x+1。λ项MN的意思是将表达式N应用到函数M上，即调用函数。N 可以是像 x 这样的简单变量，也可以是由 λ 抽象表示的项。在使用lambda抽象时，就是我们通常所说的高阶函数的概念。

绑定变量和自由变量

在 lambda 抽象中，如果变量 x 出现在表达式中，则它是绑定的。表达式中除绑定变量之外的变量称为自由变量。我们可以用函数分别定义绑定变量（bound variable，BV）和自由变量（free variable，FV）。

对于绑定变量：

对于变量 x，BV(x) = ∅。也就是说，单个变量是免费的。

对于 λ 项 M 和变量 x，BV(λx.M) = BV(M) ∪ { x }。也就是说，λ抽象在M中已有绑定变量的基础上，额外绑定了变量x。

对于 λ 项 M 和 λ 项 N，BV(MN) = BV(M) ∪ BV(N)。即λ项的应用结果中的约束变量集是各个λ项的约束变量集的并集。

对于自由变量，对应的定义和绑定变量相反：

对于变量 x，FV(x) = { x }。

对于 λ M 和变量 x，FV(λx.M) = FV(M) − { x }。

对于 λ 项 M 和 λ 项 N，FV(MN) = FV(M) ∪ FV(N)。

在 lambda 项 λx.x+1 中，x 是一个绑定变量，没有自由变量。在 lambda 项 λx.x+y 中，x 是绑定变量，y 是自由变量。

在 lambda 抽象中，绑定变量的名称在某些情况下是无关紧要的。例如，λx.x+1 和λy.y+1 实际上代表同一个函数，将输入值加 1。变量名 x 或 y 不影响函数的语义。λx.x+1 和 λy.y+1 等 λ 项在 λ 演算中被认为是相等的，称为 alpha 等价。

减少

可以对λ项进行不同的归约操作，主要包括以下三种。

阿尔法变换

α转换的目的是改变绑定变量的名称以避免名称冲突。例如，我们可以通过α变换将λx.x+1变成λy.y+1。如果两个 λ 项可以通过 α 变换进行变换，则它们是 α 等价的。这也是我们在上一节中提到的 α 等价的形式化定义。

当对 lambda 抽象进行 alpha 转换时，只能替换那些绑定到当前 lambda 抽象的变量。例如，λ抽象λx.λx.x可以α变换为λx.λy.y或λy.λx.x，但不能变换为λy.λx.y，因为两者语义不同。λx.x 表示恒等函数。λx.λx.x 和 λy.λx.x 都表示返回恒等函数的 λ 抽象，因此它们是 α 等价的。λx.y 代表的不再是恒等函数，所以 λy.λx.y 不等于 λx.λy.y 和 λy.λx.x。

β减少

β-reduction 与功能应用有关。在讨论 β 减少之前，需要引入替代的概念。对于λ项M，M[x := N]表示将λ项M中自由出现的变量x替换为N，具体替换规则如下。A、B 和 M 是 lambda 项，x 和 y 是变量。A ≡ B 表示两个 λ 项相等。

x[x := M] ≡ M：变量x直接代入的结果是用于代入的λ项M。

y[x := M] ≡ y (x ≠ y)：y和x是不同的变量，所以替换x不会影响y，替换的结果还是y。

(AB)[x := M] ≡ (A[x := M]B[x := M])：A和B都是λ项，(AB)是λ项的应用。替换λ项的应用相当于替换后应用。

(λx.A)[x := M] ≡ λx.A：此规则适用于 λ 抽象。如果 x 是 lambda 抽象的绑定变量，则不需要替换 x，结果与前面的 lambda 抽象相同。这是因为替换仅针对 x 在 M 中的自由出现，如果 x 在 M 中不是自由出现，则不需要进行替换。

(λy.A)[x := M] ≡ λy.A[x := M] (x ≠ y and y ∉ FV(M))：这条规则也适用于 λ 抽象。lambda项A的绑定变量是y，与要代入的x不同，所以可以在A中进行代入动作。

在进行替换之前，可能需要使用 alpha 转换来更改绑定变量的名称。例如，在替换 (λx.y)[y := x] 时，不能直接将出现的 y 替换为 x。这改变了先前 λ 抽象的语义。正确的做法是先进行α变换，将λx.y替换为λz.y，再进行替换，结果为λz.x。

替换的基本原则是要求替换完成后，原来的自由变量仍然是自由的。如果替换变量可能导致变量从自由变为绑定，则需要首先执行 alpha 转换。在前面的例子中，λx.y中的x是一个自由变量，直接代入λx.x的结果将x变成了一个绑定变量，所以需要进行α变换。在正确的替换结果 λz.x 中，z 仍然是自由的。

β 归约表示通过替换来应用函数。对 ((λV.E) E′) 进行 β 归约的结果是 E[V := E′]。如((λx.x+1)y)，β归约的结果为(x+1)[x := y]，即y+1。

变换

η-转换描述了函数的外延性。可扩展性意味着当且仅当它们的所有参数的结果都相同时，两个函数才被认为是相等的。比如一个函数F，当参数为x时，它的返回值为Fx。然后考虑声明为 λy.Fy 的函数 G。对于输入参数 x，函数 G 也返回结果 Fx。F 和 G 可能由不同的 λ 项组成，但只要 Fx=Gx 对所有 x 都成立，那么 F 和 G 就相等。

在 F=λx.x 和 G=λx.(λy.y)x 的情况下，F 是恒等函数，G 是应用于输入参数 x 的恒等函数。尽管 F 和 G 由不同的 λ 项组成，但它们的行为相同并且本质上是恒等函数。我们称F和G是η等价的，F是G的η约简，G是F的η扩展。F和G是彼此的η变换。

纯函数、副作用和引用透明性

了解函数式编程的人可能听说过诸如纯函数和副作用之类的名称。这两个概念与引用透明性密切相关。一个纯函数需要有两个特征：

对于相同的输入参数，总是返回相同的值。

评估过程中没有副作用，即对运行环境没有影响。

至于第一个特征，如果是从数学概念抽象出来的函数，就很好理解了。f(x)=x+1 和 g(x)=x*x 等函数是典型的纯函数。如果考虑一般编程语言中出现的方法，则不能在函数中使用静态局部变量、非局部变量、对可变对象的引用或 I/O 流。这是因为这些变量的值可能会在不同的函数执行过程中发生变化，从而导致不同的输出。第二个特性要求函数体不能修改静态局部变量、非局部变量、变量对象引用或 I/O 流。这样可以保证函数的执行不会影响外部环境。纯函数的这两个特性缺一不可。让'

在清单 1 中，方法 f1 是一个纯函数；方法 f2 不是纯函数，因为它引用了外部变量 y；方法 f3 不是纯函数，因为它使用了产生副作用的 Counter 对象的 inc 方法；f4方法不是纯函数，因为调用writeFile方法会写入文件java方法函数，会影响外部环境。

清单 1. 纯函数和非纯函数的示例

int f1(int x) {

返回 x + 1；

}

int f2(int x) {

返回 x + y；

}

int f3（计数器 c）{

c.inc();

返回 0；

}

int f4(int x) {

写文件（）；

返回 1；

}

如果一个表达式是纯表达式，那么它在代码中出现的所有地方都可以被它的值替换。对于函数调用，这意味着对于具有相同输入参数的相同函数的调用，可以使用它的值代替。这是函数的引用透明性。引用透明性的重要性在于编译器可以使用各种措施来自动优化代码。

函数式编程和并发编程

随着多核计算机硬件的普及，为了尽可能利用硬件平台的能力，并发编程显得尤为重要。与传统的命令式编程范式相比，函数式编程范式由于其天然的无状态性，在并发编程方面具有独特的优势。以Java平台为例，相信很多开发者对Java的多线程和并发编程都有一定的了解。也许最直观的感受就是Java平台的多线程和并发编程并不容易掌握。这主要是因为涉及的概念太多了，从Java内存模型，到低级原语synchronized和wait/notify，再到java.util中的高级同步对象。并发包。由于并发编程的复杂性，即使是经验丰富的开发人员也很难保持多线程代码无错误。许多错误只在运行时的特定情况下发生，因此很难排除故障和修复。在学习如何更好地进行并发编程的同时，我们可以换个角度来看这个问题。多线程编程问题的根源是对共享变量的并发访问。如果这种访问不需要存在，那么自然就不存在多线程相关的问题。在函数式编程范式中，函数中没有可变状态，也不需要控制它们的访问。这从根本上避免了多线程的问题。即使是经验丰富的开发人员也很难保持多线程代码无错误。许多错误只在运行时的特定情况下发生，因此很难排除故障和修复。在学习如何更好地进行并发编程的同时，我们可以换个角度来看这个问题。多线程编程问题的根源是对共享变量的并发访问。如果这种访问不需要存在，那么自然就不存在多线程相关的问题。在函数式编程范式中，函数中没有可变状态，也不需要控制它们的访问。这从根本上避免了多线程的问题。即使是经验丰富的开发人员也很难保持多线程代码无错误。许多错误只在运行时的特定情况下发生，因此很难排除故障和修复。在学习如何更好地进行并发编程的同时，我们可以换个角度来看这个问题。多线程编程问题的根源是对共享变量的并发访问。如果这种访问不需要存在，那么自然就不存在多线程相关的问题。在函数式编程范式中，函数中没有可变状态，也不需要控制它们的访问。这从根本上避免了多线程的问题。在学习如何更好地进行并发编程的同时，我们可以换个角度来看这个问题。多线程编程问题的根源是对共享变量的并发访问。如果这种访问不需要存在，那么自然就不存在多线程相关的问题。在函数式编程范式中，函数中没有可变状态，也不需要控制它们的访问。这从根本上避免了多线程的问题。在学习如何更好地进行并发编程的同时，我们可以换个角度来看这个问题。多线程编程问题的根源是对共享变量的并发访问。如果这种访问不需要存在，那么自然就不存在多线程相关的问题。在函数式编程范式中，函数中没有可变状态，也不需要控制它们的访问。这从根本上避免了多线程的问题。并且不需要控制他们的访问。这从根本上避免了多线程的问题。并且不需要控制他们的访问。这从根本上避免了多线程的问题。

总结

作为 Java 函数式编程系列的第一篇文章，本文简要概述了函数式编程。由于函数式编程离不开数学中的函数，本文首先介绍一下函数的基本概念。然后，详细介绍了作为函数式编程理论基础的λ-演算，包括λ-项、自由变量和约束变量、α-变换、β-约简和η-变换等重要概念。最后介绍了编程中可能遇到的纯函数、副作用、引用透明等概念。本系列的下一篇文章将介绍函数式编程中的重要概念，包括高阶函数、闭包、递归、记忆化和柯里化。

参考资源

参考维基百科关于函数式编程的介绍。

有关 lambda 演算，请参阅维基百科。

请参阅关于 lambda 演算的斯坦福哲学百科全书条目。