User-Defined Operators (ad-hoc overloading)

[Andrew J Bromage]

G'day all.

On Mon, Jul 21, 2003 at 01:07:39PM +0200, Christian Maeder wrote:

> >>Mere overload resolution (over monomorphic types) is not NP-hard. (This 
> >>is only a common misconception.)
> 
> I can only repeat my above sentence.

I'm a firm believer in the maxim that the best way to find information
on the net is to post wrong information. :-)

As a matter of interest, is there a known worst-case complexity for
the precomputation required by Earley's algorithm to handle arbitrary
CFGs?

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

I don't believe that expected-case O(N^3) behaviour counts as "not
hard", even if it's not exponential.  These things have a way of
biting you when you least expect it.

>From an economic point of view, programmer time is very expensive.
Much more so than machine time.  A few seconds spent resolving
overloading on a large program is a few seconds that the programmer
is effectively stalled.  Plus, these things add up.  A short time
plus a short time is not necessarily a short time.

Another economic issue to consider is that the time spent compiling a
program over its life is often quadratic in the final size of the
program.  One necessary requirement for tractible software development
is low constant factors.

(This, of course, assumes that the program grows linearly over its
life and the machines used to compile on are not upgraded over that
time.  In commercial development, it's generally considered good
practice to freeze the hardware/compiler/OS combination throughout the
maintenance period of a specific software release.  This assumption may
not hold in some development environments, such as in open source
development.)

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

I think we agree that Haskell's type class scheme is an extremely good
mechanism for the problem of overloading.  However, mechanism is not the
same as policy.

The issue that we have before us is that the current numeric type class
hierarchy is too coarse-grained for people developing richer varieties
of numeric types.  There are problems with making it too fine-grained,
as well.

Until we find the "sweet spot", the problem is not solved.

Cheers,
Andrew Bromage