Henning Korsholm Rohde:
Measuring the Propagation of Information in Partial Evaluation.
Technical report BRICS-RS-05-26, University of Aarhus, Denmark (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.
|
|
[dvi,ps,pdf]
|