A self-applicable online partial evaluator for recursive flowchart languages

Research output: Contribution to journalJournal articlepeer-review

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.
Original languageEnglish
JournalSoftware: Practice & Experience
Volume42
Issue number6
Pages (from-to)649-673
Number of pages25
ISSN0038-0644
DOIs
Publication statusPublished - 2012

ID: 38113374