From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: * X-Spam-Status: No, score=1.5 required=5.0 tests=SPF_SOFTFAIL autolearn=disabled version=3.1.3 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id AE83BBC0A for ; Thu, 24 May 2007 13:06:18 +0200 (CEST) Received: from spunkymail-a15.dreamhost.com (balanced.mail.policyd.dreamhost.com [208.97.132.119]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l4OB6Hsf008463 for ; Thu, 24 May 2007 13:06:18 +0200 Received: from [129.132.134.247] (beauty.inf.ethz.ch [129.132.134.247]) by spunkymail-a15.dreamhost.com (Postfix) with ESMTP id EC2F27F016 for ; Thu, 24 May 2007 04:05:19 -0700 (PDT) Mime-Version: 1.0 (Apple Message framework v752.3) Content-Transfer-Encoding: 7bit Message-Id: Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: caml-list@yquem.inria.fr From: Niko Matsakis Subject: Extracting common information Date: Thu, 24 May 2007 13:04:46 +0200 X-Mailer: Apple Mail (2.752.3) X-Miltered: at concorde with ID 465571A9.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; compiler:01 ocaml:01 pointer:01 expr:01 expr:01 annotation:01 annotations:01 compiler:01 pointer:01 subtyping:01 subtyping:01 verbose:01 parser:01 alum:98 userdata:98 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