Re: Partial evaluation vs flow-graph analysis

Christian Fabre & Francois de Ferriere wrote:
> Partial evaluation seems to be a hot topic in the compiler field
> nowaday. As far as we've understood, the basic idea is to partially
> evaluate (sic) a program based on the information we are able to
> gather about its arguments. This requires some sort of intrepreter
> (or is it a meta-interpreter?) to compute the simplified program.
>
> Did we miss something obvious so far?


Not much, but this is not very far :-) An interesting further step is,
for instance, to compile the interpreter.


Have a look at:


@Article{Jones:96,
    author = {Jones, N.D.},
    title = {An Introduction to Partial Evaluation},
    journal = {ACM Computing Surveys},
    year = 1996,
    volume = 28,
    number = 3,
    month = sep,
    pages = {480-503}
}


and


@InProceedings{Consel-Danvy:popl93,
    author = {Consel, C. and Danvy, O.},
    title = {Tutorial Notes on Partial Evaluation},
    crossref = {popl93},
    pages = {493-501}
}


@Proceedings{popl93,
    title = {Proceedings of the Twentieth Annual ACM
                                    SIGPLAN-SIGACT Symposium on Principles Of
                                    Programming Languages},
    booktitle = {Proceedings of the Twentieth Annual ACM
                                    SIGPLAN-SIGACT Symposium on Principles Of
                                    Programming Languages},
    year = 1993,
    month = jan,
    publisher = {ACM Press},
    address = {Charleston, South Carolina}
}


> This makes us think that the kind of tasks well suited for partial
> evaluation can also be done, for most of them, with "older" techniques
> such as flow-graph equations.
>
> So our question is what kind of optimisations will partial evaluation
> make possible that are out of reach of a classical optimizer (and
> vice-versa)?
>
> Is there some paper comparing the two techniques?


There is quite a number of techniques which can be both used as the basis
for building optimizing compilers and partial evaluators (data-flow equations,
abstract interpretation, type inference...) but the objectives of traditional
optimizing compilers and partial evaluators are quite different, just think
about their input and output (an important point is that a partial evaluator
takes an execution context as input, not a compiler).
On can expect however to see both worlds overlap more and more (as shown, for
instance, by the interest in "procedure cloning" and constant propagation
in the compiler community, or dynamic code generation in the partial evaluation
community).


> Also, most of the papers talk about PE in the context of functional
> languages like ML or Haskell. Is this technique also usefull/usable
> for imperative languages like C, C++, Java or Eiffel?


Of course, have a look, for instance, at the work on C-Mix at DIKU
(http://www.diku.dk/topps/activities/cmix.html), and the work on TEMPO and
Harissa (C and Java) at IRISA (http://www.irisa.fr/EXTERNE/projet/compose/).


There has also been work on other imperative languages (e.g. on Pascal, by
Meyer, et al.), see the bibliography on partial evaluation at DIKU
(ftp://ftp.diku.dk/diku/semantics/partial-evaluation/).


-- Jacques NOYE
--

Return to the comp.compilers page.
Search the comp.compilers archives again.