Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!nrl-cmf!ames!pasteur!ucbvax!decwrl!sun!pitstop!sundc!seismo!uunet!mcvax!hp4nl!eutrc3!euteal!mart
From: mart@euteal.UUCP (Mart van Stiphout)
Newsgroups: comp.lang.misc
Subject: flexible arrays
Keywords: programming languages, flexible arrays.
Message-ID: <21@euteal.UUCP>
Date: 30 Jan 89 17:57:07 GMT
Organization: Eindhoven University of Technology, The Netherlands
Lines: 58


Some time ago I initiated a discussion on the Turing Language syntax,
mainly the loops and list parts.
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.

My main point is: I REALLY HATE LISTS.
There are several reasons why I hate lists (and then I mean
lists I can use in languages like Pascal, Modula or C; not Lisp):

1. the use of lists requires me to create structures with pointers
   to the next structure (record) of the same type and I think
   this is a rather trivial action that I don't wish to repeate
   for every list I create.
2. I have to allocate memory (new, malloc) for every new list element.
   How tedious.
3. Adding, deleting or doing anything else than processing the entire
   list leads to error prone pointer manipulations that I don't want to
   use.
4. accessing elements in the list is costly because I have to scan
   the entire list until I find the element I want.

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.

The main disadvantage I can think of is the often unknown array
length.  Oh yes, and some dumm languages
(Pascal) don't allow me to dynamically allocate arrays.
The C programming language provides me with realloc to lengthen
arrays if necessary.

I hereby propose to do away with linear linked lists.
Instead we should use flexible arrays or sparse arrays.
A sparse array can be thought of as a linked list but not implemented
as one.
The only thing I have to do is to declare a flexible array.
The system does:
1. allocation of new array elements as soon as I refer to a non-existing
   one.
2. efficient storage of the used array elements: for example by some kind
   of dynamic hashing technique.

The result could be something like the arrays you can use in the
AWK programming language. These are very flexible and easy to use.
The advantages are: no messing around with pointers, no memory
trouble, easy acessing, easier to read programs
and all this at the cost of (I think) a reasonable amount op cpu time.

Please post yout comments,

Mart van Stiphout
Email: mart@euteal.eutrc3.hp4nl.mcvax.uucp