3.1 Evaluation
Execution of code can be accomplished by a variety of means ranging from direct interpretation of a form representing a program to invocation of compiled code produced by a compiler .
Evaluation is the process by which a program is executed in Common Lisp. The mechanism of evaluation is manifested both implicitly through the effect of the Lisp read-eval-print loop, and explicitly through the presence of the functions eval, compile, compile-file, and load. Any of these facilities might share the same execution strategy, or each might use a different one.
The behavior of a conforming program processed by eval and by compile-file might differ; see Section 3.2.2.3 (Semantic Constraints).
Evaluation can be understood in terms of a model in which an interpreter recursively traverses a form performing each step of the computation as it goes. This model, which describes the semantics of Common Lisp programs, is described in Section 3.1.2 (The Evaluation Model).
3.1.1 Introduction to Environments
A binding is an association between a name and that which the name denotes. Bindings are established in a lexical environment or a dynamic environment by particular special operators.
An environment is a set of bindings and other information used during evaluation (e.g., to associate meanings with names).
Bindings in an environment are partitioned into namespaces. A single name can simultaneously have more than one associated binding per environment, but can have only one associated binding per namespace.
3.1.1.1 The Global Environment
The global environment is that part of an environment that contains bindings with both indefinite scope and indefinite extent. The global environment contains, among other things, the following:
• bindings of dynamic variables and constant variables.
• bindings of functions, macros, and special operators.
• bindings of compiler macros.
• bindings of type and class names
• information about proclamations.
3.1.1.2 Dynamic Environments
A dynamic environment for evaluation is that part of an environment that contains bindings whose duration is bounded by points of establishment and disestablishment within the execution of the form that established the binding. A dynamic environment contains, among other things, the following:
• bindings for dynamic variables.
• information about active catch tags.
• information about exit points established by unwind-protect.
• information about active handlers and restarts.
The dynamic environment that is active at any given point in the execution of a program is referred to by definite reference as “the current dynamic environment,” or sometimes as just “the dynamic environment.”
Within a given namespace, a name is said to be bound in a dynamic environment if there is a binding associated with its name in the dynamic environment or, if not, there is a binding associated with its name in the global environment.
3.1.1.3 Lexical Environments
A lexical environment for evaluation at some position in a program is that part of the environment that contains information having lexical scope within the forms containing that position. A lexical environment contains, among other things, the following:
• bindings of lexical variables and symbol macros.
• bindings of functions and macros. (Implicit in this is information about those compiler macros that are locally disabled.)
• bindings of block tags.
• bindings of go tags.
• information about declarations.
The lexical environment that is active at any given position in a program being semantically processed is referred to by definite reference as “the current lexical environment,” or sometimes as just “the lexical environment.”
Within a given namespace, a name is said to be bound in a lexical environment if there is a binding associated with its name in the lexical environment or, if not, there is a binding associated with its name in the global environment.
3.1.1.3.1 The Null Lexical Environment
The null lexical environment is equivalent to the global environment.
Although in general the representation of an environment object is implementation-dependent, nil can be used in any situation where an environment object is called for in order to denote the null lexical environment.
3.1.1.4 Environment Objects
Some operators make use of an object, called an environment object, that represents the set of lexical bindings needed to perform semantic analysis on a form in a given lexical environment. The set of bindings in an environment object may be a subset of the bindings that would be needed to actually perform an evaluation; for example, values associated with variable names and function names in the corresponding lexical environment might not be available in an environment object.
The type and nature of an environment object is implementation-dependent. The values of environment parameters to macro functions are examples of environment objects.
The object nil when used as an environment object denotes the null lexical environment; see Section 3.1.1.3.1 (The Null Lexical Environment).
3.1.2 The Evaluation Model
A Common Lisp system evaluates forms with respect to lexical, dynamic, and global environments. The following sections describe the components of the Common Lisp evaluation model.
3.1.2.1 Form Evaluation
Forms fall into three categories: symbols, conses, and self-evaluating objects. The following sections explain these categories.
3.1.2.1.1 Symbols as Forms
If a form is a symbol, then it is either a symbol macro or a variable.
The symbol names a symbol macro if there is a binding of the symbol as a symbol macro in the current lexical environment (see define-symbol-macro and symbol-macrolet). If the symbol is a symbol macro, its expansion function is obtained. The expansion function is a function of two arguments, and is invoked by calling the macroexpand hook with the expansion function as its
first argument, the symbol as its second argument, and an environment object (corresponding to the current lexical environment) as its third argument. The macroexpand hook, in turn, calls the expansion function with the form as its first argument and the environment as its second argument. The value of the expansion function, which is passed through by the macroexpand hook, is a form. This resulting form is processed in place of the original symbol.
If a form is a symbol that is not a symbol macro, then it is the name of a variable, and the value of that variable is returned. There are three kinds of variables: lexical variables, dynamic variables,
and constant variables. A variable can store one object. The main operations on a variable are to read 1 and to write1 its value.
An error of type unbound-variable should be signaled if an unbound variable is referenced.
Non-constant variables can be assigned by using setq or bound 3 by using let. Figure 3–1 lists some defined names that are applicable to assigning, binding, and defining variables.
|
boundp let progv
defconstant let* psetq
defparameter makunbound set
defvar multiple-value-bind setq
lambda multiple-value-setq symbol-value
|| :- |
Figure 3–1. Some Defined Names Applicable to Variables
The following is a description of each kind of variable.
3.1.2.1.1.1 Lexical Variables
A lexical variable is a variable that can be referenced only within the lexical scope of the form that establishes that variable; lexical variables have lexical scope. Each time a form creates a lexical binding of a variable, a fresh binding is established.
Within the scope of a binding for a lexical variable name, uses of that name as a variable are considered to be references to that binding except where the variable is shadowed 2 by a form that establishes a fresh binding for that variable name, or by a form that locally declares the name special.
A lexical variable always has a value. There is no operator that introduces a binding for a lexical variable without giving it an initial value, nor is there any operator that can make a lexical variable be unbound.
Bindings of lexical variables are found in the lexical environment.
3.1.2.1.1.2 Dynamic Variables
A variable is a dynamic variable if one of the following conditions hold:
• It is locally declared or globally proclaimed special.
• It occurs textually within a form that creates a dynamic binding for a variable of the same name, and the binding is not shadowed 2 by a form that creates a lexical binding of the same variable name.
A dynamic variable can be referenced at any time in any program; there is no textual limitation on references to dynamic variables. At any given time, all dynamic variables with a given name refer to exactly one binding, either in the dynamic environment or in the global environment.
The value part of the binding for a dynamic variable might be empty; in this case, the dynamic variable is said to have no value, or to be unbound. A dynamic variable can be made unbound by using makunbound.
The effect of binding a dynamic variable is to create a new binding to which all references to that dynamic variable in any program refer for the duration of the evaluation of the form that creates the dynamic binding.
A dynamic variable can be referenced outside the dynamic extent of a form that binds it. Such a variable is sometimes called a “global variable” but is still in all respects just a dynamic variable whose binding happens to exist in the global environment rather than in some dynamic environment.
A dynamic variable is unbound unless and until explicitly assigned a value, except for those variables whose initial value is defined in this specification or by an implementation.
3.1.2.1.1.3 Constant Variables
Certain variables, called constant variables, are reserved as “named constants.” The consequences are undefined if an attempt is made to assign a value to, or create a binding for a constant variable, except that a ‘compatible’ redefinition of a constant variable using defconstant is permitted; see the macro defconstant.
Keywords, symbols defined by Common Lisp or the implementation as constant (such as nil, t, and pi), and symbols declared as constant using defconstant are constant variables.
3.1.2.1.1.4 Symbols Naming Both Lexical and Dynamic Variables
The same symbol can name both a lexical variable and a dynamic variable, but never in the same lexical environment.
In the following example, the symbol x is used, at different times, as the name of a lexical variable and as the name of a dynamic variable.
(let ((x 1)) ;Binds a special variable X
(declare (special x))
(let ((x 2)) ;Binds a lexical variable X
(+ x ;Reads a lexical variable X
(locally (declare (special x))
x)))) ;Reads a special variable X
→ 3
3.1.2.1.2 Conses as Forms
A cons that is used as a form is called a compound form.
If the car of that compound form is a symbol, that symbol is the name of an operator , and the form is either a special form, a macro form, or a function form, depending on the function binding of the operator in the current lexical environment. If the operator is neither a special operator
nor a macro name, it is assumed to be a function name (even if there is no definition for such a function).
If the car of the compound form is not a symbol, then that car must be a lambda expression, in which case the compound form is a lambda form.
How a compound form is processed depends on whether it is classified as a special form, a macro form, a function form, or a lambda form.
3.1.2.1.2.1 Special Forms
A special form is a form with special syntax, special evaluation rules, or both, possibly manipulating the evaluation environment, control flow, or both. A special operator has access to the current lexical environment and the current dynamic environment. Each special operator defines the manner in which its subexpressions are treated—which are forms, which are special syntax, etc.
Some special operators create new lexical or dynamic environments for use during the evaluation of subforms of the special form. For example, block creates a new lexical environment that is the same as the one in force at the point of evaluation of the block form with the addition of a binding of the block name to an exit point from the block.
The set of special operator names is fixed in Common Lisp; no way is provided for the user to define a special operator . Figure 3–2 lists all of the Common Lisp symbols that have definitions as special operators.
|
block let* return-from
catch load-time-value setq
eval-when locally symbol-macrolet flet macrolet tagbody
function multiple-value-call the
go multiple-value-prog1 throw
if progn unwind-protect labels progv
let quote
|| :- |
Figure 3–2. Common Lisp Special Operators
3.1.2.1.2.2 Macro Forms
If the operator names a macro, its associated macro function is applied to the entire form and the result of that application is used in place of the original form.
Specifically, a symbol names a macro in a given lexical environment if macro-function is true of the symbol and that environment. The function returned by macro-function is a function of two arguments, called the expansion function. The expansion function is invoked by calling the macroexpand hook with the expansion function as its first argument, the entire macro form as its
second argument, and an environment object (corresponding to the current lexical environment) as its third argument. The macroexpand hook, in turn, calls the expansion function with the form as its first argument and the environment as its second argument. The value of the expansion function, which is passed through by the macroexpand hook, is a form. The returned form is evaluated in place of the original form.
The consequences are undefined if a macro function destructively modifies any part of its form argument.
A macro name is not a function designator , and cannot be used as the function argument to functions such as apply, funcall, or map.
An implementation is free to implement a Common Lisp special operator as a macro. An implementation is free to implement any macro operator as a special operator , but only if an equivalent definition of the macro is also provided.
Figure 3–3 lists some defined names that are applicable to macros.
|*macroexpand-hook* macro-function macroexpand-1 defmacro macroexpand macrolet|
| :- |
Figure 3–3. Defined names applicable to macros
3.1.2.1.2.3 Function Forms
If the operator is a symbol naming a function, the form represents a function form, and the cdr of the list contains the forms which when evaluated will supply the arguments passed to the function.
When a function name is not defined, an error of type undefined-function should be signaled at run time; see Section 3.2.2.3 (Semantic Constraints).
A function form is evaluated as follows:
The subforms in the cdr of the original form are evaluated in left-to-right order in the current lexical and dynamic environments. The primary value of each such evaluation becomes an argument to the named function; any additional values returned by the subforms are discarded.
The functional value of the operator is retrieved from the lexical environment, and that function is invoked with the indicated arguments.
Although the order of evaluation of the argument subforms themselves is strictly left-to-right, it is not specified whether the definition of the operator in a function form is looked up before the evaluation of the argument subforms, after the evaluation of the argument subforms, or between the evaluation of any two argument subforms if there is more than one such argument subform. For example, the following might return 23 or 24.
(defun foo (x) (+ x 3))
(defun bar () (setf (symbol-function ’foo) #’(lambda (x) (+ x 4))))
(foo (progn (bar) 20))
A binding for a function name can be established in one of several ways. A bind ing for a function name in the global environment can be established by defun, setf of fdefinition, setf of symbol-function, ensure-generic-function, defmethod (implicitly, due to ensure-generic-function), or defgeneric. A binding for a function name in the lexical environment can be established by flet or labels.
Figure 3–4 lists some defined names that are applicable to functions.
|
apply fdefinition mapcan
call-arguments-limit flet mapcar
complement fmakunbound mapcon
constantly funcall mapl
defgeneric function maplist
defmethod functionp multiple-value-call defun labels reduce
fboundp map symbol-function
|| :- |
Figure 3–4. Some function-related defined names
3.1.2.1.2.4 Lambda Forms
A lambda form is similar to a function form, except that the function name is replaced by a lambda expression.
A lambda form is equivalent to using funcall of a lexical closure of the lambda expression on the given arguments. (In practice, some compilers are more likely to produce inline code for a lambda form than for an arbitrary named function that has been declared inline; however, such a difference is not semantic.)
For further information, see Section 3.1.3 (Lambda Expressions).
3.1.2.1.3 Self
A form that is neither a symbol nor a cons is defined to be a self-evaluating object. Evaluating such an object yields the same object as a result.
Certain specific symbols and conses might also happen to be “self-evaluating” but only as a special case of a more general set of rules for the evaluation of symbols and conses; such objects are not considered to be self-evaluating objects.
The consequences are undefined if literal objects (including self-evaluating objects) are destructively modified.
3.1.2.1.3.1 Examples of Self
*Numbers*, *pathnames*, and *arrays* are examples of *self-evaluating objects*.
3 → 3
#c(2/3 5/8) → #C(2/3 5/8)
#p"S:[BILL]OTHELLO.TXT" → #P"S:[BILL]OTHELLO.TXT"
#(a b c) → #(A B C)
"fred smith" → "fred smith"
3.1.3 Lambda Expressions
In a lambda expression, the body is evaluated in a lexical environment that is formed by adding the binding of each parameter in the lambda list with the corresponding value from the arguments to the current lexical environment.
For further discussion of how bindings are established based on the lambda list, see Section 3.4 (Lambda Lists).
The body of a lambda expression is an implicit progn; the values it returns are returned by the lambda expression.
3.1.4 Closures and Lexical Binding
A lexical closure is a function that can refer to and alter the values of lexical bindings established by binding forms that textually include the function definition.
Consider this code, where x is not declared special:
(defun two-funs (x)
(list (function (lambda () x))
(function (lambda (y) (setq x y)))))
(setq funs (two-funs 6))
(funcall (car funs)) → 6
(funcall (cadr funs) 43) → 43
(funcall (car funs)) → 43
The function special form coerces a lambda expression into a closure in which the lexical environment in effect when the special form is evaluated is captured along with the lambda expression.
The function two-funs returns a list of two functions, each of which refers to the binding of the variable x created on entry to the function two-funs when it was called. This variable has the value 6 initially, but setq can alter this binding. The lexical closure created for the first lambda expression does not “snapshot” the value 6 for x when the closure is created; rather it captures the binding of x. The second function can be used to alter the value in the same (captured) binding (to 43, in the example), and this altered variable binding then affects the value returned by the first function.
In situations where a closure of a lambda expression over the same set of bindings may be produced more than once, the various resulting closures may or may not be identical, at the discretion of the implementation. That is, two functions that are behaviorally indistinguishable might or might not be identical. Two functions that are behaviorally distinguishable are distinct. For example:
(let ((x 5) (funs ’()))
(dotimes (j 10)
(push #’(lambda (z)
(if (null z) (setq x 0) (+ x z)))
funs))
funs)
The result of the above form is a list of ten closures. Each requires only the binding of x. It is the same binding in each case, but the ten closure objects might or might not be identical. On the other hand, the result of the form
(let ((funs ’()))
(dotimes (j 10)
(let ((x 5))
(push (function (lambda (z)
(if (null z) (setq x 0) (+ x z))))
funs)))
funs)
is also a list of ten closures. However, in this case no two of the closure objects can be identical because each closure is closed over a distinct binding of x, and these bindings can be behaviorally distinguished because of the use of setq.
The result of the form
(let ((funs ’()))
(dotimes (j 10)
(let ((x 5))
(push (function (lambda (z) (+ x z)))
funs)))
funs)
is a list of ten closure objects that might or might not be identical. A different binding of x is involved for each closure, but the bindings cannot be distinguished because their values are the same and immutable (there being no occurrence of setq on x). A compiler could internally transform the form to
(let ((funs ’()))
(dotimes (j 10)
(push (function (lambda (z) (+ 5 z)))
funs))
funs)
where the closures may be identical.
It is possible that a closure does not close over any variable bindings. In the code fragment (mapcar (function (lambda (x) (+ x 2))) y)
the function (lambda (x) (+ x 2)) contains no references to any outside object. In this case, the same closure might be returned for all evaluations of the function form.
3.1.5 Shadowing
If two forms that establish lexical bindings with the same name N are textually nested, then references to N within the inner form refer to the binding established by the inner form; the inner binding for N shadows the outer binding for N. Outside the inner form but inside the outer one, references to N refer to the binding established by the outer form. For example:
(defun test (x z)
(let ((z (* x 2)))
(print z))
z)
The binding of the variable z by let shadows the parameter binding for the function test. The reference to the variable z in the print form refers to the let binding. The reference to z at the end of the function test refers to the parameter named z.
Constructs that are lexically scoped act as if new names were generated for each object on each execution. Therefore, dynamic shadowing cannot occur. For example:
(defun contorted-example (f g x)
(if (= x 0)
(funcall f)
(block here
(+ 5 (contorted-example g
#’(lambda () (return-from here 4))
(- x 1))))))
Consider the call (contorted-example nil nil 2). This produces 4. During the course of execution, there are three calls to contorted-example, interleaved with two blocks:
(contorted-example nil nil 2)
(block here1 ...)
(contorted-example nil #’(lambda () (return-from here1 4)) 1)
(block here2 ...)
(contorted-example #’(lambda () (return-from here1 4))
#’(lambda () (return-from here2 4))
\0)
(funcall f)
where f → #’(lambda () (return-from here1 4))
(return-from here1 4)
At the time the funcall is executed there are two block exit points outstanding, each apparently named here. The return-from form executed as a result of the funcall operation refers to the outer outstanding exit point (here1), not the inner one (here2). It refers to that exit point textually visible at the point of execution of function (here abbreviated by the #’ syntax) that resulted in creation of the function object actually invoked by funcall.
If, in this example, one were to change the (funcall f) to (funcall g), then the value of the call (contorted-example nil nil 2) would be 9. The value would change because funcall would cause the execution of (return-from here2 4), thereby causing a return from the inner exit point (here2).
When that occurs, the value 4 is returned from the middle invocation of contorted-example, 5 is added to that to get 9, and that value is returned from the outer block and the outermost call to contorted-example. The point is that the choice of exit point returned from has nothing to do with its being innermost or outermost; rather, it depends on the lexical environment that is packaged up with a lambda expression when function is executed.
3.1.6 Extent
Contorted-example works only because the function named by f is invoked during the extent of the exit point. Once the flow of execution has left the block, the exit point is disestablished. For example:
(defun invalid-example ()
(let ((y (block here #’(lambda (z) (return-from here z)))))
(if (numberp y) y (funcall y 5))))
One might expect the call (invalid-example) to produce 5 by the following incorrect reasoning: let binds y to the value of block; this value is a function resulting from the lambda expression. Because y is not a number, it is invoked on the value 5. The return-from should then return this value from the exit point named here, thereby exiting from the block again and giving y the value 5 which, being a number, is then returned as the value of the call to invalid-example.
The argument fails only because exit points have dynamic extent. The argument is correct up to the execution of return-from. The execution of return-from should signal an error of type control-error, however, not because it cannot refer to the exit point, but because it does correctly refer to an exit point and that exit point has been disestablished.
A reference by name to a dynamic exit point binding such as a catch tag refers to the most recently established binding of that name that has not been disestablished. For example:
(defun fun1 (x)
(catch ’trap (+ 3 (fun2 x))))
(defun fun2 (y)
(catch ’trap (* 5 (fun3 y))))
(defun fun3 (z)
(throw ’trap z))
Consider the call (fun1 7). The result is 10. At the time the throw is executed, there are two outstanding catchers with the name trap: one established within procedure fun1, and the other within procedure fun2. The latter is the more recent, and so the value 7 is returned from catch in fun2. Viewed from within fun3, the catch in fun2 shadows the one in fun1. Had fun2 been defined as
(defun fun2 (y)
(catch ’snare (* 5 (fun3 y))))
then the two exit points would have different names, and therefore the one in fun1 would not be shadowed. The result would then have been 7.
3.1.7 Return Values
Ordinarily the result of calling a function is a single object. Sometimes, however, it is convenient for a function to compute several objects and return them.
In order to receive other than exactly one value from a form, one of several special forms or macros must be used to request those values. If a form produces multiple values which were not requested in this way, then the first value is given to the caller and all others are discarded; if the form produces zero values, then the caller receives nil as a value.
Figure 3–5 lists some operators for receiving multiple values2. These operators can be used to specify one or more forms to evaluate and where to put the values returned by those forms.
|
multiple-value-bind multiple-value-prog1 return-from multiple-value-call multiple-value-setq throw
multiple-value-list return
|| :- |
Figure 3–5. Some operators applicable to receiving multiple values
The function values can produce multiple values2. (values) returns zero values; (values form) returns the primary value returned by form; (values form1 form2) returns two values, the primary value of form1 and the primary value of form2; and so on.
See multiple-values-limit and values-list.