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