| Author: |
J. Voigtländer |
| Published: |
In 13th International Conference on Rewriting Techniques and Applications (RTA'02, acceptance rate 20/40), Copenhagen, Denmark, Proceedings, volume 2378 of LNCS, pages 222-236, Springer, July 2002. |
| DOI: |
10.1007/3-540-45610-4_16 |
| BibTeX: |
Voi02a.bib |
| Abstract: |
We study the question of efficiency improvement or deterioration
for a semantic-preserving program transformation technique based
on macro tree transducer composition. By annotating functional
programs to reflect the internal property "computation time"
explicitly in the computed output, and by manipulating such
annotations, we formally prove syntactic conditions under which the
composed program is guaranteed to be more efficient than the original
program, with respect to call-by-need reduction to normal form.
The developed criteria can be checked automatically, and thus are
suitable for integration into an optimizing functional compiler.
|
| Download: |
ConditionsForEfficiencyImprovementByTreeTransducerComposition.pdf |
| Rights: |
Copyright held by Springer. |
| Slides: |
Slides of my talk at the conference are here. |