Nested Lexical Contours

Within the body of a function, additional local variables may be created using the LET special function. Consider the following:


\begin{code} (defun average (x y) (let ((sum (+ x y))) (list x y 'average (/ sum 2)))) \end{code}

Figure: Evaltrace diagram showing a local contour.
\begin{figure}{\noindent\rule{\textwidth}{.01in}} \par \begin{evaltrace} +--> ;(... ...GE 5) \end{evaltrace}\par\par {\noindent\rule{\textwidth}{.01in}} \end{figure}

An evaltrace diagram for AVERAGE is shown in Figure [*]. Notice that the lexical contour associated with the LET body is drawn as a hollow arrow rather than a solid arrow. A solid arrow indicates that the parent contour is the global contour. The hollow arrow in this diagram indicates that the parent contour is the immediately enclosing contour. Thus the parent contour of the LET body is the contour generated by the body of AVERAGE. AVERAGE's parent contour is the global contour. When evaluating the symbol SUM inside the LET body, we find that there is a variable by that name in the current contour. But when evaluating X and Y in the LET body, we find we must go look in the parent contour. Since there are local variables named X and Y in the contour of AVERAGE, the symbols X and Y are taken to refer to those variables. (This example also illustrates another of Lisp's evaluation rules: quoted objects evaluate to themselves, without the quote.)

Now we can present an example that highlights the distinction between lexical and dynamic scoping. Notice below that there is both a global variable N with value 1000, and a local variable N in the argument list of PARENT. PARENT calls CHILD, which contains the symbol N in its body. To which variable does CHILD's N refer?


\begin{code} (setf n 1000) \strut (defun parent (n) (child (+ n 2))) \strut (defun child (p) (list n p)) \end{code}

Under lexical scoping, every function has associated with it, as part of its definition, a parent contour. Functions defined at the top level with DEFUN always have the global contour as their parent. (We'll have more to say later about how contours are associated with functions that are not defined at the top level.) A function's environment is the set of objects visible within its contour, in other words, objects that reside in its own contour, or in its parent contour, or in its parent contour's parent contour, and so on. Functions can only access those variables that are visible within their environment. Variables that have the same name ``shadow'' each other. For instance, a variable N in the current contour would shadow a variable N in the parent contour, so the latter would not be visible.

In evaltrace diagrams, environments are depicted graphically via the chain of nested contours that define them. Most contours drawn with a hollow arrow (such as LET contours) have the immediately surrounding contour as their parent, while contours for functions defined at top level are drawn with a solid arrow, indicating that their parent contour is the global contour.

Figure: Evaltrace diagram illustrating lexical scoping.
\begin{figure}{\noindent\rule{\textwidth}{.01in}} \par \begin{evaltrace} ;{\it t... ...00 5) \end{evaltrace}\par\par {\noindent\rule{\textwidth}{.01in}} \end{figure}

Getting back to our present example, the lexical scope rules dictate that the symbol N inside the body of CHILD must refer to the global variable N, not to PARENT's local N. This is illustrated by the evaltrace diagram in Figure [*]. CHILD's environment consists of its own contour (in which the variable P resides), and its parent contour, which is the global contour. Since CHILD doesn't have a local variable named N, the symbol N in its body must refer to the global N, whose value is 1000. PARENT's local variable N is completely invisible to CHILD, since PARENT's contour is not part of CHILD's environment.

This scheme is called lexical scoping because environments mirror the nesting structure of the code. Since CHILD isn't defined inside of PARENT, none of PARENT's local variables are visible to it. We'll say more about the relationship between textual nesting and environments in the next section.

Early Lisp dialects, from Lisp 1.5 up through MacLisp and InterLisp—and APL and SNOBOL as well—use dynamic rather than lexical scoping [1]. In dynamic scoping functions do not have parent contours permanently associated with them; instead each contour uses the most recently created contour as its parent. Thus, environments are determined dynamically rather than statically. If the preceding example were tried in a dynamically scoped Lisp, the parent contour of CHILD would be the one created by PARENT, and the result of the evaluation would be different, as shown in Figure [*].

Figure: Evaltrace diagram illustrating dynamic scoping.
\begin{figure}{\noindent\rule{\textwidth}{.01in}} \par \begin{evaltrace} ;{\it t... ...o 3 +_\end{evaltrace}\par\par {\noindent\rule{\textwidth}{.01in}} \end{figure}

Dynamic scoping was used in early Lisp dialects because in an interpreter it is the most straightforward scoping discipline to implement efficiently. (This turns out not to be the case when compiling. This is one reason that modern dialects of Lisp which are compiled as well as interpreted, such as Common Lisp, are lexically scoped.) In evaltrace diagrams, the nesting of contours accurately reflects the structure of the call stack of an interpreter, with the inner-most contour being the top of the stack and the global contour at the bottom. So, we will often refer to the nesting of contours as the call stack. Dynamic scoping allows the call stack to be used as the environment, which means that the contours in evaltrace diagrams are drawn only with hollow, never solid, arrows.