Thursday, January 25, 2007

Arrays considered harmful

I've come to the conclusion that arrays are bad. They really have no place in a modern programming language and should go the way of the pointer: being considered an implementation detail.

The reason is that lists are just simply better: they are more flexible, allow for a wider variety of implementaion, give the compiler more room to optimise, are easier to type (this is probably the best reason here, consider the grief Java arrays cause to the type system), integrate nicely into an object-oriented model, etc, etc. All that is needed is some syntactic support so they are as easy to use as arrays and allow the compiler to optimise lists to arrays as it sees fit (as far as I'm aware this is fairly easy to do). Of course we can still let systems programmers have arrays just as they have pointers, but 99% of programmers should never use them.

I hope to never have to deal with arrays again (not that I do already), and never have to answer questions about how such and such a feature will work with arrays. If I can type generic collections that should be enough.


Anonymous said...

It seems you just want to be able to take the head and tail of an array.

Arrays and lists are typed in the same way -- even the type syntax is the same (compare int[] to [int]). You have syntax for getting an element from a collection (head vs [42]) and for creating a collection in the first place ([1,2,3] vs {1,2,3}) so the type rules are quite simple for both.

What makes you think lists are easier to optimise than arrays?

I think if you implemented random access with an O(n) trawl through a list, you would make a lot of algorithms very slow, but a common interface (both syntax and typing) to collections I think is a good idea, so long as the programmer can choose the underlying implementation to suit the algorithm or leave it undecided if they don't care. Java tried hard with this but with little or no syntax sugar it's like doing surgery with chainsaws.

Nick Cameron said...

I'm really bloggin about arrays/lists in Java-like languages, not functional ones. Here, the syntax is different, a[4] vs l.get(4), and there is no syntax for creating a list in the same was as an array (eg new int[]{1, 2, 3}). The typing differences are that arrays a re covariant and thus require a runtime check (ie the typing is broken) whereas with lists the variance can be specified by the programmer.

Lists are not necessarily easier to optimise but they do leave the implementation open. Arrays specify an implementation. A compiler could choose that implementation for a list if it wanted, or it could choose a different one (say linked list) if that would be more efficent.

I agree that Java needs the syntax sugar, my point is that if it had enough syntax sugar then you could abandon arrays altogether!