Literature references and annotations by Dick Grune, email@example.com.
Last update: Mon Sep 14 13:33:32 2009.
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,
Partial Evaluation and Program Generation,
Broad coverage of the subject, well based on theory, with excellent
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
Additionally, existing algorithms are derived from naive algorithms
using partial evaluation.
For example, Knuth, Morris and Pratt string matching is derived from a
Partial Computation and the Construction of Language Processors,
Pleasant introduction to partial evaluation with a slant towards
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
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
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 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
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
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
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.
Comparative efficiency of general and residual parsers,
ACM SIGPLAN Notices,
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,
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
Partial Evaluation and Mixed Computation,
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.