From: Christian Stork <cstork@ics.uci.edu>

> I'm tying to implement a framework for visitors over trees (e.g. ASTs).
> These trees are built according to some rules.  Rules are much like the
> productions of a grammar.

In general I would advice against using an object-oriented
representation for ASTs. Variant types are the proven approach to do
that in functional languages, and generally work much better.

> The following minimal example demonstrates my current design problem:
[...]
> The above code has one special twist, it allows the visitor's visit...
> methods to hand eachother some argument, called the baton.  Different
> visitors might want to use different types of batons.  The above code
> tries to support this by parametrizing the accept method and the
> visitor class.  Sadly, Ocaml complains about then with 

This specific typing problem can be solved.
It stems from the fact you are defining someRule and ['baton] visitor
simultaneously, but use 'baton polymorphically in someRule.
Inside mutual recursive definitions of classes, parameters cannot be
used polymorphically.
The way to a void this problem is to break the recursion.
The following code does what you want.

type 'rule node = { rule:'rule; kids:'rule node list } 

class type ['baton,'rule] visitor = object
  method visitSomeRuleNode : 'rule node -> 'baton -> 'baton
end

class someRule =
  object (self)
    method accept
      : 'baton . someRule node -> ('baton,someRule) visitor -> 'baton -> 'baton
      = fun n v b -> v#visitSomeRuleNode n b
  end

class ['baton] visitor_impl =
  object (self)
    method visitSomeRuleNode n (b : 'baton) =
      List.fold_left
        (fun b' k -> (k.rule : someRule)#accept k (self :> _ visitor_impl) b')
        b n.kids
  end

Jacques Garrigue