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

Datalogisk Institut

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

Originalsprog	Engelsk
Titel	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
Redaktører	Manuel Mazzara, Andrei Voronkov
Antal sider	19
Forlag	Springer
Publikationsdato	2016
Sider	130-148
ISBN (Trykt)	978-3-319-41578-9
ISBN (Elektronisk)	978-3-319-41579-6
DOI	https://doi.org/10.1007/978-3-319-41579-6_11
Status	Udgivet - 2016
Begivenhed	10th International Andrei Ershov Informatics Conference on Perspectives of System Informatics - Kazan & Innopolis, Rusland Varighed: 24 aug. 2015 → 27 aug. 2015 Konferencens nummer: 10

Konference

Konference	10th International Andrei Ershov Informatics Conference on Perspectives of System Informatics
Nummer	10
Land/Område	Rusland
By	Kazan & Innopolis
Periode	24/08/2015 → 27/08/2015

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

Adgang til dokumentet

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

Citationsformater

Glück, R. (2016). Maximally-polyvariant partial evaluation in polynomial time. I M. Mazzara, & A. Voronkov (red.), 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 (s. 130-148). Springer. Lecture notes in computer science Bind 9609 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. red. / Manuel Mazzara; Andrei Voronkov. Springer, 2016. s. 130-148 (Lecture notes in computer science, Bind 9609).

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

Glück, R 2016, Maximally-polyvariant partial evaluation in polynomial time. i M Mazzara & A Voronkov (red), 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, bind 9609, s. 130-148, 10th International Andrei Ershov Informatics Conference on Perspectives of System Informatics, Kazan & Innopolis, Rusland, 24/08/2015. https://doi.org/10.1007/978-3-319-41579-6_11

Glück R. Maximally-polyvariant partial evaluation in polynomial time. I Mazzara M, Voronkov A, red., 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. s. 130-148. (Lecture notes in computer science, Bind 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. red. / Manuel Mazzara ; Andrei Voronkov. Springer, 2016. s. 130-148 (Lecture notes in computer science, Bind 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

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater