1. Preface

This paper is an adaptation of a report produced for X3J13 by the authors, a technical working group engaged in standardizing Common Lisp for ANSI

2. Introduction

In 1981 the emerging Common Lisp community turned to Scheme for some of its motivation and inspiration [Steele 1984]. Adopting lexical scoping proved one of the most important decisions the Common Lisp group ever made.

One aspect of Scheme that was not adopted, however, was a single namespace for functions and values, along with uniform evaluation rules for expressions in function and argument positions within the language. At the 1986 ACM Conference on Lisp and Functional Programming, members of a part of the European Lisp community (called the EuLisp group) involved in the design of a Lisp dialect suggested that Common Lisp should have adopted this paradigm and that it might still be appropriate to do so.

Many people in the Common Lisp community were unhappy about the proposed change. Technical, philosophical, and political arguments on both sides of the issue became quickly apparent. Since the issue is controversial, the Common Lisp community felt that the technical issues should be clearly documented before any decision was attempted.

This paper addresses those technical issues.

3. Notation and Terminology

We shall begin by establishing some standard terminology. Some readers may wish to skip this section and refer to it only if a question arises about some term.

A function is anything that may correctly be given to the FUNCALL or APPLY function and is to be executed as code when arguments are supplied. A nonfunction is any other Lisp object.

An identifier is the name of a symbol or a variable. This is not an exclusive partition: a variable can be a symbol. An identifier is essentially a print name.

A symbol is a Lisp data structure that has a value cell, a property list, a function cell (in Common Lisp), and so on.

A variable is an identifier that names a location

A binding is a pairing of an identifier with a location in which a Lisp object may be placed.

A lexical variable is a binding in which the identifier is not taken to refer to a symbol. A symbol with a value in its value cell is taken to be a binding in that the name of the symbol is paired with the value cell of the symbol. A special variable is a binding in which the identifier is taken to refer to a symbol.

An environment is the set of all bindings in existence at some given time. We shall call a subset of an environment a subenvironment.

A namespace is a subenvironment. Often the location parts of the bindings in a namespace contain objects used for some purpose, and the identifiers of the namespace are said to "name objects" used for that purpose; if the types of objects that can be stored in the location parts of bindings in a namespace are used for a purpose such that only objects of a certain type can be used for that purpose, then we say that "the objects in the namespace are restricted" to that type of object. The objects that are stored in the location parts of bindings in a namespace are not necessarily restricted to first-class Lisp objects. In this paper, there are two namespaces of concern, which we shall term the "value namespace" and the "function namespace." Other namespaces include tag names (used by TAGBODY and GO) and block names (used by BLOCK and RETURN-FROM), but the objects in the location parts of their bindings are not first-class Lisp objects.

The value namespace is a subenvironment whose location parts are not restricted to any particular kind of object. The purpose of this namespace is to associate values with variables when those variables occur in certain textual contexts. The binding of an identifier referring to a symbol along with a value cell is in the value namespace. Lexical variables, such as those introduced by LET, LAMBDA, and MULTIPLE-VALUE-BIND, are in the value namespace.

The function namespace is a subenvironment whose purpose is to associate functions with variables when those variables occur in certain textual contexts. We assume that the location parts of a function namespace always contain functions. The binding of an identifier referring to a symbol along with a function cell is always in the function namespace. Functional lexical variables, such as those introduced by FLET, LABELS, and MACROLET, are in the function namespace.

Lisp's evaluation rules tell, given an expression and an environment, how to produce a value or values and a new environment. In order to do this, the meanings of identifiers in a program text need to be determined, and this requires determining in which namespace to interpret the identifiers. For example, a symbol can have something in its value cell and something else in its function cell; which of these objects is referred to by the symbol in a piece of code depends upon which namespace is defined to be used for the context in which the symbol appears.

The function and value namespaces are distinct in Common Lisp because, given a single name, the function namespace mapping and the value namespace mapping can yield distinct objects. The two mappings might yield the same object, but that would be mere coincidence.

In this paper, we shall refer to two abstract dialects of Lisp called Lisp₁ and Lisp₂.

Lisp₁ has a single namespace that serves a dual role as the function namespace and value namespace; that is, its function namespace and value namespace are not distinct. In Lisp₁, the functional position of a form and the argument positions of forms are evaluated according to the same rules. Scheme [Rees 1986] and the language being designed by the EuLisp group [Padget 1986] are Lisp₁ dialects.

Lisp₂ has distinct function and value namespaces. In Lisp₂, the rules for evaluation in the functional position of a form are distinct from those for evaluation in the argument positions of the form. Common Lisp is a Lisp₂ dialect.

4. Historical Perspective

Most Lisp dialects adopted a two-namespace approach to the naming problem. To some extent this is because most dialects followed Lisp 1.5 [McCarthy 1965] or dialects derived from Lisp 1.5

Lisp 1.5 broke symbols into values and functions; values were stored on an association list, and function on the property lists of symbols. Compiled and interpreted code worked in different ways. In the interpreter, the association list was where all bindings were kept. When an identifier was encountered (an 'atomic symbol' in Lisp 1.5 terminology), it was taken as a variable to be evaluated for its value. First the APVAL part of the symbol was interrogated—an APVAL was "A Permanent, system-defined VALue" stored in a specific place in the symbol. Second, the association list was searched. Finally, if no binding was found, an error was signaled.

When a combination was encountered, the function position was evaluated differently from other positions. First, the symbol was interrogated to see whether there was a function definition associated with it; then the association list was searched.

Here we can see two namespaces at work, though nonsymbol variables were treated somewhat uniformly (Lisp 1.5 did not have lexical variables in interpreted code): when there were no function definitions associated with a symbol, there was one namespace, which was explicitly represented by the association list.

Compiled code worked a slightly different way, and from its internals we can see where the two namespaces came about in descendants of Lisp 1.5.

The Lisp 1.5 compiler supported 'common' and 'special' variables. A common variable enabled compiled and interpreted code to communicate with each other. A common variable was bound on an explicit association list; to evaluate such a variable, a call to EVAL was emitted to determine the value. A special variable was the compiler's modeling of free variables and closely matched what is now called 'shallow binding.' Ordinary variables compiled into what we have termed lexical variables.

Thus, we see all of the components of the two-namespace world in Lisp 1.5, along with some of the components of the one-namespace world.

It seems that the designers of Lisp 1.5 thought of function names as being different from variable names—the Lisp 1.5 interpreter looked at the property list of the named atomic symbol first, and so it can be argued that a function was considered a property of a symbol. The designers used the terminology that a symbol "stands for" a function while a variable "refers" to a value.

Lisp for the PDP-6 at MIT adopted the style of the Lisp 1.5 special variables for dynamic binding in both compiled and interpreted code, thereby eliminated common variables. Compilers were still written that were to try to interpret special variables as lexical variables in as many places as possible. The value of a symbol was stored in the value cell of the symbol, and the function remained on the property list as it did in Lisp 1.5.

MacLisp [Pitman 1983] is a direct descendant of the PDP-6 Lisp and is a Lisp₂ dialect. MacLisp uses a sophisticated form of link table, which is made possible by the separation of namespaces. In particular, function-defining functions have controlled access into the places where functions are stored so that the link tables can be correctly maintained.

Vax NIL is a descendant of MacLisp and was intended to be the successor to MacLisp running on the Vax. It uses the same sort of link table ideas found in MacLisp for fast function calling. The designers of MacLisp and NIL had performance in mind when they designed the two-namespace layout. A description of Vax NIL can be found in [Gabriel 1985].

S-1 Lisp [Brooks 1982] is a dialect of NIL for the S-1 Mark IIA, and therefore it is a Lisp₂ dialect. Spice Lisp is an intellectual descendant of MacLisp and thus is a Lisp₂ dialect. A description of Spice Lisp can be found in [Gabriel 1985]. ZetaLisp [Symbolics 1986b] is an intellectual descendant of MacLisp and, for reasons like those that motivated the NIL designers, became a Lisp₂ dialect.

Common Lisp was the result of a compromise between a number of dialects of Lisp, most of them descendants of MacLisp, all of them Lisp₂s. A major aspect of the Common Lisp movement was compromise along political lines.

5. Notational Simplicity

Many believe that having the evaluation rules for expressions treat the function position and the argument positions differently is inelegant. In Lisp₂ different treatment of functional and argument positions is needed because there are different namespaces or environments, for function bindings and for value bindings.

Lisp₂ is slightly more complicated than Lisp₁ in situations where we would want to do either of the following:

• Fetch the value of an identifier in the value namespace and call it as a function
• Fetch the value of an identifier in the function namespace and pass it around as a value.

To use the value of an identifier in the value namespace as a function, Lisp₂ provides this notation:

 (FUNCALL <identifier> . <arguments>)

For example, in Lisp₂ one would write

 (DEFUN MAPC-1 (F L) (DOLIST (X L) (FUNCALL F X)))

In Lisp₁, one would write

 (DEFUN MAPC-1 (F L) (DOLIST (X L) (F X)))

To use the value of an identifier in the function namespace as a normal value, Lisp₂ provides this notation:

 (FUNCTION <identifier>)

which is often abbreviated as simply

 #'<identifier>

For example, in Lisp₂ one would write

 (MAPC #'PRINT '(A B C D))

In Lisp₁, one would write

 (MAPC PRINT '(A B C D))

The differences are more striking in a larger, more complex example. In Lisp₂, one can write the Y operator as

 (DEFUN Y (F)
  (   (LAMBDA (G) #'(LAMBDA (H) (FUNCALL (FUNCALL F (FUNCALL G  G)) H)))
    #'(LAMBDA (G) #'(LAMBDA (H) (FUNCALL (FUNCALL F (FUNCALL G  G)) H)))))

while in Lisp₁, one can write

 (DEFUN Y (F)
   ((LAMBDA (G) (LAMBDA (H) ((F (G G)) H)))
    (LAMBDA (G) (LAMBDA (H) ((F (G G)) H)))))

The call to this operator in order to compute 6! in Lisp₂ would look like

 (FUNCALL (Y #'(LAMBDA (FN)
                #'(LAMBDA (X)
                   (IF (ZEROP X) 1 (* X (FUNCALL FN (- X 1)))))))
          6)

In Lisp₁, the same call would look like

 ((Y (LAMBDA (FN)
       (LAMBDA (X)
         (IF (ZEROP  X) 1 (* X (FN (- X 1)))))))
  6)

Some argue that the Lisp₁ form is easier to read because it is more concise. Others feel that the Lisp₂ form is easier to read because the use of functions whose names are not constant is clearly marked.

Probably a programmer who frequently passes functions as arguments or who uses passed arguments functionally finds Lisp₁ syntax easier to read than Lisp₂ syntax; the programmer who infrequently passes functions as arguments and rarely uses passed arguments functionally probably prefers to use a different syntax on those occasions.

6. Multiple Denotations for a Single Name

Some find it simple and clear to have a single meaning for a name. Fewer meanings mean less to remember. For example, suppose a programmer has defined the function F as

 (DEFUN F (X) (+ X 1))

Then suppose the programmer is writing a new function, G, and wants it to take the functional parameter F, which is to apply to its other argument. Suppose the programmer writes

 (DEFUN G (F) (F 3))

Issues of defined program semantics aside, it's probably obvious that the programmer meant to call the function named by the formal parameter F on the argument 3. In Lisp₂, however, this function will ignore its argument named F and simply invoke the globally defined function named F on 3. Notice that this is precisely what Lisp 1.5 would have done.

Unfortunately, not all situations are as clear-cut as this. For example, consider the following:

 (DEFUN PRINT-SQUARES (LIST)
   (DOLIST (ELEMENT LIST)
     (PRINT (LIST ELEMENT (EXPT ELEMENT 2)))))

In this definition, there are three uses of the name LIST. The first is in the function's formal parameter list. The second is in initialization of the DOLIST variable. The third is in the PRINT expression. This program, which is valid in current Common Lisp, would not be valid in Lisp₁ because the name LIST could not simultaneously denote a list of numbers and a function. Such uses are familiar cause of programmer errors in Lisp₁. In Lisp₁, a common way to write this definition would be

 (DEFUN PRINT-SQUARES (LST)
   (DOLIST (ELEMENT LST)
     (PRINT (LIST ELEMENT (EXPT ELEMENT 2)))))

In the function PRINT-SQUARES, the parameter named LST is better named LIST-OF-NUMBERS, though some programmers would not use such a long name.

As should be clear from these examples, the advantage of treating the function and argument positions the same is that using parameters as functions is made more convenient syntactically.

The disadvantage is that not using parameters as functions is made less convenient syntactically because parameter names must be more carefully chosen so that they do not shadow the names of globally defined functions that will be needed in the function body.

Of course, care in naming must be observed in Lisp₂ anyway to ensure that variable names chosen for some inner binding do not shadow the names of the variables bound by outer binding constructs. Consider this example:

 (DEFUN HACK-LIST (LIST)
   (LET ((LST (HACK-LIST LIST)))
     (HACK-SOME-MORE LIST LST)
     (SHUFFLE LIST LST)))

There are two variables that could naturally be named 'LIST,' and the programmer must choose which one to so name.

Nevertheless, the degree of care required to avoid name collisions in Lisp₁ is theoretically no less than that required in Lisp₂ but has been observed to be far more, a point to which we shall return later.

The following is a simple example of some of the important issues in variable naming (using mixed Lisp₁ and Lisp₂ notation):

 (DEFUN ODDITY (LIST) (LIST LIST LIST))
 (ODDITY #'CONS)

Depending on which way the issue is decided, the possible return values from this function might be

 (#<SUBR CONS>  .  #<SUBR CONS>)
 (#<SUBR CONS>  #<SUBR CONS>)

7. Referential Clarity

In Lisp₂, deciding whether to use the function or the value is impossible unless the context is known. These two forms result in different interpretations of an expression, x:

(x ...)
(... x ...)

To some programmers, a basic 'rule' of Lisp style is that code is clearest when the least amount of context is necessary to determine the meaning of an expression. Unfortunately, that rule is violated in Lisp₂.

In a presentation at the 1986 ACM Conference on Lisp and Functional Programming, Steele complained that the α operator in Connection Machine^TM Lisp [Steele 1986], which he wanted to implement as a simple read macro, could not be implemented that way because of this context problem. The expansion of the α operator depended on whether it was expanding in a functional or an argument position. In Lisp₁ this problem would not have arisen. In Lisp₂ the problem could be solved by introducing 'lambda macros' such as those that are already used in ZetaLisp.

8. Compiler Simplicity

Current Common Lisp compilers use special case code when deciding which namespace mapping to use when examining a variable.

The maintainers of some Common Lisp compilers claim that a change from Lisp₂ to Lisp₁ semantics would result in simpler, smaller, faster compilers. One reason is that knowledge about which namespace is in effect at any point is often procedurally embedded. By merging the two namespaces, the same pieces of code can be used in more places, thus reducing the number of places where such information is represented and thus making maintenance simpler.

The maintainers of other Common Lisp compilers claim, however, that a change from Lisp₂ to Lisp₁ semantics would reduce the complexity of their compilers little if at all—that it might force small changes at points distributed throughout the system, but that the compiler would not change very much.

There is even some concern that the complexity of compilers might increase because of such a change. This belief is based on the observation that the change would effectively cause type information to be lost. Specifically, for Lisp₂ a compiler writer can assume that whatever is in a function cell must be a function; for Lisp₁ a compiler writer cannot assume that if a programmer has written an expression that invokes a function associated with a symbol, the contents of the value cell of that symbol will be a function when the function invocation is performed.

In Lisp₁, this information sometimes may be recoverable, but the compiler may have to perform extensive type inference to do so. Often, the compiler will have to take an unnecessarily conservative approach.

Consider a Lisp₂ function such as

 (DEFUN F (X) (G X))

Even in this simple function, we are assuming that

 (SYMBOL-FUNCTION 'G)

is a function. When a good compiler is directed to produce safe code, that compiler must concern itself with the question of whether a cell will ever contain a nonfunction. For some computers, if the compiler cannot show that the contents of the function cell is always a function, it must generate less efficient code.

Common Lisp compilers can be written that assume that function cells always contain functions in Lisp₂ because it is legal to forbid nonfunctions from ever being placed in the function cell. For example, Vax Lisp [Digital 1986] does this. Consequently, the Vax Lisp compiler can safely generate code that simply jumps to the contents of the value cell of G. In Lisp₁, however, this is not possible unless new declarations are introduced.

The conclusion here is not that some compilers are better than others, but that compilers may vary widely in their nature, and therefore the effects of the proposed change may vary widely depending upon the implementation.

9. Higher Order Functions

While functions, like Y, that directly manipulate other functions can be written in either Lisp₁ or Lisp₂, many programmers feel that they can be written more perspicuously in Lisp₁; therefore, the more cumbersome notation of Lisp₂ does nothing to encourage and may even discourage the writing of such functions.

10. Abstraction Sharing

In Lisp₁ it is easier to define a piece of code that shares abstractions between data and functions. Again, this is possible in Lisp₂, but it is not an encouraged style. The problem is that it is a burden to think about which namespace will be used for various variables.

11. Multiprocessing

A pure or side-effect-free functional programming style has been seen to be successful in multiprocessing; therefore it would seem that a Lisp-like functional style would be conducive to multiprocessing. That is, a functional style of programming might result in programs that are more easily rendered into a parallel style. For evidence of this, look at typical Common Lisp programs and contrast their style and suitability for parallelization with the same programs as they might be written in Scheme. By transitivity, since Lisp₁ tends to encourage functional programming style, it is also more conducive to multiprocessing.

Of course, Common Lisp is not designed to accommodate multiprocessing, and it would take more than uniting of the function and value namespaces to allow Common Lisp to seriously support multiprocessing. Integrated support of multiprocessing is not currently an explicit goal of Common Lisp. Nevertheless, it seems apparent that experience with a more functional programming style will provide a good foundation for programmers who later move to a language that does support multiprocessing.

12. Number of Namespaces

There is really a larger number of namespaces than just the two that are discussed here. As we noted earlier, other namespaces include at least those of blocks and tags; type names and declaration names are often considered namespaces. Thus, the names Lisp₁ and Lisp₂, which we have been using are misleading. The names Lisp₅ and Lisp₆ might be more appropriate.

Since there are other namespaces, the uniting of the function and value of namespaces does not accomplish as much as might initially appear. Even if they are united, the interpretation of a symbol in a Common Lisp program would still depend on the context to disambiguate variables from symbols, symbols from the type names, and so on.

On the other hand, some proponents of uniting have suggested that in time these other namespaces would be collapsed as well. Dialects of Scheme have done this—some to a greater extent than others. The hope is that when all namespaces are reduced to a single one, there will be a single simple evaluation rule for all identifiers. Because Lisp contains QUOTE, there is actually an arbitrary number of namespaces because of the existence of functions like GET, and GETHASH that allow users to effectively associate new kinds information with symbols. Even if the underlying Lisp supports exactly one namespace, programmers will be able to invent other namespaces. Reducing the number of namespaces in the Lisp to one will help programmers keep track of their own namespaces, but the "one identifier, one meaning" motto will not necessarily apply to user code.

Suppose a programmer has defined a macro like this:

 (DEFMACRO ADD-AUTOMOBILE (AUTO SPECS-FN DATABASE)
   `(LET ((THE-CAR (GETHASH (QUOTE ,AUTO) *AUTO-HASH-TABLE*)))
      (ADD-AUTOMOBILE-INTERNAL
        THE-CAR (FUNCALL ,SPECS-FN THE-CAR) ,DATABASE)))

Then interpreting the identifier CAR-HPM in the next form is not very different from interpreting other identifiers using the built-in namespaces:

 (ADD-AUTOMOBILE CAR-HPM CURRENT-YEAR-SPECS CAR-DATABASE)

An argument has been presented that may have left the impression that because a Lisp₁ compiler can be simpler than a Lisp₂ compiler there is an implied simplicity of Lisp₁ over Lisp₂. But the question of whether a compiler for Lisp₁ is more or less complicated than a compiler for Lisp₂ is a statement about the abstract effect of the different namespace complexities. The additional meanings that can be associated with symbols can and do have a very powerful effect.

Indeed, much of the power of associative functions like GET derives from a structured pun—the fact that a single symbol may have more than one kind of information associated with it. The power and importance of this kind of structured interplay between arbitrary namespaces is hard to deny.

13. Macros and Name Collisions.

Some contend that macros as they exist in Common Lisp have severe semantic difficulties. Macros expand into an expression that is composed of symbols that have no attached semantics. When substituted back into the program, a macro expansion could conceivably take on quite surprising meaning depending on the local environment.

Some symbols that ultimately appear in the expansion of a macro are obtained during macro definition through its parameter list from the macro consumer. It is possible to use those symbols safely. However, writers of macros often work on the hypothesis that additional functional variables may be referenced in macros as if they were globally constant. Consider the following macro definition for Lisp₁ or Lisp₂:

 (DEFMACRO MAKE-FOO (THINGS) `(LIST 'FOO ,THINGS))

Here FOO is quoted, THINGS is taken from the parameter list for the Macro, but LIST is free. The writer of this macro definition is almost certainly assuming either that LIST is locally bound in the calling environment and is trying to refer to that locally bound name or that list is to be treated as constant and that the author of the code will not locally bind LIST. In practice, the latter assumption is almost always made.

If the consumer of the above macro definition writes

 (DEFUN FOO (LIST) (MAKE-FOO  (CAR  LIST)))

in Lisp₁, there will probably be a bug in the code.

Here is another example of code that would be a problem in Lisp₁:

 (DEFMACRO FIRST (LIST) `(CAR ,LIST))
 (DEFMACRO REST (LIST) `(CDR  ,LIST))
 (DEFUN TEST-CAR  (CAR TEST-LIST)
   "The 'driver' program for Frobozz Automobile, Inc.'s
    quality assurance test."
   (DO ((TESTS TEST-LIST (REST TESTS)))
       ((NULL TESTS))
    ((FIRST TESTS) CAR)))

It's worth emphasizing, however, that these problems occur in either Lisp₁ or Lisp₂. The issue is that they are more likely to occur in Lisp₁ because there is less contextual information available. Here is an example of how the problem arises in normal Common Lisp:

 (DEFMACRO FOO (X Y) `(CONS 'FOO (CONS ,X (CONS ,Y NIL))))
 (DEFUN BAZ (X Y)
   (FLET ((CONS (X Y) (CONS Y X)))
     (FOO X Y)))

(BAZ 1 2) returns (((NIL . 2) . 1) . FOO) even though it seems that (FOO 1 2) might have been intended by the programmer.

Although few implementations support its full generality in file compilation, a strict reading of the Common Lisp specification seems to imply that writing the following should be acceptable:

 (DEFMACRO FOO (X Y) ;take deep breath
   `(FUNCALL ',#'CONS 'FOO (FUNCALL ',#'CONS ,X (FUNCALL ',#'CONS ,Y NIL))))
 (DEFUN BAZ (X Y)
   (FLET ((CONS (X Y) (CONS Y X)))
     (FOO X Y)))

Here (BAZ 1 2) should evaluate to (FOO 1 2) just as everyone expected. Of course, FUNCALL is subject to the same problems as CONS was; either FUNCALL must be considered a constant function or a construct such as

 ('#<COMPILED-CODE CONS>  ...)

Should be specially understood by the compiler and interpreter.

Given all of this, the thoughtful reader might ask: Why do macros appear to work as often as they do?

The answer seems to be based in history and statistics rather than in some theoretical foundation. In dialects preceding Common Lisp, such as MacLisp, it was fortunate that FLET, LABELS, MACROLET did not exist. Thus in these dialects there was an extremely high likelihood that the function bindings of identifiers in the macro expander's environment would be compatible with the function bindings of the same identifiers in the program environment. This coupled with the fact that the only free references that most macro expansions tend to make are functional meant that writers of macros could guess enough information about how the expansion would be understood and could develop fairly reliable macro packages.

With the advent of FLET, LABELS, and MACROLET, the risk of conflict is considerably higher. The Scheme community, which has long had constructs with power equivalent to that of these forms, has not adopted a macro facility. This is partly because macros have generally seemed like a semantically empty concept to many of the Scheme designers.

Common Lisp programmers probably have little trouble because they are still programming in a MacLisp programming style, using forms like FLET and LABELS in limited ways. People who use FLET and LABELS heavily may well have learned Lisp with Scheme and do not use macros heavily, or they understand the issues outlined here and write macros carefully.

As time goes on, it should not be surprising to find users of Common Lisp macros reporting more name collision problems. A change from Lisp₂ to Lisp₁ semantics for identifiers would probably speed up the increase in these problems.

14. The Benefits of Macros

Although macros have semantic difficulties, they are pragmatically useful, as are other constructs that don't add semantic power to a language. For example, in a Lisp with IF and PROGN, the additional semantic power of COND is null. Yet COND buys stylistic improvements to some Lisp code, especially to code written with IF and PROGN that would be indented too far to the right in proper indentation style or code that would not highlight the relationships of the conditions being tested because they would not be placed, vertically, near each other.

Therefore, semantically poor constructs like macros can help programmers organize their code to be more readable and maintainable, and so that it expresses the abstractions in such a way that the code runs efficiently.

Common Lisp programmers are judged on their ability to use macros appropriately and judiciously. Without the pervasive use of macros, a modern Lisp programming style would not have been developed, and Lisp as a mature programming language would have never come about. Many believe that the powerful Lisp macro facility is the main reason that Lisp has been successful over the years.

Macros have formed the basis for efficient abstraction within Lisp. They can be used to optimize the generated code by examining the forms passed to the macro definition function, and different code can be produced depending on the shape of those forms. Macros can be used to define extensions to Lisp because macros enable the programmer to define new evaluation rules.

Most programmers simply do not experience the name collision problems mentioned in the previous section with the frequency that seems to be appropriate to the depth of the problem, largely because of the existence of a function namespace. FLET and LABELS define functions, and programmers treat function names more carefully than nonfunction names. Therefore, letting function names be freely referenced in a macro definition is not a big problem.

There are two ways to look at the arguments regarding macros and namespaces. The first is that a single namespace is of fundamental importance, and therefore macros are problematic. The second is that macros are fundamental, and therefore a single namespace is problematic.

15. Space Efficiency

If a symbol is used both for its value and as a function, it currently costs no additional space. Any program that has symbols that are used to denote distinct functions and values, however, would have to be changed. In general, this means that some new symbols would be introduced. In most cases, the number of new symbols introduced would probably be small, but there might be pathological applications that would be exceptions.

In the Lucid Lisp system [Lucid 1986], there are 14 of these symbols, and in these cases the value cell is being used as a cache for an object related to the function. In the MACSYMA system [Symbolics 1986a] there are roughly 35 of these symbols out of a total of 10,000.

Using the same name to refer to both a function and a value cell can be more space efficient, since it means only one additional cell to an existing data structure that already has on the order of 5 to 10 cells.

This issue can be illustrated quantitatively. Let n be the number of symbols in a system, let S₁ be the space occupied by the average symbol in an implementation of Lisp₁, let S₂ be the space occupied by the average symbol in an implementation of Lisp₂, and let x be the number of symbols that must be added to a system to resolve name conflicts. Then the space saved by having separate environments is

(n + x) S₁ - nS₂

For example, if n is 8000, x is 14, S₁ is 28 (bytes), and S₂ is 32 (bytes), then the space saved by Lisp₂ is -31608 (bytes). That is, 12% of the symbol space used by such a Lisp₂ implementation might be saved if it were made to be a Lisp₁ implementation. For there are to be no net change in the amount of storage between two-namespace and a one-namespace Lisp, more than 1100 symbols would need to be added to the system to resolve name conflicts.

The issue is not likely to be important.

16. Time Efficiency

In Lisp₂, a function call to a function associated with a symbol involves the use of indirection through the symbol's function cell, which points to a piece of code possibly with an intermediate pointer through a procedure object, as in S-1 Lisp.

An optimization to this is to eliminate the indirection through the symbol's function cell and have a function call jump directly to the correct code object, perhaps indirecting through a link table in order for DEFUN and SETF of SYMBOL-FUNCTION to cause existing running code to call a redefined function, the operation of changing a symbol's function cell must invalidate the link table or otherwise cause the correct new link to be made.

In Lisp₁, the straightforward implementation of function calling would check the value cell for a valid function on each function call.

To use the link table optimization in Lisp₁, SETQ rather than SETF of SYMBOL-FUNCTION must do the invalidating or relinking. Of course, only an assignment to a symbol needs to be checked. In the worst case SETQ would become a function call rather than being open-code; in this situation, the speed loss could be the difference between a single instruction and about 30 instructions.

In the expected case a single SETQ would become two SETQs. The implementation for this case is for each symbol to have a hidden function cell that always contains a valid function, perhaps a trap function. Function calls go through the hidden function cell as usual, but DEFUN and SETQ always manipulate both the value cell and the hidden function cell. Every SETQ also assigns a trap function to the hidden function cell, so that the next function call through that symbol runs trap code that establishes the valid link to the real code or signals an error.

On some stock hardware, tricks with the addressing hardware and word alignment can be played to get away with having only a value cell and not having SETQ take any more time than it would in Lisp₂. Even with the two-SETQ implementation the additional overhead for the SETQ of symbols should not cause more than 10% degradation in the most pessimistic inner loop, and overall it is unlikely to cause a noticeable degradation in a large system.

The number and complexity of space and time trade-offs discussed here might be confusing. First, the reason that a sophisticated function-calling method is chosen by Lisp implementors for stock hardware implementations is that a shorter and faster function-calling sequence can be gained using various tricks, some of which require tables of information needed when functions are redefined; usually the objects representing compiled functions in these implementations can be shortened as well. The space gained by these shortenings is balanced fairly well with the storage needed for the tables. Second, changing from Lisp₂ to Lisp₁ results in a smaller Lisp image because of the reduction in storage needed for symbols. Third, the additional code needed for testing assignment of symbols decreases the speed of running code and increases its size. If a function cell is supported as a means of providing fast function calling, then there is no space gained by eliminating the function cell—each symbol still has one.

Because assignment to symbols is infrequent and because changing function definitions associated with symbols is rare, the speed trade-off probably results in a negligible loss in speed, and the space trade off probably results in a small space increase.

This issue is an illustration of the earlier claim that simplifying the surface language might not always result in a simpler implementation strategy: This is one of several ways that the implementation might become more complicated as a result of such a change.

17. Global Variables, Special Variables, and Constants.

A free variable in Common Lisp is currently taken to be a dynamic rather than a lexical reference because there is no global lexical environment in Common Lisp. In this code

 (DEFUN PLUS (X Y) (+ X Y))
 (DEFUN SOMEWHAT-MORE-THAN (X) (PLUS X *SOMEWHAT*))

The reference to *SOMEWHAT* is special (dynamic). On the surface, in Lisp₁ the reference to PLUS is free also, and thus it is special (dynamic).

When a variable is declared special, a free reference to it is to the most recent dynamically bound value for it; all bindings of it become special (dynamic) bindings. When a variable is declared constant, free references to it are to its permanent constant value, and compilers are free to fold that constant into the code they emit.

We introduce the concept of global variables; when a variable is global, free references to it are to the value cell of the symbol named by the variable, and all bindings of it are still lexical.

To avoid a compiler warning for free use of a variable like *SOMEWHAT*, the variable is declared SPECIAL. In order to have compilers for Lisp₁ not to warn about the free use of PLUS, it would be unfortunate to have to declare it SPECIAL.

As noted, in Common Lisp the default for free variable references is SPECIAL; that is, a free variable reference is taken to be a special variable reference. If the default in Lisp₁ were that free variable references were global (lexical), then it would make sense for a compiler not to warn about such free variable references.

17.1 An Approach to Free Functional Variables

One approach to this problem would be to introduce a new declaration that made a variable (lexically) GLOBAL but not SPECIAL. DEFUN could implicitly declare function names GLOBAL. With such a declaration, in a deep-bound Lisp₁, the compiler would not need to emit code to search the dynamic binding chain to determine what code to invoke for PLUS in SOMEWHAT-MORE-THAN.

Given such a declaration, it would still be possible in Lisp₁ to write definitions such as the following:

 (DEFUN ZAP (FN X Y)
   (LET ((PLUS (LAMBDA (X Y) (MAPCAR PLUS X Y))))
     (LIST (PLUS (FN X) (FN Y)) (PLUS (FN (FN X)) (FN (FN Y))))))

where PLUS is defined above, without worrying that the LET-binding of PLUS would affect the argument FN. To explain the issues better, here the references to PLUS are numbered and the definition is shown in a different typeface:

 (DEFUN ZAP (FN X Y) 
   (LET ((PLUS1 (LAMBDA (X Y) (MAPCAR PLUS2 X Y))))
     (LIST (PLUS3 (FN X) (FN Y)) (PLUS4 (FN (FN X)) (FN (FN Y))))))

PLUS₁ is a lexical binding of the variable named PLUS; PLUS₂ references the global value of the symbol named PLUS; PLUS₃ and PLUS₄ are lexical references to the binding of PLUS₁. If FN is bound to a function that is defined likes this, for instance,

 (DEFUN BAZ (X) (LIST X (PLUS5 X X)))

then PLUS₅ refers to the global value of PLUS rather than to the LET-bound value in FOO. If DEFUN were to declare function names SPECIAL, then PLUS₂ and PLUS₅ would refer to the SPECIAL binding for PLUS, namely PLUS₁, in this example.

17.2 A Second Approach to Free Functional Variables

An alternative approach is for DEFUN to implicitly declare function names constant. Redefining a function might cause some compilers to warn that some constant function definitions had been folded into code.

A mixed approach would be for all built-in Common Lisp functions to be declared constant, while DEFUN would implicitly declare function names global.

Closely related to this issue is the fact that there is currently no system-provided dynamic variation of FLET and LABELS in Common Lisp, although in a nonmultiprocessing environment they can be simulated by creative use of UNWIND-PROTECT. If Common Lisp were made a Lisp₁ dialect, dynamic functional variables would be something the language would get 'for free.' And if their use became popular, it might be desirable to have two kinds of DEFUN—one that created special definitions and another that created lexical definitions.

18. Compatibility Issues.

A transition from Lisp₂ semantics to Lisp₁ semantics would introduce a considerable amount of incompatibility. There is the question of implementor problems as well as user problems.

18.1 Change Existing Code

Large bodies of code already exist that assume the current semantics. That code would have to be changed. Users who did not favor this change would probably resent the amount of work required to make the change, which might be nontrivial.

In some cases, mechanical techniques could be used to diagnose which programs need to be changed. However, because of the pervasive use of macros and of automatic programming techniques, it would not be possible to do such diagnosis with 100% reliability.

As a sort of machine-gun approach to the problem, compilers could be modified to provide the user with information about conflicts as they occur. This would address some problems in automatic programming that could not be detected by statically examining the code that does such programming.

However, some situations are still more complicated because they do not directly produce code; instead, they examine and modify code. For example, compilers, translators, macros, and code walking utilities may have built-in assumption about the number of namespaces; if these assumptions are never explicitly represented, they might elude automatic techniques, which could lead to errors or inefficiencies later on.

18.2 Compatibility Packages

Various compatibility schemes have been proposed that allow these problems to be moderated. For example, we might have a Common Lisp with Lisp₁ semantics that has a compiler switch that allows Lisp₂ code to be compiled and run. Symbols would have function cells, but function cells that were possibly represented as properties on property lists. All old Common Lisp code on the form:

 (F ...)

Would be transformed to this:

 (FUNCALL #'F ...)

Where FUNCTION would look things up in the 'function cell.' FUNCALL would be retained in the compatibility package. A bigger example is more convincing:

 (LET ((LIST ...))
  (LIST ...))

would become

 (LET ((LIST ...))
  (FUNCALL #'LIST ...))

During the transformation process, variables bound by occurrences of FLET and LABELS in the old code would be renamed to new names produced by GENSYM, and the Lisp₁ versions of FLET (which is LET) and LABELS would be substituted for the function namespace versions.

Some compilers may already perform this transformation internally and will be simplified after the change. And perhaps an implementor will want to provide a real function cell for this compatibility in order to run old code relatively fast. Lisps that normally have link tables will need to provide separate linking code (possibly the old link code) for the compatibility package.

This type of compatibility takes a Lisp₂ program and produces a Lisp₁ program that uses some compatibility features for Lisp₂ programs added to the Lisp₁. In theory, the Lisp₂ source for the transformed program could be thrown away, and then only the Lisp₁ code with the compatibility features could be used for the feature.

Unfortunately, there are several problems with this simple kind of compatibility.

First, it does not easily lend itself to mixing compiled and interpreted code, especially when such code is produced at runtime. It becomes important, for example, to clearly document and control whether functions that receive expressions to be evaluated or code- walked are receiving expressions in Lisp₁ or Lisp₂.

Also, the compatibility package might expand expressions into code that was opaque to code walkers, compilers, and macro facilities, which might have built-in assumptions about the expected kinds of expressions. For example, the proposed compatibility translation may involve treating some forms that were documented as special forms as if they were macros. Possibly a code-walker expecting to see a certain class of expressions would see a different class of expressions after compatibility translation.

Another problem occurs when both the compatibility code and the Lisp₂ code to be translated use property lists to hold the 'function cells.' In this case the running Lisp₁ version of the Lisp₂ code might destroy part of the compatibility information.

There is a class of Lisp₂ programs that could be safely run under this translation style of compatibility. There is also, clearly, a class of programs that require a stricter compatibility.

A second stage of compatibility would require, essentially, a complete implementation of the semantics of Lisp₂ existing alongside of and sharing code with the Lisp₁. For example, a 'real' function cell would need to be implemented along with an EVAL and a compiler—the compiler would be a combination of the translator mentioned above and the Lisp₁ compiler.

Some programs may function correctly but suffer an efficiency loss that is greater than the simple loss that might be assumed by just analyzing the theoretical speed of the compatibility code. For example, the compiler might be able to perform better optimizations on the original program than on the same program under the compatibility package.

As mentioned, a simple compatibility package can probably take care of a certain class of Common Lisp programs, but for programs that would require an implementation of Lisp₂ in Lisp₁ for compatibility, it is probably best to require programmers to translate those programs to Lisp₁.

19. Standardization

In standardizing a language, we should take care to standardize those things that have had proven success and acceptance by a user community. It is often dangerous to standardize on the most recently formulated ideas. The new macro solution by Kohlbecker [Kohlbecker 1986] is of this form.

20. Summary

The bulk of arguments that focus on clean semantics and notational simplicity tend to favor uniting the function and value namespaces. In spite of this, there are those who hold strongly to a belief that a two-namespace system affords useful expressive power that they are unwilling to do without. In the end, practical considerations favor the status quo for Common Lisp. There is a large number of improvements beyond a single namespace that could be made to Common Lisp that would clean it up and simplify it. We feel that the time for such radical changes to Common Lisp passed, and it would be the job of future Lisp designers to take lessons from Common Lisp and Scheme to produce an improved Lisp.

21. Acknowledgements

The authors also gratefully acknowledge the useful commentary and support of Will Clinger, Scott Fahlman, David Moon, and JonL White.

References

[Abelson 1985]

H. Abelson and G.J. Sussman with J. Sussman, Structure and Interpretation of Computer Programs, The MIT Press, Cambridge, Massachusetts, 1985

[Brooks 1982]

R. A. Brooks, R.P. Gabriel, and G.L. Steele Jr., S-1 Common Lisp Implementation, Proceedings of the 1982 ACM Symposium on Lisp and Functional Programming, Pittsburgh, PA, August 1982.

[Digital 1986]

Digital Equipment Corporation, VAX LISP/VMS User's Guide, Maynard, MA, 1986.

[Gabriel 1985]

R.P. Gabriel, Performance and Evaluation of Lisp Systems, The MIT Press, Cambridge, MA 1985.

[Halstead 1984]

Halstead, Robert, MultiLisp, Proceedings of the 1984 ACM Symposium on Lisp and Functional Programming, August 1984.

[Kohlbecker 1986]

E.E. Kohlbecker, Jr., Syntactic Extensions in the Programming Language Lisp, PhD thesis, Indiana University, August 1986.

[Lucid 1986]

Lucid, Inc., Lucid Common Lisp Reference Manual for the VAX, Menlo Park, CA, 1986.

[McCarthy 1965]

J. McCarthy, et al, Lisp 1.5 Programmer's Manual, The MIT Press, Cambridge, Massachusetts, 1965.

[Padget 1986]

J. Padget, et al, Desiderata for the standardisation of LISP, Proceedings of the 1986 ACM Conference on Lisp and Functional Programming, Cambridge, MA, August 1986.

[Pitman 1983]

K.M. Pitman, The Revised Maclisp Manual (Saturday Evening Edition), LCS Technical Report 295, MIT, May 1983.

[Rees 1986]

J. Rees and W. Clinger, editors, Revised³ Report on the Algorithmic Language Scheme, SIGPLAN Notices 21(12), September 1986.

[Steele 1984]

G.L. Steele Jr., Common Lisp, The Language, Digital Press, Billerica, Massachusetts, 1984.

[Steele 1986]

G.L. Steele Jr. and W.D. Hillis, Connection Machine^TM Lisp: Fine-Grained Parallel Symbolic Processing, Proceedings of the 1986 ACM Conference on Lisp and Functional Programming, Cambridge, MA August 1986.

[Sussman 1975]

G.J. Sussman and G.L. Steele Jr., SCHEME: An Interpreter for Extended Lambda Calculus, AI Memo 349, MIT, Cambridge MA, December 1975.

[Symbolics 1986a]

Symbolics, Inc., MACSYMA Reference Manual, Cambridge, MA, 1986.

[Symbolics 1986b]

Symbolics, Inc., Symbolics Common Lisp: Language Concepts, Encyclopedia Symbolica, Volume 2A, 296-297, Cambridge, MA 1986.

Click here for an index of other titles by Kent Pitman.