AESOP home


Linearisation: An optimisation for nonlinear functional programs

Peter G. Harrison

Journal Article
Science of Computer Programming
Volume 10
Issue 3
May, 1988
DOI 10.1016/0167-6423(88)90052-4

Functional programming languages have great appeal from the point of view of both software design and amenability to formal reasoning, but to date they have suffered from poor performance when run on conventional computers. A promising solution to this problem may be provided by program transformation and several schemes have been proposed which can give quite impressive optimisations. However, these are at best only semi-automatic, requiring reasoning on behalf of the programmer to assist the transformation process. Part of the problem is that these schemes must take into account not only functions but also the objects to which they are applied in the defining expressions. By reasoning at the function level, the auxiliary domain of objects need not be considered explicitly, and transformations can be derived in terms of identities between functional expressions, rather than via sets of equations satisfied by objects from a certain class.

By expressing functional expressions in variable-free form, we use algebraic methods, based on the functional algebra of the language FP, to transform a certain class of nonlinear functions into linear form. A function in this class generates a reduction graph in the form of a balanced tree when applied to an argument, whereas a linear function generates a single-spine tree and so executes with a number of function calls which is linear in the size of its argument. Thus, for example, tail recursive functions form a small subset of the class of linear functions. Further optimisations include the tupling of functions which are defined by mutal recursion, and we identify conditions under which these are equivalent to a linear function. The compiler is able to detect if the conditions required by these transformation theorems are satisfied, and generate the appropriate optimised functions.

Information from