Jacques and John, thanks for your replies.  Sorry for the long delay in
responding, but this took me some time to figure out...

On Wed, Feb 09, 2005 at 10:53:50AM +0900, Jacques Garrigue wrote:
> 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.

Right now I think that a combination works best in my case.  My problem
is different from regular ASTs because in my application (compression of
different kinds of ASTs) the grammar for the ASTs is not fixed and for
now I really only care about certain kinds nodes/rules.

> > 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

Great, this compiles. :-)  The only problem is that I have more than one
rule which means many type parameters.  I also ran into some other
problems when I expanded the above code.  So in the end I followed your
advice and turned nodes into variants, but they still refer to a rule.
These rules can be used to differentiate among nodes of the same
variant.  So I guess I reached a kind of compromise between the two
programming paradigms (FP & OO).

On Tue, Feb 08, 2005 at 07:16:56PM -0500, John Prevost wrote:
> Hmm.  Would it be possible to include a more complete example (even if
> it doesn't compile)--that is, one where the visitor actually performs
> real work?  My suspicion is that you would be better off *not*
> encoding this visitor pattern using objects, but since I'm not clear
> on how you intend to use it, I can't give a concrete example.  (And
> likewise even if objects are the best choice.)

I attached a simplified but still lengthy version of my current design.

Any comments welcome (even if unrelated to the above points)!

Thanks,
Chris

-- 
Chris Stork   <>  Support eff.org!  <>   http://www.ics.uci.edu/~cstork/
OpenPGP fingerprint:  B08B 602C C806 C492 D069  021E 41F3 8C8D 50F9 CA2F