Higher-Order and Symbolic Computation, 14(2/3)173-219
The Second Futamura Projection for Type-Directed Partial EvaluationBernd Grobauer, BRICS , Department of Computer Science, University of Aarhus, Ny Munkegade, Building 540, 8000 Aarhus C, Denmark.
Zhe Yang, Department of Computer Science, New York University, 251 Mercer Street, New York, NY 10012, USA
|
Abstract: A generating extension of a program specializes the
program with respect to part of the input. Applying a partial
evaluator to the program trivially yields a generating extension, but
specializing the partial evaluator with respect to the program often
yields a more efficient one. This specialization can be carried out by
the partial evaluator itself; in this case, the process is known as
the second Futamura projection. 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 off-line partial evaluation. We demonstrate our technique with several examples, including compiler generation for Tiny, a prototypical imperative language. Keywords: partial evaluation, generating extension, typed functional language, computational effects, self-application, compiler generation |
This article can be downloaded [here].
![[picture of journal cover]](../LISP.JPG)