Re: [Caml-list] Labelling trees

[Christian Stork <cstork@ics.uci.edu>]

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 = <e:'e; f:'f; ...>
and 'a func = F1 of 'f * 'a bar
            | F2 of 'f * 'a bla
            | ...
            constraint 'a = <e:'e; f:'f; ...>
...

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