Partial Evaluation

Literature references and annotations by Dick Grune, dick@dickgrune.com.
Last update: Wed Sep 04 17:04:15 2024.

These references and annotations were originally intended for personal use and are presented here only in the hope that they may be useful to others. There is no claim to completeness or even correctness. Each annotation represents my understanding of the text at the moment I wrote the annotation.
No guarantees given; comments and content criticism welcome.

Neil D. Jones, Carsten K. Gomard, Peter Sestoft, Partial Evaluation and Program Generation, Prentice Hall, April 1993, pp. 400.
Broad coverage of the subject, well based on theory, with excellent explanations. Starts from basics, but goes deep. Supplies many criteria and algorithms to distinguish between static and dynamic variables, and methods to clear up entanglements. Many examples are from functional (Scheme) and logic languages, but a subset of C is defined, two-level Core C, for which a partial evaluator is given.
     Additionally, existing algorithms are derived from naive algorithms using partial evaluation. For example, Knuth, Morris and Pratt string matching is derived from a naive algorithm.

F.G. Pagan, Partial Computation and the Construction of Language Processors, Prentice Hall, 1991, pp. .
Pleasant introduction to partial evaluation with a slant towards compilation. First some notions are defined. A "partial evaluator" E takes a program P with the first part of its data $D1$ and constructs the "residual program" R, the instantiation of P for $D1$: a call of R with the data $D2$ will yield the same result as a call of P with data $D1$ and $D2$, but will do so more efficiently, we hope.
     Since we have no partial evaluator, we normally play partial evaluator ourselves, consciously or unconsciously, by creating R by hand for each instance of $D1$. To avoid this drudgery, we can instead construct a "generating extension" G of P by hand, a program that will read $D1$ and then produce R. Note that G is equivalent to what results if we would apply the partial evaluator E to itself with P as data(!).
     It turns out that generating extensions can be produced reasonably easily by hand for many programs, and this is the main theme of the book. The basic trick is to distinguish between early (partial-evaluation-time) variables and late (run-time) variables. In all examples in the book the choice is made on intuitive grounds by the author. The code surrounding early variables is "early": it can be executed at partial evaluation time; the code around late variables is itself "late": it must be generated, since its effects must be postponed until run time. No precise definition of "code surrrounding a variable" is given; the demarcation is determined intuitively by the author.
     Sometimes the early and late regions of code overlap, causing what the author calls "entanglement". Control entanglement occurs when a late piece of code assigns a value to an early variable. Although the author gives no solution to this problem, all examples suggest a unfortunate choice in early and late variables. Data entanglement occurs when late data and early data is combined in an expression. The problem can be solved when the domain of the late data is finite: the early code can be run for each value of the late variable, and the results can be combined in a run-time case statement.
     The next 9 chapters are devoted to the application of these techniques to many compiler subjects: lexical analysis, in which a general lexical analyser is instantiated with a given language description; syntax analysis, in which a general LL(1) or LR(1) syntax analyser is instantiated with a given language description; source-to-source translation (actually AST-to-source translation), in which a general tree-walker is instantiated with the source code to be generated; code generation (idem, with object code); decompilation (actually object-to-object translation), in which in a heroic effort, each source code instruction is mapped to a routine for generating the corresponding target code; and macro processing, in which a general macro processor is instantiated with a set of macros to give a specific preprocessor. The ramifications of having a real partial evaluator are examined in a final chapter.

F.G. Pagan, Comparative efficiency of general and residual parsers, ACM SIGPLAN Notices, vol. 29, #4, April 1990, pp. 59-67.
The switch from table-driven LL(1) to recursive descent or from table-driven LR(1) to recursive ascent is viewed as an example of partial computation. Underlying theory and examples are given.

Frank G. Pagan, Converting interpreters into compilers, Software -- Practice and Experience, vol. 18, #6, June 1988, pp. 509-527.
Manual conversion of an interpreter of language X written in language Y into a compiler of language X written in language Y generating code in language Y is demonstrated by replacing code frangments in the interpreter that execute statements from language X by code that output these code fragments, properly parametrized. Achieved speed-ups lie between 2 from X being vastly different from Y and 10 to 20 for X being reasonably close to Y.

D. Bjørner, A.P. Ershov, N.D. Jones, Partial Evaluation and Mixed Computation, North-Holland, Amsterdam, 1988, pp. 625.
Around 30 papers on the subject, with good introduction. A considerable number of contributions stem from Eastern Europe, where the subject has long been a topic of research. Annotated bibliography and many scattered literture references.