Memory allocation in Lisp

Question

> (cons 2 3) 
(2 . 3)

The Lisp environment needs to allocate only a single cons cell to connect the two items.

Above is from the Lisp book "Land of Lisp". I don't understand why this pair is only located in a single cons cell. What does the memory look like for this data?

Answer 1

A cons cell always holds two values, called car and cdr:

+-----+-----+
| car | cdr |
+-----+-----+

To represent a cons cell, Lisp has the "dot notation":

(car . cdr)

The function cons creates such a cons cell from its two arguments:

(cons 1 2)
=> (1 . 2)

which can be thought of like this:

+-----+-----+
|  1  |  2  |
+-----+-----+

The values of a cons cell can also be "references" or "pointers" to other things. Those other things can, for example, be other cons cells:

+-----+-----+     +-----+-----+
|  1  |   ------->|  2  | nil |
+-----+-----+     +-----+-----+

This would be (1 . (2 . nil)) in dot notation. This chaining is used in Lisp to represent lists. Since lists are used for the representation of code, they are important for Lisp. Therefore, there is a shorter notation for them: (1 2).

Answer 2

Memory is an illusion:

(define (cons a d)
    (lambda (f) (f a d)))

(define (car x)
    (x (lambda (theCar theCdr) theCar)))

(define (cdr x)
    (x (lambda (theCar theCdr) theCdr)))

Look Ma, no memory required !

(just kidding)

Answer 3

I think what's the cons in lisp is something like ( just for explanation, not the real code)

typedef struct _cons
{
    void* car;
    void* cdr;
} cons;

That's what the "single cons" means.

Answer 4

A CONS cell is a record with two fields.

In many Lisp implementations there are special optimizations for cons cells. A typical one is that fixnum numbers are stored directly in the fields - without pointers. As long as the data fits into the memory, they can be stored directly. This may be for example also the case with characters. A cons cell with two characters may also be stored such that the characters are encoded into the fields.

With other, larger, data there are pointers to that data stored into the cons cell.

Then also note the difference between:

(cons 1 2)

and

(list 1 2)

(cons 1 2) creates a single cons cell. (list 1 2) creates two cons cells. The first cons cell contains 1 and a pointer to the second one. The second cons cell contains 2 and NIL (the end of list marker).

Thus as an optimization, often in key/value pairs one uses only the cons cell and not a list.

((age . 22) (name . "Barbara))

vs.

((age 22) (name "Barbara"))

The latter uses two more cons cells.