🚀 go-pugleaf

In article  <STEPHEN.92Apr17032919@estragon.uchicago.edu> Stephen P Spackman writes:
]In article <1992Apr16.211503.20555@newshost.lanl.gov> jlg@cochiti.lanl.gov (Jim Giles) writes:
]||> [...]                      Anyway, you can drop arrays from your list of
]||> useful primitives.  They're just funtions that return lvalues.
]|
]|...  A physicist dosn't know or _care_ that these concepts are
]|equivalent in the abstract thoughts of computing scientists.  A physicist
]|shouldn't _need_ to know or care about this either.  What he wants is
]|a convenient notation to represent algorithms of interest to him.  This
]|does not mean he wants some minimalist notation which satisfies some
]|esthetic urges of a computing science theorist.
]
]Odd that you say this. C makes a distinction, but as I recall FORTRAN
]traditionally uses the same notation for both...

Of course, it isn't the notation that is the important distinction
between functions-that-return-lvalues and arrays, it is the
algorithmic properties.  Most people think of arrays as something that
guarantees fast constant-time access (though I don't know how many
languages actually guarantee that).  If you want simplicity,
generality, _and_ specifiable algorithmic properties, you could use
something like the C idea of "storage class".  For example, replace
arrays in C with a general type "map" taking declarations like

  type1 name[type2]

which declares name to be a map of type1 -> type2.  As a special case,
an integer n in place of type2 means the set of all integers from 0 to
n.  Now you have

  bool S[int]		/* a set of integers: insert i is S[i] = 1,
			 * delete i is S[i] = 0 */
  symbol T[string]	/* a symbol table (you have to define symbol) */
  unsigned U[type1]	/* a bag of element of type1: insert x is
			 * U[x]++, remove one x is U[x]==0?0:U[x]-- */
  type2 V[unsigned]	/* a list of type2 */
  type3 W[100]		/* an list of type3, indexed from 0 to 99 */

In the above declarations there is no indication of how the type is
implemented, most of them would probably be implemented as hash tables
since there is no given upper bound on the number of elements (except
for W).  If you want to specify an array, you use the storage class
modifier "array" which specifies that the map is to be allocated in
contiguous memory with constant-time access:

  array type3 W[100]

Other modifiers like "packed" apply also:

  packed array bool X[32]

declares X to be a set of integers, restricted to the range 0..31,
allocated in contiguous memory, giving the smallest possible space to
each element.  The implementation on a 32 bit machine should be a
single unsigned int with bit operations.

This sort of mechanism gives the best of both worlds, a minimal number
of semantics concepts for data structures (I hereby declare that
storage class is not a semantic concept, but a pragmatic one),
combined with user-definable implementations.
-- 
					David Gudeman
gudeman@cs.arizona.edu
noao!arizona!gudeman