第 11 章：声明式编程（Declarative Programming）
原文：Bartosz Milewski, Category Theory for Programmers, Scala Edition, Chapter 11. 原书 PDF、
.tex源文件及相关图像采用 CC BY-SA 4.0；本译文按同一许可发布。
在本书第一部分中，我论证了范畴论和编程都关乎可组合性。在编程中，你不断分解一个问题，直到达到可以处理的细节层级；然后逐个解决子问题，并自底向上重新组合这些解。粗略地说，有两种方式可以做到这一点：告诉计算机要做什么，或者告诉它如何去做。前者称为声明式，后者称为命令式。
哪怕在最基本层面也能看到这种区别。组合本身可以用声明式方式定义，例如，h 是 g 在 f 之后的组合：
h = g . f
val h = g compose f
也可以用命令式方式定义，例如，先调用 f，记住调用结果，再用结果调用 g：
h x = let y = f x
in g y
val h = x => {
val y = f(x)
g(y)
}
程序的命令式版本通常被描述为按时间排序的一系列动作。特别是，在 f 执行完成之前，不能调用 g。至少概念图景是这样；在惰性语言中，借助按需调用的参数传递，实际执行过程可能不同。
事实上，取决于编译器有多聪明，声明式代码与命令式代码的执行方式之间可能差别很小，甚至没有差别。但这两种方法在我们处理问题的方式上，以及最终代码的可维护性和可测试性上，有时会有巨大差异。
主要问题是：面对一个问题时，我们是否总能在声明式和命令式求解方式之间选择？而且，如果存在声明式解法，它是否总能被翻译成计算机代码？这个问题的答案远非显然；如果能找到答案，我们或许会彻底改变对宇宙的理解。
让我展开说说。物理学中也存在类似的二重性。它要么指向某个深层基本原理，要么告诉我们一些关于人类思维方式的事情。Richard Feynman 曾提到这种二重性是他在量子电动力学工作中的灵感来源之一。
大多数物理定律都有两种表达形式。一种使用局部的、或者说无穷小的考虑。我们观察系统在一个小邻域中的状态，并预测它在下一瞬间会如何演化。这通常用微分方程表达，而微分方程必须在一段时间内被积分，或者说求和。
注意这种方式多么像命令式思维：我们通过一连串小步骤到达最终解，每一步都依赖前一步的结果。事实上，物理系统的计算机模拟通常就是把微分方程转换成差分方程，然后迭代它们。这就是小行星游戏中飞船动画的实现方式。在每个时间步中，飞船位置会加上一个小增量，这个增量由速度乘以时间差得到。速度本身也会改变一个小增量，这个增量与加速度成正比，而加速度由力除以质量给出。
这些就是牛顿运动定律对应微分方程的直接编码：
F = m dv/dt
v = dx/dt
类似方法也可用于更复杂的问题，例如用 Maxwell 方程描述电磁场传播，甚至用格点 QCD（量子色动力学）描述质子内部夸克和胶子的行为。
数字计算机鼓励空间和时间的离散化，这种局部思维与离散化结合，在 Stephen Wolfram 试图把整个宇宙的复杂性归约为元胞自动机系统的宏大尝试中达到了极端表达。
另一种方式是全局的。我们观察系统的初态和终态，并通过最小化某个泛函来计算连接二者的轨迹。最简单的例子是 Fermat 最短时间原理。它说，光线沿着使飞行时间最短的路径传播。特别是在没有反射或折射物体时，从点 $A$ 到点 $B$ 的光线会走最短路径，也就是直线。但光在密度较高的透明材料中传播较慢，例如水或玻璃。所以，如果起点在空气中，终点在水下，那么对光来说，在空气中多走一段路，再穿过水抄近路，会更有利。最短时间路径使光线在空气与水的边界处折射，从而产生 Snell 折射定律：
sin(theta_1) / sin(theta_2) = v_1 / v_2
其中 v_1 是光在空气中的速度，v_2 是光在水中的速度。
整个经典力学都可以从最小作用量原理推出。对任意轨迹，都可以通过积分拉格朗日量来计算作用量；拉格朗日量是动能与势能之差（注意：是差，不是和；和才是总能量）。当你发射迫击炮击中给定目标时，炮弹会先上升，到达重力势能更高的地方，并在那里停留一段时间，为作用量积累负贡献。它也会在抛物线顶端减速，以最小化动能。随后它会加速，迅速穿过低势能区域。
Feynman 最大的贡献是意识到最小作用量原理可以推广到量子力学。在那里，问题同样以初态和终态来表述。连接这些状态的 Feynman 路径积分用于计算跃迁概率。
重点在于，我们描述物理定律的方式存在一种奇特而尚未解释的二重性。可以使用局部图景，其中事情按顺序、以小增量发生。也可以使用全局图景，在其中声明初始条件和最终条件，中间的一切都会随之确定。
全局方法也可以用于编程，例如实现光线追踪时。我们声明眼睛的位置和光源位置，并找出光线可能用来连接它们的路径。我们不会显式地为每条光线最小化飞行时间，但会使用 Snell 定律和反射几何达到同样效果。
局部方法与全局方法最大的差异，在于它们对空间，更重要的是对时间的处理。局部方法拥抱此时此地的即时满足，而全局方法采取长期的静态视角，仿佛未来已经预先注定，我们只是在分析某个永恒宇宙的性质。
这种差异在函数式响应式编程（FRP）处理用户交互的方式中体现得最清楚。FRP 不会为每一种可能的用户动作编写单独处理器，并让它们都访问某个共享可变状态；相反，它把外部事件看作一个无限列表，并对它应用一系列变换。
概念上，我们未来所有动作的列表已经存在，作为程序的输入数据可用。从程序视角看，圆周率数字列表、伪随机数列表，或通过计算机硬件传来的鼠标位置列表之间没有区别。在每种情况下，如果想得到第 n 项，必须先经过前 n - 1 项。当应用于时间事件时，我们把这个性质称为因果性。
那么这和范畴论有什么关系？我会主张，范畴论鼓励全局方法，因此支持声明式编程。首先，与微积分不同，它没有内建距离、邻域或时间概念。我们拥有的只是抽象对象以及它们之间的抽象连接。如果可以通过一系列步骤从 $A$ 到 $B$，也可以一跃而至。更重要的是，范畴论的主要工具是通用构造，它是全局方法的典型代表。我们已经在例如范畴积的定义中见过它的作用。它通过指定性质来完成，这是一种非常声明式的方式。它是一个配备两个投影的对象，并且是这种对象中最好的那个：它优化了某个性质，也就是分解其他这种对象的投影这一性质。
把它与 Fermat 最短时间原理或最小作用量原理比较一下。
反过来，把它与笛卡尔积的传统定义形成对比，后者更命令式得多。你描述如何通过从一个集合中选择一个元素、从另一个集合中选择另一个元素，来创建积的一个元素。这是创建 pair 的配方。还有另一个配方用于拆解 pair。
在几乎所有编程语言中，包括 Haskell 这样的函数式语言，积类型、余积类型和函数类型都是内建的，而不是由通用构造定义出来的；尽管也有人尝试创建范畴式编程语言（例如 Tatsuya Hagino 的论文）。
无论是否直接使用，范畴式定义都能为既有编程构造提供正当性，也能催生新的构造。最重要的是，范畴论提供了一种元语言，让我们能够在声明式层面推理计算机程序。它还鼓励我们先思考问题规格，再把规格转换成代码。
参考资料
- Tatsuya Hagino, A Categorical Programming Language.