This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

Labelling trees
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2007-06-07 (14:26) From: Till Varoquaux Subject: Re: [Caml-list] Labelling trees
```> 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.

Well... this is what type constraints make this slightly less messy:

module Gram =
struct
type 'cst binop = Add | Sub | Mul | Div
type 'cst constant = Int of int | Float of float
type 'cst expr =
Cst of 'constant
| Ident of 'ident
| Call of ('expr * ('expr list))
| Binop of ('binop * 'expr * 'expr)
| Fundecl of (('ident list) * 'instr)
constraint 'cst =
< instr : 'instr; ident : 'ident; expr : 'expr; constant : 'constant;
binop : 'binop; ..
>
type 'cst ident = string
type 'cst instr =
Let of ((('ident * 'expr) list) * 'instr)
| Exp of 'expr
| Assign of ('ident * 'expr)
| If of ('expr * 'instr * 'instr)
| Bloc of 'instr list
constraint 'cst = < instr : 'instr; ident : 'ident; expr : 'expr; .. >
end
type cst =
< instr : instr; ident : ident; expr : expr; constant : constant;
binop : binop
>
and binop =
cst Gram.binop
and constant =
cst Gram.constant
and expr =
cst Gram.expr
and ident =
cst Gram.ident
and instr =
cst Gram.instr

is an example. It still gets very boring and administartive so you
might want to harness Camlp4 here [1]. This file was actually
generated from a source file like this:

gram{
ident := string;
constant:= Int int | Float float;
expr :=
|Cst constant
| Ident ident
| Call expr,[expr]
| Binop binop,expr,expr
| Fundecl [ident],instr;
binop := Add | Sub | Mul | Div ;
instr :=
| Let [(ident,expr)],instr
| Exp expr
| Assign ident,expr
| If expr,instr,instr
| Bloc [instr]
}

In this case you do not need polymorphic variant since you could
always generate types like:

type cst =
< instr : instr; ident : ident; expr : expr; constant : constant;
binop : binop
>
and binop = cst Gram.binop
and constant = cst Gram.constant
and expr = edec*cst Gram.expr
and ident = cst Gram.ident
and instr = idec*cst Gram.instr

where `idec` and `edec` are the decorations you want to add on the
nodes for the instructions and the expressions respectively.

>
> 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.

> 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.

Hashtbl don't require ordering they require hashing. Anyways I'm
pretty sure both the functions `Pervasives.compare` and `Hashtbl.hash`
actually work on the representation of the data, not on its physical
address (that's why compare can fail on recursive values) . You can
use both Hashtables and Maps but you might aim for a weak data
structure to limit memory leaks.... BTW: for some akward reason
Weak.Hashtbl is not a hashtable.

>
> 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.

Huh????

Till Varoquaux
[1] This camlp4 extension is in pre-pre-pre-alpha state. It can be
browsed online:
http://till.varoquaux.free.fr/projects/mini_js/OpenTrees.ml.html

```