Re: new library modules (sets and maps)

Didier Remy (remy@research.att.com)
Wed, 5 May 93 11:40 EDT

Message-Id: <m0nqlad-000CmwC@hunny.research.att.com>
Date: Wed, 5 May 93 11:40 EDT
From: remy@research.att.com (Didier Remy)
To: xavier@theory.stanford.edu
Subject: Re: new library modules (sets and maps)

Of course, the typechecker cannot tell whether you are using two different
orderings on the same map. If you pack the ordering with the primitives in a
record, you could also associate a stamp to the package (each timem you pass
a different ordering) which you be used to mark all sets created by this
package. Then you could dynamically check whether two sets sets are
originated from the same package. Except that you cannot generate stamps in
a purely applicative style!

Using an object oriented style, you could consider the functions on sets as
methods, and pack them with each set (instead of the stamp). The primitives
then take just call the right methods from the set they operate on, which
prevent from using two differnt ordering on the same set. In fact it is
enough to pack only the ordering "method".

The interface would still be:

type 'a t;;

type 'a ordering == 'a -> 'a -> int;;

type ('a, 'b) set_operations =
{ empty: 'a t;
is_empty: 'a t -> bool;
mem: 'a -> 'a t -> bool;
add: 'a -> 'a t -> 'a t;
iter: ('a -> 'b) -> 'a t -> unit;
(* and so on *) };;

value make: 'a ordering -> ('a, 'b) set_operations;;

but the implementation of 'a t is now

type 'a t = {ordering : 'a -> 'a -> 'int;
val : 'a old_t};;

and the implementation of the functions would changed accordingly to take
the ordering from their argument rather than from their closure. Of course,
there is an ambiguity for functions working on several sets. The functions
could be written to work with two orderings, one for each set, but this may
complicate their implementation or slower their execution, for a situation
that should not arise in practice...

Didier.