An experiment with the fourth Futamura projection

Robert Glück

doi:10.1007/978-3-642-11486-1_12

An experiment with the fourth Futamura projection

Robert Glück

Department of Computer Science

3 Citations (Scopus)

Abstract

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 language	English
Title of host publication	Perspectives of System Informatics : 7th International Andrei Ershov Memorial Conference, PSI 2009, Novosibirsk, Russia, June 15-19, 2009. Revised Papers
Editors	Amir Pnueli, Irina Virbitskaite, Andrei Voronkov
Number of pages	16
Publisher	Springer
Publication date	2010
Pages	135-150
ISBN (Print)	978-3-642-11485-4
ISBN (Electronic)	978-3-642-11486-1
DOIs	https://doi.org/10.1007/978-3-642-11486-1_12
Publication status	Published - 2010
Event	7th International Andrei Ershov Memorial Conference on Perspectives of System Informatics - Novosibirsk, Russian Federation Duration: 15 Jun 2009 → 19 Jun 2009 Conference number: 7

Conference

Conference	7th International Andrei Ershov Memorial Conference on Perspectives of System Informatics
Number	7
Country/Territory	Russian Federation
City	Novosibirsk
Period	15/06/2009 → 19/06/2009

Series	Lecture notes in computer science
Volume	5947
ISSN	0302-9743

Access to Document

10.1007/978-3-642-11486-1_12

Cite this

Glück, R. (2010). An experiment with the fourth Futamura projection. In A. Pnueli, I. Virbitskaite, & A. Voronkov (Eds.), Perspectives of System Informatics: 7th International Andrei Ershov Memorial Conference, PSI 2009, Novosibirsk, Russia, June 15-19, 2009. Revised Papers (pp. 135-150). Springer. Lecture notes in computer science Vol. 5947 https://doi.org/10.1007/978-3-642-11486-1_12

An experiment with the fourth Futamura projection. / Glück, Robert.

Perspectives of System Informatics: 7th International Andrei Ershov Memorial Conference, PSI 2009, Novosibirsk, Russia, June 15-19, 2009. Revised Papers. ed. / Amir Pnueli; Irina Virbitskaite; Andrei Voronkov. Springer, 2010. p. 135-150 (Lecture notes in computer science, Vol. 5947).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Glück, R 2010, An experiment with the fourth Futamura projection. in A Pnueli, I Virbitskaite & A Voronkov (eds), Perspectives of System Informatics: 7th International Andrei Ershov Memorial Conference, PSI 2009, Novosibirsk, Russia, June 15-19, 2009. Revised Papers. Springer, Lecture notes in computer science, vol. 5947, pp. 135-150, 7th International Andrei Ershov Memorial Conference on Perspectives of System Informatics, Novosibirsk, Russian Federation, 15/06/2009. https://doi.org/10.1007/978-3-642-11486-1_12

Glück R. An experiment with the fourth Futamura projection. In Pnueli A, Virbitskaite I, Voronkov A, editors, Perspectives of System Informatics: 7th International Andrei Ershov Memorial Conference, PSI 2009, Novosibirsk, Russia, June 15-19, 2009. Revised Papers. Springer. 2010. p. 135-150. (Lecture notes in computer science, Vol. 5947). doi: 10.1007/978-3-642-11486-1_12

@inproceedings{ddd7f5d0695811de8bc9000ea68e967b,

title = "An experiment with the fourth Futamura projection",

abstract = "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{\textquoteright}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. ",

author = "Robert Gl{\"u}ck",

year = "2010",

doi = "10.1007/978-3-642-11486-1_12",

language = "English",

isbn = "978-3-642-11485-4",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "135--150",

editor = "Amir Pnueli and Irina Virbitskaite and Andrei Voronkov",

booktitle = "Perspectives of System Informatics",

note = "7th International Andrei Ershov Memorial Conference on Perspectives of System Informatics, PSI 2009 ; Conference date: 15-06-2009 Through 19-06-2009",

}

TY - GEN

T1 - An experiment with the fourth Futamura projection

AU - Glück, Robert

N1 - Conference code: 7

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-11486-1_12

DO - 10.1007/978-3-642-11486-1_12

M3 - Article in proceedings

SN - 978-3-642-11485-4

T3 - Lecture notes in computer science

SP - 135

EP - 150

BT - Perspectives of System Informatics

A2 - Pnueli, Amir

A2 - Virbitskaite, Irina

A2 - Voronkov, Andrei

PB - Springer

T2 - 7th International Andrei Ershov Memorial Conference on Perspectives of System Informatics

Y2 - 15 June 2009 through 19 June 2009

ER -