Static Shape Analysis

Shape analysis is used to determine the number of dimensions, and the size in each dimension, of every array appearing in a program. (A program is a closed term of array or command type.) In particular, it checks that every array is regular, i.e. is a hyper-cube whose entries all have the same shape. The latter requirement is necessary to ensure that every entry in a vector of vectors has the same length, i.e. that a vector of vectors is a matrix. As well as detecting irregularities, it is able to detect all other shape errors, such as multiplying matrices of innapropriate sizes, or having incompatible numbers of dimensions. It is the power of shape analysis that makes poly-dimensional programming feasible.

Knowledge of the shapes can be used to improve memory management during compilation of the resulting imperative program. In particular, FISh supports a clear stack discipline, and so does not require a garbage collector. The existing FISh compiler translates programs in to simple C code, which is then compiled and executed in the usual way. This approach is also being applied in the design and implementation of a parallel version of FISh, called GoldFISh.