Abstract
The world of program optimization and transformation takes on a new fascination when viewed through the lens of program calculation. Unlike the traditional fold/unfold approach to program transformation on arbitrary programs, the calculational approach imposes restrictions on program structures, resulting in some suitable calculational forms such as homomorphisms and mutumorphisms that enjoy a collection of generic algebraic laws for program manipulation. In this tutorial, we will explain the basic idea of program calculation, demonstrate that many program optimizations and transformations, such as the optimization technique known as loop fusion and the parallelization transformation, can be concisely reformalized in calculational form, and show that program transformation in calculational forms is of higher modularity and more suitable for efficient implementation.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Jones, S.P., Hughes, J., et al (eds.): Haskell 98: A Non-strict, Purely Functional Language (1999), Available online: http://www.haskell.org
Bird, R.: Introduction to Functional Programming using Haskell. Prentice Hall, Englewood Cliffs (1998)
Hughes, J.: Lazy memo-functions. In: Jouannaud, J.-P. (ed.) FPCA 1985. LNCS, vol. 201, pp. 129–149. Springer, Heidelberg (1985)
Burstall, R., Darlington, J.: A transformation system for developing recursive programs. Journal of the ACM 24, 44–67 (1977)
Feather, M.: A survey and classification of some program transformation techniques. In: TC2 IFIP Working Conference on Program Specification and Transformation, Bad Tolz, Germany, pp. 165–195. North-Holland, Amsterdam (1987)
Darlington, J.: An experimental program transformation system. Artificial Intelligence 16, 1–46 (1981)
Bird, R.: An introduction to the theory of lists. In: Broy, M. (ed.) Logic of Programming and Calculi of Discrete Design, pp. 5–42. Springer, Heidelberg (1987)
Backhouse, R.: An exploration of the Bird-Meertens formalism. In: STOP Summer School on Constructive Algorithmics, Ameland (1989)
Meijer, E., Fokkinga, M., Paterson, R.: Functional programming with bananas, lenses, envelopes and barbed wire. In: Hughes, J. (ed.) FPCA 1991. LNCS, vol. 523, pp. 124–144. Springer, Heidelberg (1991)
Fokkinga, M.: A gentle introduction to category theory — the calculational approach — Technical Report Lecture Notes, Dept. INF, University of Twente, The Netherlands (1992)
Jeuring, J.: Theories for Algorithm Calculation. Ph.D thesis, Faculty of Science, Utrecht University (1993)
Bird, R., de Moor, O.: Algebras of Programming. Prentice Hall, Englewood Cliffs (1996)
Hu, Z., Iwasaki, H., Takeichi, M.: Deriving structural hylomorphisms from recursive definitions. In: ACM SIGPLAN International Conference on Functional Programming, Philadelphia, PA, pp. 73–82. ACM Press, New York (1996)
Hu, Z., Iwasaki, H., Takeichi, M., Takano, A.: Tupling calculation eliminates multiple data traversals. In: ACM SIGPLAN International Conference on Functional Programming, Amsterdam, The Netherlands, pp. 164–175. ACM Press, New York (1997)
Hu, Z., Takeichi, M., Chin, W.: Parallelization in calculational forms. In: 25th ACM Symposium on Principles of Programming Languages, San Diego, California, USA, pp. 316–328 (1998)
Hu, Z., Iwasaki, H., Takeichi, M.: Calculating accumulations. New Generation Computing 17, 153–173 (1999)
Yokoyama, T., Hu, Z., Takeichi, M.: Deterministic second-order patterns. Information Processing Letters 89, 309–314 (2004)
Malcolm, G.: Data structures and program transformation. Science of Computer Programming, 255–279 (1990)
Pettorossi, A., Proiett, M.: Rules and strategies for transforming functional and logic programs. Computing Surveys 28, 360–414 (1996)
de Moor, O., Sittampalam, G.: Higher-order matching for program transformation. Theor. Comput. Sci. 269, 135–162 (2001)
Goldberg, A., Paige, R.: Stream processing. In: LISP and Functional Programming, pp. 53–62 (1984)
Aho, A., Sethi, R., Ullman, J.: Compilers – Principles, Techniqies and Tools. Addison-Wesley, Reading (1986)
Chin, W.: Towards an automated tupling strategy. In: Proc. Conference on Partial Evaluation and Program Manipulation, Copenhagen, pp. 119–132. ACM Press, New York (1993)
Gill, A., Launchbury, J., Jones, S.P.: A short cut to deforestation. In: Proc. Conference on Functional Programming Languages and Computer Architecture, Copenhagen, pp. 223–232 (1993)
Takano, A., Meijer, E.: Shortcut deforestation in calculational form. In: Proc. Conference on Functional Programming Languages and Computer Architecture, La Jolla, California, pp. 306–313 (1995)
Onoue, Y., Hu, Z., Iwasaki, H., Takeichi, M.: A calculational fusion system HYLO. In: IFIP TC 2 Working Conference on Algorithmic Languages and Calculi, Le Bischenberg, France, pp. 76–106. Chapman & Hall, Boca Raton (1997)
Banerjee, U., Eigenmann, R., Nicolau, A., Padua, D.A.: Automatic program parallelization. Proceedings of the IEEE 81, 211–243 (1993)
Cole, M.: Parallel programming, list homomorphisms and the maximum segment sum problems. Report CSR-25-93, Department of Computing Science, The University of Edinburgh (1993)
Hu, Z., Iwasaki, H., Takeichi, M.: Formal derivation of efficient parallel programs by construction of list homomorphisms. ACM Transactions on Programming Languages and Systems 19, 444–461 (1997)
Skillicorn, D.: Foundations of Parallel Programming. Cambridge University Press, Cambridge (1994)
Gorlatch, S.: Constructing list homomorphisms. Technical Report MIP-9512, Fakultät für Mathematik und Informatik, Universität Passau (1995)
Chin, W., Takano, A., Hu, Z.: Parallelization via context preservation. In: IEEE Computer Society International Conference on Computer Languages. Loyola University Chicago, Chicago (1998)
Xu, D.N., Khoo, S.C., Hu, Z.: Ptype system: A featherweight parallelizability detector. In: Chin, W.-N. (ed.) APLAS 2004. LNCS, vol. 3302, pp. 197–212. Springer, Heidelberg (2004)
Sheard, T., Peyton Jones, S.L.: Template metaprogramming for Haskell. In: Haskell Workshop, Pittsburgh, Pennsylvania, pp. 1–16 (2002)
Yokoyama, T., Hu, Z., Takeichi, M.: Deterministic second-order patterns and its application to program transformation. In: Bruynooghe, M. (ed.) LOPSTR 2004. LNCS, vol. 3018, pp. 128–142. Springer, Heidelberg (2004)
Sheard, T., Fegaras, L.: A fold for all seasons. In: Proc. Conference on Functional Programming Languages and Computer Architecture, Copenhagen, pp. 233–242 (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Hu, Z., Yokoyama, T., Takeichi, M. (2006). Program Optimizations and Transformations in Calculation Form. In: Lämmel, R., Saraiva, J., Visser, J. (eds) Generative and Transformational Techniques in Software Engineering. GTTSE 2005. Lecture Notes in Computer Science, vol 4143. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11877028_5
Download citation
DOI: https://doi.org/10.1007/11877028_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-45778-7
Online ISBN: 978-3-540-46235-4
eBook Packages: Computer ScienceComputer Science (R0)