The Second Futamura Projection for Type-Directed Partial Evaluation

  • Bernd Grobauer
  • Zhe Yang

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.
Published
1999-12-10
How to Cite
Grobauer, B., & Yang, Z. (1999). The Second Futamura Projection for Type-Directed Partial Evaluation. BRICS Report Series, 6(40). https://doi.org/10.7146/brics.v6i40.20109