Lists are not stored in the computer as sequences of BCD characters, but as structural forms built out of computer words as parts of trees.
In representing list structure, a computer word will be depicted as a rectangle divided into two sections, the address and decrement.
.------.------.
| add. | dec. |
`------'------'
Each of these is a 15-bit field of the word.
We define a pointer to a computer word as the 15-bit quantity that is the complement of the address of the word. Thus a pointer to location 77777 would be 00001.
Suppose the decrement of word x contains a pointer to word y. We diagram this as
.------.------. .------.------.
| | |---------->| | |
`------'------' `------'------'
x y
We can now give a rule for representing S-expressions in the computer. The representation of atomic symbols will be explained in section 7.3. When a computer word contains a pointer to an atomic symbol in the address or decrement, the atomic symbol will be written there as
.-------. - - - -
| ONION |
`-------' - - - -
The rule for representing non-atomic S-expressions ia to start with a word containing a pointer to car of the expression in the address, and a pointer to cdr of the expression in the decrement.
Following are some diagrammed S-expressions, shown as they would appear in the computer. It is convenient to indicate NIL by
- - - - .-------.
|*******|
- - - - `-------'
instead of
- - - - .-------.
| NIL |
- - - - `-------'.
(A . B) | .-----.-----.
`--->| A | B |
`-----'-----'
(A B C) | .-----.-----. .-----.-----. .-----.------.
`--->| A | |--->| B | |--->| C |******|
`-----'-----' `-----'-----' `-----'------'
((M . N) X (M . N))
| .-----.-----. .-----.-----. .-----.------.
`--->| | |--->| X | |--->| |******|
`-----'-----' `-----'-----' `-----'------'
| |
.--V--.-----. .--V--.-----.
| M | N | | M | N |
`-----'-----' `-----'-----'
It is possible for lists to make use of common subexpressions. ((M . N) X (M . N)) could also be represented as
| .-----.-----. .-----.-----. .-----.------.
`--->| | |--->| X | |--->| |******|
`-----'-----' `-----'-----' `-----'------'
| .----------------'
| .--V--.-----.
`------------>| M | N |
`-----'-----'
Circular lists are ordinarily not permitted. They may not be read in, however, they can occur inside the computer as the result of computations involving certain functions. Their printed representation is infinite in length. For example, the structure
| .-----.-----. .-----.-----. .-----.-----.
`--->| A | |--->| B | |--->| C | |
`-----'-----' `-----'-----' `-----'-----'
^ |
`---------------------------------------'
will print as (A B C A B C A...
That which follows is an actual assembly listing of the S-expression (A (B (C . A)) (C . A)) which is diagrammed:
| .-----.-----. .-----.-----. .-----.------.
`--->| A | |--->| | |--->| |******|
`-----'-----' `-----'-----' `-----'------'
| `--------------.
.--V--.-----. .-----.------. |
| B | |--->| |******| |
`-----'-----' `-----'------' |
| .--V--.-----.
`---------->| C | A |
`-----'-----'
The atoms A, B, and C are represented by pointers to locations
12327, 12330, and 12331, respectively. NIL is represented by
a pointer to location 00000.
10425 0 67352 0 65451 -A,,-*-1
10426 0 67351 0 67350 -*-2,,-*-1
10427 0 00000 0 67346 -*-3
10430 0 67347 0 65450 -B,,-*-1
10431 0 00000 0 67346 -*-1
10432 0 65451 0 65447 -C,,-A
The advantages of list structures for the storage of symbolic
expressions are:
1. The size and even the number of expressions with which the program
will have to deal cannot be predicted in advance. Therefore, it is
difficult to arrange blocks of
storage of fixed length to contain them.
2. Registers can be put back on the free-storage list when they are no longer needed. Even one register returned to the list is of value, but if expressions are stored linearly, it is difficult to make use of blocks of registers of odd sizes that may become available.
3. An expression that occurs as a subexpression of several expressions need be represented in storage only once.