Overload Resolution in Ada (Re: The Red Language)

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

My apologies for the off topic post...

On Thu, 18 Sep 1997, Robert A Duff wrote:
> In article <Pine.SGI.3.95.970916190053.19184D-100000@shellx.best.com>,
> Brian Rogoff  <bpr@shellx.best.com> wrote:
> >Is this second pass strictly necessary? I seem to remember reading that it 
> >is possible to do overload resolution in one pass in Ada.
> 
> Well, I suppose you can always do a two-pass algorithm in one pass, by
> having a sufficienty complicated back-patching scheme or some such.  I
> read a paper a long time ago about one-pass overload resolution in Ada,
> and my impression was that the one-pass algorithm was basically
> calculating (during the first pass) all possible results that *might*
> occur on the second pass, and then throwing all but one of them away,
> thus avoiding the need for the second pass.

OK, I cracked open my compiler reference (Dragon book, if you care) to
refresh my memory, and in the bibliographic notes to chapter 6 we find, 
after a mention of the straightforward two pass algorithms 

	... Baker (1982) avoids an explicit backward pass by carrying along 
	a DAG of possible types.  

where the paper cited is 

	Baker, T.P. (1982) "A one-pass algorithm for overload resolution 
	in Ada"  TOPLAS 4:4 601-614

I haven't read this paper, but from that one line description it appears 
that you are correct as to the approach. I'll try to find a copy and 
confirm this.

> This seemed silly at the
> time -- it seemed like the so-called one-pass algorithm would be more
> complicated to program, and less efficient, than the two-pass algorithm.

Out of curiosity, what is the worst case running time(s) of the two pass 
algorithm(s)?
 
> <... nice example arguing for two-passedness deleted ...> 
> 
> The denotation of F is determined in part by the possible denotations of
> G, and vice versa.  This seems fundamentally two-pass to me -- I don't
> like to call it "one pass" if the one pass is doing all the work of all
> possible second passes.

I agree that the two pass algorithm is obvious, and that (what I am
guessing Baker does) is cheating :-), but I did write "strictly speaking". 

-- Brian