Reviews of work in the field of partial evaluation (post 1993)

Question

I'm looking for relatively new reviews of research work on partial evaluation. The most recent work I've found is "Tutorial notes on partial evaluation" by Charles Consel and Olivier Danvy (1993). The book Partial Evaluation and Automatic Program Generation (1993) also gives a comprehensive overview of the work in this field.

In particular, I want to write a brief overview of the history of this field of research. And with the sources I've found so far, I only have enough to write about it up to the early 90s.

Terminology: In the literature, other more-or-less interchangeable terms are sometimes used instead of "partial evaluation". Like "mixed computation" (introduced by A.P. Ershov) and, as Respawned Fluff has mentioned, "program specialization". "Partial deduction" seems to be used in the context of partial evaluation applied to logic programming.

Answer 1

The PEPM (Partial Evaluation and Program Manipulation) Symposium Series is still running. That'd be a good place to start to see what the current hot topics are and who is still working on Partial Evaluation.

Answer 2

The 1998 Partial Evaluation. Practice and Theory series of lecture notes is slightly newer and fits your desired terminology.

Like said however, the notions of program specialization and partial evaluation are often taken as synonymous (e.g. they are so on p.1 of Jones et al.), so ignore the literature using/preferring the later term at your own peril. Hopefully this passage from Marlet's book (p. 44) illustrates this point:

the general idea that largely underlies program specialization is of a “partial execution”. When partial execution is understood in a fairly literal sense (when a term is entirely known, executing it and replacing it by its result or its effects), we speak of partial evaluation. A specializer based on this principle is therefore called a partial evaluator.

This kind of specialization is so widespread that, with many authors, the terms program specialization and partial evaluation are often mistaken for one another, or used as synonyms. Other authors prefer to reserve the term specialization to express the concept, i.e. the objective (to obtain a better-performing specialized program), and only to speak of partial evaluation to refer to the means used to attain that objective (evaluating anything that can be evaluated in advance). Terms other than partial evaluation are also used, such as partial computation, which remains relatively neutral, or partial deduction, which relates only to logic programming

In the rest of this book, we shall speak almost exclusively of partial evaluation, but using terminology related to specialization [...]

If want to survey a filed, you have to take into account the terminlogy issues...

Answer 3

I have not been looking at partial evaluation for a very long time. There is much stuff in code optimization techniques for compilers that can fit that framework when properly presented. Thing often become relevant when you start looking at them the right way. But people in optimizing compilers may not try to emphasize the partial evaluation view when partial evaluation is no longer fashionable. Each time has its own buzzwords to get grant money and publications accepted.

So I would suggest a good look at code optimization (unless that is dead too).

I answered recently to a question about compilers, and mentioned partial evaluation as an important issue to understand the nature of the compiling process. I doubt much you will find anything new there, but just in case ...

Partial evaluation and formal languages

Another thing in that area is not well known (afaik), though it may be seen more as an intellectual curiosity than as an important technical view. It is a bit post-1993 (in Lang 1995 actually). This concerns parsing. You may view a grammar $G$ (for example a context-free grammar, but this applies to many other kinds of syntactic formalisms) as something that computes a parse tree for a string $w$, given an appropriate grammar interpreter (the CYK algorithm is a simple example). Actually, in the case of ambiguous languages, you do not get a single parse-tree but a whole collection forming a parse-forest. There is a condensed form for parse-forest that shares subtrees that are common to several parse-trees, in different ways. With appropriate sharing structures, this shared-parse-forest is actually nothing but another grammar $G_w$. This grammar $G_w$ is a specialization of the original grammars to the string parsed.

What that means is that $G_w$ is is a grammar that generates only the string $w$ being parsed, but does it with precisely the same parse trees as the original grammars, up to a homomorphic renaming of some non-terminals. So the original grammar $G$ has been specialized to a grammar $G_w$ generating the singleton subset $\{w\}$ of the language of $G$.

This is moderately exciting. The more interesting aspect is that the technique works for other subsets of the original language. If you take any regular set $R$, its intersection with the language $L(G)$ is a context-free language (assuming we are working with CF grammars). Exactly the same techniques can be used to parse the whole regular set, represented by a FSA, to produce another grammar $G_R$, which is a specialisation of $G$ for the intersection of the CF language $R\cap L(G)$. It is a specialization in the sense that for strings in that intersection it produces exactly the same parse-trees, the same ambiguities as the original grammar $G$, up to a renaming homomorphism for non-terminals.

So the idea is that you can partially evaluate a grammar when you have some information about what should be parsed, information which is specified by a finite state automaton. This can then be extended to various games people play with grammars, such as attaching attributes or feature structures. But then one would enter more traditional partial evaluation.

These techniques have actual use in natural language processing, but could be used for programming languages too.

I have various pointers accessible following links from this answer which present an example of application in NLP amongst too many other things (but the question was a bit wide).

Answer 4

Caveat: I have not followed the field closely. In the early 1990s partial evaluation was fashionable as a research subject, but activity died down around the turn of the millennium. I think that's because nobody could make partial evaluation efficient.

Later some key ideas resurfaced from a different community and in warped form, this time leading to blindingly fast code. What happened? The modern variant does specialisation at run-time and only on "hot code", i.e. code that has been observed during the execution to be used a lot. It is know as just-in-time compilation. Some of the recent work on JIT compilation (e.g. meta-tracing) looks a lot like Futamura projections. The precise connections between partial evaluations and JIT compilation have not been explored.