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=1.1 required=5.0 tests=AWL,SPF_NEUTRAL 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 1B41ABC0A for ; Thu, 7 Jun 2007 16:26:48 +0200 (CEST) Received: from ug-out-1314.google.com (ug-out-1314.google.com [66.249.92.171]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l57EQl4X022953 for ; Thu, 7 Jun 2007 16:26:47 +0200 Received: by ug-out-1314.google.com with SMTP id p27so646817ugc for ; Thu, 07 Jun 2007 07:26:47 -0700 (PDT) DKIM-Signature: a=rsa-sha1; c=relaxed/relaxed; d=gmail.com; s=beta; h=domainkey-signature:received:received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=ZTzchclyUGPGCscjTYKPlLLraY5jHe4VW7OGeMWZ+iHIGLMR0mkjtmQLNKpqrFhY+m6QrbW0ZHaaCp8g9aEWH9n6kL+3EXDCDUoiLUARjlNFEM12TzLhuGABNm3iE7aY4gPgoFmW5jUuUupFK8evLPNeZDt28PvbrKUZ/MmEF7w= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=F/+s8TPMHd4hlmuDQ/SmAasL6D5c4/LdUGRid7+gG1GP6FARXAmj/WrKIlTYr/leOSzsiwQ/rTAJoayPBoFPfcI/EkxH32CyWkHF8Rygevtwa1fLwTu5eh1MCaZI00h/UF6XtiMbXpobVeu6VPK7Ew6DPGW3C6vy187Ujwpxr9k= Received: by 10.67.102.12 with SMTP id e12mr1226775ugm.1181226406719; Thu, 07 Jun 2007 07:26:46 -0700 (PDT) Received: by 10.66.239.7 with HTTP; Thu, 7 Jun 2007 07:26:46 -0700 (PDT) Message-ID: <9d3ec8300706070726o3ed62650ob73c832fdfa92617@mail.gmail.com> Date: Thu, 7 Jun 2007 16:26:46 +0200 From: "Till Varoquaux" To: skaller Subject: Re: [Caml-list] Labelling trees Cc: "David Teller" , OCaml In-Reply-To: <1181178046.6546.54.camel@rosella.wigram> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <1181158983.9266.12.camel@Blefuscu> <1181178046.6546.54.camel@rosella.wigram> X-j-chkmail-Score: MSGID : 466815A7.001 on concorde : j-chkmail score : X : 0/20 1 0.000 -> 1 X-Miltered: at concorde with ID 466815A7.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; variants:01 recursion:01 parametric:01 'ast:01 recursion:01 struct:01 binop:01 expr:01 binop:01 fundecl:01 instr:01 expr:01 instr:01 camlp:01 fundecl:01 > 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