一句话：提出部分求值优化技术，打破递归 rank-2 多态函数无法进行类字典特化的僵局，并在 GHC 插件中实现显著加速。
在 Haskell 中，rank-2 多态与类型类约束结合可实现强大抽象与代码复用，但 GHC 的类字典特化与内联优化在遇到递归的 rank-2 多态函数时会失效：特化多态参数需要内联被应用函数以暴露类型与字典应用，而启发式内联器不愿内联递归函数以避免编译不终止。该僵局导致 SYB、SYB3 以及 lens 库的部分实现无法被优化，带来运行时开销。本文提出一种新的优化技术，引入部分求值器，对“部分静态”的 rank-2 多态函数应用策略性地执行内联、β-归约与记忆化，从而暴露多态参数在具体类型和字典上的应用，供标准编译器优化流水线特化；同时提出 type-constant folding，将运行时类型相等测试静态求值。该技术实现为 GHC 插件，在 SYB 与 SYB3 遍历上平均加速 43×（最高 155×）和 6.1×（最高 9.5×），在 lens 库相关片段上平均加速 1.6×（最高 2.1×），达到手写版本性能。
Rank-2 polymorphism, when combined with type-class-constrained arguments, enables powerful abstractions and code reuse by allowing functions to accept arguments that are themselves ad-hoc polymorphic. Optimizing compilers like the Glasgow Haskell Compiler (GHC) use techniques like class-dictionary specialization and inlining for optimization. However, these techniques can falter when the rank-2 polymorphic functions are recursive. Specializing the polymorphic arguments of recursive rank-2 polymorphic function applications requires inlining the applied function to expose type and dictionary applications to the arguments, but the compiler’s heuristic-driven inliner is reluctant to inline recursive functions, risking non-termination during compilation. This stalemate causes recursive rank-2 polymorphic functions to remain un-optimized and be left with a runtime penalty. Within the Haskell ecosystem, we identify this stalemate within three widely used libraries: the Scrap Your Boilerplate (SYB) and SYB With Class (SYB3) generic-programming libraries, and a fragment of the lens optics library. In these libraries, the combination of rank-2 polymorphism, type-class constraints and recursion is central to their implementation. In this paper, we present a new optimization technique that breaks this stalemate and enables class-dictionary specialization with recursive rank-2 polymorphic functions. We introduce a partial evaluator that strategically applies the standard transformations of inlining, β -reduction and memoization to applications of rank-2 polymorphic functions that are partially static , i.e., whose arguments have some information known statically. This process exposes applications of its polymorphic arguments onto concrete types and dictionaries, which can be specialized by the standard compiler optimization pipeline. Additionally, we introduce type-constant folding to evaluate run-time type-equality tests statically, further leveraging static type information gained from partial evaluation. We implement our technique as a GHC plugin and demonstrate its effectiveness by resolving the performance bottlenecks in the aforementioned Haskell libraries. On SYB and SYB3 traversals, our technique achieves speedups of 43× on average (up to 155×) and 6.1× on average (up to 9.5×), respectively, matching the performance of their hand-written counterparts. On the fragment of the lens library containing the identified slowdowns, our technique achieves speedups of 1.6× on average (up to 2.1×).
@article{paperbot3813,
title = {Class-Dictionary Specialization with Rank-2 Polymorphic Functions},
author = {Yong Qi Foo and Michael D. Adams},
journal = {Proceedings of the ACM on Programming Languages},
volume = {10},
number = {OOPSLA1},
year = {2026},
doi = {10.1145/3798227}
}