Editing Lisp (programming language) (section)

==Syntax and semantics==
:''This article's examples are written in [[Common Lisp]] (though most are also valid in [[Scheme (programming language)|Scheme]]).''

===Symbolic expressions (S-expressions)===
Lisp is an [[expression oriented language]]. Unlike most other languages, no distinction is made between "expressions" and [[Statement (programming)|"statements"]];{{dubious|date=April 2013}}<!-- (progn ...), (setq ...). There is no syntactic distinction, but sequential evaluation is there. --> all code and data are written as expressions. When an expression is ''evaluated'', it produces a value (possibly multiple values), which can then be embedded into other expressions. Each value can be any data type.

McCarthy's 1958 paper introduced two types of syntax: ''Symbolic expressions'' ([[S-expression]]s, sexps), which mirror the internal representation of code and data; and ''Meta expressions'' ([[M-expression]]s), 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''.<ref name="LEVIN2">{{cite web |title=The Jargon File - Lisp |url=http://www.catb.org/~esr/jargon/html/L/LISP.html |access-date=2006-10-13}}</ref><!-- Add NO more nicknames. People can check the Jargon File for them. --> However, the S-expression syntax is also responsible for much of Lisp's power: the syntax is simple and consistent, 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. For example, XMLisp is a Common Lisp extension that employs the [[Metaobject#Metaobject protocol|metaobject protocol]] to integrate S-expressions with the Extensible Markup Language ([[XML]]).

The reliance on expressions gives the language great flexibility. Because Lisp [[function (programming)|functions]] are 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.

===Lists===
A Lisp list is written with its elements separated by [[Whitespace character|whitespace]], and surrounded by parentheses. For example, {{Lisp2|(1 2 foo)}} is a list whose elements are the three ''atoms'' {{Lisp2|1}}, {{Lisp2|2}}, and [[foo|{{#tag:syntaxhighlight|foo|lang=Lisp|inline=1}}]]. 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 {{Lisp2|()}} is also represented as the special atom {{Lisp2|nil}}. This is the only entity in Lisp which is both an atom and a list.

Expressions are written as lists, using [[Polish notation|prefix notation]]. The first element in the list is the name of a function, the name of a macro, a lambda expression or the name of a "special operator" (see below). The remainder of the list are the arguments. For example, the function {{Lisp2|list}} returns its arguments as a list, so the expression
<syntaxhighlight lang="Lisp">
 (list 1 2 (quote foo))
</syntaxhighlight>
evaluates to the list {{Lisp2|(1 2 foo)}}. The "quote" before the {{Lisp2|foo}} in the preceding example is a "special operator" which returns its argument without evaluating it. Any unquoted expressions are recursively evaluated before the enclosing expression is evaluated. For example,
<syntaxhighlight lang="Lisp">
 (list 1 2 (list 3 4))
</syntaxhighlight>
evaluates to the list {{Lisp2|(1 2 (3 4))}}. The third argument is a list; lists can be nested.

===Operators===
Arithmetic operators are treated similarly. The expression
<syntaxhighlight lang="Lisp">
 (+ 1 2 3 4)
</syntaxhighlight>
evaluates to 10. The equivalent under [[infix notation]] would be "{{Lisp2|1 + 2 + 3 + 4}}".

Lisp has no notion of operators as implemented in [[ALGOL]]-derived languages. Arithmetic operators in Lisp are [[variadic function]]s (or ''n-ary''), able to take any number of arguments. A C-style '++' increment operator is sometimes implemented under the name <code>incf</code> giving syntax
<syntaxhighlight lang="Lisp">
 (incf x)
</syntaxhighlight>
equivalent to <code>(setq x (+ x 1))</code>, returning the new value of <code>x</code>.

"Special operators" (sometimes called "special forms") provide Lisp's control structure. For example, the special operator {{Lisp2|if}} takes three arguments. If the first argument is non-nil, it evaluates to the second argument; otherwise, it evaluates to the third argument. Thus, the expression
<syntaxhighlight lang="Lisp">
 (if nil
     (list 1 2 "foo")
     (list 3 4 "bar"))
</syntaxhighlight>
evaluates to {{Lisp2|(3 4 "bar")}}. Of course, this would be more useful if a non-trivial expression had been substituted in place of {{Lisp2|nil}}.

Lisp also provides logical operators '''and''', '''or''' and '''not'''. The '''and''' and '''or''' operators do [[short-circuit evaluation]] and will return their first nil and non-nil argument respectively.
<syntaxhighlight lang="Lisp">
 (or (and "zero" nil "never") "James" 'task 'time)
</syntaxhighlight>
will evaluate to "James".

===Lambda expressions and function definition===
Another special operator, {{Lisp2|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 {{Lisp2|lambda}} are 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 expression
<syntaxhighlight lang="Lisp">
 (lambda (arg) (+ arg 1))
</syntaxhighlight>
evaluates to a function that, when applied, takes one argument, binds it to {{Lisp2|arg}} and 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 expression
<syntaxhighlight lang="Lisp">
 ((lambda (arg) (+ arg 1)) 5)
</syntaxhighlight>
evaluates to {{Lisp2|6}}. Here, we're doing a function application: we execute the [[anonymous function]] by passing to it the value 5.

Named functions are created by storing a lambda expression in a symbol using the defun macro.
<syntaxhighlight lang="Lisp">
 (defun foo (a b c d) (+ a b c d))
</syntaxhighlight>

{{Lisp2|(defun f (a) b...)}} defines a new function named {{Lisp2|f}} in the global environment. It is conceptually similar to the expression:

<syntaxhighlight lang="Lisp">
 (setf (fdefinition 'f) #'(lambda (a) (block f b...)))
</syntaxhighlight>

where {{Lisp2|setf}} is a macro used to set the value of the first argument {{Lisp2|fdefinition 'f}} to a new function object. {{Lisp2|fdefinition}} is a global function definition for the function named {{Lisp2|f}}. {{Lisp2|#'}} is an abbreviation for {{Lisp2|function}} special operator, returning a function object.

===Atoms===
In the original '''LISP''' there were two fundamental [[data type]]s: atoms and lists. A list was a finite ordered sequence of elements, where each element is either an atom or a list, and an atom was a [[number]] or a symbol. A symbol was essentially a unique named item, written as an [[alphanumeric]] string in [[source code]], and used either as a variable name or as a data item in [[symbolic processing]]. For example, the list {{Lisp2|(FOO (BAR 1) 2)}} contains three elements: the symbol {{Lisp2|FOO}}, the list {{Lisp2|(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 exactly the same way represented the same object,{{Citation needed|date=November 2008}} 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 style]]s evolved, the concept of an atom lost importance.{{Citation needed|date=November 2008}} Many dialects still retained the predicate ''atom'' for [[legacy compatibility]],{{Citation needed|date=November 2008}} defining it true for any object which is not a cons.

===Conses and lists===
{{Main|Cons}}
[[File:Cons-cells.svg|thumb|right|300px|Box-and-[[pointer (computer programming)|pointer]] diagram for the list (42 69 613)]]
A Lisp list is implemented as a [[singly linked list]].<ref name="SebestaLanguages">{{cite book |last1=Sebesta |first1=Robert W. |title=Concepts of Programming Languages |chapter="2.4 Functional Programming: LISP";"6.9 List Types";"15.4 The First Functional Programming Language: LISP" |date=2012 |publisher=Addison-Wesley |location=Boston, MA, US |isbn=978-0-13-139531-2 |pages=47–52;281–284;677–680 |edition=10th |url=https://www.pearson.com/us/higher-education/product/Sebesta-Concepts-of-Programming-Languages-10th-Edition/9780131395312.html |language=en |format=print}}</ref> Each cell of this list is called a ''cons'' (in Scheme, a ''pair'') and is composed of two [[pointer (computer programming)|pointers]], called the [[CAR and CDR|''car'' and ''cdr'']]. These are respectively equivalent to the {{Lisp2|data}} and {{Lisp2|next}} fields discussed in the article ''[[linked list]]''.

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 {{Lisp2|nil}} (empty list) symbol, or a cons in which the {{Lisp2|car}} points to a datum (which may be another cons structure, such as a list), and the {{Lisp2|cdr}} points 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 {{Lisp2|car}} and {{Lisp2|cdr}} functions are also called {{Lisp2|first}} and {{Lisp2|rest}} when 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 that 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 several [[higher-order function]]s 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 ([[Array data type|arrays]]), [[hash table]]s, structures, and so forth.

====S-expressions represent lists====
Parenthesized S-expressions represent linked list structures. There are several ways to represent the same list as an S-expression. A cons can be written in ''dotted-pair notation'' as {{Lisp2|(a . b)}}, where {{Lisp2|a}} is the car and {{Lisp2|b}} the cdr. A longer proper list might be written {{Lisp2|(a . (b . (c . (d . nil))))}} in dotted-pair notation. This is conventionally abbreviated as {{Lisp2|(a b c d)}} in ''list notation''. An improper list<ref name="r3sL3">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, although (a...) is sometimes displayed, the CDR of the cons cell defined by #1= is itself.</ref> may be written in a combination of the two – as {{Lisp2|(a b c . d)}} for the list of three conses whose last cdr is {{Lisp2|d}} (i.e., the list {{Lisp2|(a . (b . (c . d)))}} in fully specified form).

====List-processing procedures====
Lisp provides many built-in procedures for accessing and controlling lists. Lists can be created directly with the {{Lisp2|list}} procedure, which takes any number of arguments, and returns the list of these arguments.
<syntaxhighlight lang="Lisp">
 (list 1 2 'a 3)
 ;Output: (1 2 a 3)
</syntaxhighlight>
<syntaxhighlight lang="Lisp">
 (list 1 '(2 3) 4)
 ;Output: (1 (2 3) 4)
</syntaxhighlight>
Because of the way that lists are constructed from [[cons pair]]s, the {{Lisp2|cons}} procedure can be used to add an element to the front of a list. The {{Lisp2|cons}} procedure is asymmetric in how it handles list arguments, because of how lists are constructed.
<syntaxhighlight lang="Lisp">
 (cons 1 '(2 3))
 ;Output: (1 2 3)
</syntaxhighlight>
<syntaxhighlight lang="Lisp">
 (cons '(1 2) '(3 4))
 ;Output: ((1 2) 3 4)
</syntaxhighlight>
The {{Lisp2|append}} procedure appends two (or more) lists to one another. Because Lisp lists are linked lists, appending two lists has [[Big O notation|asymptotic time complexity]] <math>O(n)</math>
<syntaxhighlight lang="Lisp">
 (append '(1 2) '(3 4))
 ;Output: (1 2 3 4)
</syntaxhighlight>
<syntaxhighlight lang="Lisp">
 (append '(1 2 3) '() '(a) '(5 6))
 ;Output: (1 2 3 a 5 6)
</syntaxhighlight>

====Shared structure====
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:
<syntaxhighlight lang="Lisp">
(setf foo (list 'a 'b 'c))
(setf bar (cons 'x (cdr foo)))
</syntaxhighlight>
the lists {{Lisp2|foo}} and {{Lisp2|bar}} are {{Lisp2|(a b c)}} and {{Lisp2|(x b c)}} respectively. However, the tail {{Lisp2|(b c)}} is the same structure in both lists. It is not a copy; the cons cells pointing to {{Lisp2|b}} and {{Lisp2|c}} are 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 {{Lisp2|c}} with a {{Lisp2|goose}}, will affect the other:
<syntaxhighlight lang="Lisp">
 (setf (third foo) 'goose)
</syntaxhighlight>
This changes {{Lisp2|foo}} to {{Lisp2|(a b goose)}}, but thereby also changes {{Lisp2|bar}} to {{Lisp2|(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.

Aficionados of [[functional programming]] avoid 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 {{Lisp2|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 {{Lisp2|set-car!}} is named {{Lisp2|rplaca}} for "replace car". This function is rarely seen, however, as Common Lisp includes a special facility, {{Lisp2|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.

===Self-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; {{Lisp2|(+ 2 3)}} evaluates to {{Lisp2|5}}. However, most other forms evaluate to themselves: if entering {{Lisp2|5}} into Lisp, it returns {{Lisp2|5}}.

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 {{Lisp2|quote}} special operator, or its abbreviation {{Lisp2|'}} (one quotation mark). For instance, usually if entering the symbol {{Lisp2|foo}}, it returns the value of the corresponding variable (or an error, if there is no such variable). To refer to the literal symbol, enter {{Lisp2|(quote foo)}} or, usually, {{Lisp2|'foo}}.

{{anchor|Backquote}}Both Common Lisp and Scheme also support the ''backquote'' operator (termed ''[[quasiquote]]'' in Scheme), entered with the {{Lisp2|`}} character ([[Backtick]]). 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 {{Lisp2|,}} ''unquote'' and comma-at {{Lisp2|,@}} ''splice'' operators. If the variable {{Lisp2|snue}} has the value {{Lisp2|(bar baz)}} then {{Lisp2|`(foo ,snue)}} evaluates to {{Lisp2|(foo (bar baz))}}, while {{Lisp2|`(foo ,@snue)}} evaluates to {{Lisp2|(foo bar baz)}}. The backquote is most often used in defining macro expansions.<ref name="cTQAG">{{cite web|url=http://www.cs.washington.edu/education/courses/cse341/04wi/lectures/14-scheme-quote.html |title=CSE 341: Scheme: Quote, Quasiquote, and Metaprogramming |publisher=University of Washington Computer Science & Engineering |date=Winter 2004 |access-date=2013-11-15}}</ref><ref name="waVLs">{{cite web|archive-date=2013-06-03 |archive-url=https://web.archive.org/web/20130603114956/http://repository.readscheme.org/ftp/papers/pepm99/bawden.pdf |first1=Alan |last1=Bawden |title=Quasiquotation in Lisp |url=http://repository.readscheme.org/ftp/papers/pepm99/bawden.pdf |url-status=dead}}</ref>

Self-evaluating forms and quoted forms are Lisp's equivalent of literals. It may be 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 may alter the behavior of the function on subsequent invocations.

<syntaxhighlight lang="lisp">
(defun should-be-constant ()
  '(one two three))

(let ((stuff (should-be-constant)))
  (setf (third stuff) 'bizarre))   ; bad!

(should-be-constant)   ; returns (one two bizarre)
</syntaxhighlight>

Modifying a quoted form like this is generally considered bad style, and is defined by ANSI Common Lisp as erroneous (resulting in "undefined" behavior in compiled files, because the file-compiler can coalesce similar constants, put them in write-protected memory, etc.).

Lisp's formalization of quotation has been noted by [[Douglas Hofstadter]] (in ''[[Gödel, Escher, Bach]]'') and others as an example of the [[philosophy|philosophical]] idea of [[self-reference]].

===Scope and closure===
The Lisp family splits over the use of [[dynamic scoping|dynamic]] or [[static scoping|static]] (a.k.a. lexical) [[scope (programming)|scope]]. Clojure, Common Lisp and Scheme make use of static scoping by default, while [[newLISP]], [[Picolisp]] and the embedded languages in [[Emacs]] and [[AutoCAD]] use dynamic scoping. Since version 24.1, Emacs uses both dynamic and lexical scoping.

===List structure of program code; exploitation by macros and compilers===
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, symbols, number, characters, etc.) as would be used by the underlying Lisp system.

Lisp uses this to implement a very powerful macro system. Like other macro languages such as the one defined by the [[C preprocessor]] (the macro preprocessor for the [[C (programming language)|C]], [[Objective-C]] and [[C++]] programming languages), a macro returns code that can then be compiled. However, unlike C preprocessor macros, the macros are Lisp functions and so can exploit the full power of Lisp.

Further, 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.

This feature makes it easy to develop ''efficient'' languages within languages. For example, the Common Lisp Object System can be implemented cleanly as a language extension using macros. This means that if an application needs a different inheritance mechanism, it can use a different object system. This is in stark contrast to most other languages; for example, Java does not support multiple inheritance and there is no reasonable way to add it.

In simplistic Lisp implementations, this list structure is directly [[interpreter (computing)|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 substantial Lisp systems also include a compiler. The compiler translates list structure into machine code or [[bytecode]] for execution. This code can run as fast as code compiled in conventional languages such as C.

Macros expand before the compilation step, and thus offer some interesting options. If a program needs a precomputed table, then a macro might create the table at compile time, so the compiler need only output the table and need not call code to create the table at run time. Some Lisp implementations even have a mechanism, <code>eval-when</code>, that allows code to be present during compile time (when a macro would need it), but not present in the emitted module.<ref name="0iFgm">"[https://www.gnu.org/software/emacs/manual/html_node/cl/Time-of-Evaluation.html Time of Evaluation (Common Lisp Extensions)]". GNU. Retrieved on 2013-07-17.</ref>

===Evaluation and the read–eval–print loop===
Lisp languages are often used with an interactive [[command line]], which may be combined with an [[integrated development environment]] (IDE). 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]]'' ([[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.

The {{Lisp2|read}} function accepts textual S-expressions as input, and parses them into an internal data structure. For instance, if you type the text {{Lisp2|(+ 1 2)}} at the prompt, {{Lisp2|read}} translates this into a linked list with three elements: the symbol {{Lisp2|+}}, 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.

A {{Lisp2|foo}} will be read as a single symbol. {{Lisp2|123}} will be read as the number one hundred and twenty-three. {{Lisp2|"123"}} will be read as the string "123".

The {{Lisp2|eval}} function evaluates the data, returning zero or more other Lisp data 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, {{Lisp2|eval}} first 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 {{Lisp2|(1 2)}} yields the answer {{Lisp2|3}}. This is the result of the evaluation.

The symbol {{Lisp2|foo}} evaluates to the value of the symbol foo. Data like the string "123" evaluates to the same string. The list {{Lisp2|(quote (1 2 3))}} evaluates to the list (1 2 3).

It is the job of the {{Lisp2|print}} function to represent output to the user. For a simple result such as {{Lisp2|3}} this is trivial. An expression which evaluated to a piece of list structure would require that {{Lisp2|print}} traverse the list and print it out as an S-expression.

To implement a Lisp REPL, it is necessary only to implement these three functions and an infinite-loop function. (Naturally, the implementation of {{Lisp2|eval}} will be complex, since it must also implement all special operators like {{Lisp2|if}} or {{Lisp2|lambda}}.) This done, a basic REPL is one line of code: {{Lisp2|(loop (print (eval (read))))}}.

The Lisp REPL typically also provides input editing, an input history, error handling and an interface to the debugger.

Lisp is usually evaluated [[eager evaluation|eagerly]]. In [[Common Lisp]], arguments are evaluated in [[applicative order]] ('leftmost innermost'), while in [[Scheme programming language|Scheme]] order of arguments is undefined, leaving room for optimization by a compiler.

===Control structures===
Lisp originally had very few control structures, but many more were added during the language's evolution. (Lisp's original conditional operator, {{Lisp2|cond}}, is the precursor to later {{Lisp2|if-then-else}} structures.)

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, but this is incorrect. All oft-seen Lisp dialects have imperative-style iteration constructs, from Scheme's {{Lisp2|do}} loop to [[Common Lisp]]'s complex {{Lisp2|loop}} expressions. Moreover, the key issue that makes this an objective rather than subjective matter is that Scheme makes specific requirements for the handling of [[tail call]]s, and thus the reason that the use of tail recursion is generally encouraged for Scheme is that the practice is expressly supported by the language definition. By contrast, ANSI Common Lisp does not require<ref name="lGnFp">[http://www.lispworks.com/documentation/HyperSpec/Body/03_bbc.htm 3.2.2.3 Semantic Constraints] in [http://www.lispworks.com/documentation/HyperSpec/Front/index.htm ''Common Lisp HyperSpec'']</ref> the optimization commonly termed a tail call elimination. Thus, the fact that tail recursive style as a casual replacement for the use of more traditional [[iteration]] constructs (such as {{Lisp2|do}}, {{Lisp2|dolist}} or {{Lisp2|loop}}) is discouraged<ref name="VY38C">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 [[Kent Pitman]] and [[Peter Norvig]], August, 1993.</ref> 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 [[Branch (computer science)|jump]]) and program correctness (since tail recursion may increase stack use in Common Lisp, risking [[stack overflow]]).

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 implementing control structures using the language. 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 [[continuation]]s'' using the {{Lisp2|call/cc}} procedure, 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.

Often, 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 {{Lisp2|for}} loop 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 {{Lisp2|map}} and in Common Lisp is called {{Lisp2|mapcar}}. Given a function and one or more lists, {{Lisp2|mapcar}} applies the function successively to the lists' elements in order, collecting the results in a new list:
<syntaxhighlight lang="Lisp">
 (mapcar #'+ '(1 2 3 4 5) '(10 20 30 40 50))
</syntaxhighlight>
This applies the {{Lisp2|+}} function to each corresponding pair of list elements, yielding the result {{Lisp2|(11 22 33 44 55)}}.