This section shows how (non-dynamic) lists are represented as chained collections of pairs linked together. It is based on the Poplog file TEACH BOXES, originally written by Steve Hardy.
Consider the following set of instructions in Pop-11. We first explain what each one means to a user, and then present a graphical representation of the effects on the computers memory.
vars x;This puts an entry for the word "x" in the Pop-11 dictionary (unless it was already there), and, in the current section, associates it with an ordinary identifier record (identprops = 0). The "valof" cell in the record originally has an <undef x> record as its contents.
.---.
x! *-+----> <undef x>
.---.
"a" -> x;
This creates an entry for the word "a" in the Pop-11 dictionary (unless
it was already there) and stores a pointer to the word in the valof cell
of the identifier record associated with "x"
Dictionary Identifiers in
Current section
<word v>
.========.
<word x>----> |ident * |
.======+=.
|
<word a> <-----------+
<word if>------>....
Here the notation *----> is used to represent a "pointer" where the "*"
indicates a bit pattern that gives the address in (virtual) memory of
the item at the other end of the arrow. When a memory cell contains a
pointer to the word "a" we shall sometimes abbreviate this by displaying
the word directly in the cell. Also instead of separately representing a
word in the dictionary and its identifier record, we can write the word
immediately to the left of a box representing its "valof" cell. Thus the
above representation of the effect of "a" -> x can be abbreviated as
follows:
.===.
x| a |
.===.
We'll use this sort of abbreviation in subsequent examples.
[a] -> x;This is equivalent to
conspair("a", []) -> x;
It creates a new list, consisting of a single pair record, with a
pointer to the word "a" in its front and a pointer to the empty list []
in its back.
.===. .---.---.
x| *-+-->| a | *-+----->[]
.===. .---.---.
To simplify such examples, we'll display "[]" in the box, instead of
showing a pointer to it. So the above example becomes
.===. .---.--.
x| *-+-->| a |[]|
.===. .---.--.
[how now brown cow] -> x;
This creates records for the four words "how", "now", "brown" and "cow"
and puts them in the dictionary (so that they'll be found and re-used if
the words occur somewhere else). It does not create identifier records
for value cells for the words, because they are merely quoted in the
list, not used as variable names. It then creates a four element
list, made of four list links, the first containing a pointer to "how"
in its front and a pointer to the second in its back, the second
containing a pointer to "now" in its front, and so on. The fourth link
contains a pointer to [] in its back. When the list has been constructed
a pointer to the first pair is put on the stack. Then the assignment
removes it from the stack and puts it in the valof cell for "x", with
the following result:
.===. .---.---. .---.---. .-----.---. .---.--.
x| *-+-->|how| *-+-->|now| *-+-->|brown| *-+-->|cow|[]|
.===. .---.---. .---.---. .-----.---. .---.--.
[[a]] -> x;
This creates a list consisting of a single pair, whose front contains
"a" and whose back contains [], then creates a new list whose front
points to the original list and whose back also points to [], thus:
.===. .---.--.
x| *-+-->| * |[]|
.===. .-+-.--.
| (Note: the backs of both pairs point to the
v very same item, not two copies of [].)
.---.--.
| a |[]|
.---.--.
[[the man] kicked [a dog]] -> x;
This one is easier to show than to describe. It might be a good idea for
the reader to draw the diagram corresponding to this before looking at
the one given here.
.===. .---.---. .------.---. .---.--.
x| *-+-->| * | *-+-->|kicked| *-+-->| * |[]|
.===. .-+-.---. .------.---. .-+-.--.
| |
v v
.---.---. .---.--. .---.---. .---.--.
|the| *-+-->|man|[]| | a | *-+-->|dog|[]|
.---.---. .---.--. .---.---. .---.--.
[a b c] -> x; tl(x) -> y;
This creates the expected two-element list containing pointers to the
quoted words "a", "b" and "c" (added to the dictionary if necessary),
and inserts a pointer to the first link into the valof cell for "x".
The procedure "tl" then takes a copy of the pointer in the back of the first link pointed to by "x" (i.e. its tail, or "tl") and the assignment puts it in the valof cell for the word "y", so that "x" and "y" now both provides route to the second pair in the list, though it can be reached more directly from "y".
.===. .---.---. .---.--. .---.--.
x| *-+-->| a | *-+-->| b | * +--->| c |[]|
.===. .---.---. .---.--. .---.--.
^
.===. |
y| *-+-----------------*
.===.
After the above has been constructed, the expression "y == tl(x)"
evaluates to TRUE. I.e. it is only the pointer that has been copied
across: the list cell pointed to has not been copied. So if we were
to assign something to hd(y) then that would also change hd(tl(x)) and
vice versa.
The next example illustrates the use of the structure concatenator "<>" when used with lists. An expression of the form list1 <> list2 creates a new list, which starts with the elements of list1 and continues with the elements of list2. However although it makes a complete copy of list1, it re-uses the list2, so that we end up with two lists sharing a common "tail", as above.
[a b] -> x; [c d] -> y; x <> y -> z;This creates two two-element lists, putting pointers to the first in the valof cell for "x", the second in the valof cell for "y". It then creates a third list which starts with a *complete* copy of the list links in the first list (i.e. x) , and then instead of ending the copy with [], puts a pointer to the first link of the second list, with the following overall result:
.===. .---.---. .---.--.
x| *-+-->| a | *-+-->| b |[]| (Copied to start off z)
.===. .---.---. .---.--.
.===. .---.---. .---.--.
y| *-+-->| c | *-+-->| d |[]|
.===. .---.---. .---.--.
^
|
*---------------*
|
.===. .---.---. .---.-+-.
z| *-+-->| a | *-+-->| b | * |
.===. .---.---. .---.--.
Note that the two occurrences of "a" are actually two copies of a
pointer to the very same word "a" in the dictionary. Similarly the two
occurrences of "b". So both of the following are true:
hd(x) == hd(z), hd(tl(x)) == hd(tl(y))Also y == tl(tl(z)) is true.
[a b] -> x; [c d] -> y; y -> tl(tl(x));This is similar except that instead of making a copy of the two pairs in x and making the final link of the COPY point to the list in y, it puts a pointer to the second list in the back of the last link of x, producing this:
.===. .---.---. .---.--.
x| *-+-->| a | *-+-->| b | * |
.===. .---.---. .---.-+-.
|
*---------------*
|
v
.===. .---.---. .---.--.
y| *-+-->| c | *-+-->| d |[]|
.===. .---.---. .---.--.
Notice the lack of symmetry between hd and tl. hd(list) is the same as list(1). But tl(list) is not the same as list(2): it is a list of ALL remaining elements, or [] if there are not any more.
Simlar comments may be made about front and back when applied to lists.