🚀 go-pugleaf

In article <21@euteal.UUCP> mart@euteal.UUCP (Mart van Stiphout) writes:
>[...]
>In a reply to one of my critics, I suggested some more support in
>high level programming languages for list processing.
>Some other replyer suggested me to use Lisp.
>Well, I don't want to use Lisp but I have some ideas on
>list and I would like to know what other people think of them.

I do not know why you don't want to use Lisp, but it has the data
abstractions you want to use (the flexible arrays you described below).

>My main point is: I REALLY HATE LISTS.
>[...]
>1. [Lists use pointers]
>2. [Lists require allocation of memory]
>3. [Pointer manipulations are error prone]
>4. [Accessing the nth element takes n units of time]

The only thing I can say is: use a nicer language. Lisp, for example,
hides the use of pointers, so that unless you are Joe Lisp Programmer,
you are not going to be worried about pointers or pointer manipulations.
Allocation is easy and convenient. Accessing the nth element is not
something normally done with lists. 

>
>What I really like are arrays. They have numerous advantages:
>1. they can be processed easily.
>2. elements can be accessed randomly in a cheap manner.
>3. you don't have to mess around with pointers.
>4. you don't have to allocate memory.

You don't mention the primary disadvantage of arrays: they are
second class data structures: you cannot return them as the result
of a function in most languages. You cannot write a function in
Pascal which allocates and returns an array for use (without using
Pascal's lists). A lot of the things you hate about lists are caused
by the fact that they are first class citizens (you can return a
pointer to a list).

>
>The main disadvantage I can think of is the often unknown array
>length. [...]
>I hereby propose to do away with linear linked lists.
>[...]
>Mart van Stiphout
>Email: mart@euteal.eutrc3.hp4nl.mcvax.uucp

A list is a data structure which is easy to change the size of. An array
is a data structure which it is easy to access the nth element. Both of
these data structures are easy to implement and easy to use (especially
if you use Lisp's lists). What you are suggesting has the 'best' features
of both. It also has the costs of both.

Where a normal array reference takes a couple of instructions: an index
computation and a load, what you are suggesting takes much more. First you
must determine if the array index is in bounds. Second, if it isn't you must
reallocate, which requires copying or rehashing (or slower lookups). Then
lookup may be slower, depending on your method of storing arrays. Even
hashing is many times slower than the index computation and load.

List performance is also degraded if a list is implemented as a `dynamic'
array. Lists are (almost) always processed sequentially, this is even
faster than an array reference: load indirect from a pointer.

Many problems are better thought of as `list' problems than `array'
problems: reversing the order of a list is 'easier' than reversing
the order of an array (you reverse the pointers instead of copying the
elements), or appending two lists (this just requires a single pointer
change). Dynamic arrays would eliminate these benefits of using lists.

I do not think the `dynamic' arrays you like are a bad idea, but I do
think getting rid of lists in favor of them is bad since that incurs
a very large performance penalty.

John
gateley@tilde.csc.ti.com