Measuring the Propagation of Information in Partial Evaluation
Henning Korsholm Rohde August 2005 |
Abstract:
We present the first measurement-based analysis of the
information propagated by a partial evaluator. Our analysis is based on
measuring implementations of string-matching algorithms, based on the
observation that the sequence of character comparisons accurately reflects
maintained information. Notably, we can easily prove matchers to be different
and we show that they display more variety and finesse than previously
believed. As a consequence, we are able to pinpoint differences and
inaccuracies in many results previously considered equivalent.
Our analysis includes a framework that lets us obtain string matchers - notably the family of Boyer-Moore algorithms - in a systematic formalism-independent way from a few information-propagation primitives. By leveraging the existing research in string matching, we show that the landscape of information propagation is non-trivial in the sense that small changes in information propagation may dramatically change the properties of the resulting string matchers. We thus expect that this work will prove useful as a test and feedback mechanism for information propagation in the development of advanced program transformations, such as GPC or Supercompilation. Available as PostScript, PDF. |