User-Defined Operators (ad-hoc overloading)

[Andrew J Bromage]

G'day all.

On Fri, Jul 18, 2003 at 11:08:16AM +0200, Christian Maeder wrote:

> Mere overload resolution (over monomorphic types) is not NP-hard. (This 
> is only a common misconception.)

No, but as you note below, the "interesting" cases are.  Most
of the more interesting number-like types are polymorphic (e.g.
Complex, Ratio).

> Overload resolution in conjunction with polymorphism surely remains NP 
> hard due to the "let". Furthermore, usually unification alone (know to 
> be linear in theory) is implemented in a way that can cause "explosion".
> 
> So I doubt, that overload resolution should be blamed if front-ends 
> become really slow.

The question is not "is it theoretically slow?"  The question is "are
you ever likely to see the worst-case behaviour if you're not actively
looking for it, or otherwise doing something dubious?"

Remember that the situation we're looking at is that there are a small
number of operators (e.g. those which work on number-like types) which
people want to heavily overload.  A program which used a mixture of
these types could easily tickle exponential behaviour quite quickly if
the programmer is not careful.  Plus, what would cause this behaviour
is not their _use_ as such, but rather the number of modules imported
which have these overloaded operators defined.

Cheers,
Andrew Bromage