Re: Overload Resolution in Ada (Re: The Red Language)

[Brian Rogoff <bpr@shellx.best.com>]

On Fri, 19 Sep 1997, Robert A Duff wrote:

> In article <Pine.SGI.3.95.970918180906.18953A-100000@shellx.best.com>,
> Brian Rogoff  <bpr@shellx.best.com> wrote:
> >My apologies for the off topic post...
> 
> Heh?  Surely you jest!

I don't jest, and my name isn't Shirley :-). 
Yeah, I was kidding. I read news only once a day now, and snide little 
remarks like that relieve my annoyance at the Eternal Interlingual Flamewar 
whose skirmishes are now making a constant din on cla. I'll use a ":-)" 
next time.

> >Out of curiosity, what is the worst case running time(s) of the two pass 
> >algorithm(s)?

I suppose I should have elaborated further, though you took a very nice
stab at an answer. I'm not suggesting that overload resolution is in any 
way a limiting factor on the speed of an Ada compiler; I'm just slowly 
trying to understand how automatic generic instantiation could be made to 
work and there is a great deal of interaction between overload resolution
and type inference (as I'm sure you know ML type inference is exponential, 
but not too bad in practice :-).  

> Umm, I don't know.  I guess you can make it arbitrarily slow.  Are you
> asking for O(f(N)), where N is the number of nodes in the expression
> tree (in the "complete context", which is a single statement or
> declaration or whatever). 

Yes, although you can certainly introduce other variables in the big O
estimate for the other factors which matter. I'm most interested in 
average case behavior. We can factor out symbol table complexity and 
similar problem areas (those that can be tackled by complexity reducing
"tricks") to get a first approximation of the complexity.

> Well, maybe it's not totally useless.  I guess I would worry if the
> compiler had to look at each node O(N**2) times.  Hmm.  N isn't usually
> very big in Ada, since it's not an expression language, but it can be --
> I've seen things like "X := (... 10_000 component positional aggregate ...);"
> in machine-generated code.  Note that Ada has a special rule for
> aggregates -- the compiler has to figure out the type of the aggregate
> *before* looking inside it.

Good point. Its hard to anticipate what will be done in machine generated 
code, well, actually its easy, I guess what I mean is that I'd never expect 
to see a 10_000 component positional aggregate in *my* code :-). 

> Anyway, in an *optimizing* compiler, overload resolution is probably not
> the bottleneck.

Sure. As I said this is really an academic sort of question. We can now
return to the "God only codes in Eiffel" threads. :-)

-- Brian