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=0.0 required=5.0 tests=none 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 CF709BC0A for ; Fri, 8 Jun 2007 01:09:25 +0200 (CEST) Received: from ipmail03.adl2.internode.on.net (ipmail03.adl2.internode.on.net [203.16.214.135]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l57N9NuO029817 for ; Fri, 8 Jun 2007 01:09:24 +0200 X-IronPort-AV: E=Sophos;i="4.16,397,1175437800"; d="scan'208";a="100459756" Received: from ppp2-129.lns1.syd7.internode.on.net (HELO [192.168.1.201]) ([59.167.2.129]) by ipmail03.adl2.internode.on.net with ESMTP; 08 Jun 2007 08:39:18 +0930 Subject: Re: [Caml-list] Labelling trees From: skaller To: Till Varoquaux Cc: David Teller , OCaml In-Reply-To: <9d3ec8300706070726o3ed62650ob73c832fdfa92617@mail.gmail.com> References: <1181158983.9266.12.camel@Blefuscu> <1181178046.6546.54.camel@rosella.wigram> <9d3ec8300706070726o3ed62650ob73c832fdfa92617@mail.gmail.com> Content-Type: text/plain Date: Fri, 08 Jun 2007 09:09:17 +1000 Message-Id: <1181257757.15201.27.camel@rosella.wigram> Mime-Version: 1.0 X-Mailer: Evolution 2.10.1 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 46689023.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; 0200,:01 hashtbl:01 hashing:01 hash:01 pervasives:01 hashtbl:01 hash:01 hashing:01 indirection:01 statically:01 compiler:01 statically:01 semantics:01 decoration:98 decoration:98 On Thu, 2007-06-07 at 16:26 +0200, Till Varoquaux wrote: > Hashtbl don't require ordering they require hashing. True, but the hash required would be unstable. > Anyways I'm > pretty sure both the functions `Pervasives.compare` and `Hashtbl.hash` > actually work on the representation of the data, Yes, which is why you can't use them. The idea is: map1: address1 -> AST map2: address1 -> decoration where address1 is the address of the AST term. map1 is just the function: let id x = x map2 can be an association list, searching by address. Hashing or comparing using the value of a term as a key is no good. It's too slow. > > 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???? The Felix compiler maps like: int -> term int -> decoration This isn't statically safe. There's no assurance of a 1-1 correspondence between terms and decorations. The encoding is safe .. the semantics aren't. I use Hashtbl for this and I get 'Not_found' exception regularly. Correctness here depends on control flow -- dynamically maintaining the correspondence. -- John Skaller Felix, successor to C++: http://felix.sf.net