[Grace-core] Fixed sized lists

[Andrew P. Black]

On 15 Jul 2014, at 10:49, Kim Bruce <kim at cs.pomona.edu> wrote:

> Sorry, I can't remember if I already sent this to the list.  I'm wondering if it makes sense to have a constructor of fixed sized lists.  Many of the examples in my text are of such lists -- e.g., a calendar with days of the week or days of the year, two-dimensional tables of fixed sizes, etc.  It would be easy to set up a constructor that would set up a list with a fixed default value and then not support add operations.  I suspect it's most easily done by coding it directly from PrimitiveArray.
> 
> I'm tempted to implement this myself, though it could be added to Andrew's collections, and we could support both fixed sized arrays and more flexible lists.  Any concerns?
> 
> I think this is a good idea, but I'm interested to hear how others feel about it.

I thought about this for a bit, and decided that it was actually a bad idea.

The trend in programming languages has been to have a few, powerful abstractions rather than a few special-purpose ones.     For example, Python, Ruby and JavaScrip arrays are extensible as well as indexable.  Having a collection object that is both extensible (like a traditional list), and indexable (like a traditional array), feeds right into this.   Indeed, other languages have gone further and combined collections indexable by number with collections indexable by arbitrary key.   For example, Lua has just one container: the Table.

Certainly, some applications won’t need to extend their lists, and others won’t need to insert elements at arbitrary places.  That’s fine; those applications won’t use the methods that do these things, and their programmers won’t have to learn them.   They also won’t bear the overhead of extensions (which, in the current implementation, requires copying).   

Having just one mutable indexable collection interface, whether we call it list or array, simplifies learning. 

It’s true that arrays in C and in Java are fixed-length.   So they were in Algol 60 and Fortran.   But we have learned stuff about how to design more flexible and efficient data structures since then.  Isn’t Grace supposed to be taking advantage of advances in language design over th least 20 years?  We should do the same in our library designs.

Michael also posted some interesting comments (Subject: Indexing, posted on 2nd July) that our lists would be more “object-printed” if they abstracted over the index.   I’m not sure if this makes them more “object printed” or not, but it certainly makes them more abstract, because it hides an implementation detail that is often irrelevant.    Of course, sometimes, as Michael points out, one really does need to calculate an index, for example, when implementing a hash table (which motivates zero-indexing), or when implementing a heap (which motivates one-indexing).    So I would like to explore that direction a bit more.  

Kim, you also mentioned multiple-dimension arrays.   I think that these might be handled by declaring an array whose indexes are pairs rather than simple ranges.   

An alternative would be to have a good old fixed-size 2D matrix type.   Then what Kim is asking for becomes a special case where one dimension is of size 1.   Certainly, anyone who wants this could implement it, along with a rich set of matrix arithmetic operations, using PrimitiveArray.  But I don’t wish to write or promote such a module at this stage.  I think that we have more urger things to concern ourselves with.

On the other hand,  I so think that we should have an immutable sequence objects, primarily so that the variable-arity argument to a method can be one.     I may do this.  But I’m nervous about doing any more work on the compiler until Tim has incorporated the pull request that I made 13 days ago.

	Andrew


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailhost.cecs.pdx.edu/pipermail/grace-core/attachments/20140715/a0491314/attachment.html>