The Second Futamura Projection for Type-Directed Partial Evaluation

Forfattere

  • Bernd Grobauer
  • Zhe Yang

DOI:

https://doi.org/10.7146/brics.v6i40.20109

Resumé

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.

Downloads

Publiceret

1999-12-10

Citation/Eksport

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

Nummer

Nr. 40 (1999): RS-40 The Second Futamura Projection for Type-Directed Partial Evaluation

Sektion

Artikler

Licens

Authors who publish with this journal agree to the following terms:

    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

    1. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

  1. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).