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

Department of Computer Science

1 Citation (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.

Original language	English
Title of host publication	Perspectives of System Informatics : 8th International Andrei Ershov Memorial Conference, PSI 2011, Novosibirsk, Russia, June 27-July 1, 2011, Revised Selected Papers
Editors	Edmund Clarke, Irina Virbitskaite, Andrei Voronkov
Number of pages	17
Publisher	Springer
Publication date	2012
Pages	125-141
ISBN (Print)	978-3-642-29708-3
ISBN (Electronic)	978-3-642-29709-0
DOIs	https://doi.org/10.1007/978-3-642-29709-0_13
Publication status	Published - 2012
Event	8th International Andrei Ershov Memorial Conference on Perspectives of Systems Informatics - Novosibirsk, Russian Federation Duration: 27 Jun 2011 → 1 Jul 2011 Conference number: 8

Conference

Conference	8th International Andrei Ershov Memorial Conference on Perspectives of Systems Informatics
Number	8
Country/Territory	Russian Federation
City	Novosibirsk
Period	27/06/2011 → 01/07/2011

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

Access to Document

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

Cite this

Glück, R. (2012). Bootstrapping compiler generators from partial evaluators. In E. Clarke, I. Virbitskaite, & A. Voronkov (Eds.), Perspectives of System Informatics: 8th International Andrei Ershov Memorial Conference, PSI 2011, Novosibirsk, Russia, June 27-July 1, 2011, Revised Selected Papers (pp. 125-141). Springer. Lecture notes in computer science Vol. 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. ed. / Edmund Clarke; Irina Virbitskaite; Andrei Voronkov. Springer, 2012. p. 125-141 (Lecture notes in computer science, Vol. 7162).

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

Glück, R 2012, Bootstrapping compiler generators from partial evaluators. in E Clarke, I Virbitskaite & A Voronkov (eds), 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, vol. 7162, pp. 125-141, 8th International Andrei Ershov Memorial Conference on Perspectives of Systems Informatics, Novosibirsk, Russian Federation, 27/06/2011. https://doi.org/10.1007/978-3-642-29709-0_13

Glück R. Bootstrapping compiler generators from partial evaluators. In Clarke E, Virbitskaite I, Voronkov A, editors, Perspectives of System Informatics: 8th International Andrei Ershov Memorial Conference, PSI 2011, Novosibirsk, Russia, June 27-July 1, 2011, Revised Selected Papers. Springer. 2012. p. 125-141. (Lecture notes in computer science, Vol. 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. editor / Edmund Clarke ; Irina Virbitskaite ; Andrei Voronkov. Springer, 2012. pp. 125-141 (Lecture notes in computer science, Vol. 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

Conference

Access to Document

Fingerprint

Cite this