Re: [Haskell-cafe] Specify array or list size?

At 9:36 AM -0700 2005/5/7, Fergus Henderson wrote:

On 07-May-2005, Hamilton Richards wrote:

...

As far as I know, the last programming language that included arrays' sizes in their types was Standard Pascal,

There have been many such languages since Standard Pascal. For example C, C++, C#, Java, Ada, VHDL, and NU-Prolog.

Well, perhaps we're using the terminology in somewhat different ways. When I say that Standard Pascal includes arrays' sizes in their type, I mean that in Pascal these two arrays: X : array [1..50] of integer; Y : array [1..100] of integer; belong to different types. If I define two procedures procedure P( a : array [1..50] of integer ) procedure Q( a : array [1..100] of integer ) then the calls P( X ) Q( Y ) are valid, but P( Y ) Q( X ) are invalid. That's not the case in C, C++, Java, or Ada. In C and C++, for example, given two arrays int X[50]; int Y[100]; and a function declared as void P( int a[] ) then these calls P( X ) P( Y ) are both valid, because the sizes of X and Y are not part of their type.

...

and it turned out to be an unmitigated disaster. Because array parameters were typed with their sizes, a procedure for searching arrays of size 100 could not be used for arrays of any other size. Every useful (non-Standard) dialect of Pascal provided a way around that restriction, as did Pascal's successor, Modula-2, and as far as I know the mistake has not been repeated.

The disaster was the lack of polymorphism in Pascal's type system, not making array sizes part of their types.

Polymorphism would certainly have improved Pascal's type system, but that's a far bigger leap than simply separating arrays' sizes from their types (as was done in Modula-2).

The languages above all have some means of writing a procedure that works for different sized arrays, whether it be using pointers (in C), templates (in C++), unconstrained array parameters (in Ada and VHDL), or inheritence (in C# and Java).

As my C/C++ example above shows, in those languages at least, no such special "means" is necessary. In C and C++, there's not even any way for a function to discover the size of an array argument. This is the opposite extreme from Pascal, where the size is determined by the parameter type. Between these extremes is Modula-2, which allows array arguments of any size to be bound to an "open" array parameter, but provides a primitive function HIGH which, applied to an array parameter, returns the size of the argument to which it is bound.

Another example of a programming language for which array lengths are part of their type is Cryptol . Cryptol was designed by Galois Connections, the company that I work for, starting about five years ago (i.e. before I joined Galois). It is notable in this context because it was designed by expert functional programmers who were very familiar with Haskell, and who had indeed participated in the design and implementation of Haskell. They chose to include array sizes in the type system, despite the resulting increase in the complexity of the type system, because array sizes are often important for the domain of cryptography -- as the original poster noticed!

Thanks for the pointer-- I had not encountered Cryptol. Looks quite interesting, and I can readily see how making the size of a sequence part of its type can be useful. But it's one thing to make this a feature of a language specific to a domain in which it is useful, or to provide ways to define size-specific array types in a language such as C++, and quite something else to make size-typed arrays the only array types in what was intended to be a general-purpose programming language. That, I still maintain, was a mistake. Cheers, --Ham -- ------------------------------------------------------------------ Hamilton Richards, PhD Department of Computer Sciences Senior Lecturer The University of Texas at Austin 512-471-9525 1 University Station C0500 Taylor Hall 5.138 Austin, Texas 78712-0233 ham@cs.utexas.edu hrichrds@swbell.net http://www.cs.utexas.edu/users/ham/richards ------------------------------------------------------------------