一句话:提出 OCaml 的 Visitors 类型导向生成器与 alphaLib 库,使含名字绑定的 AST 遍历与变换可组合、可定制且模块化。
在 OCaml 中正确、简洁、模块化且可定制地遍历和变换含名字绑定的抽象语法树十分困难。论文把访问者类视为对 AST 操作的可组合局部描述,提出类型导向工具 Visitors,可自动生成不感知绑定结构的访问者类;同时给出 alphaLib,一个由手写小型访问者类组成的库,每个类封装特定绑定构造、名字表示或 AST 操作。通过组合这些组件,可定义广泛操作,支持多种名字表示及其转换,并允许以编程风格编写访问者方法或以声明式绑定组合子描述绑定结构。该工作表明 Visitor 与绑定关注点可分离,从而提升 AST 处理的复用性与模块化。
Traversing and transforming abstract syntax trees that involve name binding is notoriously difficult to do in a correct, concise, modular, customizable manner. We address this problem in the setting of OCaml, a functional programming language equipped with powerful object-oriented features. We use visitor classes as partial, composable descriptions of the operations that we wish to perform on abstract syntax trees. We introduce "visitors", a simple type-directed facility for generating visitor classes that have no knowledge of binding. Separately, we present "alphaLib", a library of small hand-written visitor classes, each of which knows about a specific binding construct, a specific representation of names, and/or a specific operation on abstract syntax trees. By combining these components, a wide range of operations can be defined. Multiple representations of names can be supported, as well as conversions between representations. Binding structure can be described either in a programmatic style, by writing visitor methods, or in a declarative style, via preprogrammed binding combinators.