Unexpected output with cons()

Question

I am from an imperative background but these days trying my hands on LISP (Common LISP)

I read here about cons that

(cons x L):

Given a LISP object x and a list L, evaluating (cons x L) creates a list containing x followed by the elements in L.

When I intentionally did not use a list as the second argument i.e when I used

(cons 'a 'a) I expected an error but whoa! I got (A . A).

What have I missed and what is (A . A)?

Answer 1

'a is a lisp atom and (A . A) is a degenerate list called a cons cell or "dotted pair". Since you didn't pass a list for argument L in (cons x L) you got back a cell.

Answer 2

(CONS x L)

Given x and L, CONS returns a new cons cell with x as the CAR of that cell and L as the CDR of that cell.

Lists are linked chains of cons cells.

CL-USER 141 > (sdraw '(a b c))

[*|*]--->[*|*]--->[*|*]---> NIL
  |        |        |
  v        v        v
  A        B        C

CL-USER 142 > (sdraw (cons 'foo '(a b c)))

[*|*]--->[*|*]--->[*|*]--->[*|*]---> NIL
  |        |        |        |
  v        v        v        v
 FOO       A        B        C

If CONS gets two symbols as an argument it looks like this:

CL-USER 143 > (sdraw (cons 'foo 'bar))

[*|*]---> BAR
  |
  v
 FOO

Answer 3

Cons constructs a "cons cell". This has nothing to do with lists at first. A cons cell is a pair of two values. A cons cell is represented in written form by a "dotted pair", e.g. (A . B), which holds the two values 'A and 'B.

The two places in a cons cell are called "car" and "cdr". You can visualize such a cons cell as a bisected block:

  car   cdr
+-----+-----+
|  A  |  B  |
+-----+-----+

In Lisp, a value can also be a reference to something else, for example, another cons cell:

+-----+-----+       +-----+-----+
|  A  |   --------> |  B  |  C  |
+-----+-----+       +-----+-----+

This would be represented in "dotted pair" form as (A . (B . C)). You can continue like this:

+-----+-----+       +-----+-----+       +-----+-----+
|  A  |   --------> |  B  |   --------> |  C  |  D  |
+-----+-----+       +-----+-----+       +-----+-----+

This is (A . (B . (C . D))). As you can see, in such a structure, the values are always in the car of a cons cell, and the cdr points to the rest of the structure. An exception is the last value, which is in the last cdr. We do not need this exception, though: there is a special value NIL in Lisp, which denotes "nothing". By putting NIL into the last cdr, you have a handy sentinel value, and all your values are in the cars:

+-----+-----+       +-----+-----+       +-----+-----+       +-----+-----+
|  A  |   --------> |  B  |   --------> |  C  |   --------> |  D  | NIL |
+-----+-----+       +-----+-----+       +-----+-----+       +-----+-----+

This is how a list is constructed in Lisp. Since (A . (B . (C . (D . NIL)))) is a bit unwieldy, it can also be represented simply as (A B C D). NIL is also called the empty list (); these are exchangable notations for the same thing.

Now you can see why (cons x list) returns another list. Cons simply constructs another cons cell with x in the car and a reference to list in the cdr:

+-----+-----+
|  X  |   --------> list
+-----+-----+

and if list is (A B), it works out as:

+-----+-----+       +-----+-----+       +-----+-----+
|  X  |   --------> |  A  |   --------> |  B  | NIL |
+-----+-----+       +-----+-----+       +-----+-----+

So, (cons x '(a b)) evaluates to (x a b).

Lists are just one very common use of cons cells. You can also construct arbitrary trees from cons cells, or circular lists, or any directed graph, actually.