We have seen that a list is actually a chained collection of pairs. But
most of the time the user does not need to know about this. High level
facilities for manipulating lists are provided, which conceal from the
user the details of how they are represented in the machine. For example
Pop-11 provides special syntax using the list brackets [ ... ] together
with "^", "^^" and "%" for creating lists by specifying what they should
"look like", without worrying about their implementation at a lower
level.
Additional facilities provided that "hide the implementation details" are the following procedures:
matches, copylist, applist, maplist, and the list concatenator <>.In addition there are looping constructs, e.g. using
for <var> in <list expression> do ... endfor
foreach <pattern> in <list> do ... endforeach
which also make it convenient to manipulate lists without knowing how
they are implemented. (The faster version: "fast_for ... endfast_for"
described in REF FASTPROCS) assumes that there are no dynamic lists
(described below), and therefore does not do as much checking.)
For the sake of efficiency it is sometimes useful to know how lists are implemented and to use the procedures conspair, destpair, front and back as in previous examples. This would have the disadvantage that if the implementation were ever to change and something other than simple chained pairs were used for lists, then programs that used these procedures would stop working.
In fact, in some versions of the Pop language that is already the case, because Pop2, Pop10 and Poplog Pop-11 support what are called "dynamic" lists, which have a slightly different implementation from the lists described so far, which are all "static" lists. These will be described below.
Meanwhile, the main justification for using hd, tl, and dest can be thought of as being to "hide the implementation details", which allows the implementation to be changed.
Note: "hd" and "tl" in Pop-11 correspond to "CAR" and "CDR" in LISP.
For this reason it is desirable to use something other than conspair, which is guaranteed always to give a list. An infix list constructor operator is provided, namely "::". It's infix precedence is 4. It is similar to conspair, except that it will complain if its second argument is clearly not a list.
"a" :: [b c d] =>
** [a b c d]
conspair("a", "b") =>
** [a|b]
"a" :: "b" =>
;;; MISHAP - LIST NEEDED
;;; INVOLVING: b
;;; DOING : :: (etc.)
Warning:
Unfortunately, for historical reasons, "::" associates to the left
rather than to the right, so parentheses are needed to produce a flat
list, as with conspair:
1 :: (2 :: (3 :: [])) =>
** [1 2 3]
Without the parentheses, it is equivalent to
((1 :: 2) :: 3) :: [] =>And the embedded invocation of "1 :: 2" will produce a LIST NEEDED error.
For this reason, when constructing a list from a number of known items it is usually simpler and clearer to use the "syntactic sugar" of list expressions than to use multiple occurrences of "::", e.g.
[1 2 a ^x ^y]is used instead of
1 :: (2 :: ("a" :: (x :: (y :: []))))
It is important to be aware of the difference between the list constructor :: and the list concatenator <>.
The procedure :: takes a potential list-head and a potential list-tail (which must already be a (possibly empty) list and makes a new list with that head and tail (and without copying the tail). Thus the first argument of :: is the first element of the new list.
By contrast the concatenator <> takes a potential initial segment of a list and a potential final segment, and makes a new list containing those segments. The first argument of <> is not the first ELEMENT of the new list: though its elements are the initial elements of the new list.
The difference can be interested with the following two examples, where both operators are applied to two lists:
[a b c] :: [d e f] =>
** [[a b c] d e f]
[a b c] <> [d e f] =>
** [a b c d e f]
The first example produces a list of four items, the second a list of
six items.
Each could be defined in terms of the other. To illustrate we can use <> to define an infix operator like :: called :+:, and we can use :: to define an infix operator like <> called <+>. In each case we give the infix precedence as an integer following "define".
define 4 :+: (item, list);
[^item] <> list
enddefine;
;;; Test it:
"a" :+: ("b" :+: []) =>
** [a b]
This is wasteful because each invocation of :+: creates a temporary list
to give to <>, which is then copied and discarded.
We can also define a concatenator in terms of ::, though this time we use recursion. The idea is that in order to create list1 <> list2 we first create tl(list1) <> list2, then use hd(list1) and :: to finish the job. The recursive call on the tail of list1 will, of course, use :: repeatedly. When it gets down to list1 == [], the concatenator simply needs to return list2, since [] <> list2 = list2.
define 5 <+> (list1, list2);
if list1 == [] then list2
else
hd(list1) :: (tl(list1) <+> list2)
endif
enddefine;
;;; Test it:
[a b c] <+> [d e f] =>
** [a b c d e f]
Notice that list2 is used exactly as it is: it is not copied. However,
:: creates new list links for the elements of list1.