Shortcut fusion for accumulating parameters & zip-like functions

ABSTRACT

We present an alternative approach to shortcut fusion based on the function unfoldr,. Despite its simplicity the technique can remove intermediate lists in examples which are known to be difficult. We show that it can remove all lists from definitions involving zip-like functions and functions using accumulating parameters.

REFERENCES

• 1: Loic Correnson, Etienne Duris, Didier Parigot, and Gilles Roussel. How to deforest in accumulative parameters? Technical Report 3608, INRIA, January 1999.
• 2: Wei-Ngan Chin, Safe fusion of functional expressions, Proceedings of the 1992 ACM conference on LISP and functional programming, p.11-20, June 22-24, 1992, San Francisco, California, United States
• 3: 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
• 4: L. Fegaras. Using the parametricity theorem for program fusion. Technical Report 96-001, Oregon Graduate Institute, 1996.
• 5: L. Fegaras, T. Sheard, and T. Zhou. Improving programs which recurse over multiple inductive structures. In ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, Orlando, Florida, June 1994.
• 6: A. Gill. Cheap Deforestation for Non-strict Functional Languages. PhD thesis, University of Glasgow, 1996.
• 7: Jeremy Gibbons , Geraint Jones, The under-appreciated unfold, Proceedings of the third ACM SIGPLAN international conference on Functional programming, p.273-279, September 26-29, 1998, Baltimore, Maryland, United States
• 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: Jörgen Gustavsson , David Sands, Possibilities and limitations of call-by-need space improvement, Proceedings of the sixth ACM SIGPLAN international conference on Functional programming, September 03-05, 2001, Florence, Italy
• 10: Geoff Hamilton, Extending Higher-Order Deforestation: Transforming Programs to Eliminate Even More Trees, Selected papers from the 3rd Scottish Functional Programming Workshop (SFP01), p.25-36, August 22-24, 2001
• 11: Zhenjiang Hu, Hideya Iwasaki, and Masato Takeichi. An Extension of the Acid Rain Theorem. In 2nd Fuji International Workshop on Functional and Logic Programming, pages 91--105, Shonan Village, Japan, November 1996. World Scientific.
• 12: S. Peyton Jones and J. Hughes. Haskell 98 library report, February 1999.
• 13: S. Peyton Jones and J. Hughes. Haskell 98 report, February 1999.
• 14: Patricia Johann, Short Cut Fusion: Proved and Improved, Proceedings of the Second International Workshop on Semantics, Applications, and Implementation of Program Generation, p.47-71, September 06, 2001
• 15: J. Launchbury, S. Krstic', and T. E. Sauerwein. Zip Fusion with Hyperfunctions. Oregon Graduate Institute, 2000.
• 16: Simon Marlow. Deforestation for Higher-Order Functional Programs. PhD thesis, University of Glasgow, 1996.
• 17: Erik Meijer , Maarten Fokkinga , Ross Paterson, Functional programming with bananas, lenses, envelopes and barbed wire, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.124-144, June 1991, Cambridge, Massachusetts, United States
• 18: Simon L. Peyton Jones , André L. M. Santos, A transformation-based optimiser for Haskell, Science of Computer Programming, v.32 n.1-3, p.3-47, Sept. 1998 [doi>10.1016/S0167-6423(97)00029-4 ]
• 19: S. Peyton Jones, A. Tolmach, and T. Hoare. Playing by the rules: rewriting as a practical optimisation technique in GHC. In Haskell Workshop, 2001.
• 20: D. Sands, Improvement theory and its applications, Higher order operational techniques in semantics, Cambridge University Press, New York, NY, 1999
• 21: 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]
• 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: J. Voigtländer and A. Kühnemann. Composition of functions with accumulating parameters. Technical Report TUD-FI01-08, Dresden University of Technology, 2001.
• 24: Janis Voigtländer, Concatenate, reverse and map vanish for free, Proceedings of the seventh ACM SIGPLAN international conference on Functional programming, p.14-25, October 04-06, 2002, Pittsburgh, PA, USA
• 25: 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]
• 26: 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]
• 27: P. Wadler, Views: a way for pattern matching to cohabit with data abstraction, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.307-313, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41653]
• 28: 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]
• 29: 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.1 Applicative (Functional) Programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Program and recursion schemes

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.4 Applications

General Terms:
Algorithms, Languages

Keywords:
deforestation, functional programming, intermediate data structures, optimisation, program transformation