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=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id 11630BC0A for ; Thu, 7 Jun 2007 03:06:00 +0200 (CEST) Received: from ipmail03.adl2.internode.on.net (ipmail03.adl2.internode.on.net [203.16.214.135]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l5715v51019348 for ; Thu, 7 Jun 2007 03:05:59 +0200 X-IronPort-AV: E=Sophos;i="4.16,391,1175437800"; d="scan'208";a="100007533" Received: from ppp2-129.lns1.syd7.internode.on.net (HELO [192.168.1.201]) ([59.167.2.129]) by ipmail03.adl2.internode.on.net with ESMTP; 07 Jun 2007 10:30:49 +0930 Subject: Re: [Caml-list] Labelling trees From: skaller To: David Teller Cc: OCaml In-Reply-To: <1181158983.9266.12.camel@Blefuscu> References: <1181158983.9266.12.camel@Blefuscu> Content-Type: text/plain Date: Thu, 07 Jun 2007 11:00:46 +1000 Message-Id: <1181178046.6546.54.camel@rosella.wigram> Mime-Version: 1.0 X-Mailer: Evolution 2.10.1 Content-Transfer-Encoding: 7bit X-Miltered: at discorde with ID 466759F5.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; 0200,:01 checker:01 annotations:01 variants:01 recursion:01 parametric:01 'ast:01 recursion:01 annotations:01 untyped:01 hashtbl:01 ocaml:01 indirection:01 statically:01 sourceforge:01 On Wed, 2007-06-06 at 21:43 +0200, David Teller wrote: > Hi everyone, > That would let me annotate instances of my_expression or my_function > with informations of type 'a. However, this won't scale in case I decide > that my static checker will need annotations of different types for > my_expression and my_function. Of course, my AST is actually a tad more > complex and would require about 15 type arguments, which I don't > consider very nice. This is indeed a nasty problem I have too. In theory, polymorphic variants with open recursion support what you want by making a new parametric term with a new case `TYPE_ast of typ * 'ast and then closing the recursion. This is a covariant extension. The problem is that whilst this is relatively easy to encode for 1 parameter, it gets messy with 2 .. and if you have 15 or so as I do as well .. it's just easier to use a dummy type or magic .. neither of which is satisfactory. Nor is the above encoding very nice, since it doesn't ensure each branch of the tree is labelled, instead it simply caches values where you chose, to speed up the functional calculation. I just do the boring thing. I make a new type with the term plus annotations and translate from the untyped to typed terms. You CAN solve this with a list or array mapping the physical term address to the type, with O(N) performance (YUK). You can't use a Map or Hashtbl because they require ordering, and Ocaml moves objects around so ordering on addresses isn't stable. Double indirection works though: instead of terms, use an integer which Maps to a term .. you can then also Map the integer to your type. Of course .. this isn't statically safe. BTW: this is basically 'parallel hierarchies' problem of OO on a value level. -- John Skaller Felix, successor to C++: http://felix.sf.net