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
_______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
