The preliminary analysis ("phase 1") is in three passes, each involving a tree-walk of the node structure, filling in information slots at each node. (Two passes would have sufficed, but for reasons of clarity and modularity there is one pass for each type of analysis.)
The first pass (ENV-ANALYZE) analyzes variable references. For each node
we determine the set of all local (bound) variables referenced at or below that
node. For example, for a variable-reference node this set is empty (for a global
variable), or the singleton set of the variable itself (for a local variable);
for a LAMBDA-expression, it is the set for its body minus the variables bound by
that LAMBDA-expression; for an IF-expression, it is the union of the sets for
the predicate, consequent, and alternative; and so on. We also compute for each
node the set of bound variables which appear in an ASET' at or below the node.
(This set will be a subset of the first set, but no non-trivial use of this
property is used in this pass.) Finally, for each variable we store several
properties on its property list, including a list of all nodes which reference
the variable (for "reading") and a list of of all ASET' nodes which modify the
variable. These lists are built incrementally, with an entry added as each
reference is encountered during the tree walk. (This exemplifies the general
strategy for passing data around; any information which cannot be passed
conveniently up and down the tree, but which must jump laterally between
branches, is accumulated on the property lists of the variables. It may appear
to be "lucky" that all such information has to do with variables, but this is
actually an extremely deep property of our notation. The entire point of using
identifiers is to relate textually separated constructions. we depend on alpha-conversion to give all variables distinct names (by "names" we really mean
