LOGO-L> Lists and Arrays - Further Reading

[Yehuda Katz <yehuka@beitberl.ac.il>]

Brian Harvey wrote:
> 
> > 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.

Hello,

You might want to read an article covering the same topics (and more)
in: Learning Mathematics and Logo, ed. Celia Hoyles and Richard Noss,
MIT Press, 1992. On page 393 there is an article named Avoiding
Recursion by Brian Harvey. This article, as well as the others, is very
intersting and well written IMO.

Regards...

[[Yehuda]]


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