|
The Second Futamura Projection for Type-Directed Partial Evaluation
Bernd Grobauer
November 1999 |
Abstract:
A generating extension of a program specializes it with respect
to some specified part of the input. A generating extension of a program can
be formed trivially by applying a partial evaluator to the program; the
second Futamura projection describes the automatic generation of non-trivial
generating extensions by applying a partial evaluator to itself with respect
to the programs. We derive an ML implementation of the second Futamura
projection for Type-Directed Partial Evaluation (TDPE). Due to the
differences between `traditional', syntax-directed partial evaluation and
TDPE, this derivation involves several conceptual and technical steps. These
include a suitable formulation of the second Futamura projection and
techniques for making TDPE amenable to self-application. In the context of
the second Futamura projection, we also compare and relate TDPE with
conventional offline partial evaluation. We demonstrate our technique with
several examples, including compiler generation for Tiny, a prototypical
imperative language.
Available as PostScript, PDF, DVI. |