Access to Nonlocal Data on the Stack
Introduction: It is very important to know that how procedures access their data, specially the mechanism for finding data used within a procedure p but that does not belong to p. Access becomes more complicated in languages where procedures can be declared inside other procedures. We therefore begin with the simple case of C functions, and then introduce a language, ML, that permits both nested function declarations and functions as "first-class objects;" that is, functions can take functions as arguments and return functions as values. This capability can be supported by modifying the implementation of the run-time stack.
Data Access without Nested Procedures: In the C family of languages, all variables are defined either within a singlefunction or outside any function ("globally"). Most importantly, it is impossibleto declare one procedure whose scope is entirely within another procedure.Rather, a global variable v has a scope consisting of all the functions that followthe declaration of v, except where there is a local definition of the identifier v.
Variables declared within a function have a scope consisting of that function only, or part of it, if the function has nested blocks, as discussed in Section 1.6.3. For languages that do not allow nested procedure declarations, allocation of storage for variables and access to those variables is simple:
1. Global variables are allocated static storage. The locations of these variables remain fixed and are known at compile time. So to access any variable that is not local to the currently executing procedure, we simply use the statically determined address.
2. Any other name must be local to the activation at the top of the stack. We may access these variables through the topsp pointer of the stack.
An important benefit of static allocation for globals is that declared procedures may be passed as parameters or returned as results (in C, a pointer to the function is passed), with no substantial change in the data-access strategy. With the C static-scoping rule, and without nested procedures, any name nonlocal to one procedure is nonlocal to all procedures, regardless of how they are activated. Similarly, if a procedure is returned as a result, then any nonlocal name refers to the storage statically allocated for it.
Issues with Nested Procedures: Access becomes far more complicated when a language allows procedure declarationsto be nested and also uses the normal static scoping rule; that is, aprocedure can access variables of the procedures whose declarations surroundits own declaration, following the nested scoping rule described for blocks inSection 1.6.3. The reason is that knowing at compile time that the declarationof p is immediately nested within q does not tell us the relative positions oftheir activation records at run time. In fact, since either p or q or both may berecursive, there may be several activation records of p and/or q on the stack.
Finding the declaration that applies to a nonlocal name x in a nested procedurep is a static decision; it can be done by an extension of the static-scoperule for blocks. Suppose x is declared in the enclosing procedure q. findingthe relevant activation of q from an activation of p is a dynamic decision; it requiresadditional run-time information about activations. One possible solutionto this problem is to use "access links”.
A Language with Nested Procedure Declarations: The C family of languages and many other familiar languages do not supportnested procedures, so we introduce one that does. The history of nested proceduresin languages is long. Algol 60, an ancestor of C, had this capability,as did its descendant Pascal, a once-popular teaching language. Of the laterlanguages with nested procedures, one of the most influential is ML, and itis this language whose syntax and semantics we shall borrow (see the box on"More about ML" for some of the interesting features of ML):
ML is a functional language, meaning that variables, once declared and initialized, are not changed. There are only a few exceptions, such as the array, whose elements can be changed by special function calls.
Variables are defined, and have their unchangeable values initialized, by a statement of the form:
val (name) = (expression)
Functions are defined using the syntax:
fun (name) ( (arguments) ) = (body)
For function bodies we shall use let-statements of the form:
let (list of definitions) in (statements) end
The definitions are normally v a l or fun statements. The scope of each such definition consists of all following definitions, up to the in, and all the statements up to the end. Most importantly, function definitions can be nested. For example, the body of a function p can contain a let-statement that includes the definition of another (nested) function q. Similarly, q can have function definitions within its own body, leading to arbitrarily deep nesting of functions.