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. ----------
