The Second Futamura Projection for Type-Directed Partial Evaluation

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.