Lists are often used as ``glue'' to connect separate parts of a program together. We propose an automatic technique for improving the efficiency of such programs, by removing many of these intermediate lists, based on a single, simple, local transformation. We have implemented the method in the Glasgow Haskell compiler.

Many compilers do some of their work by means of correctness-preserving, and hopefully performance-improving, program transformations. The Glasgow Haskell Compiler (GHC) takes this idea of ``compilation by transformation'' as its war-cry, trying to express as much as possible of the compilation process in the form of program transformations.

This paper reports on our practical experience of the transformational approach to compilation, in the context of a substantial compiler.

Virtually every compiler performs transformations on the program it is compiling in an attempt to improve efficiency. Despite their importance, however, there have been few systematic attempts to categorise such transformations and measure their impact.

In this paper we describe a particular group of transformations --- the "let-floating" transformations --- and give detailed measurements of their effect in an optimising compiler for the non-strict functional language Haskell. Let-floating has not received much attention in the past, but our measurements show that it is an important group of transformations, offering a reduction of more than 30% in heap allocation and 15% in execution time.

Sixth Conference on Functional Programming Languages and Computer Architecture, Copenhagen, pp 233-242, June 1993.

A normalization algorithm which automatically calculates improvements to programs expressed in a language based upon folds is described. It reduces programs, expressed using fold as the exclusive control operator, to a canonical form. Based upon a generic {\em promotion theorem}, the algorithm is facilitated by the explicit structure of fold programs rather than using an analysis phase to search for implicit structure. Canonical programs are minimal in the sense that they contain the fewest number of fold operations. Because of this property, the normalization algorithm has important applications in program transformation, optimization, and theorem proving.

In addition a generic promotion theorem is identified for each of the other operators. It is hoped that these theorems can be the basis of normalization algorithms for the other operators as well.

Oregon Graduate Institute Technical Report 96-001.

Herein a graphical tool HOPS for the manipulation of directed acyclic term graphs DAGs is described. Programming in a truly functional style is facilitated by the provision of immediate user interaction with functional program DAGs, a novel approach to generic data type construction and a powerful and flexible transformation system. Conceptual decisions in the design of language and system and the way they influence the programmer are outlined.

In understanding complex algorithms, the notions of encapsulation and modularization have played a key role. An algorithm is broken into several parts or modules, and understanding of each part is independent of others. In addition, each part contains details that are not needed by other parts and so can be hidden from them. Programming languages provide support for encapsulation and modularization in many different forms. Early programming languages provided the procedure and function as a means for modularization. Later, files were introduced as a means of modularizing programs. More sophisticated mechanisms were then introduced, like modules, packages, structures, and classes. In all these cases, the interface to a module remained the procedure or function call. Programs that use such modules contain calls to functions and procedures for communicating with a module. Ideally, using the operations that are provided by a module should be done in exactly the same way as using operations that are provided by modules should be easy to intermix. In addition, substituting one module for another that has the same functionality but different implementation should involve a minimal amount of effort. Recently, a new programming language, Polya, has been designed, which attempts to support modularization and at the same time incorporate the operations that are provided by the modules in the programming language itself. This is done by a sophisticated type-definition facility and a mechanism for transforming programs at the source-program level. This thesis studies mechanisms for program transformation at the source program level, in the context of Polya. Program transformation is based on a set of transformation rules that prescribe how a part of a program is to be transformed, and a set of directives that prescribe which program variables are to be transformed. We first give an algorithm for processing program transformations as described by the transform construct. The algorithm constructs a coordinate transformation of an abstract program based on a set of transforms and transform directives for transforming program variables. We then study the problem of transforming expressions that have compound types. Both the type constructor and the component expressions of the original expression may be transformed. No extra rules need be added to the bodies of transforms that transform the type constructor and the component expressions. In the sequel we investigate the problem of transforming procedures and functions that have parameters that need to be transformed. Finally, the problem of transforming program-transformation rules is studied. The program transformation techniques are applied to two well-known algorithms. The algorithms are source programs, which are subsequently transformed to programs of conventional programming languages, and then compiled and run.

In [Lisper93] some results were proved regarding properties of unfolding of purely functional programs. Especially, a theorem was shown that relates the termination of symbolic evaluation of a "less instantiated" term relative to the termination of a "more instantiated" term. An application is partial evaluation, where unfolding of function definitions is frequently performed to enable further simplifications of the resulting specialized program. The unfolding must then be kept under control to ensure that the partial evaluation terminates. In this paper, we extend the termination result from purely functional programs programs with nondeterministic operations. We give an operational semantics where the behaviour of operators is defined through rewrite rules: nondeterminism then occurs when the resulting term rewriting system is non confluent. For the confluent part, the previous termination results carry over. It is, however, not guaranteed in general that the resulting unfolded program has the same semantics as the original program. We give conditions on the rewrite rules that guarantee that both versions have the same semantics, and we show that they apply to a nontrivial class of nondeterministic languages.

We study systems where deterministic computations take place in environments which may behave nondeterministically. We give a simple formalization by unions of abstract reduction systems, on which various semantics can be based in a straightforward manner. We then prove that under a simple condition on the reduction systems, the following holds, reduction strategies which are cofinal for the deterministic reduction system will implement the semantics for the combined system, provided the environment behaves in a "fair" manner, and certain program transformations, such as folding and unfolding, will preserve the semantics. An application is evaluation strategies and program transformations for concurrent languages.

Using concepts from denotational semantics, we have produced a very simple compiler that can be used to compile standard programming languages and produces object code as efficient as that of production compil ers. The compiler is based entirely on source-to-source transformations performed on programs that have been translated into an intermediate language resembling the lambda calculus. The output of the compiler, while still in the intermediate language, can be trivially translated into machine code for the target machine. The com pilation by transformation strategy is simple, the goal is to remove any dependencies on the intermediate lan guage semantics that the target machine cannot imple ment directly. Front-ends have been written for Pascal, BASIC, and Scheme and the compiler produces code for the MC68020 microprocessor.

Tupling is a well-known transformation tactic to obtain new efficient recursive functions without multiple traversals over common data structure, which is achieved by grouping some recursive functions into a tuple. The major difficulty in tupling transformation is to find what functions are to be tupled and how to transform the tupled function into an efficient one. Previous approach to tupling transformation is essentially based on fold/unfold transformation. Though general, this approach suffers from the high cost of keeping track of function calls to avoid infinite unfolding, which prevent it from being used in a practical compiler of functional languages.
To remedy this situation, we propose a new approach based on the theory of constructive algorithmics, in which a more practical tupling calculation algorithm is proposed showing how to expose recursive structures in recursive definitions and how this structural information can be explored for calculating out efficient programs by means of tupling. Being less general, our new tupling calculation algorithm can be successfully used to eliminate most of multiple data traversals and and can be easily implemented.

Fusion, one of the most useful transformation tactics for deriving efficient programs, is the process whereby separate pieces of programs are fused into a single one, leading to an efficient program with no intermediate data structures produced. In this paper, we report our on-going investigation on the design and implementation of an automatic transformation system \hc which performs fusion transformation in a more systematic and more general way than any other systems. The distinguished point of our system is its calculational feature based on simple application of transformation laws rather than traditional search-based transformation.

Program fusion is a well-known transformation whereby compositions of several pieces of code are fused into a single one, resulting in an efficient functional program without intermediate data structures. Recent work has made it clear that fusion transformation is especially successful if recursions are expressed in terms of hylomorphisms. The point of this success is that fusion transformation proceeds merely based on a simple but effective rule called Acid Rain Theorem. However, there remains a problem. The Acid Rain Theorem can only handle hylomorphisms inducting over a single data structure. For hylomorphisms, like zip, which induct over multiple data structures, it will leave some of the data structures remained which should be removed. In this paper, we extend the Acid Rain Theorem so that it can deal with such hylomorphisms, enabling more intermediate data structures to be eliminated.

In functional programming, small programs are often glued together to construct a complex program. Program fusion is an optimizing process whereby these small programs are fused into a single one and intermediate data structures are removed. Recent work has made it clear that this process is especially successful if the recursive definitions are expressed in terms of hylomorphisms. In this paper, we propose an algorithm which can automatically turn all practical recursive definitions into structural hylomorphisms making program fusion be easily applied.

Keywords: Program transformation, supercompilation, driving, generalization, metacomputation, metasystem transition

Summary: This paper gives a gentle introduction to Turchin's supercompilation and its applications in metacomputation with an emphasis on recent developments. First, a complete supercompiler, including positive driving and generalization, is defined for a functional language and illustrated with examples. Then a taxonomy of related transformers is given and compared to the supercompiler. Finally, we put supercompilation into the larger perspective of metacomputation and consider three metacomputation tasks: specialization, composition, and inversion.

In Partial Evaluation ( O Danvy, R Glück, and P Thiemann, eds.), pp. 137-160. Volume 1110 of Lecture Notes in Computer Science. Springer-Verlag. 1996.

PhD thesis, University of Glasgow, Department of Computing Science.

PhD thesis, University of Glasgow, Department of Computing Science.