Abstract
An abstract framework is developed to describe program transformation by specializing a given program to a restricted set of inputs. Particular cases include partial evaluation [19] and Turchin's more powerful “driving” transformation [33]. Such automatic program speedups have been seen to give quite signifcant speedups in practical applications.
This paper's aims are similar to those of [18]: better to understand the fundamental mathematical phenomena that make such speedups possible. The current paper is more complete than [18], since it precisely formulates correctness of code generation; and more powerful, since it includes program optimizations not achievable by simple partial evaluation. Moreover, for the first time it puts Turchin's driving methodology on a solid semantic foundation which is not tied to any particular programming language or data structure.
This work was supported in part by the Danish Natural Science Research Council (DART project) and by an Esprit Basic Research Action (Semantique).
Preview
Unable to display preview. Download preview PDF.
References
Sergei M. Abramov, Metacomputation and program testing. In: 1st International Workshop on Automated and Algorithmic Debugging. (Linköping, Sweden). pp. 121–135, Linköping University 1993.
Samson Abramsky and Chris Hankin, editors. Abstract Interpretation of Declarative Languages. Ellis Horwood, 1987.
Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1986.
Lennart Augustsson, Compiling lazy pattern-matching. Conference on Functional Programming and Computer Architecture, ed. J.-P. Jouannoud. Lecture Notes in Computer Science 201, Springer-Verlag, 1985.
L. Beckman et al. A partial evaluator, and its use as a programming tool. Artificial Intelligence, 7(4), pp. 319–357, 1976.
D. Bjørner, A.P. Ershov, and N.D. Jones, editors. Partial Evaluation and Mixed Computation. Proceedings of the IFIP TC2 Workshop. North-Holland, 1988. 625 pages.
Wei-Ngan Chin, Safe fusion of functional expressions II: further improvements. Journal of Functional Programming. To appear in 1994.
Charles Consel and Olivier Danvy, Partial evaluation of pattern matching in strings. Information Processing Letters, 30, pp. 79–86, January 1989.
Patrick Cousot and Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Fourth ACM Symposium on Principles on Programming Languages, pp. 238–252, New York: ACM Press, 1977.
Edsger W. Dijkstra. A Discipline of Programming. Prentice-Hall, 1976.
Andrei P. Ershov. Mixed computation: Potential applications and problems for study. Theoretical Computer Science, 18, pp. 41–67, 1982.
Alex B. Ferguson and Philip Wadler, When will deforestation stop? Glasgow Workshop on Functional Programming, August 1988.
Yoshihiko Futamura and Kenroku Nogi, Generalized partial computation. In Partial Evaluation and Mixed Computation, Eds. A. P. Ershov, D. Bjørner and N. D. Jones, North-Holland, 1988.
Robert Glück and Valentin F. Turchin, Application of metasystem transition to function inversion and transformation. Proceedings of the ISSAC '90, pp. 286–287, ACM Press,1990.
Robert Glück and Andrei V. Klimov, Occam's razor in metacomputation: the notion of a perfect process tree. In Static analysis Proceedings, eds. P. Cousot, M. Falaschi, G. Filé, G. Rauzy. Lecture Notes in Computer Science 724, pp. 112–123, Springer-Verlag, 1993.
Neil D. Jones and Flemming Nielson, Abstract interpretation: a semantics-based tool for program analysis, 122 pages. In Handbook of Logic in Computer Science, Oxford University Press to appear in 1994.
Neil D. Jones, Flow analysis of lazy higher-order functional programs. In Abstract Interpretation of Declarative Languages, pp. 103–122. Ellis Horwood, 1987.
Neil D. Jones, Automatic program specialization: A re-examination from basic principles, in D. Bjørner, A.P. Ershov, and N.D. Jones (eds.), Partial Evaluation and Mixed Computation, pp. 225–282, Amsterdam: North-Holland, 1988.
Neil D. Jones, Carsten Gomard and Peter Sestoft. Partial Evaluation and Automatic Program Generation. Prentice Hall International, 425 pp., 1993.
Stephen S. Kleene, Introduction to Metamathematics. Van Nostrand, 1952, 550 pp.
John Launchbury, Projection Factorisations in Partial Evaluation. Cambridge: Cambridge University Press, 1991.
Andrei V. Klimov and Sergei Romanenko, A metaevaluator for the language Refal: basic concepts and examples. Keldysh Institute of Applied Mathematics, Academy of Sciences of the USSR, Moscow. Preprint No. 71, 1987 (in Russian).
Donald E. Knuth, James H. Morris, and Vaughan R. Pratt, Fast pattern matching in strings, SIAM Journal of Computation, 6(2), pp. 323–350, 1977.
Alexander Y. Romanenko, The generation of inverse functions in Refal, in D. Bjørner, A.P. Ershov, and N.D. Jones (eds.), Partial Evaluation and Mixed Computation, pp. 427–444, Amsterdam: North-Holland, 1988.
Sergei A. Romanenko, A compiler generator produced by a self-applicable specializer can have a surprisingly natural and understandable structure. In D. Bjørner, A.P. Ershov, and N.D. Jones (eds.), Partial Evaluation and Mixed Computation, pp. 445–463, Amsterdam: North-Holland, 1988.
Morten Heine Sørensen, A grammar-based data flow analysis to stop deforestation. Colloquium on Trees and Algebra in Programming (CAAP), edinburgh, Scotland. Lecture Notes in Computer Science, Springer-Verlag, to appear in 1994.
Morten Heine Sørensen, Robert Glück and Neil D. Jones, Towards unifying partial evaluation, deforestation, supercompilation, and GPC. European Symposium on Programming (ESOP). Lecture Notes in Computer Science, Springer-Verlag, to appear in 1994.
Akihiko Takano, Generalized partial computation for a lazy functional language. Symposium on Partial Evaluation and Semantics-Based Program Manipulation, eds. Neil D. Jones and Paul Hudak, ACM Press, 1991.
Valentin F. Turchin, Equivalent transformations of recursive functions defined in Refal. In: Teorija Jazykov i Metody Programmirovanija (Proceedings of the Symposium on the Theory of Languages and Programming Methods). (Kiev-Alushta, USSR). pp. 31–42, 1972 (in Russian).
Valentin F. Turchin, Equivalent transformations of Refal programs. In: Avtomatizirovannaja Sistema upravlenija stroitel'stvom. Trudy CNIPIASS, 6, pp. 36–68, 1974 (in Russian).
Valentin F. Turchin, The Language Refal, the Theory of Compilation and Metasystem Analysis. Courant Computer Science Report 20, 245 pages, 1980.
Valentin F. Turchin, Semantic definitions in Refal and automatic production of compilers. Semantics-Directed Compiler Generation, Aarhus, Denmark. Lecture Notes in Computer Science, Springer-Verlag, pp. 441–474, vol. 94, 1980.
Valentin F. Turchin, The concept of a supercompiler. ACM Transactions on Programming Languages and Systems, 8(3), pp. 292–325, July 1986.
Turchin V. F., A constructive interpretation of the full set theory. In: The Journal of Symbolic Logic, 52(1): 172–201, 1987.
Valentin F. Turchin, The algorithm of generalization in the supercompiler. In D. Bjørner, A.P. Ershov, and N.D. Jones (eds.), Partial Evaluation and Mixed Computation, pp. 531–549, Amsterdam: North-Holland, 1988.
Philip L. Wadler, Deforestation: transforming programs to eliminate trees. European Symposium On Programming (ESOP). Lecture Notes in Computer Science 300, pp. 344–358, Nancy, France, Springer-Verlag, 1988.
Author information
Authors and Affiliations
Editor information
Additional information
This paper is dedicated to Satoru Takasu with thanks for good advice early in my career on how to do research, and for insight into how to see the essential part of a new problem.
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Jones, N.D. (1994). The essence of program transformation by partial evaluation and driving. In: Jones, N.D., Hagiya, M., Sato, M. (eds) Logic, Language and Computation. Lecture Notes in Computer Science, vol 792. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0032402
Download citation
DOI: https://doi.org/10.1007/BFb0032402
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57935-9
Online ISBN: 978-3-540-48391-5
eBook Packages: Springer Book Archive