# Shape theory: FISh implementation

Barry Jay School of Computing Sciences University of Technology, Sydney 4pm Tuesday 24 August 1999 Room 2511, JCMB, King's Buildings

Shape theory supports abstraction over the structures used to hold data, based on new denotational concepts. This results in increased expressive power, improved error detection, and faster execution than is usually possible with higher-order, polymorphic, strongly-typed languages.

Functorial ML supports a polytypic programming style by adding a new kind of (categorical) *functors* to the core of ML. An example is

map_2 : (X0 -> Y0) -> (X1 -> Y1) -> F(X0,X1) -> F(Y0,Y1)

where F is a functor variable, and the Xs and Ys are type variables. A single, parametrically polymorphic algorithm supports all of the mapping constants.

FISh (version 1) is an array programming language in which functional programs are reduced to imperative programs through shape analysis (F = I+Sh). That is, the number of dimensions and size in each dimension of each array is determined statically, and used to specialise programs. For example, the type of its map function is

map : (a -> b) -> [a] -> [b]

where X and Y may be lists, trees, arrays, quad-trees of matrices or tuples of these (for functors of several variables).

John LongleyTuesday 7 September 1999