[m-dev.] Re: For review: changes to graph.m

Peter Schachte pets at cs.mu.oz.au
Wed Jun 4 17:19:14 AEST 1997


On 4 Jun 1997, Lee Naish wrote:

> Graphs are an excellent example of data which you may want to represent in
> different ways at different times/places.  Perhaps some extra thought should
> be put into how a collection of graph manipulation libraries could be managed
> wrt names, conversion between different representations etc.  One possibility
> would be to have a single library which uses several representations internally.
> The init predicate could specify which representation to use and other predicates
> could inspect the top level wrapper to determine what representation is used.

It has occured to me that an extension to type classes could provide an
answer to this.  Let me take maps as an example, since I think they make a
more interesting example than graphs.

Suppose you have a map(T1,T2) parametric type class that has operations
like make an empty map, insert a mapping and look up an entry.  One can
imagine implementing this as an association list, a binary tree, a hash
table, an array with range checks, and a vanilla array.  The choice of
which concrete type to choose depends on properties of the key type.  If
the key is in the 'comparable' type class, we can choose a binary tree
over an association list.  If it's in the 'hashable' type class, then we
can use a hash table.  If it's in 'enumerable' (meaning there is a trivial
bijection between elements of the type and integers), then we can use an
array with range checks.  If it's in range_limited (meaning there is a
minimum and maximum value that we can determine at compile time), then we
can avoid the range checks.

The idea then would be that the implementor would create a several types
each of which belong to the map type class and each of which insist on
their key type belonging to different type classes.  The user could then
specify the type of some predicate arguments as being in the map type
class, without actually specifying which type, and the compiler would use
the type classes of the key type in the implementations to determine which
type to use. 

The remaining question is how the compiler finds all the different
implementations of a type class, and how it chooses the best one.  One
solution would be to have a file for each type class that the user wants
to use as if it were a type that lists the types that inhabit that class
in order of preference.  The compiler would then pick the first type for
which parametric types meet the type class criteria, as described above.

As to the point that runtime properties, eg the size of a set, should also
help determine the choice of implementation, this can be handled with type
subclasses.  For example, one could define a small_set type subclass of
the set type class that uses an ordered list representation for element
types that are in 'comparable', and unordered lists otherwise.  Further,
there would be a simple_small_set type subclass that doesn't supply union,
intersection, and set difference operations, and the only implementation
of this class would use unordered lists.  Maybe someday global analysis
would be able to determine that although my particular application
declares some argument to be small_set, I never use intersection, union,
or set difference on it, and therefore the compiler could instead use
simple_small_set. 


-Peter Schachte      URL:  http://www.cs.mu.oz.au/~pets/
pets at cs.mu.OZ.AU     PGP:  finger pets at 128.250.37.150 for key
    [A computer is] like an Old Testament god, with a lot of rules
    and no mercy.  -- Joseph Campbell




More information about the developers mailing list