Using Types to Avoid Redundant Specialization

Erik Ruf and Daniel Weise

Abstract

Existing partial evaluators use a strategy called poly-variant specialization, which involves specializing program points on the known portions of their arguments, and re-using such specializations only when these known portions match exactly. We show that this re-use criterion is overly restrictive, and misses opportunities for sharing in residual programs, thus producing large residual programs containing redundant specializations. They develop a criterion for re-use based on computing the domains of specializations, and describe an approximate implementation of this criterion based on types, and its implementation in their partial evaluation system, FUSE. Finally, we relate the algorithm to existing work in partial evaluation and machine learning.

Details

Publication typeInproceedings
Published inPEPM '91
URLhttp://www.acm.org/
PublisherAssociation for Computing Machinery, Inc.
> Publications > Using Types to Avoid Redundant Specialization