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