© 1988 by British Computer Society
Algebraic Transformation Techniques for Functional Languages
Department of Computing, Imperial College of Science and Technology, 180 Queen's Gate, London SW7 2BZ, UK
The often conflicting needs to make software both efficient and correct have made a large contribution to the present so-called software crisis, and transformation-based support environments for functional languages offer a major step towards solving this conflict in requirements. In such an environment programs are initially developed by concentrating only on the understandability, correctness, clarity, reliability and maintenance aspects. This initial specification is then transformed through a series of meaning-preserving transformations to achieve an efficient implementation. We argue that the abstraction level of the majority of commonly used functional languages is too low-level for the results of the analysis to be automatically implemented or very generally applicable. However, by compiling such programs into a higher-level, more structured, variable-free representation, we show how the analysis can achieve more powerful, mechanised, and generally applicable transformations. This is due in part to the elimination of the concern for the domain of objects, since function definitions are now expressed purely in terms of functions and so become simpler.
Many recursive functions are linear in the sense that the number of recursive function calls they generate is bounded by a number which is proportional to the magnitude of their argument. The performance of functional languages can therefore be improved by a more efficient implementation of linear functions, and we derive equivalent imperative language loops for a large class of linear recursive functions. Moreover, such linear functions can be detected automatically in the parsing phase of a compiler and their loop implementations generated. Other recursive functions are non-linear, generating a number of function calls that grows in a non-linear manner with respect to the magnitude of the arguments to which they are applied, for example quadratically or exponentially. Although non-linear functions tend to be fewer, their run-time performance tends to be relatively much poorer, and so their efficient implementation too is of considerable importance to functional languages. We illustrate how certain non-linear function definitions can be transformed into linear ones, and how they can therefore subsequently be implemented as loops. An alternative, more automatic approach for the treatment of non-linear functions uses memo-functions, which are functions that ‘remember’ all the arguments to which they have been applied, together with the corresponding results computed from them. We define a class of non-linear functions for which memorisation linearises the time-cost of calls of a non-linear function to itself whilst executing in bounded space. The technique for generating such memo-functions is widely applicable, easily mechanised and achieves improvements in efficiency that are comparable with existing program transformation schemes. Furthermore, the sizes of the tables for these memo-functions are guaranteed not to exceed a compile-time constant found by a simple static analysis of the definition of the non-linear function.
Received May 1987.
* Department of Computing, Imperial College of Science and Technology, 180 Queen's Gate, London SW7 2BZ