This article needs more citations. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Cons" – news · newspapers · books · scholar · JSTOR (January 2019) (Learn how and when to remove this message)

In computer programming, consCategory:Articles with example Lisp (programming language) code (/ˈkɒnz/ or /ˈkɒns/) is a fundamental function in most dialects of the Lisp programming language. consCategory:Articles with example Lisp (programming language) code 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 ("NATSes"), or (cons) pairs. 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 carCategory:Articles with example Lisp (programming language) code (the first element, or contents of the address part of register), and a right half, referred to as the cdrCategory:Articles with example Lisp (programming language) code (the second element, or contents of the decrement part of register).

It is loosely related to the object-oriented notion of a 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 operators 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, Rocq, and Elm or the : operator in Haskell, which adds an element to the beginning of a list.)

Use

Although cons cells can be used to hold ordered pairs of data, they are more commonly used to construct more complex compound data structures, notably lists and binary trees.

(1 . 2)

Lists

In Lisp, lists are implemented on top of cons pairs. More specifically, any list structure in Lisp is either:

1. An empty list ()Category:Articles with example Lisp (programming language) code, which is a special object usually called nilCategory:Articles with example Lisp (programming language) code.
2. A cons cell whose carCategory:Articles with example Lisp (programming language) code is the first element of the list and whose cdrCategory:Articles with example Lisp (programming language) code is a list containing the rest of the elements.

This forms the basis of a simple, singly linked list structure whose contents can be manipulated with consCategory:Articles with example Lisp (programming language) code, carCategory:Articles with example Lisp (programming language) code, and cdrCategory:Articles with example Lisp (programming language) code. Note that nilCategory:Articles with example Lisp (programming language) 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:

1. Cons 3 onto nilCategory:Articles with example Lisp (programming language) code, the empty list
2. Cons 2 onto the result
3. 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, consCategory:Articles with example Lisp (programming language) 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 (cons 5 x)Category:Articles with example Lisp (programming language) code will produce the list:

(5 1 2 3)

Another useful list procedure is append, which concatenates two existing lists (i.e. combines two lists into a single list).

(cons (cons 1 2) (cons 3 4))

((1 . 2) . (3 . 4))

   *
  / \
 *   *
/ \ / \
1 2 3 4

 *--*--*--nil
 |  |  |
 1  2  3

   *
  / \
 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.Category:All articles with unsourced statementsCategory:Articles with unsourced statements from October 2022^{[citation needed]} For example:

I sped up the code a bit by putting in side effects instead of having it cons ridiculously.

Functional implementation

Since Lisp has first-class functions, all data structures, including cons cells, 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)))

This technique is known as Church encoding. 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, 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.^[1] This encoding also has the advantage of being implementable in a statically typed language that doesn't have variants, such as Java, using interfaces instead of lambdas.

See also

• Lisp (programming language)
• CAR and CDR
• Constructor (computer science)
• Algebraic data type
• Hash consing

References

External links

• SDRAW, Common Lisp code for drawing draws cons cell structures. From David S. Touretzky.