递归符号表达式线性化转换：名称与实现方法咨询

转换的名称 #

这种将递归树形表达式转换为「每个唯一节点仅出现一次、用步骤编号引用依赖节点」的线性序列的操作，通常被称为公共子表达式提取（CSE, Common Subexpression Elimination）后的线性化表示，也可以理解为抽象语法树（AST）到带节点共享的有向无环图（DAG）的拓扑排序展开。

简单来说，你是把原本可能存在重复子节点的树形结构，转换成了没有冗余的依赖序列——每个节点只被定义一次，后续节点通过编号引用前置节点。这和编译器里的静态单赋值（SSA）形式有相似的设计思路，不过SSA更侧重变量赋值的唯一性，而这里聚焦于表达式节点的唯一性复用。

OCaml实现方案 #

要实现这个转换，核心思路是：遍历表达式时记录每个唯一节点的编号，按依赖顺序收集节点，最后生成线性步骤列表。以下是具体的代码实现：

1. 定义辅助类型 #

首先我们需要定义线性化后步骤的节点类型，用来表示带编号引用的表达式：

(* 原始递归类型 *)
type t = | Param of int | Add of t * t

(* 线性化后的步骤节点：用步骤编号引用依赖 *)
type step_node =
  | StepParam of int
  | StepAdd of int * int

(* 线性步骤：(步骤编号, 节点内容) *)
type linear_step = int * step_node

2. 实现线性化函数 #

我们用哈希表来缓存已经处理过的节点，避免重复生成；同时按依赖顺序收集步骤：

open Hashtbl

let linearize_expr (expr : t) : linear_step list =
  let node_cache = create 10 in  (* 存储原始节点到步骤编号的映射 *)
  let steps = ref [] in          (* 临时存储步骤，最后反转得到顺序 *)
  let next_step_id = ref 0 in    (* 下一个可用的步骤编号 *)

  (* 递归处理每个节点，返回其对应的步骤编号 *)
  let rec process_node = function
    | Param n as orig_node ->
        (* 检查节点是否已经处理过 *)
        if mem node_cache orig_node then
          find node_cache orig_node
        else
          (* 分配新编号，记录到缓存和步骤列表 *)
          let id = !next_step_id in
          add node_cache orig_node id;
          steps := (id, StepParam n) :: !steps;
          incr next_step_id;
          id
    | Add (e1, e2) as orig_node ->
        if mem node_cache orig_node then
          find node_cache orig_node
        else
          (* 先处理子节点，保证依赖的步骤先被定义 *)
          let id1 = process_node e1 in
          let id2 = process_node e2 in
          (* 分配当前节点的编号 *)
          let id = !next_step_id in
          add node_cache orig_node id;
          steps := (id, StepAdd (id1, id2)) :: !steps;
          incr next_step_id;
          id
  in
  (* 触发遍历，填充缓存和步骤 *)
  ignore (process_node expr);
  (* 反转步骤列表，得到从Step 0开始的顺序 *)
  List.rev !steps

3. 测试示例 #

用你给出的fib表达式来测试：

let x = Param(1)
let y = Param(2)
let rec fib n x y = match n with | 0 -> (x, y) | _ -> fib (n - 1) y (Add(x, y))
let (z5_1, z5_2) = fib 5 x y

(* 线性化z5_2 *)
let linearized = linearize_expr z5_2;;

运行后linearized会输出按顺序排列的步骤，每个唯一的Param和Add只出现一次，比如开头几个步骤就是：

[(0, StepParam 1); (1, StepParam 2); (2, StepAdd (0, 1)); (3, StepAdd (1, 2)); ...]

关键细节说明 #

• 去重逻辑：哈希表node_cache用来记录已经处理过的原始节点，确保每个唯一节点只分配一个步骤编号，避免冗余。
• 依赖顺序：递归处理时先处理子节点，这样父节点的编号一定大于子节点的编号，保证线性步骤的依赖关系是合法的（引用的步骤已经被定义）。
• 顺序调整：因为我们把新步骤加到列表头部，最后需要反转列表才能得到从Step 0开始的正确顺序。

内容的提问来源于stack exchange，提问作者user2907934