Open AccessThe Second Futamura Projection for Type-Directed Partial Evaluation
Author(s) -
Bernd Grobauer,
Zhe Yang
Publication year - 1999
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v6i40.20109
Subject(s) - partial evaluation , projection (relational algebra) , computer science , extension (predicate logic) , mathematics , programming language , context (archaeology) , compiler , arithmetic , algorithm , paleontology , biology
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.