Partial Evaluation is a certain application of program specialization. Program specialization: Fix a subset of a program's arguments (i.e., a function's parameters) and specialize the code according to the values of the fixed ("static") parameters. The resulting program will be smaller, lighter, faster.

Using this kind of specializer, interpreters can be specialized for programs that must be interpreted quite often. Thus, the resulting program is a (kind of) compiled version of the original program. I think this is what just-in-time compilers (like in the JVM) do. You can push this further (it's called Futamura's projections, then): Specialize the specializer for a given interpreter (resulting in a compiler) or even specializing the specializer for itself (resulting in a compiler generator).

I am interested in this topic because we work with DSLs a lot (domain specific languages). 25 yrs ago, this wasn't a use case, because we only hat lex/yacc then for building industry-level DSLs. It would be useful to generate code generators from interpreters - we could be sure that both have identical semantics. I am currently developing a self-applicable specializer for the Xtend language.

Would be great to find people interested in this very topic... the PE community seems to be a bit inactive currently...

Yes, this is the basic idea. The specializer partly executes the program, partly reduces it to some resulting program. There is also some formal notation that can be used, e.g., in the book of Jones, Gomard, Sestoft:

[p]/L (x,y)

for executing program p in language L for arguments x and y. Do you see any connections with your current research?

Hello Klaus,

the test case generator PET (http://costa.ls.fi.upm.es/pet/pet.php) is based on an implementation of PE for Java bytecode and for a constraint programming language. See the paper http://doi.acm.org/10.1145/1706356.1706363, which is related to the paper mentioned by Peter.

Some time ago, we argued in the paper http://dx.doi.org/10.1007/978-3-642-25271-6_5 that partial evaluation is a good match to combine it with symbolic execution, because the path conditions accumulated during symbolic execution serve as static input for the partial evaluator. We implemented a PE for a Java fragment as part of the formal verification system KeY.

For current research on partial evaluation, see the PEPM conference: http://www.informatik.uni-trier.de/~ley/db/conf/pepm/

On the whole, I agree with you that research in PE is less intense these days than it used to be.

Best Wishes

Reiner

Hmm, I can't speak to state-of-the-art. My contact with Partial Evaluation is different than the sort described in the cited paper. It does arise though.

Partial Evaluation is also featured in the context of Functional Programming, since the notation provides a mean for guidance of the partial evaluation. One can even provide explicit partial evaluation by having a function adapt argument information to derivation of a result function for subsequent use. This is presented as a feature for ML and SML, for example.

At a minimum, the curried-function notational usage allows for the first arguments to be evaluated and the values fixed/bound in subsequent operations. Handling of polymorphic types would certainly be an opportunity to trigger more than that.

Those examples are cases of explicit technique by reliance on machinery exposed to the programmer, though.

I don't have knowledge on how much processors have taken advantage of this optimization opportunity for specialization of code. It seems meaningful for static compilation as well as JIT cases. I am curious what the trade-off cases are between the two. Is there experience on that score?

I am at work on a miniature system that accomplishes partial evaluation by rewriting, but that is simply how it works all of the time. I see opportunities for optimization and especially code lifting. I don't think this fits the question asked, although I am looking into code-generation from the interpreter. That does address the semantic-preservation concern. That seems different than partial evaluation to me, although it serves as a kind of specialization.

Partial evaluation also strikes me as something that one can accomplish in object-oriented programming by having objects with methods that are class factories for new objects satisfying a common exposed interface. I have only done that a little, with hand-crafted specializations. It is easy to envision practical cases, though. Treatment of templates might be applicable. Perhaps someone has investigated that?

I also notice that this conversation began 4 years ago. Has there been more light since?