An experiment with the fourth Futamura projection

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

We have experimentally validated the theoretical insight, that a compiler generator is an Ershov generating extension of a program specializer, by showing that an existing offline partial evaluator can perform the fourth Futamura projection. Specifically, an online and an offline partial evaluator for an imperative flowchart language were transformed into two new compiler generators by Romanenko’s classical partial evaluator Unmix. The two partial evaluators are described, as is a novel recursive method for polyvariant specialization. The new compiler generators are demonstrated by converting a universal parser into a parser generator. These results strongly indicate that existing partial evaluation techniques can be put to work on several new applications. To date, all previous compiler generators based on partial evaluation were either generated by self-application or handwritten. None of these works considered the generation of one compiler generator by another.
Original languageEnglish
Title of host publicationPerspectives of System Informatics : 7th International Andrei Ershov Memorial Conference, PSI 2009, Novosibirsk, Russia, June 15-19, 2009. Revised Papers
EditorsAmir Pnueli, Irina Virbitskaite, Andrei Voronkov
Number of pages16
PublisherSpringer
Publication date2010
Pages135-150
ISBN (Print)978-3-642-11485-4
ISBN (Electronic)978-3-642-11486-1
DOIs
Publication statusPublished - 2010
Event7th International Andrei Ershov Memorial Conference on Perspectives of System Informatics - Novosibirsk, Russian Federation
Duration: 15 Jun 200919 Jun 2009
Conference number: 7

Conference

Conference7th International Andrei Ershov Memorial Conference on Perspectives of System Informatics
Nummer7
LandRussian Federation
ByNovosibirsk
Periode15/06/200919/06/2009
SeriesLecture notes in computer science
Volume5947
ISSN0302-9743

ID: 12990520