企业官网建设流程全解析

• 示例工程

本文围绕《Functional Programming in Scala》（fpinscala）第 8 章“属性测试（Property-Based Testing）”中的练习 16 展开，逐行拆解其标准答案gpy2——一个能够生成“结构随输入长度变化”的Gen[Par[Int]]并行计算生成器，并顺带讲解练习 17 中基于它写出的forkProp（Par.fork(y) == y的 fork 律属性）。读完本文，你将掌握Gen组合子（choose、listOfN、map、foldLeft）在并行程序测试中的实际用法，理解forAllPar这类“执行器 + 被测值”联合生成的测试基础设施，以及仓库答案模块中“穷举 + 随机”双重生成机制的底层原理。

一、练习定位：为什么需要“结构有变化”的并行计算

第 8 章的目标是自建一个极简的属性测试库：用Gen[A]生成随机输入，用Prop描述性质，再通过大量采样来寻找反例。前几道练习依次实现了Gen的基础组合子（choose、unit、listOfN、flatMap、union、weighted）与Prop的组合逻辑（&&、||、tag、forAll）。

到了练习 16，测试对象换成了第 7 章开发的并行库Par。最简单的并行程序生成器是练习 15 之前的gpy：

val gpy: Gen[Par[Int]] = Gen.choose(0, 10).map(Par.unit(_))

它虽然能产生Par[Int]，但每个值都只是Par.unit包装的常量——没有任何fork，也没有嵌套结构。用它测试fork相关的性质时，所有测试用例长得一模一样，几乎测不到并行执行路径。

练习 16 的要求正是补上这一环：构造一个Gen[Par[Int]]，让生成出的并行程序在结构上有真实变化。仓库中该练习的答案位于 answerkey/testing/16.answer.md，其注释清楚地说明了设计意图：

AGen[Par[Int]]generated from a list summation that spawns a new parallel computation for each element of the input list summed to produce the final result. This is not the most compelling example, but it provides at least some variation in structure to use for testing.

即：生成一个“列表求和”的并行程序，输入列表的每个元素都会催生一个新的并行计算；例子本身不惊艳，但足以在结构上产生变化，供测试使用。值得一提的是，练习 16 没有提供单独提示（answerkey/testing/16.hint.md 内容仅为-，按 README.md 的说明，无提示的题目提示文件就是一个-）；而练习 17 的提示则直接点明了依赖关系：“使用上一道练习的Gen[Par[Int]]生成器”。

二、标准答案逐行拆解

练习 16 的完整答案如下：

val gpy2: Gen[Par[Int]] = choose(-100, 100).listOfN(choose(0, 20)).map(ys => ys.foldLeft(Par.unit(0))((p, y) => Par.fork(p.map2(Par.unit(y))(_ + _))))

整条流水线由三个环节组成：

环节一：choose(-100, 100)——元素取值域

生成[-100, 100)区间内的随机Int（右开区间，不含 100）。仓库答案模块 Exhaustive.scala 中的实现是：

def choose(start: Int, stopExclusive: Int): Gen[Int] = Gen(State(RNG.nonNegativeInt).map(n => start + n % (stopExclusive-start)), bounded(LazyList.from(start).take(stopExclusive-start)))

随机通道用State[RNG, Int]完成（底层是第 6 章的线性同余RNG.Simple，见 State.scala）；穷举通道则生成从start起、长度为stopExclusive - start的有限惰性列表，即该有限域内全部 200 个整数。

环节二：listOfN(choose(0, 20))——动态决定列表长度

listOfN有两个重载：固定长度版listOfN(n: Int)和动态长度版listOfN(size: Gen[Int])。这里传入的是一个Gen[Int]，因此每次采样都会先随机出一个[0, 20)的长度，再生成相应个数的元素。动态版本的本质是flatMap：

def listOfN(size: Gen[Int]): Gen[List[A]] = size.flatMap(n => this.listOfN(n))

（见 Exhaustive.scala）这一层是“结构变化”的第一来源：测试用例的列表长度从 0 到 19 随机浮动，后续并行程序的规模也随之变化。

环节三：map(ys => foldLeft(...))——把列表折叠成并行求和程序

这是核心。对采样出的列表ys，用foldLeft从Par.unit(0)起步，逐个元素把y加进并行程序：

ys.foldLeft(Par.unit(0))((p, y) => Par.fork(p.map2(Par.unit(y))(_ + _)))

其中：

• Par.unit(0)：零元素基线，立即返回常量 0（见 Par.scala，它不占用ExecutorService线程）；
• p.map2(Par.unit(y))(_ + _)：把当前累积结果p与常量y并行合并求和。阻塞版map2的实现是同时取出两个Future的结果再应用函数f（见 Par.scala）；
• Par.fork(...)：把合并动作提交到线程池异步执行。阻塞版fork的实现是es.submit(new Callable[A] { def call = a(es).get })（见 Par.scala）。

整个生成器用到的组合子及其作用汇总如下：

三、它生成的计算长什么样：一棵“求和分叉树”

以ys = List(1, 2, 3)为例，展开折叠过程：

p0 = Par.unit(0) p1 = Par.fork(p0.map2(Par.unit(1))(_ + _)) // 结果：1 p2 = Par.fork(p1.map2(Par.unit(2))(_ + _)) // 结果：3 p3 = Par.fork(p2.map2(Par.unit(3))(_ + _)) // 结果：6

最终p3是一个右嵌套（right-nested）的分叉链：每遇到一个元素，就在现有程序外包一层fork(map2(..., unit(y)))。因此：

• fork数量 = 列表长度：列表越长，并行任务越多，运行时要占用的线程池线程也越多；
• 每个fork恰好包住一个map2：map2本身不开新线程（fork是 API 中控制并行的唯一函数，这一点在 Par.scala 的注释中有明确说明），并行度全部来自fork；
• 计算结果恒等于ys.sum：无论结构如何变化，最终值都是列表元素之和，这为断言提供了天然的不变式。

换句话说，gpy2生成的不是“随机的Par值”，而是“参数化结构的求和程序”——长度变化带来嵌套深度与任务数量的变化，元素取值变化带来计算内容的变化，二者叠加，测试输入就具备了足够的多样性。

四、配套练习 17：用 forkProp 验证 fork 律

练习 16 的生成器不是摆设，它正是练习 17 的主角。练习 17 的答案位于 answerkey/testing/17.answer.md，只有一行：

val forkProp = Prop.forAllPar(gpy2)(y => equal(Par.fork(y), y))

这条属性表达的是并行库的一条核心定律——fork 律：把任意并行程序y再用fork包一层，其结果应当与原来完全相同（fork只引入异步调度，不应改变语义）。

其中两个关键拼图在答案模块 Exhaustive.scala 中均有定义：

def equalA: Par[Boolean] = p.map2(p2)(_ == _) // L150-L151：把两个 Par 的比较包装成 Par[Boolean] def forAllParA(f: A => Par[Boolean]): Prop = forAll(executors ** g)((s, a) => f(a).run(s).get) // L163-L164

equal复用map2把“比较相等”这件事也并行化；forAllPar则把“执行器”和“被测值”打包成二元组一起生成：对每个用例，先用a构造出Par[Boolean]，再在随机选出的执行器s上run(...).get取出布尔结果交给forAll判定。forkProp的完整定义与gpy2一起位于 Exhaustive.scala，pint2（语义相同、放在object Gen内的版本）见 Exhaustive.scala。

执行器也要“随机生成”

forAllPar里的executors本身就是一个Gen[ExecutorService]，位于 Exhaustive.scala：

val executors: Gen[ExecutorService] = weighted( choose(1,4).map(Executors.newFixedThreadPool) -> .75, unit(Executors.newCachedThreadPool) -> .25)

75% 的概率生成 1～4 线程的定长线程池（newFixedThreadPool），25% 的概率生成缓存线程池（newCachedThreadPool）。这样fork律就不只在线程数充足时成立，还要在线程池很小（1 个线程，fork大量排队）时依然成立——这正是属性测试优于手写示例的地方：调度环境本身也被纳入被测维度。weighted的实现（含穷举通道的加权交错interleave）见 Exhaustive.scala。

值得一提的是，equal(Par.fork(y), y)中的y来自gpy2，其结构里已经含有多层fork；再套一层fork后，两侧程序的嵌套深度不同，但求和结果必须一致。如果fork实现有并发 bug（例如竞态导致部分子任务未被等待），这类深层嵌套的用例比gpy生成的平凡unit用例更容易暴露问题。

五、底层原理：Gen 的“穷举 + 随机”双重表示

gpy2能同时服务于随机测试与穷举测试，是因为答案模块中的Gen采用双通道表示（见 Exhaustive.scala）：

case class Gen+A

• sample：随机采样通道，基于第 6 章的State[RNG, A]；
• exhaustive：穷举通道，LazyList[Option[A]]，None表示“域在此处穷尽”。

关键设计决策：

1. 有穷域穷举、无穷域退化为None：choose(-100, 100)的穷举通道是bounded(LazyList.from(start).take(200))——完整的 200 个值；而double、int等无穷域则直接使用unbounded = LazyList(None)（Exhaustive.scala）。
2. 组合子双通道同步推进：map同时映射两个通道（Exhaustive.scala）；listOfN的穷举通道用cartesian生成“所有元素组合”的笛卡尔积（Exhaustive.scala）；flatMap遇到None会转入无穷域（Exhaustive.scala）。因此gpy2的穷举通道在理论上覆盖了“所有长度 × 所有元素组合”的完整程序结构。
3. 穷举与随机按 1:2 混跑：forAll（Exhaustive.scala）把用例数分成两份——先用n/3个用例遍历穷举通道，若有限域被完整走完且无反例，则属性直接Proven；否则转入随机通道补足剩余用例，最终标记为Unfalsified。这解释了为什么forkProp这类用例可以在“有限但天文数字级大”的域上快速给出结论：它只检查前几十个穷举用例 + 随机补采，不会真的枚举200^19种组合。

正因为穷举通道可能是天量惰性流，gpy2在答案模块中被声明为lazy val（Exhaustive.scala），把构造推迟到首次使用时，避免object Prop初始化阶段就背负构造开销。

六、在仓库中运行与验证

仓库采用 Scala CLI 构建（用法见 README.md）。先在根目录编译：

scala-cli compile .

然后用 REPL 直接检验forkProp：

scala-cli console .

import fpinscala.answers.testing.exhaustive.* import fpinscala.answers.testing.exhaustive.Prop.* forkProp.run() // 默认 maxSize=100, testCases=100

若属性通过，run会按 Exhaustive.scala 的输出逻辑打印：

+ OK, property unfalsified, ran 100 tests.

（gpy2的穷举域过大，33 个穷举用例无法走完，故状态为Unfalsified而非Proven；run的默认参数与check一致，见 Exhaustive.scala。）若想拿到结构化结果而非打印，可改用forkProp.check()。

仓库的测试套件同样使用了这套穷举版Gen库来验证并行组合子：例如 NonblockingSuite.scala 里用Gen.boolean.map(Par.unit)、genShortNumber.map(Par.unit)等生成Par[Int]、Par[String]、Par[Par[String]]，再对choice、choiceN、join等逐一断言；GenSuite.scala 则用ExhGen.int、ExhGen.int ** ExhGen.int等生成器对Gen原语本身做属性测试。二者的公共基类 PropSuite.scala 把forAll的结果桥接到 munit 测试框架。

七、延伸：从Par到函数生成（练习 18～20）

gpy2的套路（组合子流水线 + 结构变化）可以继续推广。练习 18 指出：想验证takeWhile的最长前缀性质，需要Gen[Int => Boolean]这类函数生成器；练习 19 的答案给出了通用方案——引入Cogen（反生成器），用输入值扰动 RNG 种子来构造确定性函数（见 answerkey/testing/19.answer.md 与 Exhaustive.scala 的cogenInt、takeWhilePropInt）：

def cogenInt: Cogen[Int] = (i, rng) => val (seed, rng2) = rng.nextInt RNG.Simple(seed.toLong ^ i.toLong)

练习 20 则是开放题，仓库未给出固定答案（answerkey/testing/20.answer.md）。可以看到，第 8 章从“生成基本值”一路走到“生成程序结构（Par）”“生成函数”，最终把属性测试的生成能力覆盖到了高阶对象——gpy2正是这条进阶路径上承上启下的关键一环。

参考与深入阅读

• 练习 16 答案：answerkey/testing/16.answer.md；练习 17 答案：answerkey/testing/17.answer.md
• 穷举版测试库完整实现（含gpy2、forkProp、forAllPar、executors、Gen双通道表示）：Exhaustive.scala
• 非穷举版答案库（更贴近书中正文的Gen = State[RNG, A]表示）：Gen.scala
• 并行库Par（阻塞版fork/map2/unit）：Par.scala；非阻塞 CPS 版：Nonblocking.scala
• 配套测试：NonblockingSuite.scala、GenSuite.scala、PropSuite.scala
• 构建与运行方式：README.md

• 示例工程