A self-applicable online partial evaluator for recursive flowchart languages

TY - JOUR

T1 - A self-applicable online partial evaluator for recursive flowchart languages

AU - Glück, Robert

PY - 2012/6/1

Y1 - 2012/6/1

N2 - This paper describes a self-applicable online partial evaluator for a flowchart language with recursive calls. Self-application of the partial evaluator yields generating extensions that are as efficient as those reported in the literature for offline partial evaluation. This result is remarkable because it has been assumed that online partial evaluation techniques unavoidably lead to inefficient 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.

AB - This paper describes a self-applicable online partial evaluator for a flowchart language with recursive calls. Self-application of the partial evaluator yields generating extensions that are as efficient as those reported in the literature for offline partial evaluation. This result is remarkable because it has been assumed that online partial evaluation techniques unavoidably lead to inefficient 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.

U2 - 10.1002/spe.1086

DO - 10.1002/spe.1086

M3 - Journal article

SN - 0038-0644

VL - 42

SP - 649

EP - 673

JO - Software: Practice & Experience

JF - Software: Practice & Experience

IS - 6

ER -