A self-applicable online partial evaluator for recursive flowchart languages

Publikation: Bidrag til tidsskriftTidsskriftartikelfagfællebedømt

This paper describes a self-applicable online partial evaluator for a ¿owchart language with recursive calls.
Self-application of the partial evaluator yields generating extensions that are as ef¿cient as those reported in
the literature for of¿ine partial evaluation. This result is remarkable because it has been assumed that online
partial evaluation techniques unavoidably lead to inef¿cient and overgeneralized generating extensions. The
purpose of this paper is not to determine which kind of partial evaluation is better, but to show how the
problem can be solved by recursive polyvariant specialization. The design of the self-applicable online
partial evaluator is based on a number of known techniques, but by combining them in a new way this
result can be produced. The partial evaluator, its techniques, and its implementation are presented in full.
Self-application according to all three Futamura projections is demonstrated. The complete bootstrap of a
compiler generator from a partial evaluator is also reported. Copyright q 2011 John Wiley & Sons, Ltd.
OriginalsprogEngelsk
TidsskriftSoftware: Practice & Experience
Vol/bind42
Udgave nummer6
Sider (fra-til)649-673
Antal sider25
ISSN0038-0644
DOI
StatusUdgivet - 2012

ID: 38113374