Report Number: CSL-TR-92-518
Institution: Stanford University, Computer Systems Laboratory
Title: Avoiding Redundant Specialization during Partial Evaluation
Author: Ruf, Erik
Author: Weise, Daniel
Date: April 1992
Abstract: Existing partial evaluators use a strategy called polyvariant
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. We develop a criterion for re-use based on
computing the domains of specializations, describe an
approximate implementation of this criterion based on types,
and show its implementation in our partial evaluation system
FUSE. In addition, we describe several extensions to our
mechanism to make it compatible with more powerful
specialization strategies and to increase its efficiency.
After evaluating our algorithm's usefulness, we relate it to
existing work in partial evaluation and machine learning.