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

Datalogisk Institut

3 Citationer (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.

Originalsprog	Engelsk
Titel	Perspectives of System Informatics : 7th International Andrei Ershov Memorial Conference, PSI 2009, Novosibirsk, Russia, June 15-19, 2009. Revised Papers
Redaktører	Amir Pnueli, Irina Virbitskaite, Andrei Voronkov
Antal sider	16
Forlag	Springer
Publikationsdato	2010
Sider	135-150
ISBN (Trykt)	978-3-642-11485-4
ISBN (Elektronisk)	978-3-642-11486-1
DOI	https://doi.org/10.1007/978-3-642-11486-1_12
Status	Udgivet - 2010
Begivenhed	7th International Andrei Ershov Memorial Conference on Perspectives of System Informatics - Novosibirsk, Rusland Varighed: 15 jun. 2009 → 19 jun. 2009 Konferencens nummer: 7

Konference

Konference	7th International Andrei Ershov Memorial Conference on Perspectives of System Informatics
Nummer	7
Land/Område	Rusland
By	Novosibirsk
Periode	15/06/2009 → 19/06/2009

Navn	Lecture notes in computer science
Vol/bind	5947
ISSN	0302-9743

Adgang til dokumentet

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

Citationsformater

Glück, R. (2010). An experiment with the fourth Futamura projection. I A. Pnueli, I. Virbitskaite, & A. Voronkov (red.), Perspectives of System Informatics: 7th International Andrei Ershov Memorial Conference, PSI 2009, Novosibirsk, Russia, June 15-19, 2009. Revised Papers (s. 135-150). Springer. Lecture notes in computer science Bind 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. red. / Amir Pnueli; Irina Virbitskaite; Andrei Voronkov. Springer, 2010. s. 135-150 (Lecture notes in computer science, Bind 5947).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Glück, R 2010, An experiment with the fourth Futamura projection. i A Pnueli, I Virbitskaite & A Voronkov (red), 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, bind 5947, s. 135-150, 7th International Andrei Ershov Memorial Conference on Perspectives of System Informatics, Novosibirsk, Rusland, 15/06/2009. https://doi.org/10.1007/978-3-642-11486-1_12

Glück R. An experiment with the fourth Futamura projection. I Pnueli A, Virbitskaite I, Voronkov A, red., Perspectives of System Informatics: 7th International Andrei Ershov Memorial Conference, PSI 2009, Novosibirsk, Russia, June 15-19, 2009. Revised Papers. Springer. 2010. s. 135-150. (Lecture notes in computer science, Bind 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 -