Compiling equational programs into efficient machine code
Robert I. Strandh · 1988
High level programming languages have introduced models of computation that are very different from the traditional von Neumann machine. Translating such programs into efficient machine code for traditional machines is therefore non-trivial. In this thesis, we are interested in generating code for Equational Programs. An equational program consists of Equations of the form T = U, interpreted as reduction rules, i.e., the program takes an input term and replaces, repeatedly, instances of left-hand sides of equations by corresponding right-hand sides. The process, called reduction, stops when no instance of a left-hand side can be found. The term is then in normal form. The reduction process may go on forever if no normal form exists. Huet and Levy showed that the strongly sequential programs have efficient translations, in that there is an efficient algorithm for finding an instance of a left-hand side that necessary to replace in every sequence of reductions to normal form. Their algorithm does, however, not consider sequences of reductions. Simply restarting the algorithm after each replacement is too expensive. Hoffmann and O'Donnell defined the strongly left-sequential programs, for which an efficient algorithm exists that solves this problem. In this thesis we define the class of forward branching programs, and show that it is a superset of the strongly left-sequential programs. We design an efficient reduction algorithm that works for a sequence of reductions whenever the program is forward branching. We also give a decision procedure for the forward branching programs. Huet and Levy, as well as Hoffmann and O'Donnell, ignored the problem of replacing instances of left-hand sides with right-hand sides. Experience with previous implementations suggest that these replacements are serious bottle necks. We define an efficient replacement algorithm for the forward branching programs. Our algorithm is a novel application of partial evaluation. Finally, we present an experimental implementation of a compiler for forward branching programs. We present simple benchmark that suggests that our implementation performs as well as compiled Franz Lisp and within a factor of two of Unix C.