Computer programming is the process of designing, writing, testing, debugging, and maintaining the source code of computer programs. This source code is written in one or more programming languages. The purpose of programming is to create a program that performs specific operations or exhibits a...
In computer science, a subroutine is a portion of code within a larger program that performs a specific task and is relatively independent of the remaining code....
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 language in widespread use today; only Fortran is older...
. cons constructs memory objects which hold two values or pointers to values. These objects are referred to as (cons) cells, conses, non-atomic s-expressions ("NATSes"), or (cons) pairs
Ordered pair
In mathematics, an ordered pair is a pair of mathematical objects. In the ordered pair , the object a is called the first entry, and the object b the second entry of the pair...
. In Lisp jargon, the expression "to cons x onto y" means to construct a new object with (cons x y). The resulting pair has a left half, referred to as the car
Car and cdr
car and cdr are primitive operations on cons cells introduced in the Lisp programming language. A cons cell is composed of two pointers; the car operation extracts the first pointer, and the cdr operation extracts the second.Thus, the expression evaluates to x, and evaluates to...
(the first element), and a right half (the second element), referred to as the cdr
Car and cdr
car and cdr are primitive operations on cons cells introduced in the Lisp programming language. A cons cell is composed of two pointers; the car operation extracts the first pointer, and the cdr operation extracts the second.Thus, the expression evaluates to x, and evaluates to...
Object-oriented programming is a programming paradigm using "objects" – data structures consisting of data fields and methods together with their interactions – to design applications and computer programs. Programming techniques may include features such as data abstraction,...
In object-oriented programming, a constructor in a class is a special type of subroutine called at the creation of an object. It prepares the new object for use, often accepting parameters which the constructor uses to set any member variables required when the object is first created...
, which creates a new object given arguments, and more closely related to the constructor function of an algebraic data type
Algebraic data type
In computer programming, particularly functional programming and type theory, an algebraic data type is a datatype each of whose values is data from other datatypes wrapped in one of the constructors of the datatype. Any wrapped datum is an argument to the constructor...
system.
The word "cons" and expressions like "to cons onto" are also part of a more general functional programming
Functional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
Programming languages typically support a set of operators: operations which differ from the language's functions in calling syntax and/or argument passing mode. Common examples that differ by syntax are mathematical arithmetic operations, e.g...
that have a similar purpose, especially in the context of list processing, are pronounced "cons". (A good example is the :: operator in ML
ML programming language
ML is a general-purpose functional programming language developed by Robin Milner and others in the early 1970s at the University of Edinburgh, whose syntax is inspired by ISWIM...
and Scala, which adds an element to the beginning of a list.)
Use
Although cons cells can be used to hold ordered pair
Ordered pair
In mathematics, an ordered pair is a pair of mathematical objects. In the ordered pair , the object a is called the first entry, and the object b the second entry of the pair...
Simplex is Latin for "simple, pure, plain" and may refer to:*Simplex, a term in geometry meaning an n-dimensional analogue of a triangle**10-simplex, a hendecaxennon...
data, they are more commonly used to construct more complex compound data structures, notably lists
Linked list
In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...
In computer science, a binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to...
s.
For example, the Lisp expression (cons 1 2) constructs a cell holding 1 in its left half (the so-called car
Car and cdr
car and cdr are primitive operations on cons cells introduced in the Lisp programming language. A cons cell is composed of two pointers; the car operation extracts the first pointer, and the cdr operation extracts the second.Thus, the expression evaluates to x, and evaluates to...
car and cdr are primitive operations on cons cells introduced in the Lisp programming language. A cons cell is composed of two pointers; the car operation extracts the first pointer, and the cdr operation extracts the second.Thus, the expression evaluates to x, and evaluates to...
field). In Lisp notation, the value (cons 1 2) looks like:
(1 . 2)
Note the dot between 1 and 2; this indicates that the S-expression is a "dotted pair," rather than a "list."
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 nil.
A cons cell whose car is the first element of the list and whose cdr is a list containing the rest of the elements.
In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...
structure whose contents can be manipulated with cons, car, and cdr. Note that nil 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 nil, the empty list
Cons 2 onto the result
Cons 1 onto the result
which is equivalent to the single expression:
(cons 1 (cons 2 (cons 3 nil)))
or its shorthand:
(list 1 2 3)
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, cons 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 (cons 5 x) will produce the list:
In computer programming, string concatenation is the operation of joining two character strings end-to-end. For example, the strings "snow" and "ball" may be concatenated to give "snowball"...
two existing lists (i.e. combines two lists into a single list).
Trees
Binary trees that only store data in their leaves are also easily constructed with cons. For example, the code:
(cons (cons 1 2) (cons 3 4))
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
Cons can refer to the general process of memory allocation, as opposed to using destructive operations of the kind that would be used in an imperative programming language. For example:
I sped up the code a bit by putting in side effect
Side effect (computer science)
In computer science, a function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world...
In computer science, a programming language is said to have first-class functions if it treats functions as first-class objects. Specifically, this means that the language supports passing functions as arguments to other functions, returning them as the values from other functions, and assigning...
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:
(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)))
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
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped 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.
However, the same kind of encoding can be used for more complex algebraic data types with variants, where it may even turn out to be more efficient than other kinds of encoding.
This encoding also has the advantage of being implementable in a statically typed language that doesn't have variants, such as Java
Java (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
car and cdr are primitive operations on cons cells introduced in the Lisp programming language. A cons cell is composed of two pointers; the car operation extracts the first pointer, and the cdr operation extracts the second.Thus, the expression evaluates to x, and evaluates to...
In object-oriented programming, a constructor in a class is a special type of subroutine called at the creation of an object. It prepares the new object for use, often accepting parameters which the constructor uses to set any member variables required when the object is first created...
In computer programming, particularly functional programming and type theory, an algebraic data type is a datatype each of whose values is data from other datatypes wrapped in one of the constructors of the datatype. Any wrapped datum is an argument to the constructor...
In computer science, particularly in functional programming, hash consing is a technique used to share values that are structurally equal. The term hash consing originates from implementations of Lisp that attempt to reuse cons cells that have been constructed before, avoiding the penalty of memory...
Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...
code for drawing draws cons cell structures. From David S. Touretzky.
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
