表达式问题：从Visitor到Typeclass与tagless final

Expression Problem中文一般叫「表达式问题」。我工作这些年见过太多代码库在两种扩展方向上来回摆动一种写法容易加新操作另一种写法容易加新类型两头都顺的写法却很少见。很多看起来优雅的设计模式在真正面对频繁需求变更时往往只解决了一半问题。这篇东西我不会只讲理论。我会把 Visitor、Typeclass、Trait、tagless final 这些方案串起来聊聊它们各自解决什么、留下什么尾巴以及在跨语言环境下怎么权衡性能和扩展性。适合正在设计核心模型、做库抽象或者因为“加个新类型要改所有函数”而头疼的开发者。1. 先从“困局”说起表达式问题到底是什么1.1 一个问题两个维度不妨想象你有一棵表达式树。节点类型可能是常量、加法、乘法。针对这棵树你会有求值、打印、求导这类操作。现在业务方提出了两种变更想新增一种节点类型比如“减法”。这就是在类型维度上扩展。想新增一种操作比如“求变量个数”。这就是在操作维度上扩展。如果把类型和操作放在一个矩阵里你会发现两个维度的扩展难度是相反的。在面向对象语言里你通常把操作定义成每个节点上的方法。想新增“减法”这个类型只要新增一个类并实现既有方法就行很轻松。但想新增一个“求变量个数”的操作你就得给所有已有节点类都加上这个方法改一堆文件破坏性不小。在函数式语言里你通常会定义一个代数数据类型然后写一批模式匹配函数。新增操作就是新写一个函数极其顺畅。但新增类型就需要改动所有旧函数里的匹配分支因为它们现在不穷尽了编译器会报错你还是得改一堆文件。两个维度总有一个是容易的另一个是痛苦的。这个问题非常基础所以很早就有了名字叫 Expression Problem意思是在表达式数据结构设计上我们能不能找到一种编码方式让类型和操作都能在不改动旧代码的前提下自由扩展。1.2 一个具体的表达式示例为了后面讨论不飘先给出一段最朴素的实现。这是函数式风格的 Rust 版本enum Expr { Lit(i64), Add(BoxExpr, BoxExpr), Mul(BoxExpr, BoxExpr), } fn eval(e: Expr) - i64 { match e { Expr::Lit(n) *n, Expr::Add(a, b) eval(a) eval(b), Expr::Mul(a, b) eval(a) * eval(b), } }这段代码干净、穷尽、编译器会帮你保证所有情况都处理到。你很快就能写出求导函数、打印函数每个都是新的match加操作非常舒服。但如果你想加一个Expr::Sub你就会发现eval必须改之前写的show、deriv也全要改。每加一种新节点所有既有操作都要再改一遍。如果你维护的是一个被外部 crate 依赖的库这个改动就是一种破坏性变更。再看面向对象风格的 Java 版本interface Expr { int eval(); } final class Lit implements Expr { final int value; // constructor... public int eval() { return value; } } final class Add implements Expr { final Expr left, right; // constructor... public int eval() { return left.eval() right.eval(); } }这个版本加新类型很容易直接新增一个实现类就行。但加操作很难你得改Expr接口再让所有实现类跟上。两种风格正好卡在两个极端上。表达问题要挑战的就是这两个极端之间的无人区。2. 经典解法的成与败Visitor 与双分派的代价2.1 Visitor 为什么能解一半面向对象社区很早就发现了这个问题并且给出了一个带有妥协意味的方案Visitor 模式中文叫访问者模式。Visitor 核心思想是双分派。普通虚函数分派一次动态地确定了接收者的类型。访问者模式再加一层节点对象接受一个访问者对象访问者对象再反过来调用节点对应的重载方法。通过两次动态分派把“节点类型”和“操作类型”同时作为分派依据。看一个简化但能说明问题的 C 例子struct Visitor; struct Expr { virtual ~Expr() default; virtual void accept(Visitor v) 0; }; struct Lit : Expr { int value; void accept(Visitor v) override; }; struct Add : Expr { Expr* left; Expr* right; void accept(Visitor v) override; }; struct Visitor { virtual void visit(Lit n) 0; virtual void visit(Add expr) 0; };每个新增操作就是继承Visitor实现一个新类比如Evaluator实现visit(Lit)和visit(Add)。你看新增操作不需要改任何既有节点类这很划算。这也是为什么很多 AST 工具、编译器前端都喜欢用 Visitor。但再仔细看问题也很明显Visitor基类里必须提前写好所有节点类型的visit方法。一旦你想加一个Sub类型不仅Sub类要实现accept你还要往Visitor基类里加一个visit(Sub)纯虚函数。这会波及所有已有的 Visitor 实现类。曾经写过的求值器、打印器全都得补上新的visit方法。所以 Visitor 的本质是把“新增操作”的难度转移到了“新增类型”上。它只解决了表达问题的一半而且是靠牺牲另一头的扩展性换来的。2.2 新类型加入何以尴尬有人可能觉得给Visitor基类加一个默认实现不就行了比如struct Visitor { virtual void visit(Lit n) 0; virtual void visit(Add expr) 0; virtual void visit(Sub expr) {} };这样已有 Visitor 实现类即使不改也不会编译失败。但你细想默认空实现意味着某个操作对Sub节点没有定义运行时只能静默跳过或者抛异常。对于求值这种操作遇到减法却不处理结果就是错的。默认实现只是把编译期错误延迟到了运行期。也有人会说在 Java 里可以用instanceof做类型判断或者用模式匹配。但这又回到了手写类型分派的道路既不穷尽也不安全。这种尴尬的本质是开闭原则指的方向和类型系统的能力发生了冲突。开闭原则说对扩展开放、对修改关闭但经典虚函数机制只在“类型维度”上开放没有给“操作维度”留下扩展点。2.3 设计模式融合的第一层开闭原则很多讲设计模式的书会把 Visitor、Strategy、Command 分开讲好像它们是互相无关的套路。但从表达问题这个视角往回看你会发现它们其实都在解决同一件事怎么把变化点抽象成一个可插拔的扩展面。Strategy 模式是把“算法”抽成一个对象替换算法时不改上下文。Visitor 是把“对数据结构的操作”抽成一个对象增加操作时不动数据结构。两者的核心都是依赖注入只不过注入的粒度不同。我自己喜欢把表达问题当成设计模式的一个“统一场论”打散成 OOP 术语就是接口加组合打散成函数式术语就是 ADT 加高阶函数打散成现代语言术语就是类型类或 Trait。理解这条主线之后你再看任何模式都会自动思考一个问题它在哪个维度上开放又在哪个维度上封闭这比背模式目录有用得多。3. 现代语言的合流Typeclass、Trait 与 tagless final3.1 Haskell 的 Typeclass把操作变成接口约束如果你两种扩展都想要一个比较扎实的方向是把“操作”定义成接口约束而不是把操作硬塞进数据结构里。Haskell 的TypeclassRust 的TraitScala 的Typeclass本质都是这个思路。先看 Haskell 风格。我们不把Expr定义成一个封闭的 ADT而是把每种节点当成独立的类型然后定义一个Eval类型类凡是可以求值的类型都实现它class Eval a where eval :: a - Int data Lit Lit Int instance Eval Lit where eval (Lit n) n data Add a b Add a b instance (Eval a, Eval b) Eval (Add a b) where eval (Add a b) eval a eval b data Mul a b Mul a b instance (Eval a, Eval b) Eval (Mul a b) where eval (Mul a b) eval a * eval b现在想新增一个操作比如showExpr你只需要再定义一个新的类型类ShowExpr并给每种节点补一个实例class ShowExpr a where showExpr :: a - String instance ShowExpr Lit where showExpr (Lit n) show n instance (ShowExpr a, ShowExpr b) ShowExpr (Add a b) where showExpr (Add a b) ( showExpr a showExpr b )想新增一个类型比如Sub a b你同时给它补Eval和ShowExpr的实例。旧代码完全不用动data Sub a b Sub a b instance (Eval a, Eval b) Eval (Sub a b) where eval (Sub a b) eval a - eval b instance (ShowExpr a, ShowExpr b) ShowExpr (Sub a b) where showExpr (Sub a b) ( showExpr a - showExpr b )这种写法在函数式编程圈子里有个名字tagless final意思是“没有标签的最终编码”。传统Expr枚举里的每个构造器相当于一个显式标签运行时需要打 tag 做模式匹配而 tagless final 里节点类型就是结构本身没有统一 tag每个解释器各取所需。3.2 Rust 的 Trait 与孤儿规则Rust 没有严格意义的 Haskell Typeclass但 Trait 基本给出了同样的能力。上面 Haskell 的写法可以直接翻译成 Rusttrait Eval { fn eval(self) - i64; } struct Lit(i64); impl Eval for Lit { fn eval(self) - i64 { self.0 } } struct AddL, R { l: L, r: R } implL: Eval, R: Eval Eval for AddL, R { fn eval(self) - i64 { self.l.eval() self.r.eval() } }加操作就是再定义一个 Traittrait Show { fn show(self) - String; } impl Show for Lit { fn show(self) - String { self.0.to_string() } } implL: Show, R: Show Show for AddL, R { fn show(self) - String { format!(({} {}), self.l.show(), self.r.show()) } }加类型就是补实现。两种扩展都能做到不改旧代码。这就是我工作中最常用的“可扩展设计”起点。但 Rust 有一条很关键的约束孤儿规则Orphan Rule。它规定你只能为本地类型实现外部 Trait或者为外部类型实现本地 Trait不能同时跨越两个 crate 的所有权。这条规则限制了你在下游代码里凭空为别人的类型补充实例。举个例子你想为自己的ShowTrait 实现第三方库里某个DateTime类型这是允许的因为Show是你的本地 Trait。但如果你想实现标准库的Display给第三方库的DateTime补输出格式就不行。反过来若第三方库的类型和第三方的Serialize你都想用就只能在本地包一个 newtype 再去实现。这个包壳成本会影响一层抽象但从工程角度看它换来的是实例的一致性防止了隐式冲突。设计库边界时一定要搞清楚这条规则否则下游用户会很难受。3.3 跨语言方案演进对照不同语言社区在应对表达问题时演化出了各种风格。用一个表格来对照可能比长篇大论更清楚语言传统风格扩展方向表达问题解法Java / C接口 / 虚函数新类型容易新操作困难Visitor 作为补救Haskell / OCamlADT 模式匹配新操作容易新类型困难Typeclass、tagless finalScalacase class 模式匹配偏向函数式TypeclassScala 3 的 given 更轻量Rustenum match 或 trait 泛型两种都能写推荐 trait 泛型注意孤儿规则Gointerface type switch介于两者之间偏 OOP动态注册机制补足Pythonduck typing两者都灵活动态分发 注册表但安全性弱我从这个表格里得到的体会是语言不决定你能不能解决表达问题语言决定的是你能付出多少代价解决它。动态语言靠运行时灵活性什么问题都能解但问题都挪到了运行时静态语言里Rust 和 Haskell 这类拥有高阶类型能力和强大编译期检査的语言更接近问题的最终答案。4. 性能权衡vtable、单态化与数据布局4.1 四种编码的性能模型扩展性和性能往往是拉扯的。不少人问过我用 Trait 泛型写了一大堆嵌套类型会不会比直接匹配枚举慢这里要分清楚几种不同的运行时开销。第一种是 Rust 里enum match。这是最贴近“免费”的写法。枚举值就是带 tag 的内存布局match编译出来通常是一次 tag 比较加若干分支跳转热点情况下编译器还会自动做内联。数据就在栈上或者直接内嵌在容器里缓存非常友好。坏处是类型集合封闭一旦外部想要扩展新类型这条路走不通。第二种是泛型单态化Rust 的impl Trait for ConcreteType在编译后会生成具体的代码。AddLit, Lit、AddLit, MulLit, Lit各自有独立的机器码没有虚函数调用绝大多数情况下也可以内联。代价是代码膨胀如果组合很多二进制体积会涨。指令缓存压力可能变大有时反而比动态分派慢。所以单态化不是绝对快它只是统计意义上通常更快。第三种是 Trait Object即dyn Eval或者Boxdyn Eval。这是一个胖指针一份数据指针加一份虚表指针一共 16 字节。每次调用eval()都要走一次虚表间接跳转数据又通常被推到堆上缓存友好度下降。好处是类型集合完全开放而且同一个调用点可以处理所有实现了Eval的类型代码体积小。这与 Java 接口、C 虚函数是同一个模型。第四种是 Haskell 那种 Typeclass 字典传递。eval的每个实例本质上是把一组函数打包成一个字典运行时额外传递这个字典。Haskell 编译器优化好时能把字典内联掉但复杂情况下字典传递和间接调用依然存在。它的性能特征更接近一种“能内联但未必内联”的动态分发。把这些放在一起性能从好到差大致的排序是单态化泛型、枚举匹配、Typeclass 字典、Trait Object 动态分发。但这只是“大概率排序”具体项目里要打问号。4.2 热点代码怎么选我处理过的几个项目里最容易被性能歧视的其实是 Visitor 模式。访问者要做到双重分派相当于一次操作里发生了两次虚函数调用再加上业务逻辑本身开销比直接的match高出不少。如果这个操作在循环里跑了几百万次差异立刻能观察到。所以我的建议是先画一条线核心热点路径、类型集合稳定时优先enum match或者 Rust 泛型 trait。不要为了所谓的“未来可扩展”给自己上性能包袱。库的公共 API、需要外部插件扩展、调用频率不高的地方用 Trait Object、动态注册或 Typeclass 都可以。如果你写的是一个 AST解析热路径上用enum做节点在边界处用 Visitor 暴露给外部插件两个方案并不矛盾。也就是说不要对一种技术产生宗教式崇拜。数据处理上空指针问题也要注意。Boxdyn Expr把对象放在堆上只留下一个指针处理Lit这种 8 字节的小对象也要额外一次内存访问。而泛型版本里Lit可以直接嵌在AddLit, Lit结构体里连续内存碰两次性能差很多。还有一点dyn Trait不允许按值传递必须通过引用或智能指针这也会限制你可用的内存布局优化。4.3 测量优先说句大实话很多性能上的直觉都是错的。现代编译器非常聪明一个看似低效的 Typeclass 调用可能被内联成完全静态的代码一个看似高效的泛型写法也可能因为代码膨胀导致指令缓存不命中。我建议在选型时真的跑一下基准测试。Rust 有 criterionHaskell 有 criterionJava 有 JMH。先写出两种候选实现用代表性数据跑一轮再决定走哪条路。我在一个模拟项目里就把 tagless final 的表达式树跑过一轮结果单调的eval热点路径上它和enum match几乎持平因为泛型被完全单态化了但换成长递归的打印操作单态化版本代码膨胀导致速度还慢了一点。测量结果和离线推演完全不同。简单总结性能权衡不是“扩展性成品质”的权衡而是“实现路径的权衡”。让你难受的往往是不该抽象的地方过度抽象而不是抽象本身。5. 实战选型与避坑建议5.1 一个决策清单这几年的实践里我慢慢形成了一套选型决策清单。每次设计一个会被多人扩展的核心模型我都会过一遍。第一问未来更可能加新类型还是加新操作如果拿不准问需求方最近三个迭代里发生了什么。频繁加类型的业务适合接口加实现的 OOP 路线频繁加操作的业务适合枚举加模式匹配的路线。第二问这个模型是库的内部实现还是对外暴露的公共 API内部实现完全可以用封闭枚举外部用户不该看到你的所有节点也就无所谓开放扩展。公共 API 才需要认真考虑扩展点。第三问第三方使用者会不会想为这个类型添加不属于你控制的实现如果会请提前设计好 Trait 边界并把孤儿规则的后果想清楚。第四问性能要求是否明确如果没有压测数据支持“这里必须最快”先写可扩展性更好的版本让性能问题等到有真实数据再解决。这四问看起来简单但我见过太多项目从一开始就把方向定死在某个风格上。比如一个内部小工具非得上完整插件化架构结果所有节点都变成了Boxdyn Trait开发复杂度和运行开销都上去了收益却约等于零。选型要有止损线。5.2 避坑实录第一坑给枚举加新变体导致所有match报错就以为是编译器找麻烦。其实这是编译期穷尽检查在保护你。遇到这个情况先判断新类型是不是“领域内”的概念。如果是直接改全部match分支是正确的因为“新类型加入就修改相关函数”本来就应该是显式变更。如果不是比如新类型来自某个插件生态那就说明你的核心模型选错了应该从开始就用 Trait 风格开放操作。第二坑为了实现完全开放把所有节点定义成独立类型并让它们互相嵌套。这个写法会让类型签名变得很长比如AddLit, MulAddLit, Lit, Lit。更麻烦的是后续加一个“统一重命名”之类的全局转换操作时你要在 Trait 里返回Self还是别的类型很受折磨。更实用的方式是用类型别名简化type SimpleExpr AddLit, MulLit, Lit;这样日常使用里的签名不至于失控。同时把“结构递归”和“操作递归”分开。结构递归交给数据类型完成操作递归集中写好基例不要让业务代码到处展开结构。第三坑Visitor 基类新增纯虚函数导致所有实现类需要同步修改。如果你在一个中期项目里被迫往基类加方法这通常表明类型集合并不封闭Visitor 可能一开始就是错误的选择。止损方法是给新方法提供带默认行为的实现但你要明确这种默认行为的语义否则运行期出错更难查。第四坑过度相信动态语言。Python 的singledispatch、注册表、装饰器确实能拜拜解决扩展问题from functools import singledispatch singledispatch def eval_expr(expr): raise TypeError(funsupported: {type(expr)}) eval_expr.register def _eval_lit(expr: Lit): return expr.value但动态方案的约束全靠约定。别人少写一个register函数错误只在运行期浮现。如果你愿意付出这种代价没问题但如果你在做一个团队共享的 SDK其实你会需要类似 Rust Trait 那样的编译期约定。5.3 设计一个“两条腿走路”的库边界最后给一个我比较常用的模板。核心场景是我想在内部享受enum match的穷尽性与性能但依然让外部用户能够扩展。做法是把内部封闭模型和外部开放模型用一层薄薄的适配层隔开。内部定义封闭枚举enum CoreExpr { Lit(i64), Add(BoxCoreExpr, BoxCoreExpr), }对外定义开放 Traittrait ExprOp { fn eval_core(self, core: CoreExpr) - i64; fn eval_external(self, external: dyn ExternalExpr) - i64; }内部函数走match外部扩展通过 Trait Object 注入。这样做必然有一点性能损耗但损耗被限制在适配边界上核心热点依然是封闭枚举。这有点像把一个系统的内核做成微内核把可插拔能力限制在明文的接口处。6. 一些更深的思考模式融合和语言演进6.1 从“模式融合”看 Visitor 与 Typeclass 的共同点把 Visitor 和 Typeclass 摆在一起看会发现它们的内核是惊人的相似。Visitor 是“操作对象化”Typeclass 是“操作约束化”它们都在把“操作”这个维度从数据主体中抽出来。区别在于 Visitor 依赖运行期虚表Typeclass 依赖编译期实例解析。这就回答了一个初学者常问的问题如果我学设计模式还要不要学 Typeclass我的答案是不要把它们当成两门知识。它们是在不同类型系统强度下对同一个表达问题的两种近似解法。理解了问题的内核你就有了一种翻译能力。Java 里的 Visitor 思路可以平移到 Rust TraitRust Trait 的思路也可以反向平移到 Java 的接口加泛型约束。真正值钱的不是某个模式的类图而是你能在不同语言之间移植那种扩展性思维。6.2 跨语言方案演进的主线把视线拉长一点跨语言方案的演进其实有一条主线从运行期多态走向编译期多态。C 的虚函数、Java 的接口方法是动态分派的Haskell 的 Typeclass 把分派信息打包成字典在编译期决议Rust 的 Trait 更进一步倾向于单态化和静态派发同时保留dyn作为显式逃逸口。Rust 的特别之处在于它把“哪种扩展模型”的选择权交给开发者而不是由语言替你决定。enum与match是函数式路线trait与dyn是对象式路线两种路线可以共存于同一份代码里这种混合能力在主流静态语言里是很少见的。Go 的接口更像是结构类型与动态派发的结合比 Java 轻但比 Rust 静态Python 的动态分派让很多扩展问题消失于无形却把安全责任全部还给开发者。每个语言都在表达问题上交出了自己的答案有的靠类型系统有的靠运行时灵活性。6.3 我个人的一点体会如果让我总结一个最重要的实操心得那就是永远不要把一个封闭模型当成永久开放来设计也不要为了未来牺牲当下的清晰度。封闭有封闭的清楚开放有开放的复杂。enum match的好处是穷尽、直接、可读trait 泛型的好处是开放、可扩展、可插拔。两者各有价格。真正的高手并不是永远选择开放那一边而是能看出来未来两年内这个模型到底会不会真的长出新的分支。判错没关系重要的是预留出“从封闭迁移到开放”的路径。比如用 Rust 时先把核心枚举和数据操作分文件放将来真要开放时把操作挪到 Trait 实现里改动面会小很多。如果说还有什么建议那就是多去看不同语言社区对这个问题的讨论。Haskell 的 tagless final 文章、Rust 的 trait 设计讨论、Java 的 Visitor 演进历史其实都在讲同一个故事。把这些故事串起来看你才会明白一个数据结构设计得好不好不在于它今天有多优雅而在于明天需求变化时你还能不能优雅。