| Guy L. Steele Jr. | 7 | LAMBDA: The Ultimate Declarative |
1.3. LAMBDA as a Renaming Operator
Environment operators also take various forms.
The most common are assignment to local variables and binding of arguments to functions, but there are others, such as pattern-matching operators (as in COMIT [MITRLE 62] [Yngve 72], SNOBOL [Forte 67], MICRO-PLANNER [Sussman 71], CONNIVER [McDermott 74], and PLASMA [Smith 75]).
It is usually to think of these operators as altering the contents of a named location, or of causing the value associated with a name to be changed.
In understanding the action of an environment operator it may be more fruitful to take a different point of view, which is that the value involved is given a new (additional) name.
If the name had previously been used to denote another quantity, then that former use is shadowed; but this is not necessarily an essential property of an environment operator, for we can often use alpha-conversion ("uniquization" of variable names) to avoid such shadowing.
It is not the names which are important to the computation, but rather the quantities; hence it is appropriate to focus on the quantities and think of them as having one or more names over time, rather than thinking of a name as having one or more values over time.
Consider our previous example involving BAR.
On entry to BAR two quantities are passed, either in registers or on the stack.
Within BAR these quantities are known as X and Y, and may be referred to by those names.
In other environments these quantities may be know by other names; if the code in BAR's caller were (BAR W (+ X 3)), then the first quantity is known as W and the second has no explicit name.
{Note Return Address}
On entry to BAR, however, the LAMBDA assigns the names X and Y to those two quantities.
The fact that X means something else to BAR's caller is of no significance, since these names are for BAR's use only.
Thus the LAMBDA not only assigns names, but determines the extent of their significance (their scope).
Note an interesting symmetry here: control constructs determine constraints in time (sequencing) in a program, while environment operators determine constraints in space (textual extent, or scope).
One way in which the renaming view of LAMBDA may be useful is in allocation of temporaries in a compiler.
Suppose that we use a targeting and preferencing scheme similar to that described by in [Wulf 75] and [Johnsson 75].
Under such a scheme, the names used in a program are partitioned by the compiler into sets called "preference classes".
The grouping of several names into the same set indicates that it is preferable, other things being equal, to have the quantities referred to by those names reside in the same memory location at run time; this may occur because the names refer to the same quantity or to related quantities (such as X and X+1).
A set may also have a specified target, a particular memory location which is preferable to any other for holding quantities named by members of the set.
As an example, consider the following code skeleton:
((LAMBDA (A B) <body>) (+ X Y) (* Z W))
Suppose that within the compiler the names T1 and T2 have been assigned to the temporary quantities resulting from the addition of multiplication.
Then to process the "binding" of A and B we need only add A to the preference class of T1, and B to the preference class of T2.
This will have the effect of causing A and T1 to refer to the same location, wherever that may be; similarly B and T2 will refer to the same locaiton.
If T1 is saved on a stack and T2 winds up in a register, fine; references to A and B within the <body> will automatically have this information.
On the other hand, suppose that <body> is (FOO 1 A B), where FOO is a
