Jones N.D.Partial evaluation and automatic program generation.1999

Partial Evaluation

and Automatic Program Generation

Neil D. Jones

DIKU, Department of Computer Science, University of Copenhagen Universitetsparken 1, DK-2100 Copenhagen , Denmark

Carsten K. Gomard

DIKU and Computer Resources International A/S

Bregner dvej 144, DK-3460 Birker d, Denmark

Peter Sestoft

Department of Computer Science, Technical University of Denmark Building 344, DK-2800 Lyngby, Denmark

with chapters by

Lars Ole Andersen and Torben Mogensen

DIKU, Department of Computer Science, University of Copenhagen Universitetsparken 1, DK-2100 Copenhagen , Denmark1

Originally published by Prentice Hall International 1993; ISBN 0-13-020249-5. In 1999, the copyright has been transferred back to the authors.

Copyright c 1999 Neil D. Jones, Carsten K. Gomard, and Peter Sestoft; the book homepage is http://www.dina.kvl.dk/~sestoft/pebook/pebook.html

Contents

v

Preface xi

Partial evaluation and compilation

Partial evaluation gives a remarkable approach to compilation and compiler generation. For example, partial evaluation of an interpreter with respect to a source program yields a target program. Thus compilation can be achieved without a compiler, and a target program can be thought of as a specialized interpreter.

Compiler generation

Moreover, provided the partial evaluator is self-applicable, compiler generation is possible: specializing the partial evaluator itself with respect to a xed interpreter yields a compiler. Thus a compiler can be thought of as a specialized partial evaluator: one which can specialize only an interpreter for a particular language.

Finally, specializing the partial evaluator with respect to itself yields a compiler generator. Thus a compiler generator can be thought of as a specialized partial evaluator: one which can specialize only itself.

Other applications

The application of partial evaluation is not restricted to compiling and compiler generation. If a program takes more than one input, and one of the inputs varies more slowly than the others, then specialization of the program with respect to that input gives a faster specialized program. Moreover, very many real-life programs exhibit interpretive behaviour. For instance they may be parametrized with con guration les, etc., which seldom vary, and therefore they may be pro tably specialized.

The range of potential applications is extremely large, as shown by the list of examples below. All have been implemented on the computer, by researchers from Copenhagen, MIT, Princeton, and Stanford universities; and INRIA (France) and ECRC (Germany). All have been seen to give signi cant speedups.

Pattern recognition

Computer graphics by `ray tracing'

Neural network training

Answering database queries

Spreadsheet computations

Scienti c computing

Discrete hardware simulation

xii Preface

This book

We give several examples of such applications, but the main emphasis of the book is on principles and methods for partial evaluation of a variety of programming languages: functional (the lambda calculus and Scheme), imperative (a owchart language and a subset of C), and logical (Prolog). We explain the techniques necessary for construction of partial evaluators, for instance program ow analysis, in su cient detail to allow their implementation. Many of these techniques are applicable also in other advanced programming tasks.

The book is structured as follows. The rst chapter gives an overview of partial evaluation and some applications. Then Part I introduces fundamental programming language concepts, de nes three mini-languages, and presents interpreters for them. Part II describes the principles of self-applicable partial evaluation, illustrated using two of the mini-languages: ow charts and rst-order recursion equations. Part III shows how these principles apply to stronger languages: the lambda calculus, and large subsets of the Prolog, Scheme, and C programming languages. Part IV discusses practical aspects of partial evaluation, and presents a wide range of applications. Part V presents more a theoretical view and a number of advanced techniques, and provides extensive references to other research.

The book should be accessible even to beginning graduate students, and thus useful for beginners and researchers in partial evaluation alike.

The perspective on partial evaluation and the selection of material re ect the experience of our group with construction of several partial evaluators. These include the rst non-trivial self-applicable partial evaluators for a functional language, an imperative language, the lambda calculus, a Prolog subset, and a subset of C. This work has been carried out at the University of Copenhagen.

Acknowledgements

Many have contributed to both the substance and the ideas appearing in this book. In particular we want to thank Lars Ole Andersen and Torben Mogensen who wrote two specialist chapters, and Olivier Danvy who provided numerous constructive comments and suggestions. More broadly we would like to express our thanks to: Peter Holst Andersen, Henk Barendregt, Job Baretta, Anders Bondorf, Hans Bruun, Mikhail Bulyonkov, Charles Consel, Robert Gl•uck, Chris Hankin, Reinhold Heckmann, Fritz Henglein, Carsten Kehler Holst, Paul Hudak, John Hughes, Kristian Damm Jensen, Jesper J rgensen, John Launchbury, Alan Mycroft, Hanne and Flemming Nielson, Patrick O'Keefe, Sergei Romanenko, Bill Scherlis, David A. Schmidt, Harald S ndergaard, Morten Heine S rensen, Carolyn Talcott, Valentin Turchin, Phil Wadler, Daniel Weise, and last but not least, Lisa Wiese.

Parts of the research reported here were supported by DIKU (the Department of Computer Science, University of Copenhagen) by the Danish Natural Sciences Research Council, and by ESPRIT Basic Research Action 3124, `Semantique'.