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 concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 88C79BC0A for ; Thu, 7 Jun 2007 16:25:17 +0200 (CEST) Received: from stirner.roentgeninstitut.de (stirner.roentgeninstitut.de [212.110.109.210]) by concorde.inria.fr (8.13.6/8.13.6) with SMTP id l57EPG64022396 for ; Thu, 7 Jun 2007 16:25:17 +0200 Received: (qmail 28524 invoked by uid 1000); 7 Jun 2007 07:25:16 -0700 Date: Thu, 7 Jun 2007 07:25:16 -0700 From: Christian Stork To: David Teller , caml-list@inria.fr Subject: Re: [Caml-list] Labelling trees Message-ID: <20070607142516.GA28217@stirner.roentgeninstitut.de> Mail-Followup-To: David Teller , caml-list@inria.fr References: <1181158983.9266.12.camel@Blefuscu> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1181158983.9266.12.camel@Blefuscu> X-Archive: encrypt User-Agent: Mutt/1.5.13 (2006-08-11) X-Miltered: at concorde with ID 4668154C.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; 0200,:01 checker:01 syntax:01 annotations:01 checker:01 annotations:01 expr:01 foo:01 camlp:01 corrupting:98 806:98 021:98 wrote:01 abstract:01 caml-list:01 On Wed, Jun 06, 2007 at 09:43:02PM +0200, David Teller wrote: > > Hi everyone, > I'm currently in the very first stages of writing down a prototype > implementation of a type checker. At the moment, I'm looking for "the > nicest" way of labelling my abstract syntax tree with type annotations > -- without corrupting the AST at all, if possible. > > > Say I have > > type my_expression = ESomeConstructor of ... > | ESomeConstructor2 of ... > | ESomeConstructor3 of my_function > and my_function = FSomeConstructor ... > > > A first idea would be to replace this structures with > > type 'a my_expression = ESomeConstructor of ... > | ESomeConstructor2 of ... > | ESomeConstructor3 of 'a my_function > and 'a my_function = FSomeConstructor ... > > 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. Jacques Garrigue once mentioned the following trick on this list. Instead of writing out 15 type parameters each time one can use a single type paramenter with an object type constraint. For example, type 'a expr = E1 of 'e * 'a func | E2 of 'e * 'a foo | ... constraint 'a = and 'a func = F1 of 'f * 'a bar | F2 of 'f * 'a bla | ... constraint 'a = ... One could even think of reducing the remaining constraints with some camlp4 magic to a single instance. -- Chris Stork <> Support eff.org! <> http://www.ics.uci.edu/~cstork/ OpenPGP fingerprint: B08B 602C C806 C492 D069 021E 41F3 8C8D 50F9 CA2F