Maximally-polyvariant partial evaluation in polynomial time

Robert Glück

doi:10.1007/978-3-319-41579-6_11

Maximally-polyvariant partial evaluation in polynomial time

Robert Glück

Department of Computer Science

1 Citation (Scopus)

Abstract

Maximally-polyvariant partial evaluation is a strategy for program specialization that propagates static values as accurate as possible. The online partial evaluator presented here achieves this precision in time polynomial in the number of partial-evaluation configurations. This is a significant improvement because a conventional partial evaluator can take exponential time, and no fast algorithm was known for maximally-polyvariant specialization. For an important class of quasideterministic specialization problems, our algorithm performs in linear time, even for linear-time specialization of a naive string matcher into a linear-time matcher, which was Futamura’s long-standing open challenge. Our results are presented using a recursive flowchart language.

Original language	English
Title of host publication	Perspectives of System Informatics : 10th International Andrei Ershov Informatics Conference, PSI 2015, in Memory of Helmut Veith, Kazan and Innopolis, Russia, August 24-27, 2015, Revised Selected Papers
Editors	Manuel Mazzara, Andrei Voronkov
Number of pages	19
Publisher	Springer
Publication date	2016
Pages	130-148
ISBN (Print)	978-3-319-41578-9
ISBN (Electronic)	978-3-319-41579-6
DOIs	https://doi.org/10.1007/978-3-319-41579-6_11
Publication status	Published - 2016
Event	10th International Andrei Ershov Informatics Conference on Perspectives of System Informatics - Kazan & Innopolis, Russian Federation Duration: 24 Aug 2015 → 27 Aug 2015 Conference number: 10

Conference

Conference	10th International Andrei Ershov Informatics Conference on Perspectives of System Informatics
Number	10
Country/Territory	Russian Federation
City	Kazan & Innopolis
Period	24/08/2015 → 27/08/2015

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

Access to Document

10.1007/978-3-319-41579-6_11

Cite this

Glück, R. (2016). Maximally-polyvariant partial evaluation in polynomial time. In M. Mazzara, & A. Voronkov (Eds.), Perspectives of System Informatics: 10th International Andrei Ershov Informatics Conference, PSI 2015, in Memory of Helmut Veith, Kazan and Innopolis, Russia, August 24-27, 2015, Revised Selected Papers (pp. 130-148). Springer. https://doi.org/10.1007/978-3-319-41579-6_11

Maximally-polyvariant partial evaluation in polynomial time. / Glück, Robert.
Perspectives of System Informatics: 10th International Andrei Ershov Informatics Conference, PSI 2015, in Memory of Helmut Veith, Kazan and Innopolis, Russia, August 24-27, 2015, Revised Selected Papers. ed. / Manuel Mazzara; Andrei Voronkov. Springer, 2016. p. 130-148 (Lecture notes in computer science, Vol. 9609).

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

Glück, R 2016, Maximally-polyvariant partial evaluation in polynomial time. in M Mazzara & A Voronkov (eds), Perspectives of System Informatics: 10th International Andrei Ershov Informatics Conference, PSI 2015, in Memory of Helmut Veith, Kazan and Innopolis, Russia, August 24-27, 2015, Revised Selected Papers. Springer, Lecture notes in computer science, vol. 9609, pp. 130-148, 10th International Andrei Ershov Informatics Conference on Perspectives of System Informatics, Kazan & Innopolis, Russian Federation, 24/08/2015. https://doi.org/10.1007/978-3-319-41579-6_11

Glück R. Maximally-polyvariant partial evaluation in polynomial time. In Mazzara M, Voronkov A, editors, Perspectives of System Informatics: 10th International Andrei Ershov Informatics Conference, PSI 2015, in Memory of Helmut Veith, Kazan and Innopolis, Russia, August 24-27, 2015, Revised Selected Papers. Springer. 2016. p. 130-148. (Lecture notes in computer science, Vol. 9609). doi: 10.1007/978-3-319-41579-6_11

Glück, Robert. / Maximally-polyvariant partial evaluation in polynomial time. Perspectives of System Informatics: 10th International Andrei Ershov Informatics Conference, PSI 2015, in Memory of Helmut Veith, Kazan and Innopolis, Russia, August 24-27, 2015, Revised Selected Papers. editor / Manuel Mazzara ; Andrei Voronkov. Springer, 2016. pp. 130-148 (Lecture notes in computer science, Vol. 9609).

@inproceedings{9a47e51b1a6a4ab6a1e8efeea186b9cf,

title = "Maximally-polyvariant partial evaluation in polynomial time",

abstract = "Maximally-polyvariant partial evaluation is a strategy for program specialization that propagates static values as accurate as possible. The online partial evaluator presented here achieves this precision in time polynomial in the number of partial-evaluation configurations. This is a significant improvement because a conventional partial evaluator can take exponential time, and no fast algorithm was known for maximally-polyvariant specialization. For an important class of quasideterministic specialization problems, our algorithm performs in linear time, even for linear-time specialization of a naive string matcher into a linear-time matcher, which was Futamura{\textquoteright}s long-standing open challenge. Our results are presented using a recursive flowchart language.",

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

year = "2016",

doi = "10.1007/978-3-319-41579-6_11",

language = "English",

isbn = "978-3-319-41578-9",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "130--148",

editor = "Manuel Mazzara and Andrei Voronkov",

booktitle = "Perspectives of System Informatics",

note = "10th International Andrei Ershov Informatics Conference on Perspectives of System Informatics, PSI 2015 ; Conference date: 24-08-2015 Through 27-08-2015",

}

TY - GEN

T1 - Maximally-polyvariant partial evaluation in polynomial time

AU - Glück, Robert

N1 - Conference code: 10

PY - 2016

Y1 - 2016

N2 - Maximally-polyvariant partial evaluation is a strategy for program specialization that propagates static values as accurate as possible. The online partial evaluator presented here achieves this precision in time polynomial in the number of partial-evaluation configurations. This is a significant improvement because a conventional partial evaluator can take exponential time, and no fast algorithm was known for maximally-polyvariant specialization. For an important class of quasideterministic specialization problems, our algorithm performs in linear time, even for linear-time specialization of a naive string matcher into a linear-time matcher, which was Futamura’s long-standing open challenge. Our results are presented using a recursive flowchart language.

AB - Maximally-polyvariant partial evaluation is a strategy for program specialization that propagates static values as accurate as possible. The online partial evaluator presented here achieves this precision in time polynomial in the number of partial-evaluation configurations. This is a significant improvement because a conventional partial evaluator can take exponential time, and no fast algorithm was known for maximally-polyvariant specialization. For an important class of quasideterministic specialization problems, our algorithm performs in linear time, even for linear-time specialization of a naive string matcher into a linear-time matcher, which was Futamura’s long-standing open challenge. Our results are presented using a recursive flowchart language.

U2 - 10.1007/978-3-319-41579-6_11

DO - 10.1007/978-3-319-41579-6_11

M3 - Article in proceedings

SN - 978-3-319-41578-9

T3 - Lecture notes in computer science

SP - 130

EP - 148

BT - Perspectives of System Informatics

A2 - Mazzara, Manuel

A2 - Voronkov, Andrei

PB - Springer

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

Y2 - 24 August 2015 through 27 August 2015

ER -

Maximally-polyvariant partial evaluation in polynomial time

Abstract

Conference

Access to Document

Fingerprint

Cite this