Re: LOGO-L> eliminating items randomly from a list

[Brian Harvey <bh@CS.Berkeley.EDU>]

> What is the difference between a list and an array?

There are two ways to answer this question: technical and psychological.
Let me start with the technical answer.

An array is a preallocated, contiguous block of computer memory.
In other words, you decide ahead of time that you need exactly 43
elements in the array, and you ask the operating system to find you
a block of size 43 (of whatever you're going to put into the array;
in Logo this would be 43 pointers to arbitrary data structures).
Because the block is contiguous, if you know the location in memory
of the beginning of the array, you can quickly compute the location
of, say, element number 26: it's START+25 (measured in units of
however big an element is, and assuming that the first element is
called number 1 rather than number 0).

Because it's quick to find elements anywhere in the array, arrays are
really fast for applications that involve jumping around, e.g., sorting.
On the other hand, if you later learn that you need 44 elements, you
can't just expand the array, because arrays must be contiguous and
maybe you're already using the next slot in memory for something else.
Rather, you must allocate a new block of size 44, and copy the 43 old
elements into it.  For this reason, array-based programs in the real
world generally try to allocate "more space than anyone could possibly
need" and then two or three years later the program crashes because
someone does need more space.

A list is allocated one element at a time.  For each element, you
allocate a small block of memory containing a pointer to the element
itself and a pointer to the rest of the list.  (These two pointers
are the FIRST and the BUTFIRST of the list.)  If you need another
element, you don't have to copy the old elements, but merely allocate
one new block (called a "pair") to point to the new element and what
used to be the head of the list.  (This operation is FPUT).

Lists are really slow for jumping-around applications because, to
find element 26, you must track down 25 BUTFIRST pointers.  There's
no way to compute the location of that element directly.  On
the other hand, lists are really fast for applications in which you
must insert new elements, especially if you want to insert in the
middle somewhere, because you can "splice" the pointers instead of
having to copy the later elements to make room.

Both arrays and lists have been around forever, and will be around
forever, because each data structure makes some things fast and
other things slow.  In the real world, programmers tend to favor
arrays because traditional programming languages make it easier to
use arrays than to use lists.  The most obvious difference between
symbolic languages such as LISP and LOGO and traditional ones is
that symbolic languages make it easy to talk about lists.

Addendum: In recent years there has been a new technical advantage
to arrays.  Modern computers include cache memory, which allows a
big speedup for programs with "locality of reference," which means
that you tend to use things near each other.  That's automatically
true for arrays, but not necessarily for lists.

End of technical discussion; beginning of psychological one:

In an array, everything revolves around the numeric position of
a given element.  Array programs are full of FOR I = 1 to N ...
sorts of things.  This is not terrible, but it's also not the way
people ordinarily think about problems.  Lists seem to fit better
with two different program styles: the recursive style using
FIRST, BUTFIRST, SENTENCE, etc,. and the higher order function
using MAP, FILTER, etc.  By using lists, we avoid entirely having
to guess how big the data will be, because there is no preallocation.

Another point is that dynamic construction of a result means that
we never have to program a *change* in the value of an existing
element.  With arrays, we must first allocate the result array,
and only then can we assign new values to the elements of that array.
With a typical list program, the construction and the assigning of
values happens at the same time.  This no-changing style is called
"functional programming."  It is *not* more natural to most people,
although it does seem more natural to mathematicians, but it's a very
strong technique for writing well-organized programs with fewer bugs.

Early versions of Logo had both arrays and lists, and so do current
versions such as UCBLogo.  In between, there was the tiny-computer
era, in which some things had to be left out.  The decision was to
keep lists and drop arrays, because it's easy enough to treat a list
like an array if that's what you want.  (ITEM is an array-like
selector for lists.)  The program may be slower than with primitive
arrays, but it'll look similar.  By contrast, if you wanted lists,
it's very hard to simulate them using arrays, at any speed.

In particular, Logo was designed around the problem of generating
English sentences, and that's a natural for lists.  Think about
writing the standard sort of program with procedures named NOUNPHRASE
and so on, using an array-based language!  It can be done, of course,
but it'll be messier.

Does this mean lists are "better"?  No, not if, for example, you're a
physicist doing transformations on 100-by-100 matrices.  It's easy to
represent a matrix as a list of lists, but the program will be slower,
probably, than an array-based program.  But it probably does mean
that lists are better for kids; the design decision in Logo was that
kids are more likely to want to perform list-appropriate computations
than array-appropriate ones.

---------------------------------------------------------------
Please post messages to the Logo forum to logo-l@gsn.org.  Mail
questions about the list administration to logofdn@gsn.org.  To
unsubscribe send    unsubscribe logo-l    to majordomo@gsn.org.