Partial Evaluation: HoPL 2/25/2004

Presented by Owen Landgren
Transcribed by Felix Klock

The core idea of partial evaluation:specialize a program with respect to static inputs

Futamura '71
Q (from Audience) : What is the difference between static and dynamic here?
A: Static things are what we know at analysis time. Dynamic things are what we don't know untilwe actually run the program itself.

So, lets assume that

πp(s1, ..., sm, r1, ..., rn) = some new process (computation)

Well, if we apply the partial evaluatorαas follows:

α(πp, s1, ..., sm)
this application of α yields a new πsthat can be applied to the dynamic arguments:
πs(r1, ..., rn)
and this will be the same process that we produced originally without α!

Clearly this has applications in compiler engineering, where you want to use information available at compile-time to produce an optimized program

But Partial Evaluation isn't just for optimization

Lets assume we had an Interpreter process, Interp(p,d)

Then we could apply α like so:

α(Interp,p) ==> Executable
we get a new process, Executable, where
Executable(d) = result of interpretation

This means that α(Interp, p) is the compiler of p

This is known as the first Futamura projection

Where can we go from here? Well

α(α, Interp) = α'(Interp,_)
α' is a A COMPILER

This is known as the second Futamura projection

This sounds exciting. In particular, it means that we can generate compilers from interpretations with the same ease that we generate parsers from grammars; we would just use α instead of a parser generator

Parser <-- ParserGen <-- Syntax
Compiler <-- α <-- Interp
| (meta lang
\/ terms )
Object Code

This is great! Except we don't have α yet...

Finally, Futamura poses some questions

Beckman '76
Ershov '82

Classifies two approaches

p = f(x,y)
px= g(y)

p in C = all computation steps

Q (from Audience) : What do you mean by computation steps? Are p traces, or individual operations?
A: Each p is an atomic operation.

μ in C' union C''

Elements of C shift between C' and C'' are you discharge operations

We're finding a fixed point of C''

Reuses the S-m-n theorem (the theorem is not Ershov's invention)
assume we have universal U of n arguments where

Un(x1,..., xn) : interpreter for its 1st argument

then there existsSnm(x1,..., xn) such that
Um+n(N, x1, ..., xx+n) = Un(Snm(x1,..., xn)xn+1,..., xm+n)


References MIX '85 (by Jones)

Defines Similix-2 (an attempt an an auto-projectable meta-language

Q (from Audience) : What is autoprojection?
A: Its the 3rd Futamura projection, α(α, α)

Features of the meta-language

Performs Binding Time Analysis to determine which calls ar static vs dynamic

We can classify functions according to a two element lattice: S (static) <= D (dynamic)

Higher order functions are put into D, which eliminates P.E. benefits

Closure analysis: generate set sof all possible functions at a call site

Closure analysis on Higher Order Functions
Maintain two mappings:μ : Labels -> CLSets, and ρ : Variables -> CLSets

This somehow defines a lattice with elements D,S,Cl, and bot, where S <= D, Cl <= D, bot is less than everything, and S and Cl are incomparable.

An insight: the way you write the interpreter transforms theoutput of the compiler
Direct StyleDirect Style
CPS StyleCPS Style

Q (from Audience) : The latter two points aren't really stylistic decisions; they're part of the definition of the language you're interpreting.
A: Yep.
Q (from Audience) : So why should we be surprised by the result for the last two cases? It would be more surprising if the output didn't behave using the same semantics for procedure calls.
A: Fair enough

Jones '93

This is just a survey paper, summarizing work up until that point.

New things have come up in the world of Partial Evalation, butthose results are in post-2000 papers.