Hello,

Perhaps this is a beginner question.  If it's not appropriate for the  
list, I apologize in advance.  I am working on a simple compiler in  
Ocaml, and having some difficulty settling on the best design for my  
AST.

My initial attempt was to use a lot of variant types, like so:

> type type_tree = Primitive of string | Pointer of type_tree
> and  expr_tree = Unary of string * expr_tree |
>                  Binary of string * expr_tree * expr_tree
> (etc)

This seemed like it should work reasonably well, but then I realized  
I would want to thread along some annotation to store the types, line  
numbers, and things like that.  Since these annotations will change  
between compiler passes, I thought I would use a variant type like so:

> type 'ud type_tree = Primitive of 'ud * string |
>                      Pointer of 'ud * 'ud type_tree
> and 'ud expr_tree = Unary of 'ud * string * 'ud expr_tree |
>                     Binary of 'ud * string * 'ud expr_tree * 'ud  
> expr_tree
> etc

but then I ran into the problem that I sometimes want to be able to  
extract the user data without reference to the type of tree involved,  
and I can see no easy way to do that beyond:

> let ud_type type =
>   match type with
>     Primitive(ud,_) ud |
>     Pointer(ud,_) ud
> etc

Obviously, that is unappealing.

So, I am not sure what the right approach is here.  I could use  
objects, and then use subtyping (or structural subtyping?) to have a  
common base type with the userdata, but this seems significantly more  
verbose.  Also, I'm trying to explore alternatives to OOP (though if  
there is no compelling alternative, .

Various examples that I have looked at don't seem to really solve  
this problem: I guess they just try to structure things so that they  
don't ever need to extract the user data by itself.  This is an  
alternate approach that I could take, perhaps my problem is merely a  
failure of the imagination.  Another option, obviously, is not to  
embed the userdata in the variant type, but instead outside, by  
replacing any reference (for example) to type_tree with ('ud *  
type_tree).  This would be ok.

One example of when I want this ability is shown in the "Pointer"  
type constructor above: in this case, when making a pointer type I  
initially want the user data to be the same (as it contains the line  
number, let's say), but later, the user data may be different.   
Since, in my parser, I just have a "type" reduction that yields some  
kind of type_tree, it is hard to extract the user data.


thanks for any tips!

Niko