纯函数式并行编程探索

# 纯函数式并行编程探索 ## 1. 并行计算的初步思考 在并行计算中，我们常常会遇到一些复杂的表达式，例如： ```scala map2( map2( unit(1), unit(2))(_ + _), map2( unit(3), unit(4))(_ + _))(_ + _) ``` 无论使用何种数据结构来存储这样的描述，其占用的空间可能比原始列表本身还要大。因此，我们希望描述能够更加轻量级。一种思路是让 `map2` 变为惰性的，并让它立即并行执行两侧的计算，这样也能避免给任何一侧赋予优先级。 ## 2. 显式分叉（Explicit forking） 然而，我们最新的选择仍存在问题。并非总是需要并行计算 `map2` 的两个参数。例如： ```scala Par.map2(Par.unit(1), Par.unit(1))(_ + _) ``` 在这种情况下，我们知道这两个计算会很快完成，没必要为它们创建单独的逻辑线程。但当前的 API 没有提供这样的信息传递方式，即程序员无法明确指定分叉的位置。 为了解决这个问题，我们引入了 `fork` 函数： ```scala def fork[A](a: => Par[A]): Par[A] ``` 它表示给定的 `Par` 应该在单独的逻辑线程中运行。例如，计算序列和的函数可以这样实现： ```scala def sum(ints: IndexedSeq[Int]): Par[Int] = if ints.size <= 1 then Par.unit(ints.headOption.getOrElse(0)) else val (l, r) = ints.splitAt(ints.size / 2) Par.map2(Par.fork(sum(l)), Par.fork(sum(r)))(_ + _) ``` 使用 `fork` 后，我们可以让 `map2` 变为严格的，将是否并行的选择权交给程序员。这解决了并行计算实例化过于严格的问题，更重要的是，将并行性的控制权明确交给了程序员。 ## 3. `unit` 函数的严格性与惰性 现在我们来思考 `unit` 函数应该是严格的还是惰性的。有了 `fork` 后，我们可以让 `unit` 变为严格的，而不会损失表达能力。非严格版本的 `unit` 可以用 `unit` 和 `fork` 实现： ```scala def unit[A](a: A): Par[A] def lazyUnit[A](a: => A): Par[A] = fork(unit(a)) ``` `lazyUnit` 是一个派生组合子的简单例子，与 `unit` 这样的原始组合子相对。 ## 4. `fork` 函数的执行时机 我们知道 `fork` 表示其参数应该在单独的逻辑线程中评估，但它应该在调用时立即开始评估，还是在计算被强制时（如使用 `get`）再进行评估呢？即评估的责任应该由 `fork` 还是 `get` 承担？评估应该是急切的还是惰性的？ 如果 `fork` 立即并行评估其参数，实现必须知道如何创建线程或向线程池提交任务，这意味着线程池必须全局可访问且在调用 `fork` 的地方正确初始化，这会使我们失去对程序不同部分并行策略的控制。因此，让 `get` 负责创建线程和提交执行任务似乎更合适。 如果 `fork` 只是持有未评估的参数，直到稍后再进行评估，它不需要访问并行实现机制，只是标记一个 `Par` 进行并发评估。基于此，我们将 `get` 函数重命名为 `run`，并规定这里是并行性实际实现的地方： ```scala extension [A](pa: Par[A]) def run: A ``` 由于 `Par` 现在只是一个纯数据结构，`run` 需要有实现并行性的方法，比如创建新线程、将任务委托给线程池等。 ## 5. 选择表示方式 ### 5.1 初步 API 设计 通过前面的探索，我们设计了以下 API： | 函数 | 功能 | | ---- | ---- | | `def unit[A](a: A): Par[A]` | 将常量值提升为并行计算 | | `extension [A](pa: Par[A]) def map2[B, C](pb: Par[B])(f: (A, B) => C): Par[C]` | 使用二元函数组合两个并行计算的结果 | | `def fork[A](a: => Par[A]): Par[A]` | 标记一个计算进行并发评估，直到 `run` 强制时才会发生评估 | |