Editing Lisp (programming language) (section)

===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.