Safe fusion of functional expressions

ABSTRACT

Large functional programs are often constructed by decomposing each big task into smaller tasks which can be performed by simpler functions. This hierarchical style of developing programs has been found to improve programmers' productivity because smaller functions are easier to construct and reuse. However, programs written in this way tend to be less efficient. Unnecessary intermediate data structures may be created. More function invocations may be required. To reduce such performance penalties, Wadler proposed a transformation algorithm, called deforestation, which could automatically fuse certain composed expressions together in order to eliminate intermediate tree-like data structures. However, his technique is only applicable to a subset of first-order expressions. This paper will generalise the deforestation technique to make it applicable to all first-order and higher-order functional programs. Our generalisation is made possible by the adoption of a model for safe fusion which views each function as a producer and its parameters as consumers. Through this model, static program properties are proposed to classify producers and consumers as either safe or unsafe. This classification is used to identify sub-terms that can be safely fused/eliminated. We present the generalised transformation algorithm as a set of syntax-directed rewrite rules, illustrate it with examples, and provide an outline of its termination proof.

REFERENCES

• Aug85: Lennart Augustsson, Compiling pattern matching, Proc. of a conference on Functional programming languages and computer architecture, p.368-381, January 1985, Nancy, France
• BD77: R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
• BEJ88: D. Bjorner, AP. Ershov, and ND Jones. Workshop on Partial Evaluation and Mixed Computations. G1 Avarnes, Denmark, North-Holland, 1988.
• CD92: Wei-Ngan Chin and John Darlington. Higher-order removal transformation technique for functional programs. In 15th Australian Computer Science Conference, Austrahan CS Comm Vol ld, No i, pages 181-194, Hobart, Tasmania, January 1992.
• Chi90: Wei-Ngan Chin. Automatic Methods for Program Transformation. PhD thesis, Imperial College, University of London, March 1990.
• Chi91: Wei-Ngan Chin. Generalising deforestation for all first-order functional programs, in Workshop on Static Analysis of Equational, Functional and Logic Programmzng Languages, BIGRE 7~, pages 173-181, Bordeaux,France, October 1991.
• Con90: Charles Consel, Binding time analysis for high order untyped functional languages, Proceedings of the 1990 ACM conference on LISP and functional programming, p.264-272, June 27-29, 1990, Nice, France [doi>10.1145/91556.91668]
• Fea82: Martin S. Feather, A System for Assisting Program Transformation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.1, p.1-20, Jan. 1982 [doi>10.1145/357153.357154]
• FW88: AB Ferguson and Phil Wadler. When will deforestation stop? In Proc of 1988 Glasgow Workshop on Functional Programming (as Research Report 89/R$ of Glasgow University), pages 39-56, Rothesay, Isle of Bute, August 1988.
• Hol91: Carsten Kehler Holst, Finiteness analysis, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.473-495, June 1991, Cambridge, Massachusetts, United States
• Jon88: Neil J. Jones. Automatic program specialisalion: A re-examination from basic principles. In Workshop on Partial Evaluation and Mixed Computations, pages 225-282, GI Avarnes, Denmark, North-Holland, 1988.
• JSS89: ND Jones, P Sestoft, and H Sondergaard. An experiment in partial evaluation: the generation of a compiler generator. Journal of LISP and Symbolic Computation, 2(1):9-50, 1989.
• Tur86: Valentin F. Turchin, The concept of a supercompiler, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.3, p.292-325, July 1986 [doi>10.1145/5956.5957]
• Wad84: Philip Wadler, Listlessness is better than laziness: Lazy evaluation and garbage collection at compile-time, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.45-52, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802020]
• Wad85: Philip. Wadler, Listlessness is better than laziness II: composing listless functions, on Programs as data objects, p.282-305, April 1986, Copenhagen, Denmark
• Wad87: Phil Wadler. Efficient compilation of patternmatching. In The Implementation of Functional Programming Languages (by Simon Peyton- Jones), chapter 5. Prentice-Hall International, 1987.
• Wad88: Philip Wadler, Deforestation: transforming programs to eliminate trees, Proceedings of the Second European Symposium on Programming, p.231-248, January 1988, Nancy, France
• Wat91: Richard C. Waters, Automatic transformation of series expressions into loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.52-98, Jan. 1991 [doi>10.1145/114005.102806]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Functional constructs
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Algorithms, Languages