.c	Friday  June 17,1983  1:25  NM+6D.13H.45M.41S.  -*- Bolio -*-

.chapter "Scope, Extent, and Binding"
.setq scope-extent-and-binding-chapter-number chapter-number
.setq scope-extent-and-binding-section-page section-page
.setq nil-value-cell-and-bindings-section-page section-page

The lan{nil} interpreter uses lexical scoping.  What this means,
simply, is that variable references which are "textually within" the
code which binds them, are valid.  Those references which are not
"textually within" the binding form are not, and will (typically)
cause unbound-variable errors.  Consider the definition
.lisp
(defun make-associations (keys single-value)
   (mapcar #'(lambda (key) (cons key single-value)) keys))
.end_lisp
which takes a list of keys (perhaps for use by 3assoc*), and
returns an association list associating all of those keys with the
same single value.  The first argument to 3mapcar*, the lambda
expression, is technically a function.  (The 3#'* construct is
explained below.)  It is, however, textually
within the binding of the argument 3single-value*, so that
variable reference is lexical, and that function works in lan{nil}
as desired.  Consider the alternative form
.lisp
(defun make-associations (keys single-value)
   (mapcar #'make-one-association keys))
(defun make-one-association (key)
   (cons key single-value))
.end_lisp
which might appear to be equivalent.  The reference to
3single-value* in the definition of 3make-one-association* is
2not* textually within the binding of that variable, hence appears
"free".  Although this function (in the absence of extra declarations,
as described below) would function "properly" in the lan{maclisp} or
lan{zetalisp} interpreters, it will not in lan{nil}.  It is
interesting to note that  (again without special declarative
information) both the lan{maclisp} and lan{zetalisp} compilers
will treat the second example as an error (or at least produce
incorrect code), because although the interpreters do not enforce
lexical scoping rules, code is compiled that way.

A short note may be in order on the 3#'* construct which
appeared above is in order.  3#'* is an abbreviation for
3(function ...)*, just as 3'* is an abbreviation for
3(quote ...)*.  In lan{maclisp}, the
two are equivalent.  However, in lan{nil} (and to some extent in
lan{zetalisp} too), use of this special form is necessary to cause
the proper (functional) interpretation of the form being evaluated.
In fact, in the 3make-associations* example, it is that special
interpretation which makes the lexical reference to 3single-value*
"work".  If 3quote* was used instead of 3function*, the example
would not work as desired.  3function* (or 3#'*) need not just be
used around lambda expressions.  It may also be used around function
names (as in the second 3make-associations* example).  The effect of
evaluating 3(function 2name*)* is equivalent to what the
interpreter does when it "evaluates" 2name* in the function position
of a list being evaluated.

lan{Nil} does not restrict one to using only lexical scoping rules.
It is possible to declare to lan{nil} that a variable is
term_i{special}, and should be able to be referenced by code
2not* textually within the binding construct.  Or, perhaps a
variable should have a global toplevel value and not be bound
anywhere, or maybe even have a toplevel value, and be bound in some
places.  This is the purpose of the 3special* declaration, which
lan{nil} implements compatibly with lan{common lisp}, and which is
about the same as it is in lan{zetalisp} and lan{maclisp}.

Most of the time, term_i{special variables} are declared to be
special globally.  This means that the lan{nil} interpreter (and
compiler) will always treat the variable as being special, even if
there is no declaration for it at the place it is bound.  As a matter
of style, variables declared 3special* are usually given names
which begin and end with the character 3** so that they can be
visually distinguished from more "ordinary" lexically scoped
variables.  One way to globally declare a variable 3special* is
with 3defvar* ((defvar-fun)).  For instance,
.lisp
(defvar *leaves*)
(defun find-all-leaves (tree)
  (let ((*leaves* nil))		;1Empty set of leaves*
    (find-all-leaves-1 tree)	;1Grovel over the tree*
    *leaves*			;1And return the leaves found*
    ))
(defun find-all-leaves-1 (tree)
  (cond ((atom tree)
	   (cond ((not (memq tree *leaves*))
		  (setq *leaves* (cons tree *leaves*)))))
	(t (find-all-leaves-1 (car tree))
	   (find-all-leaves-1 (cdr tree)))))
.end_lisp
There are more esoteric (or lan{scheme}-like) ways in which the
above could have been performed, without the use of the special
variable 3*leaves**, but the above is fairly straightforward,
fairly efficient, and will also run (both interpreted and compiled)
compatibly in lan{maclisp} and lan{zetalisp}.

The above intuitive (or, if you prefer, hand-waving and vague)
description can now be used to more formally define the terms of
term_i{scope} and term_i{extent} which are used to describe the
accessibility and lifetimes of things, of which variable bindings are
one instance.  The 2scope* of something tells 2where* it may
be validly referred to.  To say that something has term_i{lexical
scope} then means that it may be used anywhere "textually" within the
construct which "creates" the object (e.g., the lambda-expression
which binds a variable).  Note that this does not in itself imply that
the reference becomes invalid if that construct is exited.  That
dimension is the term_i{extent} of the object, which tells the
2time* during which the object (e.g., variable binding) is valid.
term_i{dynamic extent} means that the object (reference) is only
valid during the execution of the construct.  term_i{indefinite
extent} means that there is no such limitation.  Variable bindings in
the lan{nil} interpreter (which are not 3special*) have lexical
scope and indefinite extent.  This means upward funarg capability.

term_i{indefinite scope} means that there is no restriction on where
a valid reference may occur from.  This is the case with 3special*
variables;  the "free" references may be made from any piece of code.
The bindings of such variables, however, have only term_i{dynamic
extent};  they become invalid (are "unbound") when the binding
construct is exited.  This combination of scope and extent, which is
quite common, is referred to as term_i{dynamic scope}.

Now, for the pragmatics.  The current lan{nil} compiler actually
only implements local scope instead of lexical scope.  Its
capabilities lie only in determining when it is losing.  In many
cases, this does not matter because the constructs being used are
expanded out into other constructs, making the references local.  This
is what happens for fun{mapcar}, for instance:  in the construct
.lisp
(let ((zz (computate)))
   (mapc #'(lambda (x) (mumblify x zz)) some-list))
.end_lisp
the reference to 3zz* within the lambda expression is a non-local
(but lexical) reference.  That expression is recoded by the compiler,
however, as an iteration without a separate function, in which the
reference become local.
.english
This is actually a moderately standard way to handle lexical
variables;  rewrite the form when possible to cause the reference to
become local.  The lan{maclisp} compiler does this with the mapping
functions:  even if the open-code-map switch is turned off, if such a
reference occurs it will expand out the iteration to allow the local
reference.
.end_english

Environment transfer is implemented with term_i{closures}.  A closure
is essentially an encapsulation of a function, and some portion of a
binding environment.  The closures with which lexical
environment transfer is performed in the interpreter,
term_i{interpreter closures}, bundle up the lexical environment as
of the time of their creation.  Thus,
.lisp
(setq fn (let ((x 5)) (function (lambda () x))))
  => #<Interpreter-Closure (Anon) 1 259ABC>
(funcall fn)
  => 5
.end_lisp
One may test for a closure in general with 3(typep 2x*
'closure)*, or with the fun_i{closurep} predicate
((closurep-fun)).

lan{Nil} actually has the capability for giving "dynamic" variables
2indefinite* extent.  This can be used to implement old-fashioned
closures as created by the Lisp Machine fun_i{closure} function
(which exists in lan{nil}).

In lan{nil}, what has been said for 2variables* as far as
scope, extend, binding, and shadowing is concerned, is equally true
for 2functions*.  Variable value and function value are handled in
virtually identical fashions.  The primary differences between the two
are that the interpreter does not warn you when you create a new
toplevel special function value (it does when you create a new
toplevel special variable value when the variable is not globally
declared special), and the compiler makes its kwd{special}
assumption quietly.

The design of the lan{nil} binding mechanism is described by White in
ref{NIL-Bind}.


.section "Lambda Application"
.setq lambda-list-section-page section-page
.cindex lambda lists
Application of a lambda expression in lan{nil} is much like that of
lan{lispm}.  A lambda expression is of the general form
.lisp
(lambda 2lambda-list* {2declaration*}* {2form*}*)
.end_lisp
In the simplest case, 2lambda-list* is a (possibly empty) list of
variable names, which are the formal parameters to the lambda
expression when it is treated as a function.  There must be as many
arguments to the lambda-expression as there are variables.  Thus,
.lisp
((lambda (a b c) (list a b c)) 1 2 (+ 3 4))
 => (1 2 7)
.end_lisp

The lambda-list may also contain special symbols which begin with the
character 3&*.  These are often called term_i{lambda list
keywords}, but they are "keywords" only in the general sense, i.e.,
they are not typed in with a preceding colon.
They are typically used to drive the matching of
the formal parameters (variables) in the lambda list with the values
they should be bound to.  There are basically just four such keywords,
each of which is optional, and which should appear in the order they
are shown in:
.table 3 250 250 0 0 0
.item &optional
.cindex &optional lambda-list keyword
The items from the 3&optional* to the next &-keyword (or end of
the lambda-list) describe optional arguments to the function.  Each
such item may be of one of the following forms:
.table 2 250 250 0 0 0
.item variable
If a corresponding argument is supplied, then 2variable* will be
bound to that.  Otherwise, it will be bound to 3nil*.
.item 7(*variable7)*
Same as an isolated 2variable*.
.item 7(*variable init-form7)*
If there is a corresponding argument, then 2variable* is bound to
that.  If not, then 2init-form* is evaluated, and 2variable*
bound to that result.  The evaluation of 2init-form* is performed
in an environment where all of the variables in the lambda list to the
left of this one have been bound already.
.item 7(*variable init-form init-p-var7)*
Just like the previous format.  Additionally, 2init-p-var* will be
bound to 3t* if there was an argument supplied, 3nil* if not.
.end_table
.item &rest
There must be exactly one item between an 3&rest* keyword and the
next &-keyword (or the end of the lambda-list).  This variable is
bound to a list of all the remaining arguments to the function.
.item &key
.cindex &key lambda-list keyword
The items between 3&key* and either 3&aux* or the end of the
lambda-list describe term_i{keyworded arguments} to the function.
These are arguments which are passed by keyword rather than by
position:  when given, it must be preceded by the keyword naming which
argument it is.  For example, the calls
.lisp
(fill sequence new-item :start start :end end)
(fill sequence new-item :end end :start start)
.end_lisp
are effectively the same.  All keyworded arguments are by default
optional.  The specification of a keyworded argument in the lambda
list is normally the same as that of an optional argument.  The name
of the variable is used to generate the keyword which flags that
particular parameter.
For instance, 3fill* is defined with the lambda-list
.lisp
(sequence item &key (start 0) end)
.end_lisp
Additionally, with the non-atomic forms of optional parameter
specification, a list of the actual keyword
which should be used and the variable to bind the argument to may be
used instead.  For example, if it were desired that the keyword
3:start* be used to flag the starting index, but that the formal
parameter be named 3i*, then the lambda-list could have been
written as
.lisp
(sequence item &key ((:start i) 0) end)
.end_lisp
It is important to note that if both 3&key* and 3&rest* are
given, then the list the 3&rest* variable is bound to is 2the
same* list from which the keyworded arguments are extracted.  This
is sometimes useful if the arguments are going to be passed en-mass to
some other function using 3apply*, or perhaps to reconstruct the
original arguments to the function in order to signal an error.
.item &aux
.cindex &aux lambda-list keyword
Bindings specified with 3&aux* are for term_i{auxiliary
variables};  they have no correspondence to the "arguments" given to
the lambda expression.  The only things which may follow 3&aux* in
the lambda list are bindings specs for these auxiliary variables,
which may take one of the following forms:
.table 2 250 250 0 0 0
.item variable
2variable* will be bound to 3nil*.
.item 7(*variable7)*
2variable* will be bound to 3nil*.  However, because this
syntax may eventually be either disallowed or made to mean something
else, one should use either just 2variable* or 3(2variable*
nil)*.
.item 7(*variable init-form7)*
2init-form* is evaluated, and 2variable* bound to the result.
.end_table
The first 3&aux* 2init-form* is evaluated within the
environment produced by the preceding portion of the lambda list.  As
each 3&aux* binding specification is processed, the variable is
bound, and will be available to any following 2init-form*s.
Because the stuff with 3&aux* has little to do with the lambda
application, it may be clearer for the body of the lambda expression
to be wrapped in 3let* ((let-fun)) or 3let** ((let*-fun));
in fact, the portion of the lambda list following 3&aux* could be
given as the binding-list to 3let**, and have the same meaning.
.end_table

The use of 3&rest* in lan{nil} results in consing.  If the
'cindex &restv lambda-list keyword
keyword 3&restv* is used in place of 3&rest*, then the
variable will be bound to a term_i{stack vector} rather than to a
list.  This is an object which is a 2simple general vector*, but
has only 2dynamic extent*;  it loses its validity when the
function with 3&restv* in its lambda-list is exited.  Essentially,
the stack vector is just a pointer into the stack where the values are
'setq stack-vector-section-page section-page
stored.  This feature should be used with care, if at all.

