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

_______________________________________________
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell

Reply via email to