2
（聲明：我相當肯定，這是不以任何方式慣用如果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
我知道這意味着我沒有表達的關係正確的類型之間，但我無法弄清楚這種情況下的修復程序。