在函数式编程与语言实现领域,表达式的抽象和解释器的设计是一个常见且富有挑战的话题。对 Haskell 开发者而言,GADTs 与和类型(sum-types)长期成为实现带类型信息的抽象语法树(AST)和解释器的首选工具。但当刻意避免使用这些特性,或者在受限的编码环境下,仍然可以用多种替代方案实现相同的功能。本文围绕"极致无分支"的思路展开,讨论几种不用 GADTs 或和类型实现 Expr 的路线:Church 编码、记录式产品类型、以及通过类型类与类型族完成的编码。比较它们的可读性、扩展性、类型安全性与实现复杂度,并给出实践建议与替代方案。关键词包括 Haskell、GADTs、sum-types、Church encoding、tagless final、类型族、UndecidableInstances、Identity、Const、记录类型、惰性求值、DSL 设计等。
先从一个典型问题陈述开始:我们想要定义一个简单的表达式语言,包含整型常量、加法以及相等比较,最终既可以求值也可以得到可读的打印表示。使用 GADTs 或普通代数数据类型可以很直观地表示这些节点,但如果我们不想使用和类型或者 GADT,能否仍然实现类似的功能并保持类型安全?接下来依次展示几种思路,说明各自的权衡。 Church 编码是一种将代数数据类型替换为高阶函数的技术。在表达式上下文中,可以把每个表达式看成一个接受处理函数集的封装,该处理函数集定义了对每种构造的处理方式。一个典型的 Church 编码实现会把表达式包装成一个多态的函数,运行时传入不同的分支处理器即可得到不同语义,例如求值或打印。优点在于不需要额外语言扩展,结构上紧凑,并且非常灵活:通过传入不同的处理器可以得到多种解释器。
缺点是编码可读性较差,类型签名往往复杂难懂,调试成本上升,并且在需要拓展新构造时要变动调用约定或处理器集合。 另一条更"主流"的无和类型路径是使用记录式的产品类型来嵌入多种操作实现。以一个小例子说明,定义一个通用的表达式闭包 FExpr,包含两个域:一个用于运行时语义的 feval,另一个用于格式化输出的 fprint。类型如下的结构能够把求值与打印同时封装在值里: data FExpr a = FExpr { feval :: a, fprint :: String } 然后按照需要分别提供构造器和组合器,例如构造常量的 fval,构造加法的 fadd,构造相等比较的 feq。每个组合器负责从子表达式继承前两个字段,并在此基础上构造新的 feval 与 fprint。这个方案的可读性远优于 Church 编码;实现简单直观;利用 Haskell 的惰性特性,只有真正需要某个语义时才会触发对应字段求值。
因此实现多个语义(解释、优化、代码生成、日志)变得很容易:只要在记录里添加域即可。 使用记录式产品类型的显著优势是扩展表达式节点变得廉价。新增一种表达式构造只需新增一个构造器函数即可,现有值与组合器无需改动。缺点则是增加新语义代价高:如果后来想在所有表达式上新增一个新的解释器或分析结果,就需要在记录中加入新的字段,并为已有所有构造器补全新字段,这在大型 DSL 中会带来维护负担。此外,若语义之间存在相互依赖或需要特定类型级别约束时,记录方式的静态类型表达能力不如 GADT 或标签擦除技术精确。 在一些尝试将记录式方法与类型类整合的做法中,开发者希望既保留开放式的构造扩展能力,又能在类型层面表达不同构造的输出类型。
把表达式节点写成参数化的高阶类型构造,例如类型构造器 f :: Type -> Type,是一种思路。例如定义 SVal、SAdd、SEq 等数据类型并声明一个类型类 SExpr,期望为任何 f 实现 seval 与 sprint。然而直接写出 seval :: f a -> a 会遇到明显的问题:当某种构造固定了结果类型(例如加法一定产生 Int),而类型签名又要求一个通用的 a,编译器无法在实例中知道 a 应该是什么,从而报类型不匹配的错误。 为了解决这个类型连接问题,可以引入类型族 Out f 来表示每种表达式构造在给定参数下的输出类型。即把 SExpr 写成一个关联类型类,使得 seval 返回 Out f a 而不是 a。在实践中,经常结合 Identity 与 Const 等现成的代数包装器来统一不同结构的输出表示。
Identity 表示伴随具体类型的输出(保持多态),Const 表示输出类型被固定为某个常量类型(例如加法输出 Int,比较输出 Bool)。但是直接返回这些包装器会导致后续使用不够方便,因此又引入 Extractable 这样的辅助类型类,提供一个 extract 函数把包装器解包成纯值。最终,为了让实例推导成立,往往需要很多类型级约束与等式,以及启用 UndecidableInstances 这类扩展来打破 GHC 的实例终止检查。这一整套方案可以在类型层面表达出类似 GADT 的强类型信息,但代价是大量模板化样板代码、复杂的类型族约束与可读性下降。 这一系列实现的权衡值得仔细比较。Church 编码的优点是极简的语言扩展需求与统一的运行时表示,适合对语言扩展少且追求极致抽象的场景。
记录式产品类型则能带来更好的工程可读性与即时可用性,尤其适用于需要多个并行语义(如求值、打印、调试信息、静态分析)且构造数量比语义数量更多的场合。通过类型族与复杂类型类恢复 GADT 风格的类型精确性是可能的,但需要付出可维护性与类型系统复杂度的代价,适合对类型安全有严格要求且团队能接受复杂类型级编程的项目。 从性能角度考虑,这几种实现也有不同体现。Church 编码在某些情形下能够被 GHC 优化为内联函数,从而消除部分抽象开销;但非显式的结构信息有时会阻碍某些静态分析或优化。记录式产品类型由于包含多个字段,可能会引入额外的惰性 thunk 和内存占用,特别是在字段中包含复杂闭包时,需要关注共享与求值策略。类型族与包装器方法如果引入大量 Const/Identity 包装与 extract 调用,也会带来包装拆卸的运行时支出,但这些通常可以通过内联与优化消除。
总体来说,若表达式和解释器十分敏感于性能,应当结合基准测试并观察 GHC 的 Core 输出来决定最终方案。 在实践中如何选择?若项目允许使用 GADTs 与和类型,并且表达式语言的类型结构较为复杂,优先考虑 GADT 或 finally tagless(也即标签消失的方法)。GADTs 直接而可读,支持在类型层面表达精确的约束。finally tagless(又称为抽象语法的代数接口)通过类型类接口定义构造器并为不同解释器实现这些接口,天然支持可扩展的解释器而不会暴露底层数据结构。标签消失方法在需要开放式扩展解释器行为时表现优异。 若因为某些限制(例如教学场景、库依赖限制或对语言扩展的兼容性要求)不能使用 GADTs 或和类型,记录式产品类型是一个非常实用的替代方案。
它允许快速构建具有多语义支持的表达式集合,代码可读性友好,可在代码重构与调试阶段降低认知成本。使用记录式方案时,建议在设计初期就考虑字段的命名与语义分割,尽量避免日后大量添加新字段的需要。如果新增语义仍然频繁发生,考虑把记录分解为多个可组合的层次,每一层代表一类语义,或者采用混合方案:核心表达式使用和类型或 GADT,外部解释器则使用记录式包装以便并行语义扩展。 当需要既要开放式扩展表达式节点,又要在类型层面把控输出类型时,类型族与 Extractable 的组合确实可以做到类似 GADT 的精确性。但应谨慎对待带来的复杂度。明确注释每个实例所依赖的类型族等式,保持代码模块化,并为未来维护者写清楚为何采用 UndecidableInstances 等扩展,是减少隐患的关键。
另外还有一些值得考虑的替代方案。数据类型即类(data types à la carte)提供了模块化的和类型扩展机制,通过构造可组合的 Functor 并使用 Fix 来重建 AST,可以在添加新构造时避免修改既有代码。多态变体与行类型(row types)可以更自然地支持开放式记录与变体,但需要语言扩展或编译器支持。Free monads 也常用于把语法树与解释器分离,便于多种解释器和组合优化。最后,不要忽视工程层面的工具:模板 Haskell、代码生成或简单的模板化库经常能把大量重复样板代码自动化,从而把复杂类型编码的痛苦降到可控范围。 总结性的建议如下。
优先选择简单可读的实现:如果可以使用 GADTs 或和类型,就用它们来表达带类型信息的 AST;如果希望在不改变表达式定义的前提下添加多种解释器,考虑 finally tagless。若受限不能使用这些特性,记录式产品类型是快速且实用的替代方案,适合在工程中迅速落地。仅在确有必要且团队能够维护类型级复杂性的前提下,才用类型族、Extractable 与 UndecidableInstances 来重建 GADT 式的精确性。 在实际工程中,建议编写清晰的抽象接口文档与示例代码,保持每种实现的基准测试与内存分析,关注 GHC 的优化建议与 Core 输出。通过小规模原型验证可维护性与性能,再在核心代码库中选择最合适的方案。最后,表达式设计不仅仅是类型技巧的竞技场,更关乎长期可维护性、团队熟悉程度和调试可行性。
合理权衡这些因素,才能在不同约束下选择出最合适的极致无分支实现方式。 。
