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