Cons

From Wikipedia, the free encyclopedia

In computer programming, cons (pronounced kɑnz or kɑns) is a fundamental function in all dialects of the Lisp programming language. cons constructs (hence the name) memory objects holding two values/pointers. These objects are referred to as (cons) cells, conses, or (in Scheme) pairs. In Lisp jargon, the expression "to cons x onto y" means to construct a new object with (cons x y).

The word "cons" and the expression "to cons onto" are also found in more general functional programming jargon. Sometimes operators that have the same purpose (such as :: in ML) are pronounced "cons".

Contents 1 Use 1.1 Lists 1.2 Trees 2 Use in conversation 3 Similar procedures on lists 4 Not fundamental

[edit] Use

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

For example, the Lisp expression (cons 1 2) constructs a cell holding 1 in its left half (the so-called car field) and 2 in its right half (the cdr field). In Lisp notation:

(1 . 2)

[edit] Lists

A list holding the elements 1, 2, 3 in that order can be created by the following steps:

1. Cons 3 onto the special object nil (which denotes the "empty list", the list of zero elements)
2. Cons 2 onto the result
3. Cons 1 onto the result

In one expression:

(cons 1 (cons 2 (cons 3 nil)))

The resulting value is the list

(1 . (2 . (3 . nil)))

i.e.

  *
 / \
1   *
   / \
  2   *
     / \
    3   nil

which may be abbreviated to

(1 2 3)

[edit] Trees

Binary trees, storing data in their leaves, may be constructed similarly:

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

results in the tree

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

i.e.

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

[edit] Use in conversation

cons is sometimes used colloquially in conversation (notably at MIT), usually in the expression "cons up". For example:

Can you cons up that email I sent to ec-discuss two weeks ago?

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 memory allocation, as opposed to using destructive operations of the kind that would be used in an imperative programming language. E.g., "I sped up the code a bit by putting in side effects instead of having it cons like crazy."

[edit] Similar procedures on lists

cons can be used to add one element to the front of an existing linked list. To create a list from one or more elements directly, the list procedure is used. To concatenate two existing linked lists, the append procedure is used.

[edit] Not fundamental

Since Lisp has first-class functions, 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)))

Here we re-implemented the cons, car, and cdr functions, using a function as the "cons cell". This is the usual way of defining data structures in the pure lambda calculus, the computation theory underlying Scheme.