OCaml访客模式

Question

我在OCaml中实现了一个简单的类C语言,并且像往常一样,AST是我的中间代码表示.由于我将在树上进行一些遍历,我想实现访问者模式以减轻痛苦.我的AST目前遵循该语言的语义:

type expr = Plus of string*expr*expr | Int of int | ...
type command = While of boolexpr*block | Assign of ...
type block = Commands of command list
...

现在的问题是树中的节点是不同类型的.理想情况下,我会将一个处理节点的函数传递给访问过程; 该过程将打开节点的类型并相应地进行工作.现在,我必须为每个节点类型传递一个函数,这似乎不是最佳解决方案.

在我看来,我可以(1)真正采用这种方法或(2)上面只有一种类型.通常的方法是什么？也许用OO？

Answer 1

没有人在函数式语言中使用访问者模式 - 这是一件好事.通过模式匹配,您可以更方便,更直接地使用(相互)递归函数来实现相同的逻辑.

例如,假设您想为AST编写一个简单的解释器:

let rec run_expr = function
  | Plus(_, e1, e2) -> run_expr e1 + run_expr e2
  | Int(i) -> i
  | ...

and run_command = function
  | While(e, b) as c -> if run_expr e <> 0 then (run_block b; run_command c)
  | Assign ...

and run_block = function
  | Commands(cs) = List.iter run_command cs

访问者模式通常只会使这种情况复杂化,特别是当结果类型是异构时,就像这里一样.

Answer 2

如果您必须在一组相互递归的数据类型（例如 AST）上编写许多不同的递归操作，那么您可以使用开放递归（以类的形式）对遍历进行编码并节省一些样板代码。

Real World OCaml中有一个此类访问者类的示例。

Answer 3

确实可以定义一个类,每种类型的AST都有一个访问方法(默认情况下不执行任何操作),并且您的访问函数将此类的实例作为参数.事实上,这种机制在OCaml世界中使用,尽管不常见.

特别是,CIL库有一个访问者类(参见https://github.com/kerneis/cil/blob/develop/src/cil.mli#L1816).请注意,CIL的访问者本质上是必要的(转换是在适当的位置完成的).然而,完全可以定义将AST映射到另一个的访问者,例如Frama-C,它基于CIL并提供就地和复制访问者.最后,Cαml是一个AST生成器,它可以轻松处理绑定变量,生成映射并将访问者与数据类型一起折叠.