Effectful 递归方案

# Effekt 语言：具备效应的递归方案 来源：https://effekt-lang.org/blog/recursion-schemes/ `` import set `` 像 Haskell 这样的常见函数式编程语言使用递归方案（recursion schemes）来对折叠/展开模式进行泛化。这通常依赖于无限递归类型以及某种形式的 Functor 实例化。今天我想展示一种基于效应的递归方案实现，它改用了将数据结构重新函数化为效应和处理器的方式。 事实上，这篇文章的重点更多地在于展示效应与处理器，而非递归方案本身： > 这是一篇*交互式*博客文章，鼓励大家动手尝试代码！ 让我们先构造一些基础的 Lambda 项，作为贯穿全文的例子数据结构。 `` type Term { Sym(name: String) Lam(name: String, body: Term) App(function: Term, argument: Term) } `` 例如，恒等函数 `λx.x` 被编码为如下项： `` Lam("x", Sym("x")).show `` 在 Effekt 中，我们可以通过模式匹配并递归调用遍历函数来遍历这些项。例如，如果我们想使用自定义的 `show` 实现而不是默认实现： `` def pretty(t: Term): String = t match { case Sym(x) => x.show case Lam(x, b) => s"λ${x}.${b.pretty}" case App(f, a) => s"(${f.pretty} ${a.pretty})" } `` `` App(Lam("x", Lam("y", Sym("x"))), Lam("x", Sym("x"))).pretty `` 事实上，这正是对项实现 `fold` 函数的绝佳场景。*同态折叠（catamorphism）*递归方案是对折叠操作的泛化。在这种方案中，我们不再对 `b: Term` 调用 `pretty`，而是直接处理已经是递归调用结果的 `b: String`。理想情况下，采用同态折叠风格的 `pretty` 函数可能长这样： `` def pretty?(t: Term): String = <{"something with cata"}> { case Sym(x) => x.show case Lam(x, b) => s"λ${x}.${b}" case App(f, a) => s"(${f} ${a})" } `` ## 同态折叠（Catamorphism） 传统上，你会定义一个单独的参数化 `TermF`，其中所有递归出现的 `Term` 都会被替换为一个类型变量。原来的 `Term` 类型就变成了 `TermF (TermF (TermF ...))`，即一个无限递归的类型。不过 Effect 并不支持无限类型！ 但 Effect *支持*的是效应与处理器。你可以在我们的语言导览中了解更多关于 Effect 效应机制的内容（https://effekt-lang.org/tour/effects）。重构后的 `TermF` 变体由以下接口定义： `` interface TermF[T, R] { def sym(name: String): R def lam(name: String, body: T): R def app(function: T, argument: T): R } `` 例如，对 `sym` 的调用可以像下面这样进行处理器捕获：（注意这里需要加上 `do` 前缀，因为它是一个效应操作） `` try do sym("x") with TermF[String, String] { def sym(x) = s"got ${x}!" def lam(x, b) = <{"not implemented"}> def app(f, a) = <{"not implemented"}> } `` *思考题：*尝试将`do sym("x")`替换为`do lam("x", do sym("x"))`。为什么这次不会报出 `"not implemented"` 错误？ *答案：*一旦 `do sym("x")` 被处理完毕，整个表达式 `do lam("x", do sym("x"))` 实际上已经变成了 `"got x!"`。为了让 `do sym("x")` 调用能正确拿到这个字符串作为返回值，必须通过 `resume` 将期望的值传回。 `` try do lam("x", do sym("x")) with TermF[String, String] { def sym(x) = resume(x) def lam(x, b) = resume(s"λ${x}.${b}") def app(f, a) = resume(s"(${f} ${a})") } `` 同态折叠的效应化实现，不过是这种 `Term → TermF[A]` 模式的泛化而已。`cata` 的效果签名中包含 `TermF[A, A]`，因为这些效应必须由调用方上下文来捕获处理： `` def cata[A](t: Term): A / TermF[A, A] = t match { case Sym(x) => do sym(x) case Lam(x, b) => do lam(x, b.cata) case App(f, a) => do app(f.cata, a.cata) } `` 我们可以把之前写的 `pretty` 函数重写为同态折叠形式： `` def pretty!(t: Term) = try t.cata with TermF[String, String] { def sym(x) = resume(x) def lam(x, b) = resume(s"λ${x}.${b}") def app(f, a) = resume(s"(${f} ${a})") } `` `` App(Lam("x", Lam("y", Sym("x"))), Lam("x", Sym("x"))).pretty! `` 类似地，我们也可以利用 `cata` 来统计 Lambda 项中构造函数的数量——无需显式编写递归逻辑！ `` def size(t: Term) = try t.cata with TermF[Int, Int] { def sym(x) = resume(1) def lam(_, b) = resume(1 + b) def app(f, a) = resume(1 + f + a) } `` `` App(Lam("x", Lam("y", Sym("x"))), Lam("x", Sym("x"))).size `` 或者提取项中的所有自由变量： `` def free(t: Term) = try t.cata with TermF[Set[String], Set[String]] { def sym(x) = resume(x.singletonGeneric) def lam(x, b) = resume(b.difference(x.singletonGeneric)) def app(f, a) = resume(f.union(a)) }.toList def freeIn(x: String, t: Term) = t.free.contains(x) { (a, b) => a == b } `` `` App(Lam("x", Lam("y", Sym("x"))), Lam("x", Sym("z"))).free `` ## 参数同态（Paramorphism） 与 `cata` 不同，`para` 还会向处理器传递原始数据结构。我们可以通过扩展 `cata` 来实现：让处理器接收一个包含原始项的元组： `` def para[A](t: Term): A / TermF[(Term, A), A] = t match { case Sym(x) => do sym(x) case Lam(x, b) => do lam(x, (b, b.para)) case App(f, a) => do app((f, f.para), (a, a.para)) } `` 例如在代换操作 `t[x/r]` 中，这可以用来防止向内层正在被代换的项 `t` 递归（如果它也绑定了变量 `s` 的话）： `` def substitute(t: Term, x: String, r: Term) = try t.para with TermF[(Term, Term), Term] { def sym(y) = resume(if (x == y) r else Sym(y)) def lam(y, b) = resume( if (x == y) Lam(y, b.first) // 遮蔽（shadowing）！ else if (y.freeIn(r)) <> // α-重命名（已省略） else Lam(y, b.second)) def app(f, a) = resume(App(f.second, a.second)) } `` `` App(Lam("x", Lam("y", Sym("x"))), Lam("x", Sym("z"))).substitute("z", Sym("foo")) `` ## 生成同态（Anamorphism） 生成同态专注于从单个“种子”展开构建结构。它与将结构折叠为单一值的同态折叠正好互为对偶。 考虑下面这段使用标准库中 `emit` 效应输出每个自然数的程序。 `` def nats(s: Int): Unit / emit[Int] = { do emit(s); nats(s + 1) } list::collect[Int] { limit[Int](10) { nats(0) } } `` 在这里，展开的种子是 `s`，递归调用的结果会作为下一轮迭代的种子。展开过程中产生的值随后通过 `collect` 函数被收集起来。 我们可以将其泛化为用于列表构造的 `ana` 函数，利用 `cons` 效应直接在第二个参数中提供下一个种子： `` effect cons[S, R](hd: R, tl: S): List[R] def ana[S, R](s: S) { coalg: S => List[R] / { cons[S, R], stop } }: List[R] = try coalg(s) with cons[S, R] { (hd, tl) => resume(Cons(hd, tl.ana{coalg})) } with stop { Nil[R]() } `` 该定义也支持 `stop` 效应，以便强制终止展开过程。例如，要打印直到 `n` 的斐波那契数列： `` def fib(n: Int) = ana[(Int, Int, Int), Int]((0, 0, 1)) { case (i, a, b) => if (i == n) do stop() else do cons(a, (i + 1, b, a + b)) } fib(10) `` 对于 Lambda 项，我们现在可以构造一个非常相似的函数。由于 `Term` 只能包含 `Term`，此处不需要对 `R` 进行参数化： `` def ana[S](s: S) { coalg: S => Term / TermF[S, Term] }: Term = try coalg(s) with TermF[S, Term] { def sym(x) = resume(Sym(x)) def lam(x, b) = resume(Lam(x, b.ana{coalg})) def app(f, a) = resume(App(f.ana{coalg}, a.ana{coalg})) } `` 如果你将此定义与上面的 `cata` 对比，你会发现它们确实完美互相对偶——不同的是，我们不再是*执行*效应，而是*捕获处理*效应！ 它可以应用于各种类型的种子。例如，假设我们想把使用 de Bruijn 索引的 Lambda 项（`DTerm`）转换回之前的 `Term`。那么，从一个空环境和 de Bruijn 索引项（种子）开始，随着 `DTerm` 不断缩小，`Term` 则从效应化的构建过程中逐渐浮现，同时环境也会不断被填充： `` type DTerm { DIdx(index: Int) DLam(body: DTerm) DApp(function: DTerm, argument: DTerm) } effect fresh(): String def freshener[R] { prog: => R / fresh } = { var x = 0 try prog() with fresh { x = x + 1 resume(s"x${x.show}") } } def fromDeBruijn(t: DTerm) = with on[OutOfBounds].panic() with freshener ana((t, Nil[String]())) { case (DIdx(i), env) => do sym(env.get(i)) case (DLam(b), env) => val x = do fresh(); do lam(x, (b, Cons(x, env))) case (DApp(f, a), env) => do app((f, env), (a, env)) } `` `` fromDeBruijn(DApp(DLam(DLam(DIdx(1))), DLam(DIdx(0)))).pretty `` ## 混合同态（Hylomorphism） 混合同态结合了同态折叠与生成同态。如同生成同态一样，我们从开始展开的种子出发；又如同同态折叠一样，展开的结构随后会被折叠回一个值。提醒一下，它们之前分别定义为：*\（你注意到其中的对称性了吗？*\) `` def cata[A](t: Term): A / TermF[A, A] = t match { case Sym(x) => do sym(x) case Lam(x, b) => do lam(x, b.cata) case App(f, a) => do app(f.cata, a.cata) } def ana[S](s: S) { coalg: S => Term / TermF[S, Term] }: Term = try coalg(s) with TermF[S, Term] { def sym(x) = resume(Sym(x)) def lam(x, b) = resume(Lam(x, b.ana{coalg})) def app(f, a) = resume(App(f.ana{coalg}, a.ana{coalg})) } `` 结合两者的定义，可以得到一个朴素的 `hylo` 实现： `` def hyloNaive[S, A](s: S) { coalg: S => Term / TermF[S, Term] }: A / TermF[A, A] = s.ana{coalg}.cata `` 我们现在就可以做这件事，将 `pretty!` 和 `fromDeBruijn` 合并到一个自包含的 `hyloNaive` 调用中： `` val t = DApp(DLam(DLam(DIdx(1))), DLam(DIdx(0))) with on[OutOfBounds].panic() with freshener try hyloNaive[(DTerm, List[String]), String]((t, Nil[String]())) { case (DIdx(i), env) => do sym(env.get(i)) case (DLam(b), env) => val x = do fresh(); do lam(x, (b, Cons(x, env))) case (DApp(f, a), env) => do app((f, env), (a, env)) } with TermF[String, String] { def sym(x) = resume(x) def lam(x, b) = resume(s"λ${x}.${b}") def app(f, a) = resume(s"(${f} ${a})") } `` `hyloNaive` 的问题在于，它会先递归地构建出完整的项，然后立刻再次解构它们。相反，`hylo` 也可以写成不构造任何额外 `Term` 的形式。下面是融合 `cata` 和 `ana` 的版本： `` def hylo[S, A](s: S) { coalg: S => A / TermF[S, A] }: A / TermF[A, A] = try coalg(s) with TermF[S, A] { def sym(x) = resume(do sym(x)) def lam(x, b) = resume(do lam(x, b.hylo{coalg})) def app(f, a) = resume(do app(f.hylo{coalg}, a.hylo{coalg})) } `` 注意在这个最终版本中，`Term` 类型已经完全消失了！ ## 轮到你来试试！ 现在轮到你亲自实验，进一步探索这类递归方案的构造了。如何通过参数同态或混合同态实现阶乘函数？应如何在 Effect 中定义*历史同态（histomorphism）*和*未来同态（futumorphism）*？你对 Effect 编程还有其他有趣的想法吗？ 这里有我们的*交互试玩平台*链接（https://effekt-lang.org/playground）、*语言导览*（https://effekt-lang.org/tour），以及*安装指南*（https://effekt-lang.org/docs）。玩得开心！