Re: Type-checking with polymorphism & overloading

<hat@se-46.wpa.wtb.tue.nl> writes:


>I am working on building a type-checking system for a language which
>has both polymorphism and overloading, and compile-time type checking.
>Surely, someone in this large world must have looked at the
>combination of polymorpism and overloading ?


The language Mercury (see <http://www.cs.mu.oz.au/mercury>)
supports both polymorphism and overloading.
The algorithm we use to handle overloading is a quite simple
extension of the ordinary type inference algorithm: instead
of inferring a type environment (mapping from variables to types),
we just infer a set of type environments. Inconsistent type
assignments are eliminated from the set. At the end, if the
set contains more than one member, we report an ambiguity error.


Type checking (or inference) in this system is NP-complete, but in
practice, that has not been a problem. To catch the nasty cases,
I added some code to the type checker to issue a warning ("highly
ambiguous overloading") if the set of type environments ever got too
large, but in practice those cases don't seem to occur in real code.


Peter Stuckey <pjs@cs.mu.oz.au> developed a more efficient type
inference algorithm based on the use of disjunctive constraints;
I believe he published something about this, but I can't find the
reference off-hand. You could try emailing him.


P.S.
I notice that quite a few of the references cited by other posters in
this thread were papers about Haskell type classes. Haskell type
classes were originally proposed as an alternative to overloading, but
IMHO type classes and overloading solve different problems. The latest
development version of Mercury supports Haskell-style type classes in
addition to (not instead of!) overloading. Type classes are a good
solution to the problem of implementing constrained genericity, but
they don't help with accidental name clashes -- Haskell forces users to
do manual name mangling to avoid these. Overloading, on the other
hand, is great at resolving accidental name clashes, but it doesn't
help with constrained genericity. (Actually in C++ overloading *is*
used, together with templates, for constrained genericity; but this has
a number of major problems and is not something I would recommend for
future language designers.)


--
Fergus Henderson <fjh@cs.mu.oz.au>
WWW: <http://www.cs.mu.oz.au/~fjh>
PGP: finger fjh@128.250.37.3
--

Return to the comp.compilers page.
Search the comp.compilers archives again.