Cons
208153
203175481
2008-04-04T00:10:27Z
LesmanaZimmer
294894
/* Not fundamental */ fixed indentation
{{lowercase}}
{{otheruses}}
In [[computer programming]], '''cons''' ({{pronEng|ˈkɒnz}} or {{IPA|/ˈkɒns/}}) is a fundamental [[subroutine|function]] in all dialects of the [[Lisp programming language]]. <code>cons</code> ''constructs'' (hence the name) memory objects which hold two values or pointers to values. These objects are referred to as (cons) cells, conses, or (cons) [[ordered pair|pairs]]. In Lisp jargon, the expression "to cons ''x'' onto ''y''" means to construct a new object with <code>(cons ''x'' ''y'')</code>. The resulting pair has a left half, referred to as the <code>car</code> (the first element), and a right half (the second element), referred to as the <code>cdr</code>.
It is loosely related to the [[object-oriented programming|object-oriented]] notion of a [[constructor (computer science)|constructor]], which creates a new object given arguments, and more closely related to the constructor function of an [[algebraic data type]] system.
The word "cons" and expressions like "to cons onto" are also part of a more general [[functional programming]] jargon. Sometimes [[Operator (programming)|operators]] that have a similar purpose, especially in the context of list processing, are pronounced "cons". (A good example is the <tt>::</tt> operator in [[ML programming language|ML]], which adds an element to the beginning of a list.)
==Use==
Although cons cells can be used to implement [[Ordered pair|ordered pairs]] of [[simplex]] data, they are more commonly used to construct more complex compound data structures, notably [[Linked list|lists]] and [[binary tree]]s.
For example, the Lisp expression <code>(cons 1 2)</code> constructs a cell holding 1 in its left half (the so-called <code>[[Car and cdr|car]]</code> field) and 2 in its right half (the <code>[[Car and cdr|cdr]]</code> field). In Lisp notation, the value <code>(cons 1 2)</code> looks like:
(1 . 2)
===Lists===
In Lisp, lists are implemented on top of cons pairs. More specifically, any list structure in Lisp is either:
#An empty list, which is a special object usually called <code>nil</code>.
#A cons cell whose <code>car</code> is the first element of the list and whose <code>cdr</code> is a list containing the rest of the elements.
[[Image:Cons-cells.svg|thumb|right|300px|Cons cell diagram for the list (42 69 613)]]
This forms the basis of a simple, [[Linked list|singly-linked list]] structure whose contents can be manipulated with <code>cons</code>, <code>car</code>, and <code>cdr</code>. Note that <code>nil</code> is the only list that is not also a cons pair. As an example, consider a list whose elements are 1, 2, and 3. Such a list can be created in three steps:
#Cons 3 onto <code>nil</code>, the empty list
#Cons 2 onto the result
#Cons 1 onto the result
which is equivalent to the single expression:
<source lang="lisp">(cons 1 (cons 2 (cons 3 nil)))</source>
or its shorthand:
<source lang="lisp">(list 1 2 3)</source>
The resulting value is the list:
(1 . (2 . (3 . nil)))
i.e.
*--*--*--nil
| | |
1 2 3
which is generally abbreviated as:
(1 2 3)
Thus, <code>cons</code> can be used to add one element to the front of an existing linked list. For example, if ''x'' is the list we defined above, then <code>(cons 5 ''x'')</code> will produce the list:
(5 1 2 3)
Another useful list procedure is <code>[[append]]</code>, which [[Concatenation|concatenates]] two existing lists (i.e. combines two lists into a single list).
===Trees===
[[Binary trees]] that only store data in their [[Leaf node|leaves]], are also easily constructed with <code>cons</code>. For example, the code:
<source lang="lisp">(cons (cons 1 2) (cons 3 4))</source>
results in the tree:
((1 . 2) . (3 . 4))
i.e.
*
/ \
* *
/ \ / \
1 2 3 4
Technically, the list (1 2 3) in the previous example is also a binary tree, one which happens to be particularly unbalanced. To see this, simply rearrange the diagram:
*--*--*--nil
| | |
1 2 3
to the following equivalent:
*
/ \
1 *
/ \
2 *
/ \
3 nil
==Use in conversation==
<code>cons</code> is sometimes used colloquially in conversation (notably at [[MIT]]), usually in the expression "cons up". For example:
<blockquote>Can you cons up that email I sent to ec-discuss two weeks ago?</blockquote>
The item being "cons'd up" is the first argument to the operator, with the implied second argument being the list of all current information to hand. See also [[car and cdr]].
Less whimsically, it can also refer to the general process of [[Dynamic memory allocation|memory allocation]], as opposed to using destructive operations of the kind that would be used in an imperative programming language. For example:
<blockquote>I sped up the code a bit by putting in [[side effect (computer science)|side effect]]s instead of having it cons like crazy.</blockquote>
==Not fundamental==
Since Lisp has [[first-class function]]s, all data structures, including cons cells, are not fundamentally necessary to the language, since all data structures can be implemented using functions. For example, in [[Scheme (programming language)|Scheme]]:
<source lang="scheme">
(define (cons x y)
(lambda (m) (m x y)))
(define (car z)
(z (lambda (p q) p)))
(define (cdr z)
(z (lambda (p q) q)))
</source>
The above code re-implements the ''cons'', ''car'', and ''cdr'' operations, using a function as the "cons cell". This is the usual way of defining data structures in pure [[lambda calculus]], an abstract, theoretical model of computation that is closely related to Scheme.
This implementation, while academically interesting, is impractical because it renders cons cells indistinguishable from any other Scheme procedure, as well as introducing unnecessary computational inefficiencies.
==Trivia==
Under the name of the "cons box" (which the cell is called in older Lisp texts like the [[John Allen]] classic "Anatomy of Lisp"), the cons has been the [[symbol]] and [[logotype]] of the computer science undergraduate education program at [[Uppsala University]] since its inception in 1981[http://www.dvp.nu/ordlista.php].
== See also ==
* [[Lisp (programming language)]]
* [[CAR and CDR]]
* [[Constructor (computer science)]]
* [[Algebraic data type]]
[[Category:Functional programming]]
[[Category:Lisp programming language]]
[[Category:Programming constructs]]
[[Category:Articles with example Lisp code]]
[[Category:Articles with example Scheme code]]
[[it:Cons (funzione)]]