LISTS in Pop-11 are built out of a data type called PAIRS, which are two-element records. Pairs can be created using the procedure conspair.
vars pair1 = conspair(3, "cat");
pair1 =>
** [3|cat]
Note how pairs are printed almost like lists, except for the vertical
bar to indicate that they are not two element lists.
The built in system procedures front and back can be used to access or update their elements. E.g.
front(pair1) =>
** 3
"dog" -> back(pair1);
pair1 =>
** [3|dog]
Pairs can be chained together, e.g. by creating a new pair whose back is
the old one.
vars pair2 = conspair(2, pair1);
pair2 =>
** [2 3|dog]
Notice how the printing procedure starts printing pair2 as if it were a
list, that is a chain of pairs, then suddenly it finds that the list
ends in a pair that has a word as its back, rather than another pair or
the special end of list object [], so it indicates that it's not a
proper list, by using the vertical bar again.
The procedure destpair, when given a pair, puts both the front and the back on the stack. So using destpair can sometimes be more efficient than first calling front then back.
destpair(pair1) =>
** 3 dog
The front and the back of the second pair created above, pair2, can also
be accessed in one Pop-11 instruction, using destpair:
destpair(pair2) =>
** 2 [3|dog]
For example, a loop doing something to every item in a chain of pairs
might have:
while ispair(chain) do
destpair(chain) -> (item, chain);
.... instructions involving item .....
endwhile;
instead of
while ispair(chain) do
front(chain) -> item;
.... instructions involving item .....
back(chain) -> chain;
endwhile;
The chain of two pairs created above involving pair1 and pair2 is not yet a proper list, since every list must end with the empty list [] as the back of the final pair (except for dynamic lists, described below.)
vars
pair1 = conspair("b", "c"),
pair2 = conspair("a", pair1);
So neither pair1, nor pair2 is a proper list, as is indicated by the way
they are printed, e.g.:
pair2 =>
** [a b|c]
If we now change the back of pair1, by assigning [] to it, we'll get
a proper list:
[] -> back(pair1);
pair1 =>
** [b]
and this has also changed pair2 into a properly terminated list.
pair2 =>
** [a b]
NOTE: The empty list [] is a special, unique object, with its own
dataword (like termin and popstackmark).
dataword([]) =>
** nil
The system identifier "nil" can also be used to refer to the empty list:
nil =>
** []
nil == [] =>
** <true>
conspair(3, conspair(4, nil)) =>
** [3 4]
From this, it should be clear that the list expression [a b] is actually just "syntactic sugar" for the expression:
conspair("a", conspair("b", []))
and [a ^x b] is syntactic sugar for
conspair("a", conspair(x, conspair("b", [])))
and [a %x + y% b] is syntactic sugar for
conspair("a", conspair(x + y, conspair("b", [])))
So, inside a list expression, words are quoted by default and "^" or "%"
is used to unquote them, whereas outside a list words are by default not
quoted and """ is used to quote them. The same applies to vector
expressions using { ... }
Exercise: What is [the cow is brown] syntactic sugar for?
Because all lists end in the unique object [], there are many programs that chain down a list made of pairs by assigning the first pair to a variable, then the second pair, then the third, and so on, stopping only when it is found that the variable points to [].
For example here is a recursive procedure to copy a list (which could be written more compactly but would be less clear):
define copy_list(oldlist) -> newlist;
lvars newtail ;
if oldlist == [] then
[] -> newlist
elseif ispair(oldlist) then
;;; recursively copy the back of the list
copy_list(back(oldlist)) -> newtail;
;;; and create a new list using the old front
;;; and the new tail
conspair(front(oldlist), newtail) -> newlist
else
mishap('LIST NEEDED', [^oldlist])
endif
enddefine;
copy_list([a b c d]) =>
** [a b c d]
Recursive procedures can often be understood more easily if traced,
using the trace mechanism described in Chapter 4 (or HELP TRACE). So
try running the previous command after first doing:
trace copy_listNote that the Pop-11 system procedure copylist does exactly what copy_list does, so there's no need for the user to define copy_list.
Note also that if there were an embedded list, it would not be copied: it would reappear in the new list, as in [a b [c d] e]. Lists like this have a "tree" structure, as shown by the boxes diagrams below.
Complete copying of a tree can be achieved by a "doubly recursive" procedure, which copies list elements that are lists as well as copying the "top level" list.
For example, here's a doubly recursive version, which simply leaves its results on the stack instead of using an output local variable:
define copy_tree(tree);
if ispair(tree) then
;;; copy the front if its a pair, otherwise use it, and
;;; then put the result in a new pair, with a copy of the
;;; old back
conspair(
if ispair(tree) then copy_tree(front(tree))
else tree endif,
copy_tree(back(tree)) )
else
;;; just return the item that is not a pair
tree
endif
enddefine;
vars tree = [[a 1 2] [b 3 4] [c [x y] 5 6] d];
copy_tree(tree) =>
Running that example with copy_tree traced, will show all the recursive
calls.
We turn now to showing in more detail how the static lists are actually represented.
We have already seen on numerous occasions that lists can be treated as if they were one dimensional arrays, whose elements can be accessed via numerical subscripts, starting from 1.
vars list = [a bird in the hand];
list(2) =>
** bird
"fish" -> list(2);
list(2) =>
** fish
list =>
** [a fish in the hand]
If the number is too small or too large an error will result.
list(8) =>
;;; MISHAP - BAD ARGUMENTS FOR INDEXED LIST ACCESS
;;; INVOLVING: 8 [a fish in the hand]
;;; DOING : compile ....
Here is a rather different program that uses iteration rather than recursion. It searches down the list links until if finds a target element and then returns a copy of the rest of the list, starting from the target.
define tail_list(target, oldlist) -> newlist;
oldlist -> newlist;
repeat
if newlist == [] then
mishap('TARGET NOT IN LIST', [^target ^list])
else
if front(newlist) = target then
return(); ;;; result is newlist
else
;;; get next link in the list
back(newlist) -> newlist
endif
endif
endrepeat
enddefine;
tail_list("cat", [The black cat sat on the mat]) =>
** [cat sat on the mat]
Exercise: re-write that procedure using the for loop format:
for <var> on list do .... endfor