Fusion with stacks and accumulating parameters

ABSTRACT

We propose a new algorithm for fusion transformation that allows both stacks and accumulating parameters. The new algorithm can fuse programs that cannot be handled by existing fusion techniques, eg, XML transformations. The algorithm is formulated in a modular, type-directed style where the transformation process is comprised of several transformation steps that change types but preserve the observational behavior of programs. We identify a class of functions to which our new fusion method successfully applies and show that a closure property holds for that class.

REFERENCES

• 1: R. S. Bird. Using circular programs to eliminate multiple traversals of data. Acta Informatica, 21:239--250, 1984.
• 2: John Boyland , Susan L. Graham, Composing tree attributions, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.375-388, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177971]
• 3: 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]
• 4: W.-N. Chin. Safe fusion of functional expressions II: Further improvements. Journal of Functional Programming, 4(4):515--555, 1994.
• 5: Olaf Chitil, Typer inference builds a short cut to deforestation, Proceedings of the fourth ACM SIGPLAN international conference on Functional programming, p.249-260, September 27-29, 1999, Paris, France
• 6: Harald Ganzinger , Robert Giegerich, Attribute coupled grammars, ACM SIGPLAN Notices, v.19 n.6, p.157-170, June 1984
• 7: A. Gill. Cheap Deforestation for Non-strict Functional Languages. PhD thesis, University of Glasgow, 1996.
• 8: Andrew Gill , John Launchbury , Simon L. Peyton Jones, A short cut to deforestation, Proceedings of the conference on Functional programming languages and computer architecture, p.223-232, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165214]
• 9: The Haskell home page. http://www.haskell.org/.
• 10: John E. Hopcroft , Rajeev Motwani , Rotwani , Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computability, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 11: Zhenjiang Hu , Hideya Iwasaki , Masato Takeichi, Deriving structural hylomorphisms from recursive definitions, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.73-82, May 24-26, 1996, Philadelphia, Pennsylvania, United States
• 12: Patricia Johann, Short cut fusion is correct, Journal of Functional Programming, v.13 n.4, p.797-814, July 2003 [doi>10.1017/S0956796802004409]
• 13: K. Kakehi, R. Glück, and Y. Futamura. An extension of shortcut deforestation for accumulative list folding. IEICE Transactions on Information and Systems, E85-D(9):1372--1383, 2002.
• 14: John Launchbury , Tim Sheard, Warm fusion: deriving build-catas from recursive definitions, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.314-323, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224223]
• 15: K. Nakano. Composing stack-attributed tree transducers. Technical Report METR--2004--01, Department of Mathematical Informatics, University of Tokyo, Japan, 2004.
• 16: K. Nakano and S. Nishimura. Deriving event-based document transformers from tree-based specifications. In LDTA'2001 Workshop on Language Descriptions, Tools and Applications, volume 44 of Electronic Notes in Theoretical Computer Science. Elsevier Science, 2001.
• 17: S. Nishimura. Correctness of a higher-order removal transformation through a relational reasoning. In Programming Language and Systems, First Asian Symposium, APLAS 2003 Proceedings, volume 2895 of LNCS, pages 358--375. Springer Verlag, 2003. A full version is available as a preprint Kyoto-Math 2003-06 from http://www.math.kyoto-u.ac.jp/~susumu/papers/aplas03-long.ps.gz.
• 18: S. Nishimura and K. Nakano. XML stream transformer generation through program composition and dependency analysis. submitted.
• 19: Andrew M. Pitts, Parametric polymorphism and operational equivalence, Mathematical Structures in Computer Science, v.10 n.3, p.321-359, June 2000 [doi>10.1017/S0960129500003066]
• 20: Tim Sheard , Leonidas Fegaras, A fold for all seasons, Proceedings of the conference on Functional programming languages and computer architecture, p.233-242, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165216]
• 21: Josef Svenningsson, Shortcut fusion for accumulating parameters & zip-like functions, Proceedings of the seventh ACM SIGPLAN international conference on Functional programming, p.124-132, October 04-06, 2002, Pittsburgh, PA, USA
• 22: Akihiko Takano , Erik Meijer, Shortcut deforestation in calculational form, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.306-313, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224221]
• 23: John H. G. van Groningen, Optimising Recursive Functions Yielding Multiple Results in Tuples in a Lazy Functional Language, Selected Papers from the 11th International Workshop on Implementation of Functional Languages, p.59-76, September 07-10, 1999
• 24: Janis Voigtländer, Using circular programs to deforest in accumulating parameters, Proceedings of the ASIAN symposium on Partial evaluation and semantics-based program manipulation, p.126-137, September 12-14, 2002, Aizu, Japan [doi>10.1145/568173.568187]
• 25: Janis Voigtländer, Using Circular Programs to Deforest in Accumulating Parameters, Higher-Order and Symbolic Computation, v.17 n.1-2, p.129-163, March-June 2004 [doi>10.1023/B:LISP.0000029450.36668.cb]
• 26: Philip Wadler, Theorems for free!, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.347-359, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99404]
• 27: Philip Wadler, Deforestation: transforming programs to eliminate trees, Theoretical Computer Science, v.73 n.2, p.231-248, June 22, 1990

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.2 Automatic Programming

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

General Terms:
Algorithms, Languages

Keywords:
accumulating parameters, higher-order removal, shortcut fusion, stacks, type-directed program transformation