[Haskell-cafe] Specify array or list size?

Fergus Henderson fjh007 at galois.com
Sat May 7 12:36:13 EDT 2005


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.

> 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.

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).

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!

-- 
Fergus J. Henderson                 |  "I have always known that the pursuit
Galois Connections, Inc.            |  of excellence is a lethal habit"
Phone: +1 503 626 6616              |     -- the last words of T. S. Garp.


More information about the Haskell-Cafe mailing list