OCaml visitor pattern

Question

I am implementing a simple C-like language in OCaml and, as usual, AST is my intermediate code representation. As I will be doing quite some traversals on the tree, I wanted to implement a visitor pattern to ease the pain. My AST currently follows the semantics of the language:

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

The problem is now that nodes in a tree are of different type. Ideally, I would pass to the visiting procedure a single function handling a node; the procedure would switch on type of the node and do the work accordingly. Now, I have to pass a function for each node type, which does not seem like a best solution.

It seems to me that I can (1) really go with this approach or (2) have just a single type above. What is the usual way to approach this? Maybe use OO?

Answer 1

Nobody uses the visitor pattern in functional languages -- and that's a good thing. With pattern matching, you can fortunately implement the same logic much more easily and directly just using (mutually) recursive functions.

For example, assume you wanted to write a simple interpreter for your 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

The visitor pattern will typically only complicate this, especially when the result types are heterogeneous, like here.