Abstract
Deforestation was introduced to eliminate intermediate data structures used to connect separate parts of a functional program together. Fusion is a more sophisticated technique, based on a producer-consumer model, to eliminate intermediate data structures. It achieves better results. In this paper we extend this fusion algorithm by refining this model, and by adding new transformation rules. The extended fusion algorithm is able to deal with standard deforestation, but also with higher-order function removal and dictionary elimination. We have implemented this extended algorithm in the Clean 2.0 compiler.
This work was supported by STW as part of project NWI.4411
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
P. Achten, A. Alimarine, R. Plasmeijer. When Generic Functions Use Dynamic Values. Post-workshop submission: 14th International Workshop on the Implementation of Functional Languages, IFL 2002, Madrid, Spain, September 2002.
A. Alimarine and R. Plasmeijer. A Generic Programming Extension for Clean. In: Arts, Th., Mohnen M., eds. Proceedings of the 13th International Workshop on the Implementation of Functional Languages, IFL 2001, Selected Papers, Älvsjö, Sweden, September 24–26, 2001, Springer-Verlag, LNCS 2312, pages 168–185.
W.-N. Chin. Safe fusion of functional expressions II: Further improvements Journal of Functional Programming, Volume 6, Part 4, pp 515–557, 1994.
R. Plasmeijer, M. van Eekelen. Language Report Concurrent Clean. Version 1.3. Technical Report CSI R9816, NIII, University of Nijmegen, June 1998. Also available at http://www.cs.kun.nl/~clean/contents/contents.html
R. Plasmeijer, M. van Eekelen. Language Report Concurrent Clean. Version 2.0. DRAFT!, NIII, University of Nijmegen, December 2001. Also available at http://www.cs.kun.nl/~clean/contents/contents.html
L. Fegaras, T. Sheard, and T. Zhou. Improving Programs which Recurse over Multiple Inductive Structures. In Proc. of ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, Orlando, FL, USA, June 1994
A. Ferguson and P. Wadler. When will Deforestation Stop. In Proc. of 1988 Glasgow Workshop on Functional Programming, pp 39–56, Rothasay, Isle of Bute, August 1988.
J. Fokker. Functional Specification of the JPEG algorithm, and an Implementation for Free, In Programming Paradigms in Graphics, Proceedings of the Eurographics workshop in Maastricht, the Netherlands, september 1995, Wien, Springer 1995, pp102–120.
A. Gill. Cheap Deforestation for Non-strict Functional Languages, PhD Thesis, Department of Computing Science, Glasgow University, 1996.
A. Gill, S. Peyton Jones, J. Launchbury. A Short Cut to Deforestation, Proc. Functional Programming Languages and Computer Architecture (FPCA’93), Copenhagen, June 1993, pp223–232.
P. Hartel, K. Langendoen. Benchmarking Implementations of Lazy Functional Languages, In Proc. of Functional Programming Languages and Computer Architecture, 1993, pp341–349.
P. Hartel, et al. Pseudoknot: A Float-Intensive Benchmark for Functional Compilers, 6th Implementation of Functional Languages, School of Information Systems, University of East Anglia, Norwich, UK, 1994, pp13.1–13.34.
P. Hudak, S. Peyton Jones, P. Wadler, B. Boutel, J. Fairbairn, J. Fasel, K. Hammond, J. Hughes, Th. Johnsson, D. Kieburtz, R. Nikhil, W. Partain, J. Peterson. Report on the programming language Haskell, In ACM SigPlan Notices, 27 (5): 1–164. May 1992.
R. Hinze and S. Peyton Jones. Derivable Type Classes. In Graham Hutton, editor, Proceedings of the Fourth Haskell Workshop, Canada, 2000.
S. Marlow. Deforestation for Higher-Order Functional Programs PhD Thesis, Department of Computer Science, University of Glasgow, 1995.
S. Peyton Jones, S. Marlow. Secrets of the Glasgow Haskell Compiler inliner Workshop on Implementing Declarative Languages, 1999.
C. Okasaki. Purely Functional Data Structures Cambridge University Press, ISBN 0-521-63124-6, 1998.
H. Seidl, M.H. Sørensen. Constraints to Stop Higher-Order Deforestation In 24th ACM Symp. on Principles of Programming Languages, pages 400–413, 1997.
A. Takano, E. Meijer. Shortcut to Deforestation in Calculational form, Proc. Functional Programming Languages and Computer Architecture (FPCA’95), La Jolla, June 1995, pp 306–313.
S. Taylor.Optimization of Mercury programs Honours report, Department of Computer Science, University of Melbourne, Australia, November 1998.
P. Wadler. Deforestation: Transforming Programs to Eliminate Trees Proceedings of the 2nd European Symposium on Programming, Nancy, France, March 1988. Lecture Notes in Computer Science 300.
P. Wadler, S. Blott. How to make ad-hoc polymorphism less ad hoc In Proceedings 16th ACM Symposium on Principles of Programming Languages, pages 60–76, 1989.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
van Arkel, D., van Groningen, J., Smetsers, S. (2003). Fusion in Practice. In: Peña, R., Arts, T. (eds) Implementation of Functional Languages. IFL 2002. Lecture Notes in Computer Science, vol 2670. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44854-3_4
Download citation
DOI: https://doi.org/10.1007/3-540-44854-3_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40190-2
Online ISBN: 978-3-540-44854-9
eBook Packages: Springer Book Archive