Automatic Online Partial Evaluation

Erik Ruf, Daniel Weise, Roland Conybeare, and Scott Seligman


We have solved the problem of constructing a fully automatic online program specializer for an untyped functional language (specifically, the functional subset of Scheme). We designed our specializer, called Fuse, as an interpreter that returns a trace of suspended computations. The trace is represented as a graph, rather than as program text and each suspended computation indicates the type of its result. A separate process translates the graph into a particular programming language. Producing graphs rather than program text solves problems with code duplication and premature reduce/residualize decisions. Fuse's termination strategy, which employs online generalization, specializes conditional recursive function calls and unfolds all other calls. This strategy is shown to be both powerful and safe.


Publication typeInproceedings
> Publications > Automatic Online Partial Evaluation