Point-free Program Transformation

• Autorzy: Cunha A. , Pinto J. S.
• Języki publikacji: EN

Abstrakty

EN

Functional programs are particularly well suited to formal manipulation by equational reasoning. In particular, it is straightforward to use calculational methods for program transformation. Well-known transformation techniques, like tupling or the introduction of accumulating parameters, can be implemented using calculation through the use of the fusion (or promotion) strategy. In this paper we revisit this transformation method, but, unlike most of the previous work on this subject, we adhere to a pure point-free calculus that emphasizes the advantages of equational reasoning. We focus on the accumulation strategy initially proposed by Bird, where the transformed programs are seen as higher-order folds calculated systematically from a specification. The machinery of the calculus is expanded with higher-order point-free operators that simplify the calculations. A substantial number of examples (both classic and new) are fully developed, and we introduce several shortcut optimization rules that capture typical transformation patterns.

Słowa kluczowe

EN

functional programming; program transformation; program calculation; point-free programming; accumulation strategy

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 66, nr 4
• Strony: 315--352
• Opis fizyczny: Bibliogr. 34 poz.

Twórcy

autor

Cunha A.

• Departamento de Informática, Universidade do Minho, Campus de Gualtar, 4710-057 Braga, Portugal

autor

Pinto J. S.

• Departamento de Informática, Universidade do Minho, Campus de Gualtar, 4710-057 Braga, Portugal

Bibliografia

• [1] Backhouse, R.: Making Formality Work For Us, EATCS Bulletin, 38, 1989, 219–249.
• [2] Backus, J.: Can Programming be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs, Communications of the ACM, 21(8), 1978, 613–641.
• [3] Bauer, F. L., Wössner, H.: Algorithmic Language and Program Development, Springer-Verlag, 1982.
• [4] Bird, R.: The Promotion and Accumulation Strategies in Transformational Programming, ACM Transactions on Programming Languages and Systems, 6(4), October 1984, 487–504.
• [5] Bird, R.: An Introduction to the Theory of Lists, in: Logic of Programming and Calculi of Discrete Design (M. Broy, Ed.), Springer-Verlag, 1987, 3–42.
• [6] Bird, R.: Introduction to Functional Programming using Haskell, International Series in Computer Science, Prentice Hall, 1998.
• [7] Bird, R., de Moor, O.: Algebra of Programming, Prentice Hall, 1997.
• [8] Burstall, R. M., Darlington, J.: A Transformation System for Developing Recursive Programs, Journal of the ACM, 24(1), January 1977, 44–76.
• [9] Cunha, A., Pinto, J. S.: Point-free Program Transformation, Technical Report DI-PURe-04:02:03, Departamento de Informática, Universidade do Minho, February 2004, Available from http://www.di.uminho.pt/pure.
• [10] Darlington, J.: An Experimental Program Transformation System, Artificial Intelligence, 16, 1981, 1–46.
• [11] Fokkinga, M., Meijer, E.: Program Calculation Properties of Continuous Algebras, Technical Report CSR9104, CWI, Amsterdam, January 1991.
• [12] Gibbons, J.: An Introduction to the Bird-Meertens Formalism, New Zealand Formal Program Development Colloquium Seminar, Hamilton, November 1994.
• [13] Gibbons, J.: A Pointless Derivation of Radix Sort, Journal of Functional Programming, 9(3), 1999, 339–346.
• [14] Gibbons, J.: Generic Downwards Accumulations, Science of Computer Programming, 37(1–3), 2000, 37–65.
• [15] Gibbons, J.: Calculating Functional Programs, in: Algebraic and Coalgebraic Methods in the Mathematics of Program Construction (R. Backhouse, R. Crole, J. Gibbons, Eds.), vol. 2297 of LNCS, chapter 5, Springer-Verlag, 2002, 148–203.
• [16] Gibbons, J., Jones, G.: The Under-Appreciated Unfold, Proceedings of the 3rd ACM SIGPLAN International Conference on Functional Programming (ICFP’98), ACM Press, 1998.
• [17] Hagino, T.: A Categorical Programming Language, Ph.D. Thesis, University of Edinburgh, 1987.
• [18] Hu, Z., Iwasaki, H., Takeichi,M.: Deriving Structural Hylomorphisms From Recursive Definitions, Proceedings of the ACM SIGPLAN International Conference on Functional Programming (ICFP’96), ACM Press, 1996.
• [19] Hu, Z., Iwasaki, H., Takeichi, M.: Calculating Accumulations, New Generation Computing, 17(2), 1999, 153–173.
• [20] Hu, Z., Iwasaki, H., Takeichi, M., Takano, A.: Tupling Calculation Eliminates Multiple Data Traversals, Proceedings of the ACM SIGPLAN International Conference on Functional Programming (ICFP’97), ACM Press, 1997.
• [21] Jones, S. P., Hughes, J., Eds.: Haskell 98: A Non-strict, Purely Functional Language, February 1999.
• [22] Launchbury, J., Sheard, T.: Warm Fusion: Deriving Build-Catas from Recursive Definitions, Proceedings of the ACM Conference on Functional Programming Languages and Computer Architecture, 1995.
• [23] Malcolm, G.: Data Structures and Program Transformation, Science of Computer Programming, 14(2–3), October 1990, 255–279.
• [24] Meertens, L.: Algorithmics – Towards Programming as a Mathematical Activity, Proceedings of the CWI Symposium on Mathematics and Computer Science, North-Holland, 1986.
• [25] Meijer, E., Fokkinga, M., Paterson, R.: Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire, Proceedings of the 5th ACMConference on Functional Programming Languages and Computer Architecture (FPCA’91) (J. Hughes, Ed.), 523, Springer-Verlag, 1991.
• [26] de Moor, O., Sittampalam, G.: Generic Program Transformation, Proceedings of the 3rd International Summer School on Advanced Functional Programming (D. Swierstra, P. Henriques, J. Oliveira, Eds.), 1608, Springer-Verlag, 1999.
• [27] Pardo, A.: Generic Accumulations, Proceedings of the 2002 IFIP TC2 Working Conference on Generic Programming (J. Gibbons, J. Jeuring, Eds.), Kluwer Academic Publishers, Schloss Dagstuhl, Germany, 2003.
• [28] Pettorossi, A., Proietti, M.: Rules and Strategies for Transforming Functional and Logic Programs, ACM Computing Surveys, 28(2), 1996, 360–414.
• [29] Reynolds, J.: Semantics of the Domain of Flow Diagrams, Journal of the ACM, 24(3), July 1977, 484–503.
• [30] Sheard, T., Fegaras, L.: A Fold for All Seasons, Proceedings of the 6th Conference on Functional Programming Languages and Computer Architecture, 1993.
• [31] Sittampalam, G., de Moor, O.: Mechanising Fusion, in: The Fun of Programming (J. Gibbons, O. de Moor, Eds.), chapter 5, Palgrave Macmillan, 2003, 79–104.
• [32] Svenningsson, J.: Shortcut Fusion for Accumulating Parameters & Zip-like Functions, Proceedings of the 7th ACM SIGPLAN International Conference on Functional Programming (ICFP’02), ACM Press, 2002.
• [33] Takano, A., Hu, Z., Takeichi, M.: Program Transformation in Calculational Form, ACM Computing Surveys, 30(3), September 1998.
• [34] Wadler, P.: Deforestation: Transforming Programs to Eliminate Trees, Proceedings of the European Symposium on Programming, number 300 in LNCS, Springer-Verlag, 1988.