User-Defined Operators (ad-hoc overloading)

[Christian Maeder]

Andrew J Bromage wrote:
> Of course you could always allow overloading _without_ requiring
> module qualification (unless the overloading can't be resolved
> using type information).  It'd make type checking NP-hard, but I
> seem to recall that it's already more complex than that.

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

Operators with function profiles can be viewed as context free grammar 
productions where the types are non-terminals. Overlaod resolution, like 
for ADA, corresponds then to the word problem for context free grammars 
that can be solved (by Earley's algorithm) in O(n^3) with n being the 
input length, ie. the length of an expression. (Although for overload 
resoultion the dominating input will be the number of productions.)

Surely the number of ambiguous expression may grow exponentially (like 
in Isabelle, as far as I know) but you do not need to compute all these.

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.

Christian