TEACH LISTS Revised A.Sloman Nov 1989
INTRODUCTION TO LISTS
=====================
CONTENTS - (Use <ENTER> g to access required sections)
-- Introduction
-- Prerequisites
-- Introductory examples
-- How to read assignment and print instructions
-- The procedure length
-- Length of an empty list
-- Getting at the individual elements of a list
-- Changing the Nth element of a list
-- The procedure member
-- A list can contain other lists
-- A list has a tail, and its tail has a tail and ...
-- An empty list has no tail
-- A list also has a "head"
-- Updating the first element of a list
-- The asymmetry between hd and tl
-- A more explicit notation using "::"
-- Joining lists using <>
-- Reversing a list
-- The procedure last
-- Miscellaneous examples
-- Further reading-- Introduction -------------------------------------------------------
Intelligent systems need to represent things, like objects in the world,
goals, strategies.... This requires a 'representation language', which
can be used to build descriptions, store them, compare them, make
inferences from them.
An important type of object used for building descriptions in POP-11
programs is the list. You can make lists of words, lists of numbers,
lists of words and numbers, lists of lists, lists of all sorts of
things. In the exercises below we introduce you to programs which
manipulate lists of words and numbers, mainly. Lists are an important
'data type' in POP-11 since they can be used for a wide variety of
purposes. E.g. programs which understand sentences represent them as
lists of words, and represent their interpretations as, for example,
lists of lists of propositions.
For the purpose of "looking inside" lists, and building new lists,
POP-11 provides a powerful collection of procedures. What follows is a
brief introduction to some of these procedures.
-- Prerequisites ------------------------------------------------------
Before working through these examples you should be familiar with the
editor (TEACH VED, TEACH VEDPOP)) and the use of marked ranges (as
explained in TEACH MARK, TEACH LMR)
-- Introductory examples ----------------------------------------------
Here is a collection of little examples which should give you a basic
grasp of list processing in POP-11. You are advised to make notes on
everything as you work through the examples. Try the following Pop-11
commands and see what happens:
vars list;
[1 2 3 4 5] -> list;
list =>
(E.g. type that in a file, then mark the range, and use <ENTER> lmr to
get the commands obeyed.)
The first line declared a variable called LIST,
vars list;
The next line assigned a list of numbers to it,
[1 2 3 4 5] -> list;
then the third line used the print-arrow to print out the value of the
variable LIST:
list =>
Now try assigning a different list of numbers:
[1 2 3 4 5 6] -> list;
list =>
or a list of words
[the cat ate the mouse] -> list;
list =>
Try assigning a list of words and numbers to list, and then print it
out.
-- How to read assignment and print instructions ----------------------
It is important to note that something like
[the cat ate the mouse] -> list;
is really made of two separate instructions. The first is
[the cat ate the mouse]
which means, "create the list [the cat ate the mouse] and put it on the
stack". The stack is a part of the computer's memory reserved by Pop-11
for communication between different procedures. All arguments for a
procedure (i.e. inputs for the procedure) are put on the stack, where
the procedure will find them, and if the procedure produces a result it
will leave it on the stack.
The second instruction is
-> list;
and this means, assign the last thing put on the stack to be the value
of the variable called "list".
The following print instruction also has two separate parts:
list =>
The first part "list" just means put the value of the variable "list" on
the stack.
The second part "=>" means, run the print-arrow procedure. This prints
out whatever is on the stack.
-- The procedure length -----------------------------------------------
The procedure LENGTH, when applied to a list, counts the number if items
in the list, and returns a number as its result.
length(list) =>
length( [ 1 5 9 16 ] ) =>
Note the difference between the square brackets, which make a list, and
the round brackets, which function as "doit" brackets. I.e. they tell
Pop-11 to DO (or RUN or EXECUTE or OBEY) the procedure length.
You can tell Pop-11 to run the procedure without anything between the
doit brackets, but you will get a 'STACK EMPTY' error message. Try it
length() =>
;;; MISHAP - STE: STACK EMPTY (missing argument? missing result?)
;;; DOING : length ......
(The error message may have some additional information. I have left
out everthing irrelevant.)
The procedure length requires an object to be given to it as its "input"
(sometimes called its "actual parameter" or its "argument"). If an
argument is given between the doit brackets, as in
length([ 9 8 7]) =>
Then the input (the list [9 8 7] in this case) is put on the stack, and
that is where the procedure finds it. If it does not find it, the STACK
EMPTY mishap message results.
-- Length of an empty list --------------------------------------------
Note that the length of the empty list is 0
length([]) =>
-- Getting at the individual elements of a list -----------------------
Now assign a list of 5 words to the variable LIST and try:
list(1) =>
list(2) =>
list(4) =>
Those commands print out, respectively, the first, second and fourth
elements of the list. Try
list(999) =>
You will get an error message, because there are not as many as 999
elemets in the list.
-- Changing the Nth element of a list ---------------------------------
If a list contains certain elements and you want to change one of them
them you can "update" the list. E.g. first create a list
[the cat ate the mouse] -> list;
check its contents
list =>
Now make the word "dog" the second element of the list, by updating it,
using the assignment arrow.
"dog" -> list(2);
I.e. assign "dog" to be the second element of the value of the variable
list.
(The double quote marks are required to indicate that it is the word
"dog" itself, not the value of the variable dog that is to be stored in
the list.)
Check the contents again to see what is now in the list.
list =>
Try to make the number 6 the third element of the list, using the
assignment arrow in the same way.
Although it is often useful to represent a changing world by means of
lists whose contents change, it can sometimes cause considerable
confusion if a list is altered after it has been created, and some
programming languages do not permit this. It is permitted in Pop-11, but
the facility has to be used with care, as one part of a program can
change a list while another part is intended to go on operating on the
original list.
-- The procedure member -----------------------------------------------
If you know that a list has the item you want in its 4th location you
can use the numerical notation explained above to get at the 4th
element, in order to print it out, or assign it to some other variable.
If you don't know whether some item occurs in a list or not, there is a
predicate (a procedure that returns true or false) built in to Pop-11
for testing whether something is a member of a list. the procedure is
called "member". It takes two inputs, an item and a list, and returns
the result true if the item is in the list, false otherwise.
member(3, [1 2 3 4 5]) =>
** <true>
Compare the behaviour with this one-element list:
member(3, [ 12345 ])=>
** <false>
Nothing is a member of the empty list:
member(3, []) =>
** <false>
member("fox", [the fox ate the grain]) =>
** <true>
member("chicken", [the fox ate the grain]) =>
** <false>
Note that when testing if a word occurs in a list we have to put the
word between "quote" marks to ensure that member looks for the word
itself, and not the value of the word treated as a variable. The
procedure member is just one of many procedures available for operating
on lists.
The procedure must be given two arguments. If you give it only one, a
mishap will occur:
member([the fac cat]) =>
;;; MISHAP - STE: STACK EMPTY (missing argument? missing result?)
;;; DOING : member .....
Member took one thing off the stack, then looked for another and found
the stack empty, and complained.
-- A list can contain other lists -------------------------------------
A list may include lists among its elements, just as a bag of things may
include smaller bags of things, e.g.
vars l;
[ one [ list a ] two [ list b ] ] -> l;
l=>
l(1) =>
l(2) =>
l(3) =>
l(4) =>
So the 2nd and 4th elements of L are not words, but lists containing
words. Thus we can ask for the first of the second element, or the
second of the fourth element:
l =>
l(2)(1) => ;;; get 2nd of L, then the first element of that.
l(4)(2) => ;;; get 4th of L, then 2nd element of that.
Note that in POP-11 three semi-colons mean 'ignore the rest of the line'.
I.e. they start an "end-of-line comment".
Another example:
vars newlist;
[[one list] [another list] [yet another]] -> newlist;
newlist =>
The variable newlist now has as its value a list containing three
elements, all of them lists.
length(newlist) =>
The length does not include the number of items in the lists contained
in newlist. Only the "top level" items are counted, and there are three
of them. How many elements are there in the following:
[ a b 99 [c d e] [f g h] 10 [2 4 5] ]
Mark and copy that, and give it as input to the procedure LENGTH and see
what result it produces.
Here is how you count elements in a list like the one above
[ a b 99 [c d e] [f g h] 10 [2 4 5] ]
1 2 3 4 5 6 7
Note that an included list, enclosed in [ ... ] is counted as ONE item.
You can see that the second element of a list of lists is itself a list,
thus:
[ [a b c] [d e f g] [h i j k l] ] -> newlist;
newlist(2) =>
** [d e f g]
Since this is itself a list, we can ask for its first element, i.e. the
first element of the second element of newlist is the word "d".
newlist(2)(1) =>
Try giving a command to print the fourth element of the third element of
newlist, which should be the word "k".
We can ask how many elements, the second element of newlist contains,
thus:
length(newlist(2)) =>
Try giving a command to print out the length of the third element of
newlist.
The procedure member can be asked if a list occurs as a member of
another list:
member([the man], [the man on the moon]) =>
** <false>
member([the man], [ [the man] on [the moon] ]) =>
** <true>
member([the man], [ [the] [man on] [the moon] ]) =>
** <false>
Note the comma separating the first "argument" of member from the second
argument. The second argument HAS to be a list. The first argument may
be but need not be.
-- A list has a tail, and its tail has a tail and ... -----------------
One of the important things about lists is that they have tails which
are also lists. In fact the tail of a (non-empty) list is a list
containing all the elements but the first.
[a b c d e] -> list;
tl(list) =>
** [b c d e]
What would the tail of the tail of the list be? Try giving a command
to print it out. Try the above with different lists.
If the length of a list is N, then the length of its tail is N - 1.
length(list) =>
length(tl(list)) =>
TL (read as "tail") is a procedure which, when given a list as input,
produces another list as output, containing all but the first element of
the original. (In some programming languages the name "REST" or
"BUTFIRST" would be used for this. In LISP it is called "CDR"!)
This means that if you start with a list containing only ONE item, then
its tl must contain NO items, i.e. it must be the empty list. Try these:
tl([cat]) =>
tl([9]) =>
tl([[a b c]]) =>
Note that the last one is tricky [[a b c]] is a ONE element list. It
contains one element which is a list [a b c].
In every case the tail of a one element list is the same thing, the
empty list [].
-- An empty list has no tail ------------------------------------------
If you try to find the tail of an empty list you will get a mishap
message. Try this:
tl( [] ) =>
;;; MISHAP - NON-EMPTY LIST NEEDED
;;; INVOLVING: []
;;; DOING : tl ....
Note that the "DOING" line tells you that it was trying to run the
procedure tl. The "INVOLVING" line tells you what caused the trouble,
and made tl complain that it wants a non-empty list.
-- A list also has a "head" -------------------------------------------
You've alread seen that writing "(1)" can be used to get the first
element of a list. Alternatively you can apply the procedure hd
(pronounced "head") to the list.
[the silly cat] -> list;
list(1) =>
hd(list) =>
What is the hd of this list?
[[the very silly cat] [ate the mighty mouse]]
Try it.
Like the procedure tl, hd also expects a non empty list. Try:
hd( [] ) =>
Also it complains if not given anything as input
hd() =>
-- Updating the first element of a list -------------------------------
You can also use both formats to update the head of a list. E.g.
make "pig" the first element of list:
"pig" -> hd(list);
check that it has changed.
list =>
The above command is equivalent to
"pig" -> list(1);
-- The asymmetry between hd and tl ------------------------------------
Because hd(list) and list(1) are the same thing you might think that
tl(list) and list(2) are the same thing. But they are not. Why?
Look back at the definition of the tail of a list. The crucial point is
that whereas hd is defined to produce only the first element of a list,
which may or may not be a list, tl always produces a list containing ALL
the elements apart from the first.
So hd([ a silly cat]) is the word "a" and hd([6 7 8]) is the number 6,
whereas hd([[a b] [c d]]) is the list [a b]). So the result of applying
hd to a list can be anything, depending on what the first element of the
list is.
By contrast tl always returns a list, even if it is the empty list. Try:
tl([ a silly cat]) =>
tl([6 7 8]) =>
tl([[a b] [c d]]) =>
Here is one way to think of the difference between hd and tl. The square
bracket notation for creating lists may lead you to think that a list is
created from left to right. However the opposite is the case. The
instruction to create the list
[1 2 3 4]
amounts to the instruction first to combine 4 with the empty list to
give a one element list, thus
[4]
Then 3 is stuck on the front of that, giving a two element list
[3 4]
whose tail is the previous list, [4]. Then yet another list is created
starting with 2 joined on to the last list, giving
[2 3 4]
whose tail is [3 4]. Finally a list is created containing 1 as its first
element and [2 3 4] as its tail, namely the list
[1 2 3 4]
So there is a sense in which the notation for lists is misleading,
because there is only one pair of brackets when in fact several
different lists exist.
-- A more explicit notation using "::" --------------------------------
In Pop-11 the symbol "::" is the name of a procedure for creating a new
list containing a new object as its head and an old list as its tail.
Like the symbol for the arithmetic operation "+", the symbol "::" is
an "infix" symbol, and is written BETWEEN its two inputs, rather than in
front of them (like member).
The second argument of :: MUST always be a list, possibly the empty
list.
We can now see the following equivalences
[3] is the same thing as 3 :: [] whose tail is []
[2 3] is the same thing as 2 :: (3 :: [])
i.e. 2 :: [3] whose tail is [3]
[1 2 3] is the same thing as 1 :: (2 :: (3 :: []))
i.e. 1 :: (2 :: [3])
i.e. 1 :: [2 3] whose tail is [2 3]
This should make clear why we use the convention that as you make a big
list you don't need to show all the brackets corresponding to all its
tails. Being able to type [1 2 3] is far more convenient, and much
easier to read than
1 :: (2 :: (3 :: []))
So you can think of :: as if it "shoves" its left hand argument just
inside the left square bracket of its right hand argument, even if
several things have already been shoved there.
This shows how to understand the operation of hd and tl.
Think of hd as getting the last item joined to the list, ie. the first
item in the list. So
hd([1 2 3]) is hd(1 :: [2 3]) which is 1.
Whereas tl gets what existed before the list item was joined to the
list. So
tl([1 2 3]) is tl(1 :: [2 3]) which is [2 3]
It should be clear from this that the second item of a list is the hd of
the tl of the list. I.e.
list(2)
is equivalent to
hd(tl(list))
Now try to express the 4th item of a list in terms of hd and tl. I.e.
list(4) is equivalent to ... what ???
-- Joining lists using <> ---------------------------------------------
If you already have two lists list1 and list2, and wish to make a third
list containing first all the elements of list1 then all the elements of
list2 you can use the "append" or "join" operator <>. This, like "::" is
an infix operator, written between its two arguments.
Here are some examples:
[1 2 3] <> [a b c d] =>
** [1 2 3 a b c d]
(i.e. create the list [1 2 3] and put it on the stack, create the list
[a b c d] and put it on the stack, then run the procedure <> which takes
two things off the stack and puts a list back, then run the print
procedure => which prints out what is on the stack.
See if you can anticipate what the following will print, and then try
them out.
vars list1, list2, list;
[a b c d] -> list1;
[9 8 7 6] -> list2;
list1 <> list2 -> list;
list =>
list2 <> list1 -> list;
list =>
list1 <> list1 =>
tl(list1) <> tl(list2) =>
-- The difference between <> and :: -----------------------------------
The operator :: is more basic than <>. The instruction
[1 2 3] <> [4 5]
is best thought of as starting with the list [4 5] and then using :: to
add 3 at the front, then :: to add 2 at the front then :: to add 1 at
the front. i.e.
1 :: ( 2 :: ( 3 :: [4 5] ) )
I.e. the operator <> uses the list given as its second argument, but
essentially builds a new "inital sublist" copying the list given as its
first argument.
For this reason <> MUST have a list of items on its left, if given a
list on its right. It can't join a number to a list, for example:
3 <> [4 5] =>
;;; MISHAP - ILLEGAL ARGUMENTS FOR <>
;;; INVOLVING: 3 [4 5]
;;; DOING : <> ....
whereas :: can
3 :: [4 5] =>
** [3 4 5]
If you give a list as the first argument to :: it will keep it as a
single entity to add onto its second argument, e.g.
[1 2] :: [3 4] =>
** [[1 2] 3 4]
So the new list has as its head the list [1 2]. Contrast
[1 2] <> [3 4] =>
Always remember: :: produces a list ONE element longer than its second
argument, whereas <> produces a list whose length is the SUM of the
lengths of its two arguments.
-- Reversing a list ---------------------------------------------------
The built in procedure REV, can be given a list as input and produces
a new list as output, containing the same elements but in reverse order.
Note that the original list is unchanged.
vars x;
[1 2 3 4] -> list;
rev(list) =>
** [4 3 2 1]
The result of rev can be assigned to another variable:
rev(list) -> x;
x =>
** [4 3 2 1]
Notice that the instruction 'rev(list) -> x' is actually made of THREE
separate instructions.
(a) put the value of list on the stack
(b) run the procedure rev (which may be composed of many
instructions, and which will put its result on the stack)
(c) assign what is left on the stack to the variable x.
Work out what each of the following should print out, and then check
your reasoning by giving the command:
rev(rev(list)) =>
rev(list)(1) =>
rev(list)(4) =>
rev(tl(list)) =>
tl(rev(list)) =>
vars list1, list;
[a b c] -> list1;
list1 <> rev(list1) -> list;
list =>
-- The procedure last -------------------------------------------------
Can you anticipate what these commands will do:
vars num;
[a b c d e] -> l;
length(l) -> num;
num =>
l(num) =>
This method can be used to get at the last element of a list. However it
is rather clumsy and the procedure last is provided to access, or to
update, the last element of a list. Try this:
last(list)=>
last(rev(list)) =>
99 -> last(list);
list =>
"cat" -> last(list)
list =>
-- Miscellaneous examples ---------------------------------------------
Notice what happens if you don't leave spaces between the numbers
when you type in a list:
[1234] -> x;
x(1) =>
tl([1234]) =>
length([1234])=>
length ([1 2 3 4]) =>
tl([1 2 3 4]) =>
Before trying each of these write down what you think will be
printed as a result:
[c a T](1) =>
[cat](1) =>
tl([c a t]) =>
tl([cat]) =>
length ([c a t]) =>
length ([cat]) =>
[cat on mat](1) =>
[c a t o n m a t](3)=>
[cat on mat](3) =>
vars x;
[[one two three]] -> x;
How many elements in x?
length(x) =>
The tail of x is empty ie. there are no elements after the first
x =>
tl(x) =>
And x has no second element:
x(2) =>
;;; MISHAP - BAD ARGUMENTS FOR INDEXED LIST ACCESS
;;; INVOLVING: 2 [[one two three]]
-- Revision -----------------------------------------------------------
Before proceeding, it is a good idea to make sure that you remember
everything you've read so far. You should, for example, be able to write
explanations of what the following are:
hd
tl
length
rev
last
member
::
<>
and what the following do:
[ 1 2 [ a b c ] d e ] -> list;
list(1) =>
list(3) =>
list(3)(1) =>
-- Further reading ----------------------------------------------------
See TEACH * STACK for more on the stack.
To learn more on lists and pattern matching, see the following:
TEACH * ARROW
TEACH * MATCHES
TEACH * LISTSUMMARY
There are two files that attempt to explain in more detail how lists are
represented in the computer's memory.
TEACH * BOXES
TEACH * WAL
To learn about procedure definitions, see
TEACH * DEFINE
TEACH * VARS
and thereafter have practice defining procedures that operate on lists,
as indicated in
TEACH * SETS
TEACH * SETS2
--- C.all/teach/lists
--- Copyright University of Sussex 1989. All rights reserved. ----------