函数式编程溯源

可编程这件事

第一台可编程电子计算机 ENIAC 的诞生时间是 1946 年, 基本上可以说在这个时间之后, 才有了真正的 计算机编程.

我一直很好奇在此之前, 可编程这件事情事如何发展的. 在经过了一些调研后, 才知道可编程这件事情不是一蹴而就的, 而是经过许多数学前辈的天才思考、论证, 才堆筑起一座可编程技术的大厦.

我们大概听说过我们当前使用的计算机, 绝大部分基于冯·诺依曼在设计 ENIAC 时创建的硬件架构. 这个架构非常强大, 在数量上大概是没有其他架构能与之匹敌的, 但是向上溯源的话, 我们就会发现一个 1936 年由阿兰·图灵提出来的 图灵机运算模型 的影子. 如果说 图灵机运算模型 是当代计算机的蓝图, 那么 冯·诺依曼架构 是这个蓝图的的一种实现方案.

当各种硬件参照 冯·诺依曼架构 搭建起来后, 就化身一台庞大的状态机, 当你向它输入一系列的初始数据与指令后, 它就在指令的指挥下, 改变寄存器、内存或磁盘中的数据. 在执行完成后, 你就可以读取这台状态机中的输出, 从而得到你想要的计算结果.

很容易发现, 图灵机模型 在运算时离不开存储设备! 读写存储设备就是它达成运算的必要条件. 但是对于运算这件事情来说, 存储反而是个副作用. 那么有没有更加纯粹的模型可以用来表示运算呢?

答案是肯定的, 这个模型就是由图灵就读于普林斯顿大学时的博士生导师阿隆佐·邱奇提出来的 λ演算模型 .

λ演算模型

λ演算模型 是函数式编程的基础, 现代很多编程语言都与它有紧密的联系, 我们来了解一下邱奇提出这个模型的动机.

在 λ演算模型 被提出来之前, 人们对运算的函数有各种各样奇妙表达, 这就导致了:

不统一: 不同的人虽然在表述同一个问题, 但是因为表述的方式不一致, 无法沟通;
不准确: 一些表达既可以表示A类情况, 又可以表示B类情况, 导致模棱两可...

当然还有其他问题, 基于这些问题, 邱奇提出了 λ演算模型 , 这个模型允许人们形式化地表达函数, 以及函数如何运算, 在这个基础之上进行进一步的推演, 从而得出更深刻的概念.

那么 λ演算模型 里包含了哪些内容呢? 其实非常简单, 这个模型中只定义了一种元素, 那就是 λ表达式 , 现在开始, 抛开你曾经掌握的任何有关编程的知识, 从零开始了解 λ演算模型 吧!

关于 λ表达式 , 我们可以通过这三个规则判断一个 λ表达式 是否合法:

变量(Variable): 如果一个符号是一个变量, 例如: $x$ , 那么它就是一个合法的 λ表达式 ;
抽象(Abstraction): 如果 $x$ 是一个变量, $t$ 是一个合法的 λ表达式 , 那么 $λx.t$ 也是一个合法的 λ表达式 ;
应用(Application): 如果 $t$ 与 $s$ 都是合法的 λ表达式 , 那么 $(t\ s)$ 也是一个合法的 λ表达式 , 它表示将 $t$ 应用到 $s$ .

如果你了解编程, 定义过函数(或方法), 就很容易发现, 上面的三个规则, 分别对应着:

声明函数参数变量;
声明函数的入参和返回值;
通过参数调用函数.

可能你会觉得这些规则有点简单甚至简陋, 但是不要被它的简单性欺骗了! 正是因为这种简单性, 才赋予了 λ演算 强大的推演能力.

在深入了解之前, 有一些 潜规则 你可能需要了解一下:

抽象时, 如果没有括号约束, 应该尽量往右扩展, 例如: $λx.t\ s$ , 等价于 $λx.(t\ s)$ 而不是 $(λx.t)\ s$ ;
应用时, λ表达式最外层的小括号是可以去掉的, 例如: $(t\ s)$ 等价于 $t\ s$ ;
应用时, λ表达式是左结合的, 例如: $t\ s\ r$ 等价于 $(t\ s)\ r$ , 当你需要优先运算 $s\ r$ , 时, 请加上括号: $t\ (s\ r)$ .

接下来我们来尝试用直觉来对以下的λ表达式进行化简:

$\begin{align} \ \ & (\lambda \color{blue}{A}.A\ b\ c\ ((\lambda D.D)d\ ((\lambda E.E\ f)e\ )))\ \color{blue}{a} \\ \ = \ & a\ b\ c\ (( \lambda D.D )d\ ((\lambda \color{blue}{E}.Ef )\color{blue}{e})\ ) \\ \ = \ & a\ b\ c\ ((λ \color{blue}{D}.D)\color{blue}{d}\ (e\ f)) \\ \ = \ & a\ b\ c\ (d\ (b\ c)) \end{align}$

* 想尝试一下其他表达式? 可以利用在线计算器哦

化简步骤似乎很符合直觉, 就是不断将表达式代入另一个表达式的变量, 然后得到新的表达式.
这种代入, 每次生成的新表达式与原始表达式都是等价的, λ演算中称这种形式为 $\beta$ -归约 .

除了 $\beta$ -归约 , λ演算中还有另一种等价形式: $\alpha$ -变换 .

$\alpha$ -变换也很简单, 想象有这两个表达式: $\lambda x.x$ 与 $\lambda y.y$ , 虽然变量的名称不一样, 但是将他们应用到别的表达式时, 效果是一样的:
$(\lambda x.x)\ q = q$
$(\lambda y.y)\ q = q$

所以我们可以认为这两个表达式是等价的.

柯里化(Currying)

很好, 我们已经对λ表达式有了大致的理解了, 但是如果你留意到抽象规则, 你会发现: 定义函数时, 只能传入一个变量.
那如果需要多个参数的话, 应该如何处理呢?

哈斯克尔·柯里先生表示, 你搞反了~

你可能听说过一门函数式编程语言 Haskell , 就是以哈斯克尔命名的, 而另一种以他名称命名的技术 柯里化 , 则能够将一个接受多个参数的函数变换成只接受一个参数(原函数的第一个参数)的函数, 并且返回一个 接受原函数剩余参数 而且 返回原函数结果 的新函数。

看到定义你可能会感觉有点绕, 我们举一个实际的例子吧.

假设我们现在有一个普通的数学函数: $f(m, n) = n$ (简单起见, 让它永远返回 $n$ )
我们尝试写成一个 λ表达式: $\lambda m n . n$ (有两个参数, 好像不太符合标准λ表达式定义)
我们对它应用柯里化, 就可以得到: $\lambda m.(\lambda n. n) \iff \lambda m. \lambda n. n$

看, 我们做到了! 我们将一个接受两个参数的函数, 转化为一个只接受一个参数(并返回另一个函数)的函数. 所以如果以后你看到有多个变量的λ表达式, 你就知道了, 其实它是由多个λ表达式组合在一起而已.

那么为什么说搞反了呢, 因为我们熟悉的多参数函数, 在λ演算中可以视为由多个λ表达式组合而成的.

可能很多已经有过编程经历的人, 在接触函数式编程的时候, 会对柯里化技术一头雾水, 为什么要对一个函数进行拆分呢?

产生这样的疑问非常正常, 我个人理解是, 在λ演算中, 我们为了研究运算的本质, 所以定义了这种最基础的函数形式: λ表达式.

这就像物理中, 我们总是在深入研究最小的物质形态, 从分子, 到原子, 再到质子中子等等, 为什要研究呢, 因为越基础的元素, 掌握了规则之后, 能覆盖的面就越广.

对于函数的研究也是如此, 面对多元的函数, 我们可以通过柯里化将其拆分成多个更基础的函数, 就更方便我们探索他的本质.

运算

讨论完上述的内容, 我们终于可以进入另一个阶段了, 这个小节我们开始分析函数与生俱来的作用: 运算.

我们先了解一下比较简单的布尔运算, 因为它只针对两个常量: $True$ 与 $False$ .

你可能会觉得, 这我可太熟悉了, 有什么值得讨论的呢?

确实, 如果这两个常量是值 , 那确实是非常熟悉, 但是我这里讨论的是 λ表达式 , 我们要做的事情是, 找到一个λ表达式, 让他具有 $True$ 和 $False$ 的性质, 也就是能够满足诸如 $and$ $or$ $not$ 等运算规则的 λ表达式 .

好消息是, 邱奇老先生早已经帮我们找到了这两个λ表达式:

真: $True \iff \lambda x. \lambda y . x$
假: $False \iff \lambda x. \lambda y . y$

有了常量 , 那么就可以运算了, 邱奇还提供了多个算子 λ表达式 , 用于这些常量的运算:

与: $and \iff \lambda x . \lambda y . (x\ y\ False)$
或: $or \iff \lambda x . \lambda y . (x\ True\ y)$
非: $not \iff \lambda x . (x\ False\ True)$

接下来, 我们就尝试用 $and$ 算子来运算一下吧, 观察 $and$ 算子, 它需要传入两个变量, 其实也就是说传递两个布尔值, 这里我们分别传入 $True$ 与 $False$ , 期待的结果是 $False$

$\begin{align} \ \ & and\ True\ False \\ \ = \ & \color{blue}{\lambda x . \lambda y . (x\ y\ False)} \ True\ False \\ \ = \ & (\lambda y. (True\ y\ False))\ False \\ \ = \ & True\ False\ False \\ \ = \ & \color{blue}{(\lambda x. \lambda y . x)} \ False\ False \\ \ = \ & (\lambda y. False)\ False \\ \ = \ & False \end{align}$

同样的, 也可以尝试使用 $or$ 算子来对 $True$ 与 $False$ 进行运算, 这次我们期待的结果是 $True$ :

$\begin{align} \ \ & or\ True\ False \\ \ = \ & \color{blue}{\lambda x . \lambda y . (x\ True\ y)} \ True\ False \\ \ = \ & (\lambda y . (True\ True\ y))\ False \\ \ = \ & True\ True\ False \\ \ = \ & \color{blue}{(\lambda x. \lambda y . x)} \ True \ False \\ \ = \ & (\lambda y. True)\ False\\ \ = \ & True \end{align}$

你会发现, 运算的过程就跟解方程一样, 不断地将符号展开, 归约, 然后理所当然地就得到结果, 更有意思的是, 上述的每一次运算过程中, 每一行都是等价的, 只要你有想象力, 你完全可以从最后的结果反推出最开始的式子.

在编程方面, 一旦有了布尔值, 我们瞬间就拥有了一项强大的技能: 条件判断 .

想想我们有一个变量 $isMealTime$ (假设当前值为 $True$ ), 然后我们又两个函数 $eat$ 与 $play$ ,我们就可以判断是否可以开始干饭了(✧◡✧)

$\begin{align} \ \ & isMealTime\ eat\ play \\ \ = \ & \color{blue}{(\lambda x. \lambda y . x)}\ eat \ play \\ \ = \ & (\lambda y . eat) \ play \\ \ = \ & eat \end{align}$

感觉能看到这里的小伙伴, 脑子应该已经嗡嗡作响了, 事实上基于最开始的三个规则, 我们可以做事情还有很多:

定义出代表自然数(邱奇数)的函数与相关的算子, 然后就能愉快的计算加减乘除.
定义出一个循环 , 甚至 无限循环 , 然后在每次迭代中做点事情.

—— 如果感兴趣, 可以参看 GZTime's 大大的 Blog , 上方的内容大部分都是从他那里白嫖的 (逃

一旦有了 条件判断, 有了数字 , 能够循环 , 一个基本具备编程能力的体系就被搭建出来了.

事实上, 图灵机 能做的事情, λ演算 同样也能做到, 两者同样强大!

编程语言中的函数式

了解了 λ演算 后, 我们不禁要问, 既然现在市面上大多数计算机都是基于图灵机来设计的, 是不是函数式编程没有容身之所了呢?

在硬件层面确实是的, 专门为函数式编程搭建的硬件架构屈指可数, 但是如果你留意, 你会发现有好多支持函数式编程的语言, 甚至有的语言只支持函数式编程, 它们是怎么做到的呢?

这里有个误区, 函数式编程并不一定需要硬件支持, 在一些脚本语言中, 因为代码是由解释器逐行解释的, 只要解释器能够理解代码, 就能够运行了. 退一步来说, 在没有提供函数式编程支持的语言中, 只要我们遵循函数式编程的一些规则, 我们也能够体现出函数式编程的优点.

接下来我就为大家罗列一些常见的函数式编程特性吧.

函数式编程特性

函数式编程的特性来自于各种已经存在的函数式编程语言, 我将尝试能将这些特性与λ演算强行关联一下, 没准有加深印象的效果. 网络上大多数特性的代码示例都选择了使用 JavaScript , 不过我更熟悉 Kotlin , 所以下面的代码示例我就用 Kotlin 来展示了.

不可变性(Immutability)
在λ演算中, 所有元素都是λ表达式, 一旦声明了一个λ表达式, 它就是不变的, 你不用担心在此后的某个时刻它会变成另一个表达式.
而在函数式编程中, 也延续了这个思想. 函数式编程中, 只有值, 而值是不会改变的. 实际上一个值也是一个表达式, 形如: $\lambda x. 1$ .

这一点从根源上解决了并发环境中的很多问题, 考虑这个可以在并发环境完成的需求: 计算一个 Int 列表中所有元素的和 .
在命令式编程的情况下, 代码是这样的(Kotlin Playground):
```
suspend fun main() {
    val list = List(10000) { 1 }

    var sum = 0
    coroutineScope {
        list.forEach {
            launch(Dispatchers.Default) { sum += it }
        }
    }

    println("sum: $sum") // sum: 9964
}
```
尝试运行就会发现, 很难得到正确的的结果, 除非加锁(Kotlin Playground).

相反如果以函数式的方式实现(Kotlin Playground):
```
suspend fun sum(list: List<Int>): Int {
    val size = list.size
    if (size == 0) return 0
    if (size == 1) return list.first()

    val left = size / 2
    val leftList = list.take(left)

    val right = size - left
    val rightList = list.takeLast(right)

    return coroutineScope {
        val leftJob = async(Dispatchers.Default) { sum(leftList) }
        val rightJob = async(Dispatchers.Default) { sum(rightList) }
        leftJob.await() + rightJob.await()
    }
}

fun main() {
    val list = List(10000) { 1 }
    val sum = runBlocking { sum(list) }
    println("sum: $sum") // sum: 10000
}
```
这段代码所有声明的值都不会改变, 每次运算都会产生新值, 这保证了运算不受并发环境影响.

因为值不可变, 所以依赖于更新变量来进行迭代循环的方式就无法实现了. 纯函数是编程中, 是以递归来实现循环的效果的, 这就对以调用栈来记录程序运行状态的程序模型提出了很大的挑战. 不过在数学上, 很多递归是可以转化为迭代循环的, 而其中一种被称为 尾递归 的递归形式甚至可以用固定的方式转化. 所以有些语言为尾递归提供了魔法: 编译器优化.

在 Kotlin 中, 可以为一段尾递归形式的函数添加 tailrec 关键字, 提示编译器将其在编译时转化为循环(如果不符合尾递归的形式, 会有一个编译警告), 以下为一个计算阶乘的尾递归函数:
```
tailrec fun factorial(n: Long, accumulator: Long = 1): Long =
    when (n) {
        0L -> accumulator
        else -> factorial(n - 1, n * accumulator)
    }
```
求值方式
λ演算中, 可以通过 $\beta$ -归约来生成等价的表达式, 既然表达式等价, 我们其实可以不用在一开始就归约成表达式的简化形式, 没准在运算过程中它就被忽略了, 比如: $(\lambda x. y) (\lambda o. \lambda p. q)$ , 第二个括号中的表达式无论多复杂, 都不会影响运行的结果, 因为当第一个表达式应用道它身上后, 都会变成 $y$ .

函数式编程中, 有些表达式声明之后, 也有可能不会被运行, 那么他们就可以被忽略, 这种忽略被称为: 惰性求值. 考虑这段代码(Kotlin Playground):
```
fun f1(i: Int, j: Int) = i
fun f2(): Int = f2()
fun main() {
    f1(1, f2())
}
```
它有显著的问题: 调用函数 f2() 时会进行无限递归, 导致程序资源耗尽崩溃. 但是反观 f1(...) 函数, 实际根本没使用到第二个参数的值. 如果将其稍加改造, 就可以让程序忽略 f2() 正常运行了(Kotlin Playground):
```
fun f1(i: Int, j: () -> Int) = i
fun f2(): Int = f2()
fun main() {
    f1(1, ::f2)
}
```
你可能已经用到一些惰性求值的方式了, 下面这些值声明时, 都不会立即对 complexExp() 进行求值:
```
val value1 = (true || complexExp()) 
val value2 by lazy { complexExp() }
```
你甚至可以写出这样的代码(Kotlin Playground):
```
fun main() {
    val sequence = sequence {
        while (true) {
            println("yield")
            yield(1)
        }
    }
    val take = sequence.take(Int.MAX_VALUE)

    println("before evaluate")
    take.first()
    println("after evaluate")
}
// <log>
// before evaluate
// yield
// after evaluate
```
就算调用 take(...) 获取了庞大数量的序列, 但是还没使用到值的时候, 这个序列是一点反应都没有. 只有当你调用 first() 求值时, 它才慵懒地计算第一个值然后返回给你.
纯函数&副作用
λ演算中, 所有表达式都有返回值, 而且每个表达式都是独立的, 只关注运算, 而不关注环境.

函数式编程中, 也要求我们编写与之类似的函数, 即: 有返回值 与 无副作用 . 这样的函数被称为 纯函数 . 这两点我们展开来说明一下:
1. 有返回值
  函数必须有返回值, 一个没有返回值的函数, 往往意味着这个函数在产生副作用.
2. 无副作用
  所谓的副作用, 指的是跟运算无关的行为, 可能是这些:
  - 修改一个变量;
  - 抛出一个异常或以一个错误停止;
  - 打印到终端或读取用户的输入;
  - 读取或写入一个文件...
虽然你可能无法想象没有这些功能, 一个程序有什么作用. 但是这些行为都在破坏运算的纯粹性.
函数式编程约束的是编程方式, 而不是程序表达. 那我们应该怎样做呢? 其实很简单, 我们应该将副作用抽象成一个值返回给调用者, 例如这样一个需求: 用支付宝购买一颗糖 , 如果写成这种形式:
```
const val CANDY_PRICE = 1.0
class Candy
fun payByZhiFuBao(amount: Double) { ... }
fun buyCandy(): Candy {
    payByZhiFuBao(CANDY_PRICE) // 副作用
    return Candy()
}
```
那么就相当于把支付行为这种副作用嵌入到函数中, 这就导致这个函数难以测试, 也无法预知它的行为(支付是否能成功取决于许多外部因素), 为了使这个函数更加纯粹, 我们可以这么写:
```
const val CANDY_PRICE = 1.0
class Candy
class Payment(val amount: Double)
fun buyCandy() = (Payment(CANDY_PRICE) to Candy())
```
这种形式将支付的行为抽象成一个订单, 并返回给调用者, 由调用者来决定如何处理订单. 这种抽象让一个函数变得极易测试: 你不用真的向支付宝支付糖果的价格了, 而且你如果有一天想要改用微信支付, 这个函数也压根不用修改.

从这个案例中我们可以窥探出, 一个程序如果积极编写纯函数, 那么就会形成这种结构: 一个由纯函数构成的核心, 在外层包裹着一层与外界沟通的壳.
这种程序稳重又轻盈, 你可以随时向内核增加新的功能而不影响已有的功能, 也可以自由地替换外层装饰满足新的需求.

收尾

摸了一星期鱼, 终于把这篇文章码出来了.

一直很想总结一下函数式编程的知识点, 通过编写这篇文章, 又加深了我对它的认识, 不过这还都只是开始, 函数式编程还有很多可以深入探讨的内容, 如果大家有兴趣可以继续深入研究.

这篇文章都是我的个人理解, 可能有错误或疏漏, 如果发现请不吝指教!

学无止境, 与君共勉~