Specification of conses

Question

The Wikipedia-page about car and cdr says that a cons is a pair of pointers.

The following code seems to confirm that:

(progn
  (setq a '(1 . 2))
  (setq b a)
  (setf (car b) 10)
  (print a))

The evaluation of that form gives the cons (10 . 2). Setting the car of b changes the car of a. You can try that in the online repl at compileonline.com.

Where is that behavior defined in the Common Lisp specification?

(I've read some of the text but couldn't find the section pin-pointing that behavior.)

Interestingly the Wikipedia page on conses says "cons constructs memory objects which hold two values or pointers to values". If the atom 1 would directly be stored in the cons object then changing b wouldn't change a, would it?

I assume above that a and b hold the cons objects and not pointer to conses. Even if the actual lisp implementation works with pointers this should not be visible on repl-level or should it according to the spec? One could achieve a similar effect when one assumes that a and b hold pointers that both point to the same cons. Consing, i.e., the construction of lists through repeated application of cons, supports the assumption that conses are represented by pointers in symbol values.

The following two forms are equivalent:

(let ((a '(1)))
  (setq b (cons 2 a)))

(setq b '(2 1))

Answer 1

Setting the car of b changes the car of a.

You are not setting the car of b. You are setting the car of the same cons cell which is referenced by b and a.

CL-USER 1 > (let (a b)
              (setq a (cons 1  2))
              (setq b a)

              (eq a b))
T

Explanation:

• we have variables a and b.
• (cons 1 2) returns a cons cell
• (setq a (cons 1 2)) sets a to the result of (cons 1 2), a cons cell.
• (setq b a) evaluates a, which returns above cons cell and sets b to that cons cell.

The key to understand is that evaluation of variables and functions returns non-primitive (that is other than primitive numbers, characters, ...) objects as themselves - not as a copy.

I assume above that a and b hold the cons objects and not pointer to conses.

That's wrong. a and b are variables, which just point to both the same single cons cell.

"cons constructs memory objects which hold two values or pointers to values"

In a Common Lisp implementation something like small numbers (fixnums) might be stored directly in a cons cell. One can not reliably compare numbers by identity (using EQ) and has to do numeric comparison (EQL, =, ...).

OTOH, cons cells can't be stored inside cons cells and thus are referenced by pointers internally.

The operations you use:

• SETQ : First form1 is evaluated and the result is stored in the variable var1. -> Notice how it says: result and not copy of the result.

• RPLCA - this is what (setf CAR) actually uses. : rplaca replaces the car of the cons with object and The cons is modified -> thus it modifies the cons object it gets passed as an argument.

• Evaluation - since you execute your code, the rules for evaluation apply.

Further useful to understand the execution model of Lisp:

• An old Lisp book: 'Anatomy of LISP' by John Allen. (amazon)
• A Scheme spec like R5RS.
• Lisp in small pieces, a book explaining the execution models of Scheme/Lisp and their implementation.

Answer 2

First of all, your code is invalid because you're not allowed to modify constant lists. It should be:

(progn
  (setq a (cons 1  2))
  (setq b a)
  (setf (car b) 10)
  (print a))

When you perform an assignment like (setq b a), it sets the value of b to be the same as the value of a. The specification of SETQ says nothing about making a copy of the value, so the two variables contain the same value, which in this case is a cons cell.

Setting the car of that cons cell modifies that object -- again, there's no copying being done. So you'll see the change through any variable that refers to the cons cell, or any other reference (it could be in a structure slot, an array element, another cons cell, etc.).

I don't think the specification ever actually comes out and says that these things are all the same, it's just implicit in the fact that we're passing around abstract objects, and no copying is done unless you call a function that's explicitly defined to do so (e.g. COPY-TREE).

The specification doesn't talk about pointers, but that's generally what's going on under the covers. A cons cell is like a C structure:

typedef struct cons {
    lisp_object car,
    lisp_object cdr
} cons;

lisp_object would probably be a union of various types (some immediate types for things like FIXNUM, and pointers for other types). When a variable contains a cons, it actually contains a pointer to the above structure, and the assignment copies the pointer, not the structure. So the Lisp code is analogous to C code like:

cons *a = make_cons(1, 2);
cons *b = a;
b->car = 10;
printf("%d\n", a->car);