From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id TAA30827; Fri, 31 May 2002 19:29:25 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id TAA31030 for ; Fri, 31 May 2002 19:29:25 +0200 (MET DST) Received: from sunny.pacific.net.au (sunny.pacific.net.au [203.25.148.40]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id g4VHTKn03170; Fri, 31 May 2002 19:29:22 +0200 (MET DST) Received: from wisma.pacific.net.au (wisma.pacific.net.au [210.23.129.72]) by sunny.pacific.net.au with ESMTP id g4VHTGZr019421; Sat, 1 Jun 2002 03:29:16 +1000 (EST) Received: from ozemail.com.au (ppp10.dyn17.pacific.net.au [61.8.17.10]) by wisma.pacific.net.au with ESMTP id DAA14512; Sat, 1 Jun 2002 03:29:13 +1000 (EST) Message-ID: <3CF7B2E7.2030408@ozemail.com.au> Date: Sat, 01 Jun 2002 03:29:11 +1000 From: John Max Skaller User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:0.9.2.1) Gecko/20010901 X-Accept-Language: en-us MIME-Version: 1.0 To: Francois.Pottier@inria.fr CC: caml-list@inria.fr Subject: Re: [Caml-list] Hashtbl iter semantics References: <200205271904.VAA0000015105@beaune.inria.fr> <3CF5258C.3080409@ozemail.com.au> <20020530085315.A24997@pauillac.inria.fr> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Francois Pottier wrote: >On Thu, May 30, 2002 at 05:01:32AM +1000, John Max Skaller wrote: > >>[The replace semantics you describe are unfortunate for me: my unification >>algorithm keeps a hashtable of variable -> term bindings into which >>I have to incrementally subtitute while iterating through the table. >> > >Do you need to maintain *several* such substitutions (i.e. tables) with >the same domain (i.e. the same set of variables)? > Don't know. At present, I have a single global table, and the variables are 'unknowns' rather than variables: they represent function return types (or components thereof). So at present, all the variables must be eliminated, and have a universal value. (and this is proving much harder than I thought to get right ..) However, I am just introducing parametric polymorphism .. in that case a 'variable' takes on a new value for each instantiation. On the other hand, the client will initially have to provide the values explicitly. I will still need subsumption, however, to resolve overload ambiguity in favour of the most specialised matching function. [Things get really interesting when subtyping is introduced as well ..] >If not (that is, if >you only have one hash table), then it is customary to use a mutable >field, within each variable record, to store the associated term. It's >simpler and the overhead for access is very small. > Yes, I could do that (though it doesn't handle deletion so well .) >One nice way of doing so is to use a generic union/find algorithm, such >as the one I am attaching to this message. > Thx. I'm using the Robinson algorithm at present: simple, but not efficient. [And it doesn't match equi-recursive terms correctly .. I can't figure out a fast way to minimise such a term .. hmmm.. linearise and use a string matching algorithm ..?] -- John Max Skaller, mailto:skaller@ozemail.com.au snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia. voice:61-2-9660-0850 ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners