Re: [Caml-list] Labelling trees

["Till Varoquaux" <till.varoquaux@gmail.com>]

> 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