Blog. Derive Iteration from Recursion [blog/defunctionalize]

CAIMEOX
2025-04-07

递归和迭代是编程中两种基础的重复执行模式，它们在实现方式上有所不同，但计算能力上是等价的。递归通过函数调用自身来分解问题，通常表达简洁，符合数学 (结构) 归纳法的思维模式；而迭代则借助循环结构 (如 for、while) 逐步更新状态，直接控制计算流程。然揆诸实现，则各具长短：

递归代码短小清晰，适合解决分治问题 (如树的遍历、动态规划)，但可能导致栈溢出 (stack overflow) 和较高的函数调用开销，尤其是深度递归时效率降低。
迭代虽然执行更快，节省栈空间，但需要开发者显式管理状态 (如循环变量、临时存储、甚至需要手动维护一个栈)，逻辑可能不如递归直观。

既然两者各有优劣，是否存在一种通用方法，能够自动或半自动地将递归逻辑转换为等价的迭代实现？答案是肯定的，而这正是本文的核心概念——去函数化 (defunctionalization)，即将递归的函数调用关系转换为显式的栈管理结构，从而在保持正确性的同时提升运行效率。

1. Defunctionalization: A Taste on Filter DSL [blog/defunctionalize/filter]

让我们以循序渐进的方式展开论述。作为切入点，不妨考察一个具有典型性的基础案例：设想需要实现 filter 函数，该函数接收列表与谓词函数作为输入，返回满足谓词条件的所有元素构成的新列表。采用递归策略可达成如下实现：

fn filter[T](xs : List[T], pred : (T) -> Bool) -> List[T] {
  match xs {
    Nil => Nil
    Cons(x, xs) if pred(x) => Cons(x, filter(xs, pred))
    Cons(_, xs) => filter(xs, pred)
  }
}

此处 pred 作为高阶函数的特性引发了一个本质性问题：在底层编译场景中 (如将 MoonBit 编译至 C 语言时)，函数无法以常规数据结构的形式进行存储与传递。换言之，在目标语言层面，一等函数的直接表示存在根本性限制。

最直观的解决思路莫过于穷举法——将所有可能用到的谓词函数进行枚举编码。以下示例展示了针对整数的几种基本谓词：

enum Filter {
  IsEven
  IsOdd
  IsPositive
  IsNegative
}

fn run(self : Filter, data : Int) -> Bool {
  match self {
    IsEven => data % 2 == 0
    IsOdd => data % 2 != 0
    IsPositive => data > 0
    IsNegative => data < 0
  }
}

借此定义，可重构出经过去函数化处理的过滤函数：

fn filter_defunct(xs : List[Int], pred : Filter) -> List[Int] {
  match xs {
    Nil => Nil
    Cons(x, xs) if run(pred, x) => Cons(x, filter_defunct(xs, pred))
    Cons(_, xs) => filter_defunct(xs, pred)
  }
}

然而此方案存在明显局限性。诚然，高阶谓词函数的集合实为不可数无穷集，这使得完备枚举在理论上即不可行。但通过代数数据类型的参数化特性，我们可获得某种程度上的扩展能力。例如将 IsNegative 推广为带参数的 IsLessThan：

enum FilterExtend {
  //...
  IsLessThan(Int)
}

fn run_extend(self : FilterExtend, data : Int) -> Bool {
  match self {
    IsLessThan(n) => data < n
    //...
  }
}

更富启发性的是引入复合逻辑结构。通过增加 And 等逻辑连接词，可实现谓词函数的组合运算：

enum FilterExtendCompose {
  //...
  And(FilterExtend, FilterExtend)
}

fn run_extend_compose(self : FilterExtendCompose, data : Int) -> Bool {
  match self {
    And(f1, f2) => run_extend(f1, data) && run_extend(f2, data)
    //...
  }
}

经过这般层层抽象，我们所构建的 Filter 类型本质上已演变为一种领域特定语言 (Domain-Specific Language)。建议感兴趣的读者可进一步探索其 Parser 与 Pretty Printer 的实现路径，以完善该 DSL 的序列化能力。

但必须指出，这种基于代数数据类型的方案存在固有的封闭性缺陷——每新增一个枚举成员都需要修改所有相关的模式匹配逻辑 (本案例中的 run 函数)。这与高阶函数与生俱来的开放性形成鲜明对比：后者允许在不修改现有代码的前提下自由扩展新函数。

2. Traverse a Tree [blog/defunctionalize/tree]

通过前文的讨论，读者应对去函数化的核心思想建立了基本认知。本节将运用该技术解决更具挑战性的问题——二叉树遍历优化。首先给出二叉树的规范定义：

enum Tree[T] {
  Leaf(T)
  Node(T, Tree[T], Tree[T])
}

考虑基础的前序遍历实现：

fn pre_order[T : Show](tree : Tree[T], f : (T) -> Unit) -> Unit {
  match tree {
    Leaf(x) => f(x)
    Node(x, left, right) => {
      f(x)
      pre_order(left, f)
      pre_order(right, f)
    }
  }
}

在该函数的设计实现中，我们采用递归算法对树形数据结构进行系统性遍历，这种方法虽能确保每个节点都受到函数 f 的精确，且严格遵循前序遍历（pre-order traversal）的既定顺序，但其递归范式存在显著的效率瓶颈。具体而言，由于该递归过程并非尾递归（tail recursion）的优化形态，导致现代编译器的尾调用优化（TCO）机制无法将其自动转换为等价的迭代形式，这种特性必然造成调用栈的持续累积，进而影响程序的执行效能。有鉴于此，我们亟需运用前文阐述的「去函数化」（defunctionalization）这一程序变换技术来突破此局限。

3. Continuation-Passing Style Transformation [blog/defunctionalize/cps]

面对这个看似棘手的控制流问题，我们稍作停顿。考虑引入“延续” (continuation) 这一关键概念——其本质是对程序剩余计算过程的抽象建模。具体而言，对于表达式 $1 + 2 * 3 + 4$ 的求值过程：当计算 $2 * 3$ 时，其延续即为带洞表达式 $1 + \square + 4$ 所表征的后续计算。形式化地，我们可以将延续定义为高阶函数 $\lambda x. 1 + x + 4$，该函数接收当前计算结果并执行剩余计算过程。

延续传递形式 (Continuation-Passing Style，CPS) 的核心范式在于：所有函数均不直接返回结果，而是通过将中间值传递给延续函数来实现控制流转移。以树的前序遍历为例，当第一个 pre_order(left, f) 调用执行时，其延续正是 fn (_) { pre_order(right, f) } 表征的右子树遍历过程。我们通过扩展函数签名引入延续参数，重构后的实现显式地将计算结果注入到延续中：

fn pre_order_cps[T : Show](self : Tree[T], f : (T) -> Unit) -> Unit {
  fn go {
    Leaf(x), k => k(f(x))
    Node(x, left, right), k => {
      f(x)
      go(left, fn { _ => go(right, k) })
    }
  }

  go(self, fn { x => x })
}

通过严格的 CPS 变换，程序的控制流获得了显式的过程化表征。基于此，我们可进一步实施延续的去函数化，即将高阶函数表示转化为数据结构表示。观察到延续包含两种形态：递归处理函数 go(tree, cont) 与恒等函数 fn { x => x }，我们将其编码为代数数据类型：

enum TreeCont[T] {
  Return
  Next(Tree[T], TreeCont[T])
}

重构后的实现将函数调用转化为对延续结构的模式匹配，引入辅助函数 run_cont 实现之：

fn pre_order_cps_defunct[T : Show](self : Tree[T], f : (T) -> Unit) -> Unit {
  fn run_cont {
    Next(tree, k) => go(tree, k)
    Return => ()
  }

  fn go {
    Leaf(x), k => {
      f(x)
      run_cont(k)
    }
    Node(x, left, right), k => {
      f(x)
      go(left, Next(right, k))
    }
  }

  go(self, Return)
}

为实现彻底的命令式转换，我们先将尾递归形式改写为显式循环结构。通过 MoonBit 的 loop 语法，控制流的跳转关系得到直观呈现：

fn pre_order_cps_defunct_loop[T : Show](
  self : Tree[T],
  f : (T) -> Unit
) -> Unit {
  loop self, Return {
    Leaf(x), k => {
      f(x)
      match k {
        Next(tree, k) => continue tree, k
        Return => ()
      }
    }
    Node(x, left, right), k => {
      f(x)
      continue left, Next(right, k)
    }
  }
}

此时，向传统循环的转换已水到渠成。通过引入可变状态变量，我们获得完全命令式的实现：

fn pre_order_loop[T : Show](self : Tree[T], f : (T) -> Unit) -> Unit {
  let mut k = Return
  let mut t = self
  while true {
    match t {
      Leaf(x) => {
        f(x)
        match k {
          Next(tree, next) => {
            k = next
            t = tree
          }
          Return => break
        }
      }
      Node(x, left, right) => {
        f(x)
        k = Next(right, k)
        t = left
      }
    }
  }
}

经仔细分析可见，延续结构 TreeCont 实质上模拟了栈式存储结构：Next(right, k) 对应入栈操作，而模式匹配 Next(tree, next) 则对应出栈操作。这一洞察使我们能直接给出基于显式栈的实现：

fn pre_order_loop_stack[T : Show](self : Tree[T], f : (T) -> Unit) -> Unit {
  let k = []
  let mut t = self
  while true {
    match t {
      Leaf(x) => {
        f(x)
        match k.pop() {
          Some(tree) => t = tree
          None => break
        }
      }
      Node(x, left, right) => {
        f(x)
        k.push(right)
        t = left
      }
    }
  }
}

这项系统性的转换工程清晰展现了从高阶函数到数据结构，从递归到迭代，从隐式控制流到显式状态管理的完整范式迁移路径。

4. Review and Summary [blog/defunctionalize/review]

$$ \text{CPS} \to \text{Defunctionalization} \to \text{Inlining} \to \text{Tail Call Elimination} $$

让我们对这一系列精妙的程序转换过程进行系统性的理论总结。整个改造工程可分解为四个阶段：

第 Ⅰ 阶段：控制流显式化 (CPS 变换)：通过引入延续传递形式，我们将原本隐含在语言运行时中的执行上下文显式提升为可操作的一等公民。这一关键转换使递归调用点的控制流转移过程浮出水面，为后续的机械化改造奠定了基础。
第 Ⅱ 阶段：去函数化：基于 Reynolds 提出的去函数化理论，我们将高阶的延续函数降维为具体的代数数据类型 TreeCont。这一转换揭示了延续本质上是对调用栈的结构化建模，其中 Next 构造子对应栈帧压入操作，对其模式匹配则是出栈， Return 则表征栈空状态。通过此步骤，动态的函数调用关系被静态的数据结构所替代。
第 Ⅲ 阶段：内联与尾递归化：通过将辅助函数 run_cont 内联到主处理流程，我们消除了函数间的相互递归调用，形成严格的尾递归形式。此时程序的执行流已呈现近线性结构，每个函数调用点的上下文关系完全由传入的延续对象所决定，这为尾调用优化提供了理想的先决条件。
第 Ⅳ 阶段：迭代式转换：最终阶段将尾递归结构转换为基于可变状态和循环命令的迭代实现。这一转换过程严格对应现代编译器对尾调用的优化策略：将递归调用点改写为带状态更新的循环跳转，将延续对象转换为显式的栈数据结构。值得注意的是，从 TreeCont 到命令式栈的转换验证了理论计算机科学中“程序即数据”的观点。

“去函数化”的确是精妙的程序转换技术，若读者在看完本文仍意犹未尽，希望能够深入了解其背后的理论基础，推荐阅读 John Reynolds 关于去函数化的经典文章，以及 Olivier Danvy 很多相关的研究工作。