One of the most common uses of computers is to organize and operate on large amounts of information. Thus, deciding how information will be stored and retrieved is a very important part of writing computer programs. This lesson deals with lists, which are one of the most basic ways of storing information.

We have already encountered lists in our programming. The PRINT command requires that its argument be a list. The REPEAT, IF and IFELSE commands require lists of instructions as their arguments.

You can create a list in LOGO simply by enclosing its elements in square brackets ([]) or by using the LIST command. Here are two very simple examples of lists:

[The quick brown fox jumped over the lazy dog.]
(LIST 1 2 3 4 5)

PRINT [1 2 3 4 5]


NOTE: the LIST command evaluates its arguments before putting
them in a list; compare the output of the following two commands.
PRINT (LIST (SQRT 4) (SQRT 9)) PRINT [(SQRT 4) (SQRT 9)]




A good example of programming with lists is Jenny's Madlib program in
chapter 9 of the text.  This is a fairly complicated exercise in text
processing; we'll start with a much simpler (and more boring)
example.


The FIRST command takes a list as its argument and outputs
the first (leftmost) thing in a list.  The BUTFIRST command
(abbreviated BF) takes a list as its argument and outputs
everything but the first element of the list.  Take a few seconds to
try out these commands.


The EMPTY? predicate takes a list as its argument and outputs
true if the list is empty and false otherwise.  The
empty list is represented by [].
PRINT EMPTY? [1 2 3 4 5]
PRINT EMPTY? []

The FPUT command adds an element to a list:
PRINT FPUT "Once [the quick brown fox jumped over the lazy dog.]
PRINT FPUT 0 [1 2 3 4 5]


We can combine these three commands to write a recursive procedure that
reverses the order of the words in a sentence.
TO PRINTREVERSE :SENTENCE
  PRINT RECURSIVEREVERSE :SENTENCE []
END

TO RECURSIVEREVERSE :SENTENCE :REVERSED
  IFELSE NOT (EMPTY? :SENTENCE) ~
    [OUTPUT RECURSIVEREVERSE ~
       (BUTFIRST :SENTENCE) (FPUT (FIRST :SENTENCE) :REVERSED)] ~
    [OUTPUT :REVERSED]
END


Once you have run the PRINTREVERSE procedure a few times
(e.g. PRINTREVERSE [the quick brown fox jumped over the lazy
dog]), try walking through it step by step.  What commands does
the computer execute when running this procedure?  What does each
procedure output when it's finished running?


When you feel you understand how this program uses FIRST,
BUTFIRST and EMPTY?, there are a few other things
you should look at in the program.  First, it is interesting to note
that arguments whose values are lists are handled very much like other
arguments in LOGO.


Second, notice how the PRINTREVERSE procedure does little
more than run the RECURSIVEREVERSE procedure.  All the hard
work is done in RECURSIVEREVERSE; PRINTREVERSE was
just written to print the output and to provide the empty list as an
argument to RECURSIVEREVERSE.


On its final iteration, RECURSIVEREVERSE outputs the reversed
sentence.  This output is then passed up through all levels of
recursion until, at the very end, RECURSIVEREVERSE outputs
the reversed sentence to PRINTREVERSE.




LAST and BUTLAST are very similar to FIRST
and BUTFIRST.  Experiment with them to discover what they do,
then write a LOGO program PRINTSENTENCE that prints the
result of combining two lists.  Your program may be similar to
PRINTREVERSE above.




With some difficulty, we have defined LOGO commands to reverse a list
and to combine two lists.  In fact, UCB LOGO has built in commands
REVERSE and SENTENCE that already do this; these two
operations on lists are so important that the designers of UCB LOGO
built them into their language.  Our experience here gives us an idea
of the sorts of things programmers do when writing the code that runs
LOGO.


Mtht420