Bootstrapping compiler generators from partial evaluators

Robert Glück

doi:10.1007/978-3-642-29709-0_13

Bootstrapping compiler generators from partial evaluators

Robert Glück

Datalogisk Institut

1 Citationer (Scopus)

Abstract

This paper shows that bootstrapping of compiler generators from program specializers is a viable alternative to the third Futamura projection. To practically validate the technique, a novel partial evaluation-based compiler generator was designed and implemented for a recursive flowchart language. Three-step bootstrapping was found to be faster and to produce the same compiler generator that Gomard and Jones produced two decades ago by double self-application. Compiler-generator bootstrapping has distinct properties that are not present in the classic three Futamura projections, such as the ability to turn a specializer into a compiler generator in one step without self-application. Up to now, the approach of hand-writing compiler generators has only been used to avoid difficulties when specializing strongly-typed languages, not as a first step towards compiler-generator bootstrapping.

Originalsprog	Engelsk
Titel	Perspectives of System Informatics : 8th International Andrei Ershov Memorial Conference, PSI 2011, Novosibirsk, Russia, June 27-July 1, 2011, Revised Selected Papers
Redaktører	Edmund Clarke, Irina Virbitskaite, Andrei Voronkov
Antal sider	17
Forlag	Springer
Publikationsdato	2012
Sider	125-141
ISBN (Trykt)	978-3-642-29708-3
ISBN (Elektronisk)	978-3-642-29709-0
DOI	https://doi.org/10.1007/978-3-642-29709-0_13
Status	Udgivet - 2012
Begivenhed	8th International Andrei Ershov Memorial Conference on Perspectives of Systems Informatics - Novosibirsk, Rusland Varighed: 27 jun. 2011 → 1 jul. 2011 Konferencens nummer: 8

Konference

Konference	8th International Andrei Ershov Memorial Conference on Perspectives of Systems Informatics
Nummer	8
Land/Område	Rusland
By	Novosibirsk
Periode	27/06/2011 → 01/07/2011

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

Adgang til dokumentet

10.1007/978-3-642-29709-0_13

Citationsformater

Glück, R. (2012). Bootstrapping compiler generators from partial evaluators. I E. Clarke, I. Virbitskaite, & A. Voronkov (red.), Perspectives of System Informatics: 8th International Andrei Ershov Memorial Conference, PSI 2011, Novosibirsk, Russia, June 27-July 1, 2011, Revised Selected Papers (s. 125-141). Springer. Lecture notes in computer science Bind 7162 https://doi.org/10.1007/978-3-642-29709-0_13

Bootstrapping compiler generators from partial evaluators. / Glück, Robert.

Perspectives of System Informatics: 8th International Andrei Ershov Memorial Conference, PSI 2011, Novosibirsk, Russia, June 27-July 1, 2011, Revised Selected Papers. red. / Edmund Clarke; Irina Virbitskaite; Andrei Voronkov. Springer, 2012. s. 125-141 (Lecture notes in computer science, Bind 7162).

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

Glück, R 2012, Bootstrapping compiler generators from partial evaluators. i E Clarke, I Virbitskaite & A Voronkov (red), Perspectives of System Informatics: 8th International Andrei Ershov Memorial Conference, PSI 2011, Novosibirsk, Russia, June 27-July 1, 2011, Revised Selected Papers. Springer, Lecture notes in computer science, bind 7162, s. 125-141, 8th International Andrei Ershov Memorial Conference on Perspectives of Systems Informatics, Novosibirsk, Rusland, 27/06/2011. https://doi.org/10.1007/978-3-642-29709-0_13

Glück R. Bootstrapping compiler generators from partial evaluators. I Clarke E, Virbitskaite I, Voronkov A, red., Perspectives of System Informatics: 8th International Andrei Ershov Memorial Conference, PSI 2011, Novosibirsk, Russia, June 27-July 1, 2011, Revised Selected Papers. Springer. 2012. s. 125-141. (Lecture notes in computer science, Bind 7162). doi: 10.1007/978-3-642-29709-0_13

Glück, Robert. / Bootstrapping compiler generators from partial evaluators. Perspectives of System Informatics: 8th International Andrei Ershov Memorial Conference, PSI 2011, Novosibirsk, Russia, June 27-July 1, 2011, Revised Selected Papers. red. / Edmund Clarke ; Irina Virbitskaite ; Andrei Voronkov. Springer, 2012. s. 125-141 (Lecture notes in computer science, Bind 7162).

@inproceedings{8c599e8254004ab28032cc5decc98551,

title = "Bootstrapping compiler generators from partial evaluators",

abstract = "This paper shows that bootstrapping of compiler generators from program specializers is a viable alternative to the third Futamura projection. To practically validate the technique, a novel partial evaluation-based compiler generator was designed and implemented for a recursive flowchart language. Three-step bootstrapping was found to be faster and to produce the same compiler generator that Gomard and Jones produced two decades ago by double self-application. Compiler-generator bootstrapping has distinct properties that are not present in the classic three Futamura projections, such as the ability to turn a specializer into a compiler generator in one step without self-application. Up to now, the approach of hand-writing compiler generators has only been used to avoid difficulties when specializing strongly-typed languages, not as a first step towards compiler-generator bootstrapping.",

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

year = "2012",

doi = "10.1007/978-3-642-29709-0_13",

language = "English",

isbn = "978-3-642-29708-3",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "125--141",

editor = "Edmund Clarke and Irina Virbitskaite and Andrei Voronkov",

booktitle = "Perspectives of System Informatics",

note = "8th International Andrei Ershov Memorial Conference on Perspectives of Systems Informatics, PSI 2011 ; Conference date: 27-06-2011 Through 01-07-2011",

}

TY - GEN

T1 - Bootstrapping compiler generators from partial evaluators

AU - Glück, Robert

N1 - Conference code: 8

PY - 2012

Y1 - 2012

N2 - This paper shows that bootstrapping of compiler generators from program specializers is a viable alternative to the third Futamura projection. To practically validate the technique, a novel partial evaluation-based compiler generator was designed and implemented for a recursive flowchart language. Three-step bootstrapping was found to be faster and to produce the same compiler generator that Gomard and Jones produced two decades ago by double self-application. Compiler-generator bootstrapping has distinct properties that are not present in the classic three Futamura projections, such as the ability to turn a specializer into a compiler generator in one step without self-application. Up to now, the approach of hand-writing compiler generators has only been used to avoid difficulties when specializing strongly-typed languages, not as a first step towards compiler-generator bootstrapping.

AB - This paper shows that bootstrapping of compiler generators from program specializers is a viable alternative to the third Futamura projection. To practically validate the technique, a novel partial evaluation-based compiler generator was designed and implemented for a recursive flowchart language. Three-step bootstrapping was found to be faster and to produce the same compiler generator that Gomard and Jones produced two decades ago by double self-application. Compiler-generator bootstrapping has distinct properties that are not present in the classic three Futamura projections, such as the ability to turn a specializer into a compiler generator in one step without self-application. Up to now, the approach of hand-writing compiler generators has only been used to avoid difficulties when specializing strongly-typed languages, not as a first step towards compiler-generator bootstrapping.

U2 - 10.1007/978-3-642-29709-0_13

DO - 10.1007/978-3-642-29709-0_13

M3 - Article in proceedings

SN - 978-3-642-29708-3

T3 - Lecture notes in computer science

SP - 125

EP - 141

BT - Perspectives of System Informatics

A2 - Clarke, Edmund

A2 - Virbitskaite, Irina

A2 - Voronkov, Andrei

PB - Springer

T2 - 8th International Andrei Ershov Memorial Conference on Perspectives of Systems Informatics

Y2 - 27 June 2011 through 1 July 2011

ER -

Bootstrapping compiler generators from partial evaluators

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater