TEACH WAL                                  Steve Hardy & Chris Mellish

=== WHAT ARE LISTS? ==================================================

This handout is intended to give you some idea  of  'what  lists  REALLY
are`,  in  the  sense of 'how are they represented within the computer`.
This will have to be a technical discussion - so don't worry if (a)  you
don't  understand  it or (b) you find it boring.  I believe that just as
one can drive a car without knowing how  they  work  so  one  can  write
programs  without knowing how everything works - and the courses I teach
are more akin to 'driving lessons` than 'vehicle maintenance classes` in
that  they  aim  to  get  you  programming  rather  than  being computer
scientists.  This handout is  more  computer  science  than  programming
instruction.

The computer's memory
=====================

Almost all modern computers have the same kind of main memory - a lot of
numbered  'boxes`.   The  normal  term for these boxes is 'word`, so one
says that a computer has so many 'words` of memory -  our  computer  has
1 million (called 4 "megabytes", because a "byte" is a quarter of a word on
this machine). I'll use the word 'boxes` to avoid confusion with POP11 words
like NIL etc.

These boxes contain numbers and a program can either examine  or  change
the  contents  of  any  box.   These  numbers  are almost always used to
represent something other than a simple number - for example:

     (1) A number can be viewed as the ADDRESS of  another  box  in
     the machine's memory.
     (2) A number can be viewed as an instruction.
     (3) A number can be viewed as a character, e.g A=1,  B=2,  C=3
     etc.
     (4) A number can be viewed as a number|

When you type an instruction into  the  POP11  system  it  is  converted
('compiled`)  into  a  series of numbers representing instructions; when
you type in a character string:

        : 'THE CAT SAT ON THE MAT'

the POP11 system finds space to store the series of numbers representing
the  characters  of the string.  A similar process happens when you type
in a word, like "NIL".

Most things in POP11 are represented  by the number of the box at  which
they are stored, so that when you type:

        : 'CAT' -> X;

The POP11 system finds three unused boxes, puts the character  code  for
'C'  in  the  first,  that for 'A' in the second and that for 'T' in the
third.  The address (i.e number) of the first box is then stored in  the
variable  X,  i.e.  in the box associated with the word X when you typed
VARS X.

The representation of lists
===========================

When you type in, say:

        : [HOW NOW BROWN COW] -> L;

the POP11 system assigns the address of the first of a pair of boxes  to
L.  The first box contains the address of a series of boxes representing
the word HOW, the second box contains the address of a  second  pair  of
boxes.   This  second pair (of boxes) contains the address of (the boxes
representing) the word NOW and the address of a third pair  whose  first
component  contains (the address of) the word BROWN and the address of a
fourth pair containing the address the word COW and the address  of  the
word  NIL.   Let us suppose that the box representing the variable L was
100, that of the first pair 101, that of the second  103,  that  of  the
third  105  and  that  of  the  last  107.   If we could look inside the
machine's memory we would see:

        ADDRESS CONTENTS
        100     101
        101     Address of HOW
        102     103
        103     Address of NOW
        104     105
        105     Address of BROWN
        106     107
        107     Address of COW
        108     Address of  NIL

It  is  not  necessary  for  the  boxes representing  a  list  to be
consecutive (as I have shown them here) and usually a list will be scattered
over  the  computer's  memory.   For  a pictorial explanation of this see
later in this demo.

I have glossed over some problems in this account, in particular:

     (1) If you type:

             : [1 2 3 4] -> L;

     how come the computer doesn't get confused  between  a  number
     representing  itself  (e.g  1)  and  a number reprresenting an
     address?  The solution adopted by the  POP11  system  to  this
     problem  is  to add some huge number, say 10000000, to a number.
     Since there isn't a box numbered 10000001 the POP11 system knows
     that  10000001 must represent the number one and not the address
     of a box.

     (2) How does the computer tell the difference between a series
     of boxes representing a pair, say, and a series representing a
     character string?  A solution to this problem  is  to  reserve
     one  box  in  every  series  to  say  what  type  of  thing it
     represents.

     Thus our list [HOW NOW BROWN COW] would look like:

             ADDRESS CONTENTS
             100     101
             101     Address of PAIR
             102     Address of HOW
             103     104
             104     Address of PAIR
             105     Address of NOW
             106     107
             107     Address of PAIR
             108     Address of BROWN
             109     110
             110     Address of PAIR
             111     Address of COW
             112     Address of NIL

     There is a procedure in POP11 called  DATAWORD  which  returns
     the contents of the first box in a series, so that:

                     : DATAWORD("CAT")=>
                     ** WORD

                     : DATAWORD([HOW NOW BROWN COW])=>
                     ** PAIR
                     : DATAWORD(DATAWORD)=>
                     ** PROCEDURE

     For the sake of consistency DATAWORD 'cheats` if you give it a
     number:
                     : DATAWORD(3)=>
                     ** INTEGER

Its a bit tiresome to say 'a box contains the address of the first of  a
series  of boxes representing the word ...' so I am going to say that 'a
box contains the word ...'.
Similarly, it is often clearer to say ' a box contains a pointer to ...'
than  to  say  'a  box  contains the address of the first of a series of
boxes representing ...'.  I will use these two  abbreviations  from  now
on.

Some of the list processing procedures built into POP11
======================================================

Let us suppose that there is a procedure, called CONTENTS, which given a
number, N, and the address of the first of series of boxes, BOX, returns
the contents of the N'th box in the series.
Using this procedure we can define the procedure HD as:

        : DEFINE HD(BOX);
        :       IF      CONTENTS(0,BOX) = "PAIR"
        :       THEN    CONTENTS(1,BOX)
        :       ELSE    MISHAP('Finding HD of non-pair',[^BOX])
        :       ENDIF
        : ENDDEFINE;

Similarly TL can be defined as:

        : DEFINE TL(BOX);
        :       IF      CONTENTS(0,BOX) = "PAIR"
        :       THEN    CONTENTS(2,BOX)
        :       ELSE    MISHAP('Finding TL of non-pair',[^BOX])
        :       ENDIF
        : ENDDEFINE;

In addition to the CONTENTS procedure the POP11 system has  a  FINDBOXES
procedure  available  to  it.   This  takes  a number and find an unused
sequence of boxes the required size - it  returns  the  address  of  the
first, thus:

        : DEFINE 3 X :: Y -> RESULT;
        :       FINDBOXES(3) -> RESULT;
        :       "PAIR" -> CONTENTS(0,RESULT);
        :       X -> CONTENTS(1,RESULT);
        :       Y -> CONTENTS(2,RESULT)
        : ENDDEFINE;

The procedure DATAWORD is defined as:

        : DEFINE DATAWORD(BOX);
        :       IF      BOX > 10000000
        :       THEN    "INTEGER"
        :       ELSE    CONTENTS(0,BOX)
        :       ENDIF
        : ENDDEFINE;

                   Lists represented by little boxes
                   =================================

It is sometimes easier to think about the internal representation of lists in
terms of diagrams of "little boxes". A box represents one location ('word')
in the memory of the computer. Whenever we declare a variable, the POP11
system allocates an unused box somewhere to store that variable's value. So,
for instance, if we type:

    : VARS X;
    : "A" -> X;

then part of the computer's memory ends up looking a bit like this:

     *---*
  X: | A |
     *---*

I have put a label "X:" here to indicate that POP11 "knows" that this is the
box holding the value of X. There is nothing attached to the box itself to
indicate that it is holding the value of X. The POP11 system must keep track
of it by putting the string of characters "X" together with the address of
this box in one of its own datastructures (the DICTIONARY). This diagram
also uses another convenient abbreviation. It assumes, in a way, that it is
possible to store everything about the word "A" in this single box. In
reality, the word "A" must be allocated several boxes, which indicate that it
is a word, give the characters that make up the word and perhaps give the
value of the variable called A, if such a variable has been declared. So the
box for X must actually contain a pointer to (that is, the address of) the
whole sequence of boxes describing "A". To be precise, then, our above
diagram should really look more like:

     *---*
  X: | *-+-------> ..... some boxes representing "A"
     *---*

where the arrow indicates that the box holds the address of whatever the
arrow points to. Since we are not interested here in the internal
representation of words, we will stick to the shorter notation where we
just put the name of the word in the box.

Now for lists. What happens if we type the following:

    : [A] -> X;

Part of the memory now looks as follows:

     *---*   *---*---*
  X: | *-+-->| A |NIL|
     *---*   *---*---*

We still have the original box for X, but now there are two more
(consecutive) boxes in use. These represent the HD and TL of the list that
has been created. Here are some more examples:

    :  [HOW NOW BROWN COW] -> L;

     *---*   *---*---*   *---*---*   *-----*---*   *---*---*
  L: | *-+-->|HOW| *-+-->|NOW| *-+-->|BROWN| *-+-->|COW|NIL|
     *---*   *---*---*   *---*---*   *-----*---*   *---*---*

This is the same example that was treated earlier (in terms of numbers). If
you are uneasy about the diagrammatic representation, you might like to
refer back to the other treatment. Note that in the diagrammatic
representation it would clutter up the diagrams unnecessarily if we included
the DATAWORD components for all these pairs.

Here are more examples, with no commentary:

    : [[A]] -> X;

     *---*   *---*---*
  X: | *-+-->| * |NIL|
     *---*   *-+-*---*
               |
               V
             *---*---*
             | A |NIL|
             *---*---*

: [[THE MAN] KICKED [A DOG]] -> X;

     *---*   *---*---*   *------*---*   *---*---*
  X: | *-+-->| * | *-+-->|KICKED| *-+-->| * |NIL|
     *---*   *-+-*---*   *------*---*   *-+-*---*
               |                          |
               V                          V
             *---*---*   *---*---*      *---*---*   *---*---*
             |THE| *-+-->|MAN|NIL|      | A | *-+-->|DOG|NIL|
             *---*---*   *---*---*      *---*---*   *---*---*

    : [A B] -> X; TL(X) -> Y;

     *---*   *---*---*   *---*---*
  X: | *-+-->| A | *-+-->| B |NIL|
     *---*   *---*---*   *---*---*
                           ^
                           |
     *---*                 |
  Y: | *-+-----------------*
     *---*

    : [A B] -> X; [C D] -> Y; X <> Y -> Z;

     *---*   *---*---*   *---*---*
  X: | *-+-->| A | *-+-->| B |NIL|
     *---*   *---*---*   *---*---*

     *---*   *---*---*   *---*---*
  Y: | *-+-->| C | *-+-->| D |NIL|
     *---*   *---*---*   *---*---*
               ^
               |
               *---------------*
                               |
     *---*   *---*---*   *---*-+-*
  Z: | *-+-->| A | *-+-->| B | * |
     *---*   *---*---*   *---*---*

    : [A B] -> X; [C D] -> Y; Y -> TL(TL(X));

     *---*   *---*---*   *---*---*
  X: | *-+-->| A | *-+-->| B | * |
     *---*   *---*---*   *---*-+-*
                               |
               *---------------*
               |
               V
     *---*   *---*---*   *---*---*
  Y: | *-+-->| C | *-+-->| D |NIL|
     *---*   *---*---*   *---*---*

EXERCISE:
=========

Write a POP-11 program that performs actions on a simulated computer memory.
First of all, the memory can be represented by a large array, eg.

   vars contents;
   newarray([1 1000]) -> contents;

The procedure CONTENTS can be used to either get the value at some particular
address, or to put a value in some particular address. It is slightly
different from the CONTENTS used in earlier examples in this file. Examples
of its use:

   34 -> contents(56);      ;;; Puts 34 into the location at address 56
   contents(56) =>          ;;; Prints out the contents of location 56

Given this basis, implement the following procedures. The word "address" here
refers to a number that is representing a location in the CONTENTS array.
You should try to restrict yourself to only putting numbers into the CONTENTS
array (so start by only representing numbers and lists).

   CONS - given an item and an address, returns the address of a new list
          pair, whose HD is the first argument, and whose TL is the list whose
          address is the second argument. (You may want to include a check
          that it IS the address of a list, or some special address denoting
          []).

   CAR  - given the address of a list, returns the HD of the list. If the HD
          is itself a list, then it should return the address of that list.

   CDR  - similar to CAR, but returning the TL of the list.

Write a short POP-11 program that uses these procedures instead of ::, HD and
TL (examples: reversing a list, seeing whether something is in a list,
"flattening" a list). To see what is going on, you may want to implement the
following extra procedure:

   SHOW - given an address, prints out what is there in a readable form. If
          it is the address of a list, the whole list should be printed out
          (perhaps in the POP-11 syntax).

If you find all this too easy, think about implementing words (or strings) in
this scheme, again restricting yourself to only putting numbers in the
CONTENTS array. Or start thinking about how you would implement a GARBAGE
COLLECTOR.

FURTHER READING
===============

Foster, J.M., "List Processing", MacDonald/Elsevier, 1970.

Winston, P.H. and Horn, B.K.P., "LISP", Addison Wesley, 1981.
(Chapter 9)

Allen, J., "Anatomy of LISP", McGraw Hill, 1978.


See also TEACH BOXES
