Visitor in OCaml [was Re: [Caml-list] C++/C# inheritance is bad?]

[Yoann Padioleau <padator@wanadoo.fr>]

Jon Harrop <jon@ffconsultancy.com> writes:

> On Saturday 17 January 2009 14:35:22 Kuba Ober wrote:
>
> In contrast, metaprogramming is the pedagogical example for algebraic 
> datatypes. There is almost no need for users to extend the abstract syntax 
> tree but there is huge value in being able to rewrite expressions using 
> pattern matching. 
> There is an idiomatic OOP solution to this problem that 
> involves visitor patterns and so forth but it is comparatively verbose, 
> obfuscated and unmaintainable.

Actually I think there are some good ideas in the visitor pattern. I
personnaly use a mix of pattern matching and of the visitor idiom in
one of my project about C program transformation
(http://www.emn.fr/x-info/coccinelle/).

The problem we had is that we manipulate the AST of C programs 
and some of our analysis need only to specify an action for 
specific cases, such as the function call case, and recurse
for the other cases. 
Here is an simplification of our AST: 

type ctype = 
 | Basetype of ...
 | Pointer of ctype
 | Array of expression option * ctype
 | ...
and expression = 
 | Ident of string
 | FunCall of expression * expression list
 | Postfix of ...
 | RecordAccess of ..
 | ...
and statement = 
 ...
and declaration =
 ...
and program = 
 ...

What we want is really give code like 

let my_analysis program = 
 analyze_all_expressions program (fun expr ->
   match expr with
   | FunCall (e, es) -> do_something()
   | _ -> <find_a_way_to_recurse_for_all_the_other_cases> 
 )

The problem is how to write analyze_all_expressions
and find_a_way_to_recurse_for_all_the_other_cases.

Our solution is to mix the ideas of visitor, pattern matching, 
and continuation. Here is how it looks like in our coccinelle project
using our hybrid-visitor API: 

let my_analysis program = 
 Visitor.visit_iter program {
   Visitor.kexpr = (fun k e -> 
    match e with
    | FunCall (e, es) -> do_something()
    | _ -> k e
   );
  }

You can of course also give action "hooks" for 
kstatement, ktype, or kdeclaration. But we don't overuse
visitors and so it would be stupid to provide
kfunction_call, kident, kpostfix hooks as one can just
use pattern matching with kexpr to achieve the same effect.


The code in Visitor.visit_iter is then of course a little bit tricky.
You can have a look in the source of coccinelle.

>
> -- 
> Dr Jon Harrop, Flying Frog Consultancy Ltd.
> http://www.ffconsultancy.com/?e
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs