编程语言应当内置树遍历原语

编程语言应当内置树遍历原语

• 编程语言应该拥有一种专门用于树形遍历的原语控制流结构
• 这种结构在现有的主流编程语言中存在缺失
• 目前的for/forEach循环可以优雅地处理线性遍历
• 但每当需要进行树状结构遍历时，我们总是需要重复编写大量的样板代码
• 此处尝试构思这种控制流结构的具体形态
• (示例代码将以C++风格呈现，但其核心思想具有跨语言适用性)
• 注意：这更多是一个初步构想而非严谨方案

  1
  2
  3
  for_tree(Node* N = mytreeroot; N != NULL; N : {N->left, N->right}){
    print(N->value);
  }
  

• (去除语法细节后)这几乎与现有的 for 循环语法无异

  1
  2
  3
  for_tree(init; condition; branch){
    //body
  }
  

• 本质上，它就是一个通过分支而非线性延续的 for 循环：
  • 初始化（init）：与普通 for 循环完全一致，在进入 for_tree 时执行
  • 条件（condition）：与普通循环相同，决定是否进入循环体
  • 分支（branch）：将初始值演变为多个分支(底层可能编译为递归函数调用)

为何不直接使用递归函数

• 这种语法结构相比手动实现递归函数具有显著优势：
  • 开发效率：无需为每种树类型重复编写递归模板
  • 错误防护：自动处理递归边界条件，避免栈溢出风险
  • 代码可读性：相关逻辑保持内联，形成连贯的上下文语义流
  • 编译优化：最终生成的机器码与手动递归等效，但提供了更优雅的抽象层
• 正如 for 循环是 goto 和标签的优雅替代
• 这种树遍历结构也可视为递归范式的高阶语法糖
• 它在保持底层机制透明的同时，为开发者提供了声明式的遍历表达方式

  1
  2
  3
  for_tree(Node* N = mytreeroot; N != NULL; N : {N->left, N->right}){
    print(N->value);
  }
  

• 将编译成等效的：

  1
  2
  3
  4
  5
  6
  7
  8
  9
  void for_tree_internal(Node* N){
    print(N->value);
    for(Node* n2 : {N->left, N->right}){
        if(n2 != NULL){
            for_tree_internal(n2);
        }
    }
  }
  for_tree_internal(mytreeroot);
  

• 这个语法结构最终将编译为等效的递归函数代码
• 但关键区别在于：for_tree(...) 语法相比手动实现递归函数更为优雅简洁且不易出错
• 此外，for_tree 还会提供一些递归函数难以实现的优势：
• 例如：支持在循环体内直接使用 break、continue、return 等控制语句(行为与标准 for 循环一致)

  1
  2
  3
  4
  5
  6
  7
  for_tree(Node* N = mytreeroot; N != NULL; N : {N->left, N->right}){
    if(N->value == 10) {
        found = true;
        break; //break 语句将直接跳出整个 for_tree 代码块,
                       //在此过程中展开调用栈
    }
  }
  

• 这里还可以添加一个额外的流程结构，”prune(剪枝)”

  1
  2
  3
  4
  5
  for_tree(Node* N = mytreeroot; N != NULL; N : {N->left, N->right}){
    if(N->value == 10) {
        prune; //完全跳过该节点的所有子节点检查
    }
  }
  

• 这将阻止遍历当前节点的子分支

与范围循环对比

• 传统的基于范围的 for 循环要求：
  • 树结构必须实际存在于内存中
  • 必须预先为树结构定义迭代器
• 而 for_tree 的优势在于：
• 即使面对完全隐式的树结构
• 也无需定义任何迭代器或生成函数即可操作
• 例如：检查所有由”a”、”b”、”c”组成且长度不超过8的字符串：

  1
  2
  3
  for_tree(string x = ""; x.size() <= 8; x : {x+"a", x+"b", x+"c"}){
    print(x);
  }
  

• 这种操作虽然需要”类树状遍历”
• 但实际遍历的并非内存中真实存在的数据结构
• 通过for_tree可以完整实现该过程，它完全独立于任何底层数据结构(无论是否实际存在)
• 前文所述的”prune”控制流，也是基于范围的for循环无法实现的特性
• 这里存在一个隐患：
• 在上述字符串示例中，实际上会生成并拒绝所有长度为9的字符串
• 普通的for循环在退出前确实也会达到最后一个有效状态之后的状态
• 但对于线性for循环来说，这个问题并不严重(通常这只会产生一次额外的加法操作和条件检查)
• 然而在树遍历中，”再深入一层”意味着需要检查的末端节点数量将呈现指数级增长
• 可以通过多种方式手动解决这个问题：
• 若当前已处于叶子节点则生成空分支列表

  1
  2
  3
  4
  for_tree(string x = ""; x.size() <= 8; 
  x : x.size() < 8 ? {x+"a", x+"b", x+"c"} : {}){
    print(x);
  }
  

• 或在函数体内直接执行prune操作

  1
  2
  3
  4
  for_tree(string x = ""; x.size() <= 8; x : {x+"a", x+"b", x+"c"}){
    print(x);
    if(x.size() == 8) prune;
  }
  

关于遍历顺序的疑问

• “如果想进行广度优先遍历而非深度优先该怎么办？”
• 深度优先搜索(DFS)实现简单，内存消耗极小，完美契合现有的栈机制
• 而广度优先搜索(BFS)需要大量额外内存(通常需堆内存分配)，实现复杂度更高
• 理论上可以创建类似for_tree_breadth_first(...)的变体
• 但这样的复杂性可能超出”基础语法结构”的合理范畴

关于现有迭代器的疑问

• “多数编程语言已有定义好的树迭代器，为何不使用它们？”
• 树状关系在编程实践中无处不在，即使未显式声明为树结构
• 当我们拥有”MyTree”这类显式树时，当然可以使用forEach和迭代器遍历
• 但抽象出这种控制流的真正价值在于处理以下场景：
  • 隐式树结构：例如对象间存在多级引用关系(即使未被定义为Tree类)
  • 虚拟树结构：如动态生成的组合可能性(前文的字符串示例)
• 这类场景的遍历代码具有高度重复性
• 正是语法抽象的最佳候选方案

关于扩展正则表达式能力的思考

• 是否可以实现以下功能：
  • 正则表达式可解析流(类Perl5 IO::Async机制，现有实现可能欠优化)
  • 正则表达式可解析树结构(完全可行)?
• 事实上这正是Perl5中=~操作符(或其他语言对应API)作用于结构化数据的理念延伸
• 从实现角度观察
• 有限状态机(FSM)或其他自动机模型完全能够通过选择并穷举符合条件的分支路径来实现该功能
• 这种机制可应用于流式数据处理
• 某种程度上，Protobuf的编解码机制便具备类似特征
• 其本质上是一种宏观视角下的巴科斯范式(BNF)实现

多元视角

• 反对观点
• “完全可以通过库实现，无需内置于语言本身；树结构并非’特例’”
• 核心反驳
• 序列、树与图是编程的核心抽象范式，为何要将树/图强行扁平化为序列？
• 执行顺序论据
• 由于代码实际以串行方式执行，因此必然存在迭代顺序
• 即使逻辑上不关注顺序，迭代策略仍显著影响性能(例如：默认选用高效的深度优先迭代器)
• 并行性反驳
• 该论点不适用于并行计算场景
• SQL范例证明：通过声明式语法描述目标结果(如使用WITH RECURSIVE实现树遍历)，无须显式指定迭代顺序
• 文章提出的原语理念与SQL公用表表达式(CTE)具有相似的设计哲学

• Previous
  AI Agent的检验标准