Poly-dimensional array programming

Abstract

FISh is the first language to support a poly-dimensional, data polymorphic type constructor for regular arrays. Now a fully-typed program may take a vector, matrix or higher-dimensional regular array as argument. Regularity is defined using shape theory, which was also used to guide the language design, e.g. by justifying the exclusion of arrays of functions.

Regularity is enforced by static shape analysis which determines the shape of all arrays during compilation. As well as supporting poly-dimensional programming, it detects all shape errors, a common source of array bound errors. Further, shape analysis supports an aggressive compilation strategy, that compiles FISh programs into simple, efficient C programs.

Thus FISh combines the expressive power of higher-order polymorphic programming with the speed of simple imperative programming. Version~1 is available over the internet.

Key words poly-dimensional arrays, FISh, shape analysis