Lisp internal details

Lee Spector, lspector@hampshire.edu, 1995-1998

 


CONS cells and "dotted pair" notation.


Lists are made out of data elements called CONS
cells.

Each CONS cell has two components: the CAR and
the CDR. The CAR contains a pointer to the first
element of the list, and the CDR contains a pointer
to the rest of the list.

In a "normal" list, the CDR of the last cell
in the list points to NIL, and the CDRs of all
other cells point to other CONS cells.

SDRAW is a utility program that helps to visualize
the internal representation of lists as collections
of CONS cells. It was written by David Touretzky,
and is available on the net.

? (sdraw '(a b c))

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



? (sdraw '(a (b) c))

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

? (sdraw '((a b)(c d)))

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


This is probably a good place to point out that
although NIL is a list, it is not a cons:

(listp nil)
--> T

(consp nil)
--> NIL


Recall that it is possible to CONS something
onto a non-list. This is unusual, but it can
be done. The result is a list with a last CONS
cell that has a non-nil CDR:


? (sdraw (cons 'a 'b))

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



When you ask Lisp to print such a list, it uses
"dotted pair" notation:
(cons 'a 'b)
--> (A . B)

Dotted pair notation can actually be used for
"normal" lists as well -- whatever follows the
dot is the CDR of the list:
'(a b . (c d))
--> (A B C D)

Lisp avoids the use of dotted pair notation except
when there is no alternative. 

Dotted pairs are sometimes handy. If you want
to keep a list of pairs of items, dotted pairs
are slightly more efficient than 2-item lists.


(sdraw '((sky yellow)
         (sun blue)
         (begonias scarlet)))

[*|*]------------------>[*|*]------------------>[*|*]--->NIL
 |                       |                       |
 v                       v                       v
[*|*]--->[*|*]--->NIL   [*|*]--->[*|*]--->NIL   [*|*]----->[*|*]--->NIL
 |        |              |        |              |          |
 v        v              v        v              v          v
SKY      YELLOW         SUN      BLUE           BEGONIAS   SCARLET


(sdraw '((sky . yellow)
         (sun . blue)
         (begonias . scarlet)))

[*|*]------------>[*|*]---------->[*|*]--->NIL
 |                 |               |
 v                 v               v
[*|*]--->YELLOW   [*|*]--->BLUE   [*|*]--->SCARLET
 |                 |               |
 v                 v               v
SKY               SUN             BEGONIAS

Common Lisp includes a bunch of built-in functions
for manipulating lists of dotted pairs. These
lists are called "association lists".

The function SUBLIS is handy for making substitutions
in a list based on the values in an association
list:

SUBLIS a-list tree  &key :test :test-not :key
[Function]
creates a new tree based on tree, except that
elements that appear as keys in a-list  are replaced
with the corresponding value from a-list. The
original tree  is not modified, but the new tree
may share list structure with it. In effect,
sublis can perform several subst operations simultaneously.


Examples of SUBLIS:

(sublis '((x . 1) (y . 2))
        '(a b x c d y))
--> (A B 1 C D 2)

(sublis '((x . 1) (y . 2))
        '(a b (x y) c d))
--> (A B (1 2) C D)

(sublis '((x hello there) (y sweety))
        '(a b x c d y))
--> (A B (HELLO THERE) C D (SWEETY))



The function ACONS is used to build association
lists:

ACONS key datum alist
[Function]
creates a cons with key in the car and datum
in the cdr, conses this onto the front of alist,
and returns the resulting list.  alist is not
destructively modified.

(setq *favorites* nil)
--> NIL

(setq *favorites* (acons 'cheese 'blue *favorites*))
--> ((CHEESE . BLUE))

(setq *favorites* (acons 'color 'green *favorites*))
--> ((COLOR . GREEN) (CHEESE . BLUE))

(setq *favorites* (acons 'food 'turnips *favorites*))
--> ((FOOD . TURNIPS) (COLOR . GREEN) (CHEESE . BLUE))

*favorites*
--> ((FOOD . TURNIPS) (COLOR . GREEN) (CHEESE . BLUE))

(sublis *favorites*
        '(I will turn color if i do not get a
          cheese milk product with my food))
--> (I WILL TURN GREEN IF I DO NOT GET A BLUE
MILK PRODUCT WITH MY TURNIPS)



Now that we know how lists are represented internally,
we can look at functions that DESTRUCTIVELY modify
lists. Recall that most functions that we've
used are NOT destructive -- they return NEW list
structures (that may include some of the old
list structures). For example:

(setq foods '(apple peach pear))
--> (APPLE PEACH PEAR)

(setq groceries (cons 'light-bulbs foods))
--> (LIGHT-BULBS APPLE PEACH PEAR)

foods
--> (APPLE PEACH PEAR)   ;; not modified

(eq foods (cdr groceries))
--> T ;; same internal structures


One function that we've looked at that IS destructive
is SETF.

(setf (nth 2 groceries) 'spam)
--> SPAM

groceries
--> (LIGHT-BULBS APPLE SPAM PEAR)

NOTE: This can have unexpected effects:

foods
--> (APPLE SPAM PEAR)


Destructive operations are in general VERY DANGEROUS.
They are the source of many subtle, nasty bugs.
AVOID them unless you know exactly what you're
doing!


Here are some low-level destructive functions:

RPLACA cons object
[Function]
destructively alters cons so that its car points
to object. Returns the modified cons.

RPLACD cons object
[Function]
destructively alters cons so that its cdr points
to object. Returns the modified cons.

(setq x '(a b c))
--> (A B C)

(rplaca x 'd)
--> (D B C)

x
--> (D B C)

(setq x '(a b c))
--> (A B C)

(setq y x)
--> (A B C)

(eq x y)
--> T

(rplaca x 'd)
--> (D B C)

x
--> (D B C)


y
--> (D B C)

(eq x y)
--> T

(setq y (cons 'e (cdr x)))
--> (E B C)

y
--> (E B C)

x
--> (D B C)

NCONC &rest lists-or-thing
[Function]
concatenates lists destructively and returns
the resulting list. The lists are not copied,
but are destructively altered in place. nconc
is the destructive equivalent of append.

Here's an example with append:

(setq gravy '(lumpy brown))
--> (LUMPY BROWN)

(setq bread '(crusty white))
--> (CRUSTY WHITE)

(setq food-features (append gravy bread))
--> (LUMPY BROWN CRUSTY WHITE)

gravy
--> (LUMPY BROWN)

bread
--> (CRUSTY WHITE)

food-features
--> (LUMPY BROWN CRUSTY WHITE)

We get different results with nconc:

(setq gravy '(lumpy brown))
--> (LUMPY BROWN)

(setq bread '(crusty white))
--> (CRUSTY WHITE)

(setq food-features (nconc gravy bread))
--> (LUMPY BROWN CRUSTY WHITE)

gravy
--> (LUMPY BROWN CRUSTY WHITE)

bread
--> (CRUSTY WHITE)

food-features
--> (LUMPY BROWN CRUSTY WHITE)

There are special versions of many of the mapping
functions that produce their return-results destructively.
For example, MAPCAN is just like MAPCAR except
that it NCONCs its results together instead of
LISTing them.

(defun double (something) (list something something))
--> DOUBLE

(mapcar #'double
        '(1 2 3 4 can I show you out the door))
--> ((1 1) (2 2) (3 3) (4 4) (CAN CAN) (I I)
(SHOW SHOW)
     (YOU YOU) (OUT OUT) (THE THE) (DOOR DOOR))

(mapcan #'double
        '(1 2 3 4 can I show you out the door))
--> (1 1 2 2 3 3 4 4 CAN CAN I I SHOW SHOW YOU
YOU OUT OUT THE THE DOOR DOOR)

This is safe because DOUBLE returns new list
structure every time it is called. But trouble
lurks:

(defvar birth-month-attributes)
--> BIRTH-MONTH-ATTRIBUTES

(setq birth-month-attributes
      '((selfish greedy) (nasty ugly) (cranky
smelly)
        (beautiful smart) (foul wrinkley) (cheesey)
        (washed-up blue) (crusty oily) (fetid
purple)
        (fishy) (snake-like wet nosey) (dry colorless)))
--> ((SELFISH GREEDY) (NASTY UGLY) (CRANKY SMELLY)
     (BEAUTIFUL SMART) (FOUL WRINKLEY) (CHEESEY)
     (WASHED-UP BLUE) (CRUSTY OILY) (FETID PURPLE)
     (FISHY) (SNAKE-LIKE WET NOSEY) (DRY COLORLESS))

(defun birth-month-lookup (n)
  (nth (- n 1) birth-month-attributes))
--> BIRTH-MONTH-LOOKUP

(birth-month-lookup 3)
--> (CRANKY SMELLY)

(mapcar #'birth-month-lookup
        '(3 6 9))
--> ((CRANKY SMELLY) (CHEESEY) (FETID PURPLE))

(mapcan #'birth-month-lookup
        '(3 6 9))
--> (CRANKY SMELLY CHEESEY FETID PURPLE)

(mapcan #'birth-month-lookup
        '(3 6 9))   ;; nasty loop!

Weird! The first MAPCAN worked fine, the next
one went nuts.... Why?

birth-month-attributes  ;; also loops & never
prints!

Let's look again at the variable after the first
MAPCAN:

(setq birth-month-attributes
      '((selfish greedy) (nasty ugly) (cranky
smelly)
        (beautiful smart) (foul wrinkley) (cheesey)
        (washed-up blue) (crusty oily) (fetid
purple)
        (fishy) (snake-like wet nosey) (dry colorless)))
--> ((SELFISH GREEDY) (NASTY UGLY) (CRANKY SMELLY)
     (BEAUTIFUL SMART) (FOUL WRINKLEY) (CHEESEY)
     (WASHED-UP BLUE) (CRUSTY OILY) (FETID PURPLE)
     (FISHY) (SNAKE-LIKE WET NOSEY) (DRY COLORLESS))

(mapcan #'birth-month-lookup
        '(3 6 9))
--> (CRANKY SMELLY CHEESEY FETID PURPLE)

birth-month-attributes
--> ((SELFISH GREEDY) (NASTY UGLY)
     (CRANKY SMELLY CHEESEY FETID PURPLE)
     (BEAUTIFUL SMART) (FOUL WRINKLEY) (CHEESEY
FETID PURPLE)
     (WASHED-UP BLUE) (CRUSTY OILY) (FETID PURPLE)
(FISHY)
     (SNAKE-LIKE WET NOSEY) (DRY COLORLESS))


It's difficult to see the exact ways in which
this one is mangled, but it's obvious that you
don't want to be doing things like this!



Here's a simpler pathological case:

(setq circle '(first second))
--> (FIRST SECOND)

(rplacd circle circle)
--> (FIRST FIRST FIRST FIRST FIRST FIRST FIRST
FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST
FIRST FIRST FIRST FIRST FIRST FIRST
Aborted

circle
--> (FIRST FIRST FIRST FIRST FIRST FIRST FIRST
FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST
FIRST FIRST FIRST FIRST FIRST FIRST
Aborted

(setq *print-circle* t)
--> T

circle
--> #1=(FIRST . #1#)