From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,8f8cea8602e61aba X-Google-Attributes: gid103376,public From: Brian Rogoff Subject: Overload Resolution in Ada (Re: The Red Language) Date: 1997/09/18 Message-ID: #1/1 X-Deja-AN: 273674205 References: <340E2DC5.25D7@worldnet.att.net> X-Trace: 874632697 27476 (none) 206.86.0.12 Newsgroups: comp.lang.ada Date: 1997-09-18T00:00:00+00:00 List-Id: My apologies for the off topic post... On Thu, 18 Sep 1997, Robert A Duff wrote: > In article , > Brian Rogoff 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