Re: The Red Language

[dewar@merv.cs.nyu.edu (Robert Dewar)]

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


Whether you call things one pass or two pass is to some extent just an
excercise in semantics. But when I say that two passes is fundamental,
what I mean is that before assigning the proper type to a given node,
it is necessary to visit nodes both above you and below you in the tree.
That means there is no canonical traversal scheme which allows you to
visit nodes just once. 

OK, of course you can visit nodes just once and then build a list of
results which are accessed separately, but by one pass scheme I would
mean a scheme that operates as follows.

There is a canonical traversal of the operator tree which visits nodes
one by one and assigns types to each node at the time they are visited.

Any other definition of one pass is unuseful. For example, the more flexible
definition would lead one to consider all compilers one pass because they
only look at the source once, and from then on they are dealing with
auxiliary data structures -- not a useful definition.

Note that in Algol-68, which uses operand type overloading only, there is
indeed a one pass algorithm in the sense I define it above.