- Lisp (programming language)
Infobox programming language
name = Lisp
paradigm = multi-paradigm: functional, procedural, reflective
year = 1958
designer = John McCarthy
Steve Russell, Timothy P. Hart, and Mike Levin
latest release version =
latest release date =
turing-complete = Yes
typing = dynamic, strong
Common Lisp, Scheme, Emacs Lisp, Arc, ISLISP, Newlisp.
influenced by =
influenced = Logo,
Perl, Python, Smalltalk, Ruby, Dylan, Mathematica, Rebol
Lisp (or LISP) is a family of
computer programming languages with a long history and a distinctive, fully parenthesized syntax. Originally specified in 1958, Lisp is the second-oldest high-level programming languagein widespread use today; only Fortranis older. Like Fortran, Lisp has changed a great deal since its early days, and a number of dialects have existed over its history. Today, the most widely known general-purpose Lisp dialects are Common Lispand Scheme.
Lisp was originally created as a practical mathematical notation for computer programs, based on
Alonzo Church's lambda calculus. It quickly became the favored programming language for artificial intelligence(AI) research. As one of the earliest programming languages, Lisp pioneered many ideas in computer science, including tree data structures, automatic storage management, dynamic typing, object-oriented programming, and the self-hosting compiler.
The name "Lisp" derives from "List Processing Language".
Linked lists are one of Lisp languages' major data structures, and Lisp source codeis itself made up of lists. As a result, Lisp programs can manipulate source code as a data structure, giving rise to the macro systems that allow programmers to create new syntax or even new domain-specific programming languages embedded in Lisp.
The interchangeability of code and data also gives Lisp its instantly recognizable syntax. All program code is written as "
s-expressions", or parenthesized lists. A function call or syntactic form is written as a list with the function or operator's name first, and the arguments following; for instance, a function f that takes three arguments might be called using
(f x y z).
Lisp was invented by John McCarthy in 1958 while he was at the
Massachusetts Institute of Technology(MIT). McCarthy published its design in a paper in " Communications of the ACM" in 1960, entitled "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I"cite web | title=Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I| author=John McCarthy | url=http://www-formal.stanford.edu/jmc/recursive.html | accessdate=2006-10-13] ("Part II" was never published). He showed that with a few simple operators and a notation for functions, one can build a Turing-completelanguage for algorithms. Information Processing Languagewas the first AI language, from 1955 or 1956, and already included many of the concepts, such as list-processing and recursion, which came to be used in Lisp.
McCarthy's original notation used bracketed "
M-expressions" that would be translated into S-expressions. As an example, the M-expression
is equivalent to the S-expression
car [cons [A,B]
(car (cons A B)). Once Lisp was implemented, programmers rapidly chose to use S-expressions, and M-expressions were abandoned. M-expressions surfaced again with short-lived attempts of
MLISPcite web | title=MLISP Users Manual| author=David Canfield Smith | url=http://community.computerhistory.org/scc/projects/LISP/stanford/Smith-MLISP-AIM-84.pdf | accessdate=2006-10-13] by Horace Eneaand CGOLby Vaughan Pratt.
Lisp was first implemented by
Steve Russellon an IBM 704computer. Russell had read McCarthy's paper, and realized (to McCarthy's surprise) that the Lisp "eval" function could be implemented in machine code. [ According to what reported by Paul Grahamin " Hackers & Painters", p. 185, McCarthy said: "Steve Russell said, look, why don't I program this "eval"..., and I said to him, ho, ho, you're confusing theory with practice, this "eval" is intended for reading, not for computing. But he went ahead and did it. That is, he compiled the "eval" in my paper into IBM 704machine code, fixing bug , and then advertised this as a Lisp interpreter, which it certainly was. So at that point Lisp had essentially the form that it has today..."] The result was a working Lisp interpreter which could be used to run Lisp programs, or more properly, 'evaluate Lisp expressions.'
Two assembly language routines for the
IBM 704became the primitive operations for decomposing lists:
car(Contents of Address Register) and
cdr(Contents of Decrement Register). Lisp dialects still use
cdr(pronEng|ˈkɑr and IPA|/ˈkʊdər/) for the operations that return the first item in a list and the rest of the list respectively.
The first complete Lisp compiler, written in Lisp, was implemented in 1962 by Tim Hart and Mike Levin at MIT.cite web | title=AI Memo 39-The new compiler| author=Tim Hart and Mike Levin | url=ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-039.pdf | accessdate=2006-10-13] This compiler introduced the Lisp model of incremental compilation, in which compiled and interpreted functions can intermix freely. The language used in Hart and Levin's memo is much closer to modern Lisp style than McCarthy's earlier code.
Genealogy and variants
Over its fifty-year history, Lisp has spawned many variations on the core theme of an S-expression language. Moreover, each given dialect may have several implementations — for instance, there are more than a dozen implementations of
Differences between dialects may be quite visible — for instance, Common Lisp and Scheme use different keywords to define functions. Within a dialect that is standardized, however, conforming implementations support the same core language, but with different extensions and libraries.
Historically significant dialects
*LISP 1.5 [http://community.computerhistory.org/scc/projects/LISP/book/LISP%201.5%20Programmers%20Manual.pdf] – First widely distributed version, developed by McCarthy and others at MIT. So named because it contained several improvements on the original "LISP 1" interpreter, but was not a major restructuring as the planned
LISP 2would be.
Stanford LISP1.6 [http://community.computerhistory.org/scc/projects/LISP/stanford/SAILON-28.6.pdf] – This was a successor to LISP 1.5 developed at the Stanford AI Lab, and widely distributed to PDP-10systems running the TOPS-10operating system. It was rendered obsolete by Maclisp and InterLisp.
*MACLISP [http://zane.brouhaha.com/~healyzh/doc/lisp.doc.txt] – developed for MIT's
Project MAC(no relation to Apple's Macintosh, nor to McCarthy), direct descendant of LISP 1.5. It ran on the PDP-10 and Multicssystems. (MACLISP would later come to be called Maclisp, and is often referred to as MacLisp.)
InterLisp[http://www.bitsavers.org/pdf/xerox/interlisp/1974_InterlispRefMan.pdf] – developed at BBN Technologiesfor PDP-10 systems running the Tenex operating system, later adopted as a "West coast" Lisp for the Xerox Lisp machines. A small version called "InterLISP 65" was published for Atari's 6502-based computer line. For quite some time Maclisp and InterLisp were strong competitors.
Franz Lisp– originally a Berkeley project; later developed by Franz Inc. The name is a humorous deformation of " Franz Liszt". The name "Franz Lisp" does "not" refer to Allegro Common Lisp, the dialect of Common Lisp sold by Franz Inc. in more recent years.
ZetaLisp– used on the Lisp machines, direct descendant of Maclisp.
*Common Lisp (1984), as described by "" – a consolidation of several divergent attempts (ZetaLisp,
Spice Lisp, NIL, and S-1 Lisp) to create successor dialects [http://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node6.html] to Maclisp, with substantive influences from the Scheme dialect as well. This version of Common Lisp was available for wide-ranging platforms and was accepted by many as a de facto standard[http://www.cs.cmu.edu/Groups/AI/html/faqs/lang/lisp/part2/faq-doc-13.html] until the publication of ANSI Common Lisp (ANSI X3.226-1994).
EuLisp– attempt to develop a new efficient and cleaned-up Lisp.
ISLisp– attempt to develop a new efficient and cleaned-up Lisp. Standardized as [http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=22987 ISO/IEC 13816:1997] and later revised as [http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=44338 ISO/IEC 13816:2007] - "Information technology – Programming languages, their environments and system software interfaces – Programming language ISLISP".
*IEEE Scheme – IEEE standard, 1178-1990 (R1995)
ANSI Common Lisp– an American National Standards Institute(ANSI) standard for Common Lisp, created by subcommittee X3J13, chartered [http://www.nhplace.com/kent/CL/x3j13-86-020.html] to begin with "Common Lisp: The Language" as a base document and to work through a public consensus process to find solutions to shared issues of portability of programs and compatibility of Common Lisp implementations. Although formally an ANSI standard, the implementation, sale, use, and influence of ANSI Common Lisp has been and continues to be seen world-wide.
*arc – a new sub version of Lisp created by Paul Graham, released on January 29, 2008.
Connection to artificial intelligence
Since its inception, Lisp was closely connected with the
artificial intelligenceresearch community, especially on PDP-10[The 36-bit word size of the PDP-6/ PDP-10was influenced by the usefulness of having two Lisp 18-bit pointers in a single word. "The PDP-6 project started in early 1963, as a 24-bit machine. It grew to 36 bits for LISP, a design goal." [http://groups.google.com/group/alt.folklore.computers/browse_thread/thread/6e5602ce733d0ec/17597705ae289112] ] systems. Lisp was used as the implementation of the programming language Micro Planner that was the foundation for the famous AI system SHRDLU. In the 1970s, as AI research spawned commercial offshoots, the performance of existing Lisp systems became a growing issue.
Lisp was a difficult system to implement with the compiler techniques and stock hardware of the 1970s. Garbage collection routines, developed by then-
MITgraduate student Daniel Edwards, made it practical to run Lisp on general-purpose computing systems, but efficiency was still a problem. This led to the creation of Lisp machines: dedicated hardware for running Lisp environments and programs. Advances in both computer hardware and compiler technology soon made Lisp machines obsolete, to the detriment of the Lisp market.
During the 1980s and 1990s, a great effort was made to unify the numerous Lisp dialects (most notably,
InterLisp, Maclisp, ZetaLisp, MetaLisp, and Franz Lisp) into a single language. The new language, Common Lisp, was essentially a compatible subset of the dialects it replaced. In 1994, ANSIpublished the Common Lisp standard, "ANSI X3.226-1994 Information Technology Programming Language Common Lisp." At that time the world market for Lisp was much smaller than it is today.
Having declined somewhat in the 1990s, Lisp has experienced a regrowth of interest since 2000. Most new activity is focused around
open sourceimplementations of Common Lisp, and includes the development of new portable libraries and applications. This interest can be measured partly by sales from the print version of " Practical Common Lisp" by Peter Seibel, a tutorial for new Lisp programmers published in 2004 [ [http://gigamonkeys.com/blog/2007/05/26/pcl-third-printing.html Practical Common Lisp going into 3rd printing] ] . It was briefly Amazon.com's second most popular programming book. It is now available online for free [ [http://gigamonkeys.com/book/ Practical Common Lisp] ] . This can also be measured by higher attendance of related conferences [ [http://www.regdeveloper.co.uk/2007/04/02/international_lisp_conference_2007/ Keeping Lisp alive and practical | Reg Developer] ] and analyzing newsgroup postings [ [http://www.complang.tuwien.ac.at/anton/comp. _st. title=The Road To Lisp Survey | url=http://wiki.alu.org/The_Road_To_Lisp_Survey | accessdate=2006-10-13] Contemporary programmers learning Lisp may also have been introduced to it by Peter Norvig's commentary [ [http://norvig.com/Lisp-retro.html A Retrospective on PAIP ] ] , author of ' and ', or Phillip Greenspun, who has had business successes involving Lisp.
This increase in awareness may be contrasted to the "
AI winter" and Lisp's brief gain in the mid-1990s. [ [http://www.faqs.org/docs/artu/ch14s05.html Trends for the Future] ]
Major modern dialects
The two major dialects of Lisp used for general-purpose programming today are
Common Lispand Scheme. These languages represent significantly different design choices.
Common Lisp, descended mainly from
MacLisp, Interlisp, and Lisp Machine Lisp, is an expanded superset of earlier Lisp dialects, with a large language standard including many built-in data types and syntactic forms, as well as an object system. Scheme is a more minimalist design, with a much smaller set of standard features but with certain implementation features (such as tail-call optimizationand full continuations) not necessarily found in Common Lisp. Common Lisp also borrowed certain features from Scheme such as lexical scoping and lexical closures.
In addition, Lisp dialects are used as
scripting languages in a number of applications, with the most well-known being Emacs Lispin the Emacseditor and Autolispin AutoCAD.
Lisp was the first homoiconic programming language: the primary representation of program code is the same type of list structure that is also used for the main data structures. As a result, Lisp functions can be manipulated, altered or even created within a Lisp program without extensive parsing or manipulation of binary machine code. This is generally considered one of the primary advantages of the language with regards to its expressiveness, and makes the language amenable to
The now-ubiquitous "if-then-else" structure, now taken for granted as an essential element of any programming language, was invented by McCarthy for use in Lisp, where it saw its first appearance in a more general form (the cond structure). It was inherited by Algol, which popularized it.
Lisp deeply influenced
Alan Kay, the leader of the research on Smalltalk, and then in turn Lisp was influenced by Smalltalk, by adopting object-oriented programming features (classes, instances, etc.) in the late 1970s.
Largely because of its resource requirements with respect to early computing hardware (including early microprocessors), Lisp did not become as popular outside of the
AIcommunity as Fortranand the ALGOL-descended C language. Newer languages such as Java and Python have incorporated some limited versions of some of the features of Lisp, but are necessarily unable to bring the coherence and synergy of the full concepts found in Lisp. Because of its suitability to ill-defined, complex, and dynamic applications, Lisp is currently enjoying some resurgence of popular interest.
See also "The evolution of Lisp",cite web | title=The evolution of Lisp| author=Guy L Steele Jr, Richard P Gabriel | url=http://www.dreamsongs.com/NewFiles/HOPL2-Uncut.pdf | accessdate=2006-10-12] a paper written by
Guy L. Steele, Jr.and Richard P. Gabriel.
yntax and semantics
:"Note: This article's examples are written in
Common Lisp(though most are also valid in Scheme)."
Lisp is an expression-oriented language. Unlike most other languages, no distinction is made between "expressions" and "statements"; all code and data are written as expressions. When an expression is "evaluated", it produces a value (or list of values), which then can be embedded into other expressions.
McCarthy's 1958 paper introduced two types of syntax:
S-expressions (Symbolic Expressions, also called "sexps"), which mirror the internal representation of code and data; and M-expressions (Meta Expressions), which express functions of S-expressions. M-expressions never found favor, and almost all Lisps today use S-expressions to manipulate both code and data.
The use of parentheses is Lisp's most immediately obvious difference from other programming language families. As a result, students have long given Lisp nicknames such as "Lost In Stupid Parentheses", or "Lots of Irritating Superfluous Parentheses".cite web | title=The Jargon File - Lisp| url=http://www.catb.org/~esr/jargon/html/L/LISP.html| accessdate=2006-10-13] However, the S-expression syntax is also responsible for much of Lisp's power; the syntax is extremely regular, which facilitates manipulation by computer. However, the syntax of Lisp is not limited to traditional parentheses notation. It can be extended to include alternative notations.
XMLisp, for instance, is a Common Lisp extension that employs the metaobject-protocol to integrate S-expressions with the Extensible Markup Language (XML).
The reliance on expressions gives the language great flexibility. Because Lisp functions are themselves written as lists, they can be processed exactly like data. This allows easy writing of programs which manipulate other programs (
metaprogramming). Many Lisp dialects exploit this feature using macro systems, which enables extension of the language almost without limit.
A Lisp list is written with its elements separated by whitespace, and surrounded by parentheses. For example,
(1 2 foo)is a list whose elements are three "atoms": the values
foo. These values are implicitly typed: they are respectively two integers and a Lisp-specific data type called a "symbol", and do not have to be declared as such.
The empty list
()is also represented as the special atom
nil. This is the only entity in Lisp which is both an atom and a list.
Expressions are written as lists, using
prefix notation. The first element in the list is the name of a "form", i.e., a function, operator, macro, or "special operator" (see below.) The remainder of the list are the arguments. For example, the function
listreturns its arguments as a list, so the expressionevaluates to the list
(1 2 foo). The "quote" before the arguments in the preceding example is a "special operator" which prevents the quoted arguments from being evaluated (not strictly necessary for the numbers, since 1 evaluates to 1, etc). Any unquoted expressions are recursively evaluated before the enclosing expression is evaluated. For example,evaluates to the list
(1 2 (3 4)). Note that the third argument is a list; lists can be nested.
Arithmetic operators are treated similarly. The expressionevaluates to 10. The equivalent under
infix notationwould be "
1 + 2 + 3 + 4". Arithmetic operators in Lisp are variadic (or "
n-ary"), able to take any number of arguments.
"Special operators" (sometimes called "special forms" by older users) provide Lisp's control structure. For example, the special operator
iftakes three arguments. If the first argument is non-nil, it evaluates to the second argument; otherwise, it evaluates to the third argument. Thus, the expressionevaluates to
(3 4 "bar"). Of course, this would be more useful if a non-trivial expression had been substituted in place of
Another special operator,
lambda, is used to bind variables to values which are then evaluated within an expression. This operator is also used to create functions: the arguments to
lambdaare a list of arguments, and the expression or expressions to which the function evaluates (the returned value is the value of the last expression that is evaluated). The expressionevaluates to a function that, when applied, takes one argument, binds it to
argand returns the number one greater than that argument. Lambda expressions are treated no differently from named functions; they are invoked the same way. Therefore, the expressionevaluates to
In the original LISP there were two fundamental
data types: atoms and lists. A list was a finite ordered sequence of elements, where each element is in itself either an atom or a list, and an atom was a numberor a symbol. A symbol was essentially a unique named item, written as an Alphanumericstring in source code, and used either as a variable name or as a data item in symbolic processing. For example, the list
(FOO (BAR 1) 2)contains three elements: the symbol FOO, the list
(BAR 1), and the number 2.
The essential difference between atoms and lists was that atoms were immutable and unique. Two atoms that appeared in different places in source code but were written in the exact same way represented the same object, whereas each list was a separate object that could be altered independently of other lists and could be distinguished from other lists by comparison operators.
As more data types were introduced in later Lisp dialects, and
programming styles evolved, the concept of an atom lost importance. Many dialects still retained the predicate "atom" for legacy compatibility, defining it true for any object which is not a cons.
Conses and lists
A Lisp list is a
singly-linked list. Each cell of this list is called a "cons" (in Scheme, a "pair"), and is composed of two pointers, called the "car" and "cdr". These are equivalent to the
nextfields discussed in the article "
linked list", respectively.
Of the many data structures that can be built out of cons cells, one of the most basic is called a "proper list". A proper list is either the special
nil(empty list) symbol, or a cons in which the
carpoints to a datum (which may be another cons structure, such as a list), and the
cdrpoints to another proper list.
If a given cons is taken to be the head of a linked list, then its car points to the first element of the list, and its cdr points to the rest of the list. For this reason, the
cdrfunctions are also called
restwhen referring to conses which are part of a linked list (rather than, say, a tree).
Thus, a Lisp list is not an atomic object, as an instance of a container class in C++ or Java would be. A list is nothing more than an aggregate of linked conses. A variable which refers to a given list is simply a pointer to the first cons in the list. Traversal of a list can be done by "cdring down" the list; that is, taking successive cdrs to visit each cons of the list; or by using any of a number of
higher-order functions to map a function over a list.
Because conses and lists are so universal in Lisp systems, it is a common misconception that they are Lisp's only data structures. In fact, all but the most simplistic Lisps have other data structures – such as vectors (
arrays), hash tables, structures, and so forth.
-expressions represent lists
Parenthesized S-expressions represent linked list structure. There are several ways to represent the same list as an S-expression. A cons can be written in "dotted-pair notation" as
(a . b), where
ais the car and
bthe cdr. A longer proper list might be written
(a . (b . (c . (d . nil))))in dotted-pair notation. This is conventionally abbreviated as
(a b c d)in "list notation". An improper list [NB: a so-called "dotted list" is only one kind of "improper list". The other kind is the "circular list" where the cons cells form a loop. Typically this is represented using #n=(...) to represent the target cons cell that will have multiple references, and #n# is used to refer to this cons. For instance, (#1=(a b) #1#) would normally be printed as ((a b) a b) (without circular structure printing enabled), but makes the reuse of the cons cell clear. #1=(a . #1#) cannot normally be printed as it is circular, the CDR of the cons cell defined by #1= is itself.] may be written in a combination of the two – as
(a b c . d)for the list of three conses whose last cdr is
d(i.e., the list
(a . (b . (c . d)))in fully specified form).
Lisp provides many built-in procedures for accessing and controlling lists. Lists can be created directly with the
listprocedure, which takes any number of arguments, and returns the list of these arguments.Because of the way that lists are constructed from
cons pairs, the
procedure can be used to add an element to the front of a list. Note that the
consprocedure is asymmetric in how it handles list arguments, because of how lists are constructed.The
procedure appends two (or more) lists to one another. Because Lisp lists are linked lists, appending two lists has asymptotic time complexity .
Lisp lists, being simple linked lists, can share structure with one another. That is to say, two lists can have the same "tail", or final sequence of conses. For instance, after the execution of the following Common Lisp code:the lists
(a b c)and
(x b c)respectively. However, the tail
(b c)is the same structure in both lists. It is not a copy; the cons cells pointing to
care in the same memory locations for both lists.
Sharing structure rather than copying can give a dramatic performance improvement. However, this technique can interact in undesired ways with functions that alter lists passed to them as arguments. Altering one list, such as by replacing the
goose, will affect the other:This changes
(a b goose), but thereby also changes
(x b goose)– a possibly unexpected result. This can be a source of bugs, and functions which alter their arguments are documented as "destructive" for this very reason.
functional programmingavoid destructive functions. In the Scheme dialect, which favors the functional style, the names of destructive functions are marked with a cautionary exclamation point, or "bang" — such as
set-car!(read "set car bang"), which replaces the car of a cons. In the Common Lisp dialect, destructive functions are commonplace; the equivalent of
rplacafor "replace car." This function is rarely seen however as Common Lisp includes a special facility,
setf, to make it easier to define and use destructive functions. A frequent style in Common Lisp is to write code functionally (without destructive calls) when prototyping, then to add destructive calls as an optimization where it is safe to do so.
elf-evaluating forms and quoting
Lisp evaluates expressions which are entered by the user. Symbols and lists evaluate to some other (usually, simpler) expression – for instance, a symbol evaluates to the value of the variable it names;
(+ 2 3)evaluates to
5. However, most other forms evaluate to themselves: if you enter
5into Lisp, it returns
Any expression can also be marked to prevent it from being evaluated (as is necessary for symbols and lists). This is the role of the
quotespecial operator, or its abbreviation
'(a single quotation mark). For instance, usually if you enter the symbol
fooyou will get back the value of the corresponding variable (or an error, if there is no such variable). If you wish to refer to the literal symbol, you enter
(quote foo)or, usually,
Both Common Lisp and Scheme also support the "backquote" operator (often called "quasiquote" by Schemers), entered with the
`character. This is almost the same as the plain quote, except it allows expressions to be evaluated and their values interpolated into a quoted list with the comma and comma-at operators. If the variable
snuehas the value
`(foo ,snue)evaluates to
(foo (bar baz)), while
`(foo ,@snue)evaluates to
(foo bar baz). The backquote is most frequently used in defining macro expansions.
Self-evaluating forms and quoted forms are Lisp's equivalent of literals. It is possible to modify the values of (mutable) literals in program code. For instance, if a function returns a quoted form, and the code that calls the function modifies the form, this will alter the behavior of the function on subsequent iterations.
Modifying a quoted form like this is generally considered bad style, and is defined by some implementations as erroneous (resulting in "undefined" behavior in compiled files, because the file-compiler can coalesce similar constants, put them in write-protected memory, etc). When behavior like this is intentional, using a closure is the explicit way to do it.
Lisp's formalization of quotation has been noted by
Douglas Hofstadter(in " Gödel, Escher, Bach") and others as an example of the philosophical idea of self-reference.
cope and closure
The modern Lisp family splits over the use of dynamic or static (aka lexical) scope. Scheme and Common Lisp make use of static scoping by default, while
Newlispand the embedded languages in Emacsand AutoCADuse dynamic scoping.
List structure of program code
A fundamental distinction between Lisp and other languages is that in Lisp, the textual representation of a program is simply a human-readable description of the same internal data structures (linked lists) as would be used by the underlying Lisp system.
Lisp macros operate on these structures. Because Lisp code has the same structure as lists, macros can be built with any of the list-processing functions in the language. In short, anything that Lisp can do to a data structure, Lisp macros can do to code. In contrast, in most other languages the parser's output is purely internal to the language implementation and cannot be manipulated by the programmer. Macros in C, for instance, operate on the level of the "
preprocessor", before the parser is invoked, and cannot re-structure the program code in the way Lisp macros can.
In simplistic Lisp implementations, this list structure is directly interpreted to run the program; a function is literally a piece of list structure which is traversed by the interpreter in executing it. However, most actual Lisp systems (including all conforming
Common Lispsystems) also include a compiler. The compiler translates list structure into machine code or bytecodefor execution.
Evaluation and the Read-Eval-Print Loop
Lisp languages are frequently used with an interactive
command line, which may be combined with an integrated development environment. The user types in expressions at the command line, or directs the IDE to transmit them to the Lisp system. Lisp "reads" the entered expressions, "evaluates" them, and "prints" the result. For this reason, the Lisp command line is called a " read-eval-print loop", or " REPL".
The basic operation of the REPL is as follows. This is a simplistic description which omits many elements of a real Lisp, such as quoting and macros.
readfunction accepts textual S-expressions as input, and parses them into list structure. For instance, if you type the string
(+ 1 2)at the prompt,
readtranslates this into a linked list with three elements: the symbol
+, the number 1, and the number 2. It so happens that this list is also a valid piece of Lisp code; that is, it can be evaluated. This is because the car of the list names a function — the addition operation.
evalfunction evaluates list structure, returning some other piece of structure as a result. Evaluation does not have to mean interpretation; some Lisp systems compile every expression to native machine code. It is simple, however, to describe evaluation as interpretation: To evaluate a list whose car names a function,
evalfirst evaluates each of the arguments given in its cdr, then applies the function to the arguments. In this case, the function is addition, and applying it to the argument list
(1 2)yields the answer
3. This is the result of the evaluation.
It is the job of the
3this is trivial. An expression which evaluated to a piece of list structure would require that
To implement a Lisp REPL, it is necessary only to implement these three functions and an infinite-loop function. (Naturally, the implementation of
evalwill be complicated, since it must also implement all special operators like
if.) This done, a basic REPL itself is but a single line of code:
(loop (print (eval (read)))).
Lisp is usually evaluated eagerly. In
Common Lisp, arguments are evaluated in applicative order('leftmost innermost'), while in Scheme order of arguments is undefined, leaving room for optimization by a compiler.
Lisp originally had very few control structures, but many more were added during the language's evolution. (Lisp's original conditional operator,
cond, is the precursor to later
Programmers in the Scheme dialect often express loops using
tail recursion. Scheme's commonality in academic computer science has led some students to believe that tail recursion is the only, or the most common, way to write iterations in Lisp; this is incorrect. All frequently seen Lisp dialects have imperative-style iteration constructs, from Scheme's
Common Lisp's complex
loopexpressions. Moreover, the key issue that makes this an objective rather than subjective matter is that Scheme makes specific requirements for the handling of
tail calls, and consequently the reason that the use of tail recursion is generally encouraged for Scheme is that the practice is expressly supported by the language definition itself. By contrast, ANSI Common Lispdoes not require [ [http://www.lispworks.com/documentation/HyperSpec/Body/03_bbc.htm 126.96.36.199 Semantic Constraints] in [http://www.lispworks.com/documentation/HyperSpec/Front/index.htm "Common Lisp HyperSpec"] ] the optimization commonly referred to as tail call elimination. Consequently, the fact that tail recursive style as a casual replacement for the use of more traditional iterationconstructs (such as
loop) is discouraged [4.3. Control Abstraction (Recursion vs. Iteration) in [http://www.cs.umd.edu/~nau/cmsc421/norvig-lisp-style.pdf Tutorial on Good Lisp Programming Style] by Pitman and Norvig, August, 1993.] in Common Lisp is not just a matter of stylistic preference, but potentially one of efficiency (since an apparent tail call in Common Lisp may not compile as a simple jump) and program correctness (since tail recursion may increase stack use in Common Lisp, risking
Some Lisp control structures are "special operators", equivalent to other languages' syntactic keywords. Expressions using these operators have the same surface appearance as function calls, but differ in that the arguments are not necessarily evaluated — or, in the case of an iteration expression, may be evaluated more than once.
In contrast to most other major programming languages, Lisp allows the programmer to implement control structures using the language itself. Several control structures are implemented as Lisp macros, and can even be macro-expanded by the programmer who wants to know how they work.
Both Common Lisp and Scheme have operators for non-local control flow. The differences in these operators are some of the deepest differences between the two dialects. Scheme supports "re-entrant
continuations" using the
call/ccprocedure, which allows a program to save (and later restore) a particular place in execution. Common Lisp does not support re-entrant continuations, but does support several ways of handling escape continuations.
Frequently, the same algorithm can be expressed in Lisp in either an imperative or a functional style. As noted above, Scheme tends to favor the functional style, using tail recursion and continuations to express control flow. However, imperative style is still quite possible. The style preferred by many Common Lisp programmers may seem more familiar to programmers used to structured languages such as C, while that preferred by Schemers more closely resembles pure-functional languages such as Haskell.
Because of Lisp's early heritage in list processing, it has a wide array of higher-order functions relating to iteration over sequences. In many cases where an explicit loop would be needed in other languages (like a
forloop in C) in Lisp the same task can be accomplished with a higher-order function. (The same is true of many functional programming languages.)
A good example is a function which in Scheme is called
mapand in Common Lisp is called
mapcar. Given a function and one or more lists,
mapcarapplies the function successively to the lists' elements in order, collecting the results in a new list:This applies the
+function to each corresponding pair of list elements, yielding the result
(11 22 33 44 55).
Here are examples of Common Lisp code.
The basic "
Hello world" program:As the reader may have noticed from the above discussion, Lisp syntax lends itself naturally to recursion. Mathematical problems such as the enumeration of recursively defined sets are simple to express in this notation.
Evaluate a number's
factorial:An alternative implementation, often faster than the previous version if the Lisp system has tail recursionoptimization:Contrast with an iterative version which uses Common Lisp's
The following function reverses a list. (Lisp's built-in "reverse" function does the same thing.)
Various object systems and models have been built on top of, alongside, or into Lisp, including:
*ObjectLisp [pg 17 of Bobrow 1986] or Object Lisp, favored by
Lisp Machines Incorporated
*LOOPS (Lisp Object-Oriented Programming System) and the later
*Flavors, built at MIT, and its descendant New Flavors, which were favored by
Common Lisp Object System, CLOS (descended from New Flavors and CommonLOOPS)
*KR (short for Knowledge Representation), a
constraints-based object system developed to aid the writing of Garnet, a GUI library for Common Lisp
* KEE was written similarly, but incorporating an
inference engine. [Veitch, p 108, 1988] and a truth maintenance system (ATMS).
*Lush is an object-oriented lisp code with a goal of extensive programming capabilities, as it interfaces with many data libraries for math and science, but also interfaces with C code in-line, is still dynamic, and has graphics and hardware support.
SageCLOS, an Object Oriented Interface to AutoLISP invented by Ralph GimenezCLOS features multiple inheritance, multiple dispatch("multimethods"), and a powerful system of "method combinations". In fact, Common Lisp, which includes CLOS, was the first object-oriented language to be officially standardized.
* M&P [www.hdolder.com/ARTEC_EN.htm] "The first model driven system completely opreational" incorporates mpLISP, a minimum LISP dialect and a powerful LISP interpreter that enable a new object oriented architecture.
: "SQL, Lisp, and Haskell are the only programming languages that I've seen where one spends more time thinking than typing.": —
Philip Greenspun, March 2007, [http://blogs.law.harvard.edu/philg/2005/03/07/how-long-is-the-average-internet-discussion-forum-posting/]
: "I suppose I should learn Lisp, but it seems so foreign.": —
Paul Graham, November 1983
: "One can even conjecture that Lisp owes its survival specifically to the fact that its programs are lists, which everyone, including me, has regarded as a disadvantage.": — John McCarthy, Inventor of Lisp, "
Early History of Lisp"
: "Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified bug-ridden slow implementation of half of Common Lisp.": —
Philip Greenspun, often called " Greenspun's Tenth Ruleof Programming" [cite web | title=Research| author=Phillip Greenspun | url=http://philip.greenspun.com/research/ | accessdate=2006-10-13]
: "Please don't assume Lisp is only useful for Animation and Graphics, AI, Bioinformatics, B2B and E-Commerce, Data Mining, EDA/Semiconductor applications, Expert Systems, Finance, Intelligent Agents, Knowledge Management, Mechanical CAD, Modeling and Simulation, Natural Language, Optimization, Research, Risk Analysis, Scheduling, Telecom, and Web Authoring just because these are the only things they happened to list.": —
: "Lisp has all the visual appeal of oatmeal with fingernail clippings mixed in.": —
Larry Wall, creator of the Perl programming language
: "Lisp being the most powerful and cleanest of languages, that's the language that the GNU project always prefers.": —
: "The greatest single programming language ever designed.": —
Emacsis written in Lisp, which is the only computer language that is beautiful.": — Neal Stephenson, " In the Beginning...was the Command Line"
: "A Lisp programmer knows the value of everything, but the cost of nothing.": —
Alan Perlis, " Epigrams on Programming"
: "I think it's the only computer programming language that is mathematically respectable, because it's the only one that I can prove theorems about!": —
: "Pascal is for building pyramids -- imposing, breathtaking structures built by armies pushing heavy blocks into place. Lisp is for building organisms -- imposing, breathtaking, dynamic structures built by squads fitting fluctuating myriads of simpler organisms into place." : —
* "A History and Description of CLOS", by Jim Veitch. Pages 107-158 of "Handbook of Programming Languages, Volume IV: Functional and Logic Programming Languages", ed.
Peter H. Salus. 1998 (1st edition), Macmillian Technical Publishing; ISBN 1-57870-011-6
Structure and Interpretation of Computer Programs", by Harold Abelson, Gerald Jay Sussmanand Julie Sussman. 1996 (2nd edition), MIT Press; ISBN 0262011530.
* [http://lispers.org/ Lispers.org] - Choice selection of Lisp quotes by eminent Lispers.
* [http://www-formal.stanford.edu/jmc/history/lisp/node3.html The implementation of LISP] , Stanford
* [http://www.gnu.org/gnu/rms-lisp.html My Lisp Experiences and the Development of GNU Emacs] ,
transcriptof Richard Stallman's speech, 28 Oct 2002, at the International Lisp Conference
* [http://www.defmacro.org/ramblings/lisp.html The Nature of Lisp] , DefMacro
Paul Graham, " Hackers & Painters. Big Ideas from the Computer Age", 2004, O'Reilly, ISBN 0-596-00662-4
Scheme (programming language)
* [http://www-formal.stanford.edu/jmc/history/lisp/lisp.html History of Lisp]
John McCarthy (computer scientist)'s history of 12 Feb 79
* [http://www8.informatik.uni-erlangen.de/html/lisp-enter.html Lisp History] Herbert Stoyan's history compiled from the documents (acknowledged by McCarthy as more complete than his own, see: [http://www-formal.stanford.edu/jmc/history/ McCarthy's history links] )
* [http://groups.google.com/group/comp.lang.lisp/topics comp.lang.lisp]
* [http://lisp.org Association of Lisp Users]
* [http://wiki.alu.org/ Association of Lisp Users Wiki] , a general discussion of things Lispish
* [http://community.computerhistory.org/scc/projects/LISP/ History of LISP at the Computer History Museum]
* [http://www.lispmachine.net LispMachine.net - Lisp books and information]
* [http://paulgraham.com/onlisptext.html?asdf On Lisp] , a free book by
* [http://se-radio.net/podcast/2008-01/episode-84-dick-gabriel-lisp Interview] with
Richard P. Gabriel(Podcast)
* [http://common-lisp.net/project/lispbox/ Lisp in a Box] , a useful package for lisp beginners - for Windows or Unix
* [http://www.gigamonkeys.com/book/ Practical Common Lisp] , a free book by Peter Seibel
* [http://www.faqs.org/faqs/lisp-faq/ LISP FAQ]
* [http://arclanguage.org/ arc] , the arc homepage.
Wikimedia Foundation. 2010.