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?

Zabrina

Can you specify the type that you want your function to have? – Danelaw

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.

Alansen

+1 One minor logistic advantage of visitor over this implementation (that I would still choose) is the fact that it offers a common interface for all the visit operations. – Irtysh

@Mau, yes, but I'm not sure what that would buy you, though. That interface is both underspecified (fully generic types that don't tell anything) and overspecified (visit methods for all cases, even if you don't need all of them in many circumstances). More importantly, what kind of generic abstraction would one want to build over all possible visitors? – Alansen

Thanks for the answer. I know that pattern matching gives me this ability. So, in essence, it is easier to write tree traversal all over again each time I need it for some functionality, rather than implementing a visitor pattern. – Zabrina

@bellpeace, yes, the amusing thing is that the code repetition in writing the tree traversal "all over again" is substantially less than the repetitive boilerplate necessary for every visitor. In any case, if you want to abstract away the traversal then just write morphisms over your trees (map, fold, and friends) -- they arguably are the functional counterpart to visitors. – Alansen

Yeah, it is kind of hard to write morphisms when your nodes are of different type. Current idea I have now is to use functors. Basically, I would wrap traversal in a functor, which expects a module that implements preVisit and postVisit functions for each node. Of course, this module would need to follow a certain interface. – Zabrina

@bellpeace, a functor like that should be possible, but I still don't understand what benefit you want to get out of this. Wouldn't using it be 3 times more complicated and verbose than a direct formulation? – Alansen

Answer 2

If you have to write many different recursive operations over a set of mutually recursive datatypes (such as an AST) then you can use open recursion (in the form of classes) to encode the traversal and save yourself some boiler plate.

There is an example of such a visitor class in Real World OCaml.

Stake

Answer 3

It is indeed possible to define a class with one visiting method per type of the AST (which by default does nothing) and have your visiting functions taking an instance of this class as a parameter. In fact, such a mechanism is used in the OCaml world, albeit not that often.

In particular, the CIL library has a visitor class (see https://github.com/kerneis/cil/blob/develop/src/cil.mli#L1816 for the interface). Note that CIL's visitors are inherently imperative (transformations are done in place). It is however perfectly possible to define visitors that maps an AST into another one, such as in Frama-C, which is based on CIL and offer in-place and copy visitor. Finally Cαml, an AST generator meant to easily take care of bound variables, generate map and fold visitors together with the datatypes.

Diagnostician

Answer 4

The Visitor pattern (and all pattern related to reusable software) has to do with reusability in an inclusion polymorphism context (subtypes and inheritance). Composite explains a solution in which you can add a new subtype to an existing one without modifying the latter one code. Visitor explains a solution in which you can add a new function to an existing type (and to all of its subtypes) without modifying the type code. These solutions belong to object-oriented programming and require message sending (method invocation) with dynamic binding.

You can do this in Ocaml is you use the "O" (the Object layer), with some limitation coming with the advantage of having strong typing.

In OCaml Having a set of related types, deciding whether you will use a class hierarchy and message sending or, as suggested by andreas, a concrete (algebraic) type together with pattern matching and simple function call, is a hard question.

Concrete types are not equivalent. If you choose the latter, you will be unable to define a new node in your AST after your node type will be defined and compiled. Once said that a A is either a A1 or a A2, your cannot say later on that there are also some A3, without modifying the source code.

In your case, if you want to implement a visitor, replace your EXPR concrete type by a class and its subclasses and your functions by methods (which are also functions by the way). Dynamic binding will then do the job.

Nous