一个程序先读取计数器，再加上“旧值加一”，最后重新读取。初始值为二时，结果应该是五。测试希望把计数器放在纯状态里，运行时希望把它放在原子引用里，同时又不想写两套业务流程。这是程序描述和程序解释分离的一个足够小的例子。

Free 把指令与依赖关系组成一个可解释的值；Tagless Final 把程序写成针对能力接口的多态函数。两者都能支持多个解释器，也都可能被错误使用。本篇用同一套指令和同一条流程做四格实验，再检查十万步组合与一个实际栈溢出反例。背景可衔接Scala 的高阶类型与组合定律和Cats 与 IO 的执行和取消，系列入口见导读与能力自测。

先把程序允许做的事限制下来

程序只能 Read 或 Add，不允许任意删除文件、发网络请求，也不允许取得整个可变引用。指令用带结果类型的枚举描述：

1
2
3
4
5
6
7
enum Op[A]:
  case Read extends Op[Int]
  case Add(n: Int) extends Op[Unit]

trait Counter[F[_]]:
  def read: F[Int]
  def add(n: Int): F[Unit]

Read 产生 Int，Add 只确认动作完成。Op[A] 保存单条指令，Counter[F] 则暴露两种可以组合的能力。二者没有定义执行位置、错误策略或线程模型。特别是 Add 返回 Unit，不代表它不会失败；本例暂时选择没有业务错误的解释器，真实接口需要另外表达失败能力。

业务流程只需要顺序组合：

1
2
3
4
5
6
def program[F[_]: Monad](c: Counter[F]): F[Int] =
  for
    before <- c.read
    _ <- c.add(before + 1)
    after <- c.read
  yield after

初始二，第一次读出二，加三得到五，再读出五。第二条指令的参数依赖第一条指令的结果，所以这里需要 flatMap。若所有参数在构造时就已经知道，较弱的 Applicative 结构可能足够；不能仅因写成 for 就认定必须选择最强抽象。

这里 F 的实例必须提供符合约定的 Monad。类型类约束能提供方法，但编译器不会替实例证明结合律。Counter 的 read/add 还需要遵守领域契约，例如 read 不应额外加一；这些都是解释器测试需要覆盖的内容。

Free保存了什么

为每条指令调用 Free.liftF，可以把它提升成 Free 程序：

1
2
3
4
5
val freeCounter = new Counter[[A] =>> Free[Op, A]]:
  def read = Free.liftF(Op.Read)
  def add(n: Int) = Free.liftF(Op.Add(n))

val free: Free[Op, Int] = program(freeCounter)

调用 program 时获得的是组合描述。Read 尚未读到二，因此程序不能提前把 Add 的参数固定成三；这个参数要等解释 Read 后，由保存的后续计算产生。Free 不必把全部未来步骤都展开成一个静态列表。

这也是“程序是数据”容易被过度解释的地方。Free 的结构中可以保存宿主语言函数作为 continuation，而普通 Scala 闭包不是天然可序列化、可跨版本存储的协议。若需求是持久化工作流、人工审批恢复或跨机器迁移，仍要设计稳定的指令编码、数据版本、外部结果记录和恢复语义，不能只调用 Free.liftF 就视为完成。

解释器是一个保持结果类型的变换 Op ~> F。读指令必须给出 F[Int]，加指令必须给出 F[Unit]，不能统一返回 Any 后再靠调用方猜类型：

1
2
3
4
def compiler[F[_]](c: Counter[F]): Op ~> F = new (Op ~> F):
  def apply[A](op: Op[A]): F[A] = op match
    case Op.Read   => c.read
    case Op.Add(n) => c.add(n)

foldMap 在目标效果中解释单条指令，并把结果交给后续程序。Cats 的Free 文档给出了这种 liftF、自然变换与解释的基本关系。本实验只借用这组接口，具体计数器语义和四格断言由本地代码定义。

两个解释器，四次真实执行

纯解释器选择 State[Int,A]。read 是 State.get，add 是 State.modify(_ + n)；运行结果包含最终状态和返回值。初始二时，Free 解释结果与直接多态程序都应为 (5,5)。只检查返回值五不足以证明状态正确，因为坏解释器可能伪造返回值却未更新状态。

效果解释器选择 Cats Effect IO 与 AtomicInteger。read 放进 IO(cell.get())，add 放进 IO 后再调用 addAndGet。这一层延迟非常重要：若先在外面执行 cell.get，再用 IO.pure 包装，程序构造时就会读状态，复用时也会读到旧快照。

实验在运行 IO 前断言原子引用仍为二，执行之后同时检查返回值五、引用值五。每一种编码都使用新的原子引用，避免前一次实验留下的状态污染下一次。四种组合的实际含义如下：

程序形式 解释载体 初值 返回值与最终状态
Free 指令描述 State 2 5、5
能力参数程序 State 2 5、5
Free 指令描述 IO 原子引用 2 5、5
能力参数程序 IO 原子引用 2 5、5

这不是用纯解释器模拟 IO 后声称效果已验证。实际执行确实经过 IO 的运行时和原子引用，但没有网络、数据库或事务。原子 Add 也不代表整个 Read/Add/Read 流程是原子事务；如果插入其他并发写入，程序可能观察到不同状态。当前实验是单流程顺序执行，边界需要保持明确。

Tagless Final并不禁止程序分析

对 program[F] 传不同 Counter，就可以把相同业务流程解释成不同载体。代码没有先建立 Op 枚举再遍历它，因此通常减少显式指令节点的样板。但“没有默认 AST”与“无法分析或优化”不是同一个结论：还可以选择记录描述的解释器，或在解释器里组合分析结果。

Oleg Kiselyov 的Tagless-Final 作者材料把求值器、编译器、分析器和优化器都视为解释器，并展示该风格的扩展方向。本篇的能力参数写法是工程上常见的受限实例，不覆盖类型化高阶 DSL、分阶段生成代码或完整表达式问题。

某些业务流程依赖读取结果，纯静态分析未必能枚举所有路径。想提前知道“最多会加多少次”，需要描述输入范围、循环界限与解释器语义。把 F 换成 Writer 并不能凭空知道未知的 Read 结果；分析器要么使用抽象值，要么承认它只分析一条具体执行路径。

两种编码也可以相互配合。本例就通过 Counter[Free[Op,*]] 复用同一个业务函数生成 Free 程序，避免为了比较而维护两份逻辑。这样比较关注的是表示和解释机制，而不是两份业务代码是否偶然写得一致。

栈安全必须区分构造与运行

程序最终处于 IO 里，不代表构造它的 Scala 递归自动栈安全。下面的递归在返回第一个 IO 之前就继续调用自己：

1
2
3
def unsafe(n: Int): IO[Int] =
  if n == 0 then IO.pure(0)
  else unsafe(n - 1).map(_ + 1)

实验对一百万层调用实际捕获 StackOverflowError，随后断言确实发生。这里的失败发生在描述构造阶段，尚未进入 unsafeRunSync。为了检验这个反例而捕获该错误，不意味着生产服务应该依赖捕获栈溢出来恢复任意状态。

对 Free，实验用宿主语言的 foldLeft 构造十万个 add(1)，再 foldMap 到 State，断言最终状态十万。构造使用循环式集合折叠，避免先在普通递归中溢出；解释依赖实际库实例的栈安全实现。这个结果不能被外推为任意手写 Free 解释器都安全。

对最终风格，实验使用 Monad[IO].tailRecM，状态计数从零到十万。Left 表示继续，Right 表示结束，每轮执行一次 add(1)。这里明确把循环交给效果实例，而不是让 Scala 调用栈保存十万层未返回的方法。

还可以用 IO.defer 延迟递归构造，但延迟点必须覆盖递归调用本身。先递归求出参数再传给延迟函数，仍然太晚。判断方法是沿求值顺序问：下一次普通方法调用发生在 IO 值创建之前，还是由运行时解释一个延迟节点时触发？类型表面一样，执行位置不同。

栈安全也不等于常量空间。Free 程序节点、闭包、收集的结果和解释器状态都可能占堆；遍历十万步成功不能证明百万步的内存可接受。本实验没有测吞吐、GC、分配率，也没有跨版本基准，因此只报告具体深度上的行为，不比较性能优劣。

扩展指令时需要维护的契约

如果新增 Reset，初始编码要扩展 Op 并检查解释器模式匹配；能力参数编码要扩展 Counter 或引入较小的新能力接口。Scala 编译器能帮助定位漏实现，但业务语义仍需用同一组例子检查。把新增方法默认实现成无操作会让编译变容易，却让解释器间的行为一致性更难确认。

如果新增业务错误，State 的状态变化与错误之间也存在设计选择：失败时保留已发生状态，还是回滚整条流程？StateT[Either,...] 与把 Either 放在 State 返回值里可能表现不同。Free 或 Tagless Final 不替项目选择事务语义，必须在解释器契约中明确。

对于有外部写入的解释器，纯 State 测试只能证明算法和预期指令顺序，不能证明幂等键、网络重试或取消后远端状态。效果边界应保留集成验证，不能因为核心程序可解释就把所有测试都降成纯函数断言。

测试解释器的能力与局限

纯解释器特别适合把外部响应作为确定输入。比如把 read 的结果固定成某个状态，再检查业务计算选择了哪些 add 参数。这能使失败复现不依赖真实数据库，也能对边界数值做大量组合测试。不过解释器必须忠实于被测契约：若真实 add 可能失败，而测试版永远成功，测试只能说明成功路径，不能被用来批准故障恢复逻辑。

记录指令序列也不等于验证执行结果。一个解释器可以记录 Add(3)，却忘记更新计数器；另一个可以更新到五，却记录错误参数。需要哪些可观察量，取决于系统要求。当前四格同时比较结果与状态，构造前检查则额外证明 IO 未提前访问可变引用；这些检查彼此不能相互替代。

选型时可以先问程序是否确实需要被保存、遍历或改写。如果只需要替换数据库实现，能力参数往往足够直接；如果需要对受限指令做统一解释，Free 可以提供现成的组合描述。但 Free 中的后续函数仍可能包含不透明宿主代码，而最终风格也可以解释成描述，因此这个区分是默认表示方式和维护成本的差异，不是绝对能力边界。

两种风格都应避免把整个应用接口塞进单个巨大的代数。只有读取能力的程序不必获得写入、清库或发布消息的方法。较窄的接口使类型参数真正限制程序可做的事，也减少测试解释器必须实现的无关操作。为了方便而返回底层客户端，会绕过原先的能力边界。

此外，解释时机决定配置和资源的生命周期。若解释器闭包捕获已经关闭的连接，Free 描述本身再纯也无法保证执行成功；若同一个状态解释器被多个任务共享，测试中顺序运行的结果也不能直接推广。把连接获取与释放放到明确作用域，在作用域内解释程序，才有机会验证完整生命周期。

复现、预测与修改

版本固定为 Scala 3.3.7、Cats Core/Free 2.12.0、Cats Effect 3.5.7。运行 node examples/functional-programming/run.mjs E04，实际输出：

1
2
free/state=5; final/state=5; free/io=5; final/io=5; construction-no-effects=true
free-depth=100000; final-tailRecM=100000; eager-recursion=StackOverflowError

完整代码见Main.scala，依赖指令、执行命令、哈希与退出状态见result.json。库提示有更新版本不影响本实验固定版本的验收，也不构成升级建议。

手算初始值为负二的流程：先读负二，再加负一，最终得到负三。若某个解释器返回一，检查它是否错误地把 add 理解成替换，或者把旧值加一计算成绝对值。四格实验的重要性就在于把同一领域契约施加于不同载体。

修改题是在能力与指令中增加 set(n)，写“读取旧值、设为零、返回旧值”的程序，并在四种组合里验证最终状态零、返回值仍为原值。另写一个故意把 set 实现成 add 的解释器，确保同一断言能抓到它。然后把不安全递归改为 IO.defer 版本，保持一百万层目标，区分构造成功与实际执行成功，分别设置断言。