[kepler-dev] Re: zero-length arrays

[Tobin Fricke]

On Wed, 11 Aug 2004, Shawn Bowers wrote:

> Isn't this last point just an implementation detail? Ultimately, a list
> is the "abstract" data structure, and array is just a common programming
> language implementation for a list-like structure.  The more general
> construct is really "collection" for which bags (mult-sets), sets, and
> lists are specific types of collections.

That's completely true.  But the underlying implementation determines the
efficiency of operations on the structure, and therefore the algorithms
that you'll choose to use.

Java strings are sort of "array-like" in that, to concatenate two strings,
you have to make a new string of the desired length and copy the original
strings into that.  If you want to concatenate a large number of strings,
it takes an incredibly long time, since all these intermediate copies are
floating around.  Try this:

	sum( map( function(x:int)(x.toString), [1:1:10000].toArray ) )

It takes about a minute (!) to execute in the stock Ptolemy.  I added
special code to handle the case of sum({string}) by using a StringBuffer
to accumulate the intermediate results (a "list-like" implementation), and
the execution time was reduced to approximately one second.

Having an 'ordered collection' data type where appending is expensive
makes a lot of things difficult, notably just about any lisp idiom.  But
it's possible that the right avenue IS just to create a decent set of
built-in primitives, so that these expensive implementations are not
necessary, and therefore avoid language creep.

> Also, it isn't clear to me that an empty record is a useful structure,
> whereas I definately see how an empty array (or more specifically an empty
> list) is useful.

That's a good point.  But I don't think we'd want to rule out empty
records entirely... who knows when they might be useful?  (Also, the empty
record is a good type signature of "a record of some kind.")

But it seems that Ptolemy allows empty records: intersect({foo=0},{bar=0}) !

Also seems like a good reason to allow empty records.

Tobin