English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
Re: [Caml-list] Hashtbl iter semantics
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2002-05-31 (17:29)
From: John Max Skaller <skaller@o...>
Subject: Re: [Caml-list] Hashtbl iter semantics
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 
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.

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