(免责声明:我相当确定这在任何方面都不是惯用的。如果 OCaml 中有一些替代的树遍历惯用法,我洗耳恭听:))
我正在用 OCaml 编写一个玩具编译器,我希望有一个访问者来访问我的大型语法树类型。我使用类编写了一个,但我认为尝试使用模块/仿函数来实现一个会很有趣。我的类型层次结构很大,所以让我来说明一下我想要做什么。
考虑以下类型定义(现场制作):
type expr =
SNum of int
| SVarRef of string
| SAdd of expr * expr
| SDo of stmt list
and stmt =
SIf of expr * expr * expr
| SAssign of string * expr
让我简单说明一下用法。举例来说,我想收集程序内部的所有 SVarRef
。如果我有一个映射访问者(访问树的每个节点并且默认情况下不执行任何操作),我可以执行以下操作(在完美的世界中):
module VarCollector : (sig
include AST_VISITOR
val var_refs : (string list) ref
end) = struct
include MapVisitor
let var_refs = ref []
let s_var_ref (s : string) =
var_refs := s::!var_refs
SVarRef(s)
end
(* Where my_prog is a stmt type *)
let refs = begin
let _ = VarCollector.visit_stmt my_prog in
VarCollector.!var_refs
end
我应该注意到,为每个特定变体提供函数的优点是我的实际代码库具有一种类型,该类型既具有大量变体,又没有分段意义。特定于变体的函数可以避免对类型的其他变体进行重复迭代实现。
看起来很简单,但有一个问题:访问者有不同类型。 MapVisitor
返回原始语法树,因此它具有类型
sig
(** Dispatches to variant implementations *)
val visit_stmt : stmt -> stmt
val visit_expr : expr -> expr
(** Variant implementations *)
val s_num : int -> expr
val s_var_ref : string -> expr
val s_add : (expr * expr) -> expr
val s_do : stmt list -> expr
val s_if : (expr * expr * expr) -> stmt
val s_assign : (string * expr) -> stmt
end
同时,人们可能会想象一个折叠访问器,其中每个函数的返回类型都是某种t
。尝试尽可能地抽象这一点,这是我的尝试:
module type AST_DISPATCHER = sig
type expr_ret
type stmt_ret
val visit_expr : expr -> expr_ret
val visit_stmt : stmt -> stmt_ret
end
(** Concrete type designation goes in AST_VISITOR_IMPL *)
module type AST_VISITOR_IMPL = sig
type expr_ret
type stmt_ret
val s_num : int -> expr_ret
val s_var_ref : string -> expr_ret
val s_add : (expr * expr) -> expr_ret
val s_do : stmt list -> expr_ret
val s_if : (expr * expr * expr) -> stmt_ret
val s_assign : (string * expr) -> stmt_ret
end
module type AST_VISITOR = sig
include AST_VISITOR_IMPL
include AST_DISPATCHER with type expr_ret := expr_ret
and type stmt_ret := stmt_ret
end
(** Dispatcher Implementation *)
module AstDispatcherF(IM : AST_VISITOR_IMPL) : AST_DISPATCHER = struct
type expr_ret = IM.expr_ret
type stmt_ret = IM.stmt_ret
let visit_expr = function
| SNum(i) -> IM.s_num i
| SVarRef(s) -> IM.s_var_ref s
| SAdd(l,r) -> IM.s_add (l,r)
| SDo(sl) -> IM.s_do sl
let visit_stmt = function
| SIf(c,t,f) -> IM.s_if (c,t,f)
| SAssign(s,e) -> IM.s_assign (s,e)
end
module rec MapVisitor : AST_VISITOR = struct
type expr_ret = expr
type stmt_ret = stmt
module D : (AST_DISPATCHER with type expr_ret := expr_ret
and type stmt_ret := stmt_ret)
= AstDispatcherF(MapVisitor)
let visit_expr = D.visit_expr
let visit_stmt = D.visit_stmt
let s_num i = SNum i
let s_var_ref s = SVarRef s
let s_add (l,r) = SAdd(D.visit_expr l, D.visit_expr r)
let s_do sl = SDo(List.map D.visit_stmt sl)
let s_if (c,t,f) = SIf(D.visit_expr c, D.visit_expr t, D.visit_expr f)
let s_assign (s,e) = SAssign(s, D.visit_expr e)
end
但是,运行此命令会出现以下错误消息:
Error: Signature Mismatch:
Values do not match:
val visit_expr : expr -> expr_ret
is not included in
val visit_expr : expr -> expr_ret
我知道这意味着我没有正确表达类型之间的关系,但我无法弄清楚在这种情况下修复是什么。
最佳答案
免责声明:模块只是带有类型定义的值的记录。由于模块中没有类型,因此根本不需要使用它们,只需使用普通的旧记录类型,您将获得一种惯用的 AST 遍历模式。很快,您就会发现您需要开放递归,并将切换到基于类的方法。不管怎样,这是类被添加到 OCaml 的主要原因。您还可以将类包装到状态 monad 中,以将 AST 与任意用户数据折叠起来。
关于您的错误消息,那么很简单,您用签名隐藏了类型,这是一个常见的错误。最简单的解决方案是完全省略仿函数返回类型的注释,或者使用带有 type expr = expr 注释的 来传播类型相等性。
如果您需要更惯用方法的示例,那么您可以访问 ppx mappers 来获取记录。 ,这是一个example通过类实现的不同访问者,包括 those被包装到一个状态单子(monad)中。
关于module - 使用多态递归模块创建访问者模式,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35671647/