cons
   HOME

TheInfoList



OR:

In
computer programming Computer programming is the process of performing a particular computation (or more generally, accomplishing a specific computing result), usually by designing and building an executable computer program. Programming involves tasks such as ana ...
, ( or ) is a fundamental
function Function or functionality may refer to: Computing * Function key, a type of key on computer keyboards * Function model, a structured representation of processes in a system * Function object or functor or functionoid, a concept of object-oriente ...
in most dialects of the
Lisp A lisp is a speech impairment in which a person misarticulates sibilants (, , , , , , , ). These misarticulations often result in unclear speech. Types * A frontal lisp occurs when the tongue is placed anterior to the target. Interdental lisping ...
programming language. ''constructs'' memory objects which hold two values or pointers to two values. These objects are referred to as (cons) cells, conses, non-atomic
s-expressions In computer programming, an S-expression (or symbolic expression, abbreviated as sexpr or sexp) is an expression in a like-named notation for nested list (tree-structured) data. S-expressions were invented for and popularized by the programming la ...
("NATSes"), or (cons)
pairs Concentration, also known as Memory, Shinkei-suijaku (Japanese meaning "nervous breakdown"), Matching Pairs, Match Match, Match Up, Pelmanism, Pexeso or simply Pairs, is a card game in which all of the cards are laid face down on a surface and tw ...
. 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 (the first element, or ''contents of the address part of register''), and a right half, referred to as the (the second element, or ''contents of the decrement part of register''). It is loosely related to the
object-oriented Object-oriented programming (OOP) is a programming paradigm based on the concept of "objects", which can contain data and code. The data is in the form of fields (often known as attributes or ''properties''), and the code is in the form of pro ...
notion of a constructor, which creates a new object given arguments, and more closely related to the constructor function of an
algebraic data type In computer programming, especially functional programming and type theory, an algebraic data type (ADT) is a kind of composite type, i.e., a type formed by combining other types. Two common classes of algebraic types are product types (i.e., t ...
system. The word "cons" and expressions like "to cons onto" are also part of a more general
functional programming In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declar ...
jargon. Sometimes
operators Operator may refer to: Mathematics * A symbol indicating a mathematical operation * Logical operator or logical connective in mathematical logic * Operator (mathematics), mapping that acts on elements of a space to produce elements of another sp ...
that have a similar purpose, especially in the context of list processing, are pronounced "cons". (A good example is the :: operator in ML, Scala, F#,
Lean Lean, leaning or LEAN may refer to: Business practices * Lean thinking, a business methodology adopted in various fields ** Lean construction, an adaption of lean manufacturing principles to the design and construction process ** Lean governm ...
and
Elm Elms are deciduous and semi-deciduous trees comprising the flowering plant genus ''Ulmus'' in the plant family Ulmaceae. They are distributed over most of the Northern Hemisphere, inhabiting the temperate and tropical-montane regions of North ...
or the : operator in
Haskell Haskell () is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research and industrial applications, Haskell has pioneered a number of programming lan ...
, which adds an element to the beginning of a list.)


Use

Although cons cells can be used to hold
ordered pair In mathematics, an ordered pair (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In con ...
s of data, they are more commonly used to construct more complex compound data structures, notably
lists A ''list'' is any set of items in a row. List or lists may also refer to: People * List (surname) Organizations * List College, an undergraduate division of the Jewish Theological Seminary of America * SC Germania List, German rugby unio ...
and
binary tree In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary t ...
s.


Ordered pairs

For example, the Lisp expression constructs a cell holding 1 in its left half (the so-called field) and 2 in its right half (the field). In Lisp notation, the value looks like: (1 . 2) Note the dot between 1 and 2; this indicates that the S-expression is a "dotted pair" (a so-called "cons 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 . #A cons cell whose is the first element of the list and whose is a
list A ''list'' is any set of items in a row. List or lists may also refer to: People * List (surname) Organizations * List College, an undergraduate division of the Jewish Theological Seminary of America * SC Germania List, German rugby union ...
containing the rest of the elements. This forms the basis of a simple,
singly linked list In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whic ...
structure whose contents can be manipulated with , , and . Note that 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 , 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, 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 will produce the list: (5 1 2 3) Another useful list procedure is , which concatenates two existing lists (i.e. combines two lists into a single list).


Trees

Binary tree In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary t ...
s that only store data in their
leaves A leaf (plural, : leaves) is any of the principal appendages of a vascular plant plant stem, stem, usually borne laterally aboveground and specialized for photosynthesis. Leaves are collectively called foliage, as in "autumn foliage", wh ...
are also easily constructed with . 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 Memory management is a form of Resource management (computing), resource management applied to computer memory. The essential requirement of memory management is to provide ways to dynamically allocate portions of memory to programs at their re ...
, 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 In medicine, a side effect is an effect, whether therapeutic or adverse, that is secondary to the one intended; although the term is predominantly employed to describe adverse effects, it can also apply to beneficial, but unintended, consequence ...
s instead of having it cons ridiculously.


Functional implementation

Since Lisp has
first-class function In computer science, a programming language is said to have first-class functions if it treats functions as first-class citizens. This means the language supports passing functions as arguments to other functions, returning them as the values from ...
s, all data structures, including cons cells, can be implemented using functions. For example, in
Scheme A scheme is a systematic plan for the implementation of a certain idea. Scheme or schemer may refer to: Arts and entertainment * ''The Scheme'' (TV series), a BBC Scotland documentary series * The Scheme (band), an English pop band * ''The Schem ...
: (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))) This technique is known as
Church encoding In mathematics, Church encoding is a means of representing data and operators in the lambda calculus. The Church numerals are a representation of the natural numbers using lambda notation. The method is named for Alonzo Church, who first encoded da ...
. It re-implements the ''cons'', ''car'', and ''cdr'' operations, using a function as the "cons cell". Church encoding is a usual way of defining data structures in pure
lambda calculus Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation ...
, 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 introduces 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 (; id, Jawa, ; jv, ꦗꦮ; su, ) is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea to the north. With a population of 151.6 million people, Java is the world's List ...
, using interfaces instead of lambdas.


See also

*
Lisp (programming language) Lisp (historically LISP) is a family of programming languages with a long history and a distinctive, fully parenthesized prefix notation. Originally specified in 1960, Lisp is the second-oldest high-level programming language still in common us ...
* CAR and CDR *
Constructor (computer science) In class-based, object-oriented programming, a constructor (abbreviation: ctor) is a special type of subroutine called to create an object. It prepares the new object for use, often accepting arguments that the constructor uses to set required ...
*
Algebraic data type In computer programming, especially functional programming and type theory, an algebraic data type (ADT) is a kind of composite type, i.e., a type formed by combining other types. Two common classes of algebraic types are product types (i.e., t ...
*
Hash consing 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 ...


References


External links


SDRAW
Common Lisp Common Lisp (CL) is a dialect of the Lisp programming language, published in ANSI standard document ''ANSI INCITS 226-1994 (S20018)'' (formerly ''X3.226-1994 (R1999)''). The Common Lisp HyperSpec, a hyperlinked HTML version, has been derived fro ...
code for drawing draws cons cell structures. From David S. Touretzky. {{Data types Functional programming Lisp (programming language) Articles with example Lisp (programming language) code Articles with example Scheme (programming language) code Composite data types Data types