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: bobduff@world.std.com (Robert A Duff) Subject: Re: The Red Language Date: 1997/09/18 Message-ID: #1/1 X-Deja-AN: 273438642 References: <340E2DC5.25D7@worldnet.att.net> Organization: The World Public Access UNIX, Brookline, MA Newsgroups: comp.lang.ada Date: 1997-09-18T00:00:00+00:00 List-Id: 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. 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. Suppose the following declarations are visible: type Int1 is range 1..10; type Int2 is range 1..10; type Int3 is range 1..10; procedure P(X: Int1; Y: Int1); procedure P(X: Int2; Y: Int2); -- (*) procedure P(X: Int3; Y: Int3); function F(X: Int1) return Int1; function F(X: Int2) return Int2; -- (*) function G(X: Int2) return Int2; -- (*) function G(X: Int3) return Int3; And suppose we're trying to resolve this statement: P(F(1), G(2)); The correct answer is that P, F, and G denote the declarations that are marked with "-- (*)" above. It's easy to see that by trying all combinations of denotations. 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. To make the example more interesting, change it to: P(-(-(-(-(-(F(1)))))), -(-(-(-(-(G(2))))))); where P, F, and G resolve as in the previous example, but the necessary information is buried deep within each subtree. (All of the occurrences of "-" resolve to the predefined unary minus of type Int2.) We can't know which F we're talking about until we've propagated information all the way up from the literal 2, and we can't know which G we're talking about until we've propagated information all the way up from the literal 1. In C++ and Red, the above examples would be considered ambiguous. (I mean, of course, after converting the syntax as appropriate.) They're perfectly legal in Ada (if I haven't made any silly mistakes!). - Bob