User-Defined Operators (ad-hoc overloading)

[Christian Maeder]

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

I can only repeat my above sentence.

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

This kind of overloading is no cause for exponentiell behaviour, if it's 
either solved by type class overloading or by monomorphic overload 
resolution. (Only let-polymorphism is "hard".)

> 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?"

I agree with this statement, in fact this argument was used to employ an 
exponentiell algorithm (I think Cormacks's algorithm in ADA, below) that 
is fast in practice.

> 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.

Again, this standard case is no problem for overload resolution (unless 
implemented too naively.) Cormack's algorithm will solve such cases fast 
by feeding in the expected result type.

Some books on compilers explain overload resolution by (two, set-valued) 
attributes. Such an algorithm is also not exponentiell!

I admit the combination of overload resolution and polymorphism is not 
simple, but Haskell has solved it in a certain way with type classes!

Cheers Christian

See: T.Pennello, F.DeRemer, and R.Meyers: A simplified Operator 
Identification Scheme for ADA, 1980 (ACM SIGPLAN Notices 15(7-8):82-87