Re: [Caml-list] Labelling trees

[skaller <skaller@users.sourceforge.net>]

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 <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net