Higher Order Deforestation

• Autorzy: Hamilton G.W.
• Języki publikacji: EN

Abstrakty

EN

Deforestation is a well known transformation algorithm which can eliminate intermediate structures from functional programs. In previous work, we have shown how the deforestation algorithm can be extended to handle higher order programs. A higher order treeless form of expression was defined to ensure the termination of this algorithm. Our higher order algorithm was further extended by Seidl and S?rensen, and this extension was shown to remove some intermediate structures not removed by our algorithm (although our original algorithm can also remove some intermediate structures not removed by their technique). In this paper, we show how our original definition of higher order treeless form can be extended to allow the intermediate structures in the examples given by Seidl and S?rensen to be removed. We argue that, because our extended algorithm uses an easy to recognise treeless form, there is more transparency for the programmer in terms of the improvements which will be made. We prove that our new algorithm terminates, and we conjecture that it ensures that there is no efficiency loss, which we argue is essential for any optimisation.

Słowa kluczowe

EN

deforestation; transformation; termination; efficiency

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 69, nr 1,2
• Strony: 39--61
• Opis fizyczny: bibliogr. 46 poz.

Twórcy

autor

Hamilton G.W.

• School of Computer Applications Dublin City University Dublin 9, Ireland,

Bibliografia

• [1] Ariola, Z., Felleisen, M.: The Call-by-Need Lambda Calculus, Journal of Functional Programming, 7(3), 1997, 265-301.
• [2] Ariola, Z., Felleisen, M., Maraist, J., Odersky, M., Wadler, P.: A Call-By-Need Lambda Calculus, Proceedings of the Twenty-Second ACM Symposium on Principles of Programming Languages, January 1995.
• [3] Augustsson, L.: Compiling Pattern Matching, Functional Programming Languages and Computer Architecture, 1985.
• [4] Burstall, R., Darlington, J.: A Transformation System for Developing Recursive Programs, Journal of the ACM, 24(1), January 1977, 44-67.
• [5] Chin, W.-N.: Automatic Methods for Program Transformation, Ph.D. Thesis, Imperial College, University of London, July 1990.
• [6] Chin, W.-N.: Generalising Deforestation for All First-Order Functional Programs, Journées de Travail sur L'Analyse Statique en Programmation Equationnelle, Fonctionnelle et Logique, October 1991.
• [7] Chin, W.-N.: Fully-Lazy Higher Order Removal, Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, 1992.
• [8] Chin, W.-N.: Safe Fusion of Functional Expressions, Proceedings of the ACM Conference on LISP and Functional Programming, 1992.
• [9] Chin, W.-N.: Safe Fusion of Functional Expressions II: Further Improvements, Journal of Functional Programming, 4(4), 1994, 515-555.
• [10] Chin, W.-N., Darlington, J.: Higher-Order Removal Transformation Technique for Functional Programs, Australian Computer Science Communications, 14(1), January 1992, 181-194.
• [11] Chin, W.-N., Khoo, S.-C.: Better Consumers for Deforestation, Proceedings of the Seventh International Symposium on Programming, Logics, Implementation and Programs (PLILP '95), number 982 in Lecture Notes in Computer Science, 1995.
• [12] Damas, L., Milner, R.: Principal Type Schemes for Functional Programs, Proceedings of the Ninth ACM Symposium on Principles of Programming Languages, 1982.
• [13] Fegaras, L., Sheard, T., Zhou, T.: Improving Programs Which Recurse Over Multiple Inductive Structures, Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, 1994.
• [14] Gill, A.: Cheap Deforestation for Non-Strict Functional Languages, Ph.D. Thesis, Glasgow University, 1996.
• [15] Gill, A., Launchbury, J., Peyton Jones, S. L.: A Short Cut to Deforestation, Proceedings of the Sixth International Conference on Functional Programming Languages and Computer Architecture, 1993.
• [16] Gill, A., Peyton Jones, S. L.: Cheap Deforestation in Practice: An Optimiser for Haskell, IFIP, 1994.
• [17] Hamilton, G. W.: Compile-Time Optimisation of Store Usage in Lazy Functional Programs, Ph.D. Thesis, University of Stirling, October 1993.
• [18] Hamilton, G. W.: Higher Order Deforestation, Technical Report TR 95-07, Dept. of Computer Science, Keele University, 1995.
• [19] Hamilton, G. W.: Higher Order Deforestation, Proceedings of the Eighth International Symposium on Programming, Logics, Implementation and Programs, 1996.
• [20] Hamilton, G. W.: Extending Higher Order Deforestation: Transforming Programs to Eliminate Even More Trees, in: Trends in Functional Programming (Volume 3), Intellect Books, 2002, 25-36.
• [21] Hamilton, G. W., Jones, S. B.: Extending Deforestation for First Order Functional Programs, Proceedings of the 1991 Glasgow Workshop on Functional Programming, Workshops in Computing, Springer-Verlag, August 1991, Published 1992.
• [22] Hamilton, G. W., Jones, S. B.: Transforming Programs to Eliminate Intermediate Structures, Journées de Travail sur L'Analyse Statique en Programmation Equationnelle Fonctionnelle et Logique, 74, Bordeaux, France, October 1991.
• [23] Hu, Z., Iwasaki, H., Takeichi, M.: Deriving Structural Hylomorphisms From Recursive Definitions, Proceedings of the ACM International Conference on Functional Programming, 1996.
• [24] Hughes, R. J. M.: Supercombinators: A New Implementation Method for Applicative Languages, Proceedings of the ACM Conference on LISP and Functional Programming, 1982.
• [25] Hughes, R. J.M.: Why Functional ProgrammingMatters, The Computer Journal, 32(2), April 1989, 98-107.
• [26] Launchbury, J., Sheard, T.: Warm Fusion: Deriving Build-Cata's from Recursive Definitions, Proceedings of the Conference on Functional Programming and Computer Architecture, 1995.
• [27] Maraist, J., Odersky, M., Wadler, P.: The Call-by-Need Lambda Calculus, Journal of Functional Programming, 8(3), 1998, 275-317.
• [28] Marlow, S.: Deforestation for Higher-Order Functional Programs, Ph.D. Thesis, Glasgow University, 1996.
• [29] Marlow, S., Wadler, P.: Deforestation for Higher-Order Functions, Proceedings of the Fifth Annual Glasgow Workshop on Functional Programming, July 1992.
• [30] Milner, R.: A Theory of Type Polymorphism in Programming, Journal of Computer and System Science, 17, 1978, 348-375.
• [31] Moran, A. K., Sands, D.: Improvement in a Lazy Context: An Operational Theory for Call-By-Need, 26th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, January 1999.
• [32] Nielsen, K., Sørensen, M. H.: Deforestation, Partial Evaluation, and Evaluation Orders, 1995, Unpublished.
• [33] Onoue, Y., Hu, Z., Iwasaki, H., Takeichi, M.: A calculational fusion system HYLO, in: Algorithmic Languages and Calculi, Chapman and Hall, 1997, 76-106.
• [34] Sands, D.: Proving the Correctness of Recursion-Based Automatic Program Transformations, Sixth International Conference on Theory and Practice of Software Development, 1995.
• [35] Sands, D.: Total Correctness by Local Improvement in Program Transformation, Proceedings of the 22nd ACM Symposium on Principles of Programming Languages, ACM Press, 1995.
• [36] Sands, D.: Proving the Correctness of Recursion-Based Automatic Program Transformations, Theoretical Computer Science, 1-2(167), 1996.
• [37] Sands, D.: Total Correctness by Local Improvement in the Transformation of Functional Programs, ACM Transactions on Programming Languages and Systems, 18(2),March 1996.
• [38] Seidl, H.: Integer Constraints to Stop Deforestation, Proceedings of the European Symposium on Programming, 1996.
• [39] Seidl, H., Sørensen, M. H.: Constraints to Stop Higher-Order Deforestation, Proceedings of the Twelfth Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, 1997.
• [40] Seidl, H., Sørensen, M. H.: Constraints to Stop Deforestation, Science of Computer Programming, 32(1-2), 1998, 73-107.
• [41] Sheard, T., Fegaras, L.: A Fold for All Seasons, Proceedings of the Conference on Functional Programming and Computer Architecture, 1993.
• [42] Sørensen, M. H.: A Grammar-Based Data-Flow Analysis to Stop Deforestation, Proceedings of the International Logic Programming Symposium, 1995.
• [43] Takano, A., Meijer, E.: Shortcut Deforestation in Calculational Form, Proceedings of the Conference on Functional Programming and Computer Architecture, 1995.
• [44] Wadler, P.: Efficient Compilation of Pattern Matching, in: The Implementation of Functional Programming Languages (S. P. Jones, Ed.), Prentice Hall, 1987, 78-103.
• [45] Wadler, P.: Deforestation: Transforming Programs to Eliminate Trees, European Symposium on Programming, 1988.
• [46] Wadler, P.: Deforestation: Transforming Programs to Eliminate Trees, Theoretical Computer Science, 73, 1990, 231-248.