[apologies for multiple announcements] *********************************** * Functional = Imperative + Shape * *********************************** FISh is a new array programming language that combines (and extends) the EXPRESSIVE POWER of functional programming with the EFFICIENT EXECUTION of imperative, or procedural, programming by performing STATIC SHAPE ANALYSIS on all programs. This shape computation reduces higher-order functional programs to simple imperative forms, i.e. F - Sh = I. Conversely, FISh works best when functions are constructed from imperative procedures and shape functions, as recommended by the slogan that gives the language its name. F = I + Sh FISh execution speeds on typical array problems are SEVERAL TIMES FASTER than other higher-order, polymorphic languages. This announcement, research papers, reference material and the implementation are all available from http://linus.socs.uts.edu.au/~cbj/FISh/announcement.html The main themes are introduced in the paragraphs below. Barry Jay http://linus.socs.uts.edu.au/~cbj *********************************** Expressive Power ~~~~~~~~~~~~~~~~ FISh supports - the usual functional features such as strong typing, higher-order functions and parametric polymorphism. It also supports - simple imperative features such as assignment, for- and while-loops, and local variables, using a type of commands. Procedures are represented as functions into commands, as in Algol-like languages. Unlike existing Algol-like languages, it also supports data types of arrays, so that array programs may be polymorphic in the size of the array. Now this has been extended to support - poly-dimensional array programming. If a is any array type then [a] is the type of all arrays with entries in a that are - finite dimensional, and - regular, such as vectors, matrices, three-dimensional arrays, etc. Thus, poly-dimensional array programs can be written that act on a vector, matrix, or higher-dimensional array. For example, the standard prelude supports a polymorphic constant map : (a -> b) -> [a] -> [b] which will map a function over a vector, matrix, or higher-dimensional array. Note that a matrix of integers, or type [int] has a different type from a vector of vectors of type [[int]]. Thus, given sum_int : [int] -> int which adds up an array of integers, we have map sum_int : [[int]] -> [int] which will sum each entry of the outer array. This is useful when - representing complex numbers as arrays of length 2, or - each entry in an array has an associated array of data, e.g. - each entry is given an array of nearest neighbours, or - decomposing an array into an array of blocks, e.g. - a matrix into a matrix of matrices. Efficiency ~~~~~~~~~~ ------------------------------------------------------------- | |Map Reduce Q'sort FFT MM-loops MM-ip | |_______________|____________________________________________| |---------------|--------------------------------------------| |FISh |1.04 0.37 1.93 3.57 4.36 7.05 | |---------------|--------------------------------------------| |Ocaml(in-lined)|4.00 2.66 3.53 | |---------------|--------------------------------------------| |Ocaml |5.99 4.59 15.47 8.16 7.71 60.61 | |---------------|--------------------------------------------| |speedup |5.8 12.4 8.0 2.3 1.8 8.6 | -------------------------------------------------------------- Benchmark user times See http://linus.socs.uts.edu.au/~cbj/FISh/Benchmarks for more details. 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. F = I + Sh ~~~~~~~~~~ The slogan is represented within the standard prelude by a function proc2fun : (var a -> var b -> comm) -> (#b -> #a) -> b -> a for converting procedures (and shapes) to functions. proc2fun pr sh x uses the shape function sh and the shape #x of the array x to determine the shape of the result. It then creates a local variable y of this shape, and invokes the procedure pr on and a stored value of x, finally returning the value of y. Semantics ~~~~~~~~~ Shape analysis is supported by a clean and powerful categorical semantics, in which the shape-data (or shape-entry) decomposition is represented by a pullback. For multi-dimensional arrays, this is entries [a] ---------> List a | | | |___| | shape | | map # | | \/ \/ List N x #a -----> List #a c where c takes the list of numbers ns and the a-shape sh and produces a list of length given by the product of ns whose entries are all sh. In other words, all entries of an array must have the same shape. Poly-dimensionality ~~~~~~~~~~~~~~~~~~~ FISh supports the usual Hindley-Milner style of polymorphism. It also supports polymorphism in array sizes (unlike earlier Algol-like languages) and in the number of dimensions of an array. That is, FISh supports polydimensional programming. For example, the map function is defined to have type map : (a -> b) -> [a] -> [b] and so may act on a vector, matrix or higher-dimensional array. However, the existence of the simple imperative features means that this can be compiled into a sequence of nested for-loops corresponding to the number of dimensions of the array argument. Polydimensionality is a form of *shape polymorphism*. Array Programming ~~~~~~~~~~~~~~~~~ Poly-dimensionality means that many array programs, e.g. numerical recipes, can be written for any number of dimensions while maintaining static type and shape checking. For example, FISh supports poly-dimensional stencilling and a poly-dimensional difference equation solver (see Sample Programs). Parallel Programming ~~~~~~~~~~~~~~~~~~~~ Size and shape are important parameters in estimating the cost of alternative parallel implementations. FISh has been designed to support a parallel variant, called GoldFISh, currently under development. GoldFISh will support additional parallel combinators for some of the existing FISh functions that express the usual second-order constants and also the usual array distributions (see Sample Programs). ***********************************