Re: The Red Language

[bobduff@world.std.com (Robert A Duff)]

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.  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