Controlled self-applicable on-line partial evaluation, using strategies

Mattox Beckman, Sam Kamin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

On-line partial evaluators are hardly ever self-applicable, because the complexity of deciding whether to residualize terms causes combinatorial explosion when self-application is attempted. Recently, T. Mogensen found a way to write a self-applicable on-line partial evaluator for λ-calculus. His method is to regard every λ-term as having both static and dynamic aspects; then, applications can always be done statically (using the static aspect of the operator). However, the absence of decision-making about residualization has a down side: his partial evaluator knows only how to fully reduce partially evaluated terms. The result is considerable code explosion. We show how this problem can be overcome, in part, by changing the type of the partial evaluator, and giving a new version of the Futamura projections to correspond to that new type. Specifically, we have the partial evaluator take a third argument, called a strategy, which `advises' the partial evaluator whether to residualize. Strategies allow the programmer to control the trade-off between the size of a specialized term and the cost of subsequently applying it. We present a number of strategies and examples of each.

Original languageEnglish (US)
Title of host publicationProceedings of the IEEE International Conference on Computer Languages
PublisherIEEE Comp Soc
Pages143-152
Number of pages10
ISBN (Print)0818684542
DOIs
StatePublished - 1998
EventProceedings of the 1998 International Conference on Computer Languages - Chicago, IL, USA
Duration: May 14 1998May 16 1998

Conference

ConferenceProceedings of the 1998 International Conference on Computer Languages
CityChicago, IL, USA
Period5/14/985/16/98

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Controlled self-applicable on-line partial evaluation, using strategies'. Together they form a unique fingerprint.

Cite this