Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document Information Technology - Programming Language - Common Lisp, formerly X3.226-1994 (R1999). Developed to standardize the divergent variants of Lisp which predated it, it is not an implementation but rather a language specification. Several implementations of the Common Lisp standard are available, including commercial products and open source software.
Common Lisp is a general-purpose, multi-paradigm programming language. It supports a combination of procedural, functional and object-oriented programming paradigms. As a dynamic programming language, it facilitates rapid development, with iterative compilation into efficient run-time programs. Common Lisp includes CLOS, an object system that supports multimethods and method combinations. It is extensible through standard features such as Lisp macros (compile-time code rearrangement accomplished by the program itself) and reader macros (extension of syntax to give special meaning to characters reserved for users for this purpose).
Common Lisp is a dialect of Lisp; it uses S-expressions to denote both code and data structure. Function and macro calls are written as lists, with the name of the function first, as in these examples:
The symbol type is common to Lisp languages, but largely unknown outside them. A symbol is a unique, named data object with several parts: name, value, function, property list and package. Of these, value cell and function cell are the most important. Symbols in Lisp are often used similarly to identifiers in other languages: to hold value of a variable; however there are many other uses. Normally, when a symbol is evaluated, its value is returned. Some symbols evaluate to themselves, for example all symbols in keyword package are self-evaluating. Boolean values in Common Lisp are represented by the self-evaluating symbols T and NIL. Common Lisp has namespaces for symbols, called 'packages'.
As in almost all other Lisp dialects, lists in Common Lisp are composed of conses, sometimes called cons cells or pairs. A cons is a data structure with two slots, called its car and cdr. A list is a linked chain of conses. Each cons's car refers to a member of the list (possibly another list). Each cons's cdr refers to the next cons -- except for the last cons, whose cdr refers to the nil value. Conses can also easily be used to implement trees and other complex data structures; though it is usually advised to use structure or class instances instead. It is also possible to create circular data structures with conses.
Common Lisp supports multidimensional arrays, and can dynamically resize arrays if required. Multidimensional arrays can be used for matrix mathematics. A vector is a one-dimensional array. Arrays can carry any type as members (even mixed types in the same array) or can be specialized to contain a specific type of members, as in a vector of integers. Many implementations can optimize array functions when the array used is type-specialized. Two type-specialized array types are standard: a string is a vector of characters, while a bit-vector is a vector of bits.
Hash tables store associations between data objects. Any object may be used as key or value. Hash tables, like arrays, are automatically resized as needed.
Packages are collections of symbols, used chiefly to separate the parts of a program into namespaces. A package may export some symbols, marking them as part of a public interface. Packages can use other packages.
Classes are similar to structures, but offer more dynamic features and multiple-inheritance. (See CLOS.) Classes have been added late to Common Lisp and there is some conceptual overlap with structures. Objects created of classes are called Instances. A special case are Generic Functions. Generic Functions are both functions and instances.
The Common Lisp library relies heavily on such higher-order functions. For example, the
sort function takes a relational operator as an argument and key function as an optional keyword argument. This can be used not only to sort any type of data, but also to sort data structures according to a key.
The evaluation model for functions is very simple. When the evaluator encounters a form
(F A1 A2...) then it is to assume that the symbol named F is one of the following:
If F is the name of a function, then the arguments A1, A2, ..., An are evaluated in left-to-right order, and the function is found and invoked with those values supplied as parameters.
defundefines functions. A function definition gives the name of the function, the names of any arguments, and a function body:
Function definitions may include declarations, which provide hints to the compiler about optimization settings or the data types of arguments. They may also include documentation strings (docstrings), which the Lisp system may use to provide interactive documentation:
Anonymous functions (function literals) are defined using
lambda expressions, e.g.
(lambda (x) (* x x)) for a function that squares its argument. Lisp programming style frequently uses higher-order functions for which it is useful to provide anonymous functions as arguments.
Local functions can be defined with
There are a number of other operators related to the definition and manipulation of functions. For instance, a function may be recompiled with the
compile operator. (Some Lisp systems run functions in an interpreter by default unless instructed to compile; others compile every entered function on the fly.)
defgenericdefines generic functions. The macro
defmethoddefines methods. Generic functions are a collection of methods.
Methods can specialize their parameters over classes or objects.
When a generic function is called, multiple-dispatch will determine the correct method to use.
Generic Functions are also a first class data type. There are many more features to Generic Functions and Methods than described above.
To pass a function by name as an argument to another function, one must use the
function special operator, commonly abbreviated as
#'. The first
sort example above refers to the function named by the symbol
> in the function namespace, with the code
Scheme's evaluation model is simpler: there is only one namespace, and all positions in the form are evaluated (in any order) -- not just the arguments. Code written in one dialect is therefore sometimes confusing to programmers more experienced in the other. For instance, many CL programmers like to use descriptive variable names such as list or string which could cause problems in Scheme as they would locally shadow function names.
Whether a separate namespace for functions is an advantage is a source of contention in the Lisp community. It is usually referred to as the Lisp-1 vs. Lisp-2 debate. These names were coined in a 1988 paper by Richard P. Gabriel and Kent Pitman, which extensively compares the two approaches.
Like programs in many other programming languages, Common Lisp programs make use of names to refer to variables, functions, and many other kinds of entities. Named references are subject to scope.
The association between a name and the entity which the name refers to is called a binding.
Scope refers to the set of circumstances in which a name is determined to have a particular binding.
The circumstances which determine scope in Common Lisp include:
To understand what a symbol refers to, the Common Lisp programmer must know what kind of reference is being expressed, what kind of scope it is uses if it is a variable reference (dynamic versus lexical scope), and also the run-time situation: in what environment is the reference resolved, where was the binding introduced into the environment, et cetera.
Some environments in Lisp are globally pervasive. For instance, if a new type is defined, it is known everywhere thereafter. References to that type look it up in this global environment.
One type of environment in Common Lisp is the dynamic environment. Bindings established in this environment have dynamic extent, which means that a binding is established at the start of the execution of some construct, such as a LET block, and disappears when that construct finishes executing: its lifetime is tied to the dynamic activation and deactivation of a block. However, a dynamic binding is not just visible within that block; it is also visible to all functions invoked from that block. This type of visibility is known as indefinite scope. Bindings which exhibit dynamic extent (lifetime tied to the activation and deactivation of a block) and indefinite scope (visible to all functions which are called from that block) are said to have dynamic scope. Common Lisp has support for dynamically scoped variables, which are also called special variables. Certain other kinds of bindings are necessarily dynamically scoped also, such as restarts and catch tags. Function bindings cannot be dynamically scoped (but, in recognition of the usefulness of dynamically scoped function bindings, a portable library exists now which provides them).
Dynamic scope is extremely useful because it adds referential clarity and discipline to global variables. Global variables are frowned upon in computer science as potential sources of error, because they can give rise to ad-hoc, covert channels of communication among modules that lead to unwanted, surprising interactions.
In Common Lisp, a special variable which has only a top-level binding behaves just like a global variable in other programming languages. A new value can be stored into it, and that value simply replaces what is in the top-level binding. Careless replacement of the value of a global variable is at the heart of bugs caused by use of global variables. However, another way to work with a special variable is to give it a new, local binding within an expression. This is sometimes referred to as "rebinding" the variable. Binding a dynamically scoped variable temporarily creates a new memory location for that variable, and associates the name with that location. While that binding is in effect, all references to that variable refer to the new binding; the previous binding is hidden. When execution of the binding expression terminates, the temporary memory location is gone, and the old binding is revealed, with the original value intact. Of course, multiple dynamic bindings for the same variable can be nested.
In Common Lisp implementations which support multithreading, dynamic scopes are specific to each thread of execution. Thus special variables serve as an abstraction for thread local storage. If one thread rebinds a special variable, this rebinding has no effect on that variable in other threads. The value stored in a binding can only be retrieved by the thread which created that binding. If each thread binds some special variable *X*, then *X* behaves like thread-local storage. Among threads which do not rebind *X*, it behaves like an ordinary global: all of these threads refer to the same top-level binding of *X*.
Dynamic variables can be used to extend the execution context with additional context information which is implicitly passed from function to function without having to appear as an extra function parameter. This is especially useful when the control transfer has to pass through layers of unrelated code, which simply cannot be extended with extra parameters to pass the additional data. A situation like this usually calls for a global variable. That global variable must be saved and restored, so that the scheme doesn't break under recursion: dynamic variable rebinding take care of this. And that variable must be made thread-local (or else a big mutex must be used) so the scheme doesn't break under threads: dynamic scope implementations can take care of this also.
In the Common Lisp library, there are many standard special variables. For instance, the all standard I/O streams are stored in the top-level bindings of well-known special variables. The standard output stream is stored in *standard-output*.
Suppose a function foo writes to standard output:
It would be nice to capture its output in a character string. No problem, just rebind *standard-output* to a string stream and call it:
-> "Hello, world" ; gathered output returned as a string
Common Lisp supports lexical environments. Formally, the bindings in a lexical environment have lexical scope and may have either indefinite extent or dynamic extent, depending on the type of namespace. Lexical scope means that visibility is physically restricted to the block in which the binding is established. References which are not textually (i.e. lexically) embedded in that block simply do not see that binding.
The tags in a TAGBODY have lexical scope. The expression (GO X) is erroneous if it is not actually embedded in a TAGBODY which contains a label X. However, the label bindings disappear when the TAGBODY terminates its execution, because they have dynamic extent. If that block of code is re-entered by the invocation of a lexical closure, it is invalid for the body of that closure to try to transfer control to a tag via GO:
When the TAGBODY is executed, it first evaluates the setf form which stores a function in the special variable *stashed*. Then the (go end-label) transfers control to end-label, skipping the code (print "Hello"). Since end-label is at the end of the tagbody, the tagbody terminates, yielding NIL. Suppose that the previously remembered function is now called:
This situation is erroneous. One implementation's response is an error condition containing the message, "GO: tagbody for tag SOME-LABEL has already been left". The function tried to evaluate (go some-label), which is lexically embedded in the tagbody, and resolves to the label. However, the tagbody isn't executing (its extent has ended), and so the control transfer cannot take place.
Local function bindings in Lisp have lexical scope, and variable bindings also have lexical scope by default. By contrast with GO labels, both of these have indefinite extent. When a lexical function or variable binding is established, that binding continues to exist for as long as references to it are possible, even after the construct which established that binding has terminated. References to a lexical variables and functions after the termination of their establishing construct are possible thanks to lexical closures.
Lexical binding is the default binding mode for Common Lisp variables. For an individual symbol, it can be switched to dynamic scope, either by a local declaration, by a global declaration. The latter may occur implicitly through the use of a construct like DEFVAR or DEFPARAMETER. It is an important convention in Common Lisp programming that special (i.e. dynamically scoped) variables have names which begin and end with an asterisk. If adhered to, this convention effectively creates a separate namespace for special variables, so that variables intended to be lexical are not accidentally made special.
Lexical scope is useful for several reasons.
Firstly, references to variables and functions can be compiled to efficient machine code, because the run-time environment structure is relatively simple. In many cases it can be optimized to stack storage, so opening and closing lexical scopes has minimal overhead. Even in cases where full closures must be generated, access to the closure's environment is still efficient; typically each variable becomes an offset into a vector of bindings, and so a variable reference becomes a simple load or store instruction a base-plus-offset addressing mode.
Secondly, lexical scope (combined with indefinite extent) gives rise to the lexical closure, which in turn creates a whole paradigm of programming centered around the use of functions being first-class objects, which is at the root of functional programming.
Thirdly, perhaps most importantly, even if lexical closures are not exploited, the use of lexical scope isolates program modules from unwanted interactions. Due to their restricted visibility, lexical variables are private. If one module A binds a lexical variable X, and calls another module B, references to X in B will not accidentally resolve to the X bound in A. B simply has no access to X. For situations in which disciplined interactions through a variable are desirable, Common Lisp provides special variables. Special variables allow for a module A to set up a binding for a variable X which is visible to another module B, called from A. Being able to do this is an advantage, and being able to prevent it from happening is also an advantage; consequently, Common Lisp supports both lexical and dynamic scope.
Macros allow Lisp programmers to create new syntactic forms in the language. For instance, this macro provides the
until loop form, which may be familiar from languages such as Perl:
All macros must be expanded before the source code containing them can be evaluated or compiled normally. Macros can be considered functions that accept and return abstract syntax trees (Lisp S-expressions). These functions are invoked before the evaluator or compiler to produce the final source code. Macros are written in normal Common Lisp, and may use any Common Lisp (or third-party) operator available. The backquote notation used above is provided by Common Lisp specifically to simplify the common case of substitution into a code template.
Variable capture can introduce software defects. This happens in one of the following two ways:
The Scheme dialect of Lisp provides a macro-writing system which provides the referential transparency that eliminates both types of capture problem. This type of macro system is sometimes called "hygienic", in particular by its proponents (who regard macro systems which do not automatically solve this problem as unhygienic).
In Common Lisp, macro hygiene is ensured one of two different ways.
One approach is to use gensyms: guaranteed-unique symbols which can be used in a macro-expansion without threat of capture. The use of gensyms in a macro definition is a manual chore, but macros can be written which simplify the instantiation and use of gensyms. Gensyms solve type 2 capture easily, but they are not applicable to type 1 capture in the same way, because the macro expansion cannot rename the interfering symbols in the surrounding code which capture its references. Gensyms could be used to provide stable aliases for the global symbols which the macro expansion needs. The macro expansion would use these secret aliases rather than the well-known names, so redefinition of the well-known names would have no ill effect on the macro.
Another approach is to use packages. A macro defined in its own package can simply use internal symbols in that package in its expansion. The use of packages deals with type 1 and type 2 capture.
However, packages don't solve the type 1 capture of references to standard Common Lisp functions and operators. The reason is that the use of packages to solve capture problems revolves around the use of private symbols (symbols in one package, which are not imported into, or otherwise made visible in other packages). Whereas the Common Lisp library symbols are external, and frequently imported into or made visible in user-defined packages.
The following is an example of unwanted capture in the operator namespace, occurring in the expansion of a macro:
UNTIL macro will expand into a form which calls
DO which is intended to refer to the standard Common Lisp macro
DO. However, in this context,
DO may have a completely different meaning, so
UNTIL may not work properly.
Common Lisp solves the problem of the shadowing of standard operators and functions by forbidding their redefinition. Because it redefines the standard operator
DO, the preceding is actually a fragment of non-conforming Common Lisp, which allows implementations to diagnose and reject it.
Common Lisp includes a toolkit for object-oriented programming, the Common Lisp Object System or CLOS, which is one of the most powerful object systems available in any language. Originally proposed as an add-on, CLOS was adopted as part of the ANSI standard for Common Lisp. CLOS is a dynamic object system with multiple dispatch and multiple inheritance, and differs radically from the OOP facilities found in static languages such as C++ or Java. As a dynamic object system, CLOS allows changes at runtime to generic functions and classes. Methods can be added and removed, classes can be added and redefined, objects can be updated for class changes and the class of objects can be changed.
CLOS has been integrated into ANSI Common Lisp. Generic Functions can be used like normal functions and are a first-class data type. Every CLOS class is integrated into the Common Lisp type system. Many Common Lisp types have a corresponding class. There is more potential use of CLOS for Common Lisp. The specification does not say whether conditions are implemented with CLOS. Pathnames and streams could be implemented with CLOS. These further usage possibilities of CLOS for ANSI Common Lisp are not part of the standard. Actual Common Lisp implementations are using CLOS for pathnames, streams, input/output, conditions, the implementation of CLOS itself and more.
Common Lisp is a general-purpose programming language, in contrast to Lisp variants such as Emacs Lisp and AutoLISP which are embedded extension languages in particular products. Unlike many earlier Lisps, Common Lisp (like Scheme) uses lexical variable scope.
Most of the Lisp systems whose designs contributed to Common Lisp—such as ZetaLisp and Franz Lisp—used dynamically scoped variables in their interpreters and lexically scoped variables in their compilers. Scheme introduced the sole use of lexically-scoped variables to Lisp; an inspiration from ALGOL 68 which was widely recognized as a good idea. CL supports dynamically-scoped variables as well, but they must be explicitly declared as "special". There are no differences in scoping between ANSI CL interpreters and compilers.
Common Lisp is sometimes termed a Lisp-2 and Scheme a Lisp-1, referring to CL's use of separate namespaces for functions and variables. (In fact, CL has many namespaces, such as those for go tags, block names, and
loop keywords.) There is a long-standing controversy between CL and Scheme advocates over the tradeoffs involved in multiple namespaces. In Scheme, it is (broadly) necessary to avoid giving variables names which clash with functions; Scheme functions frequently have arguments named
lyst so as not to conflict with the system function
list. However, in CL it is necessary to explicitly refer to the function namespace when passing a function as an argument -- which is also a common occurrence, as in the
sort example above.
CL also differs from Scheme in its handling of boolean values. Scheme uses the special values #t and #f to represent truth and falsity. CL follows the older Lisp convention of using the symbols T and NIL, with NIL standing also for the empty list. In CL, any non-NIL value is treated as true by conditionals such as
if as are non-#f values in Scheme. This allows some operators to serve both as predicates (answering a boolean-valued question) and as returning a useful value for further computation.
Lastly, the Scheme standards documents require tail-call optimization, which the CL standard does not. Most CL implementations do offer tail-call optimization, although often only when the programmer uses an optimization directive. Nonetheless, common CL coding style does not favor the ubiquitous use of recursion that Scheme style prefers -- what a Scheme programmer would express with tail recursion, a CL user would usually express with an iterative expression in
loop, or (more recently) with the
See the Category Common Lisp implementations.
Common Lisp is defined by a specification (like Ada and C) rather than by a single implementation (like Perl). There are many implementations, and the standard spells out areas in which they may validly differ.
In addition, implementations tend to come with library packages, which provide functionality not covered in the standard. Free Software libraries have been created to support such features in a portable way, most notably Common-Lisp.net and the Common Lisp Open Code Collection project.
Common Lisp has been designed to be implemented by incremental compilers. Standard declarations to optimize compilation (such as function inlining) are proposed in the language specification. Most Common Lisp implementations compile source code to native machine code. Some implementations offer block compilers. Some implementations can create (optimized) stand-alone applications. Others compile to bytecode, which reduces speed but eases binary-code portability. There are also compilers that compile Common Lisp code to C code. The misconception that Lisp is a purely-interpreted language is most likely due to the fact that Lisp environments provide an interactive prompt and that functions are compiled one-by-one, in an incremental way. With Common Lisp incremental compilation is widely used.
Commercial implementations include:
Freely redistributable implementations include:
See the Category Common Lisp software.
Common Lisp is used in many commercial applications, including the Yahoo! Store web-commerce site, which originally involved Paul Graham and was later rewritten in C++ and Perl. Other notable examples include:
There also exist open-source applications written in Common Lisp, such as: