[Haskell-cafe] Specify array or list size?

[Hamilton Richards]

At 9:36 AM -0700 2005/5/7, Fergus Henderson wrote:
>On 07-May-2005, Hamilton Richards <ham at cs.utexas.edu> 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 <www.cryptol.net>.  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 at cs.utexas.edu                hrichrds at swbell.net
http://www.cs.utexas.edu/users/ham/richards
------------------------------------------------------------------