Algebraic fusion of functions with an accumulating parameter and its improvement
Abstract
We present a unifying solution to the problem of fusion of functions, where both the producer function and the consumer function have one accumulating parameter. The key idea in this development is to formulate the producer function as a function which computes over a monoid of data contexts. Upon this formulation, we develop a fusion method called algebraic fusion based on the elementary theory of universal algebra and monoids. The producer function is fused with a monoid homomorphism that is derived from the definition of the consumer function, and is turned into a higher-order function f that computes over the monoid of endofunctions.We then introduce a general concept called improvement, in order to reduce the cost of computing over the monoid of endofunctions (i. e., function closures). An improvement of the function f via a monoid homomorphism h is a function g that satisfies f =h ºg. This provides a principled way of finding a first-order function representing a solution to the fusion problem. It also presents a clean and unifying account for varying fusion methods that have been proposed so far. Furthermore, we show that our method extends to support partial and infinite data structures, by means of an appropriate monoid structure.
References
[1]
S. Abramsky. Retracting some paths in process algebra. In CONCUR '96, Concurrency Theory, 7th International Conference, Pisa, Italy, August 26-29, 1996, Proceedings, volume 1119 of LNCS, pages 1--17. Springer, 1996.
[2]
R.M. Burstall and J. Darlington. A transformation system for developing recursive programs. Journal of ACM, 24(1):44--67, 1977.
[3]
W.-N. Chin. Safe fusion of functional expressions II: Further improvements. Journal of Functional Programming, 4(4):515--555, 1994.
[4]
Z. Fülöp and H. Vogler. Syntax-Directed Semantics, Formal Models Based on Tree Transducers. Springer Verlag, 1998.
[5]
H. Ganzinger and R. Giegerich. Attribute coupled grammars. In Proceedings of the ACM SIGPLAN '84 Symposium on Compiler Construction, volume 19(6) of SIGPLAN Notices, pages 157--170, June 1984.
[6]
N. Ghani, P. Johann, T. Uustalu, and V. Vene. Monadic augment and generalised short cut fusion. In International Conference on Functional Programming (ICFP '05), pages 294--305. ACM Press, 2005.
[7]
N. Ghani, T. Uustalu, and V. Vene. Generalizing the augment combinator. In Trends in Functional Programming 5, pages 65--78. Intellect, 2006.
[8]
A. Gill. Cheap Deforestation for Non-strict Functional Languages. PhD thesis, University of Glasgow, 1996.
[9]
A. Gill, J. Launchbury, and S. Peyton Jones. A short cut to deforestation. In Proc. of the Conference on Functional Programming Languages and Computer Architecture, pages 223--232. ACM Press, June 1993.
[10]
J.A. Goguen, J.W. Thatcher, E.G. Wagner, and J.B. Wright. Initial algebra semantics and continuous algebras. J. ACM, 24(1):68--95, 1977.
[11]
P. Johann. A generalization of short-cut fusion and its correctness proof. Higher-Order and Symbolic Computation, 15 4):273--300, 2002.
[12]
A. Joyal, R. Street, and D. Verity. Traced monoidal categories. In Math. Proc. Camb. Phil. Soc., pages 447--468, 1996.
[13]
K. Kakehi, R. Glück, and Y. Futamura. On deforesting parameters of accumulating maps. In Logic Based Program Synthesis and Transformation, 11th International Workshop, LOPSTR 2001, volume 2372 of LNCS, pages 46--56. Springer Verlag, 2001.
[14]
Q. Ma and J.C. Reynolds. Types, abstractions, and parametric polymorphism, part 2. In Proc. of Mathematical Foundations of Programming Semantics (MFPS 1991), volume 598 of LNCS, pages 1--40. Springer Verlag, 1991.
[15]
G. Malcolm. Homomorphisms and promotability. In Mathematics of Program Construction, volume 375 of LNCS, pages 335--347. Springer Verlag, 1989.
[16]
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.
[17]
S. Nishimura. Fusion with stacks and accumulating parameters. In Proc. of the 2004 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, pages 101--112. ACM Press, 2004.
[18]
T. Sheard and L. Fegaras. A fold for all seasons. In International Conference on Functional Programming Languages and Computer Architecture (FPCA'93), pages 233--242. ACM Press, 1993.
[19]
A. Takano and E. Meijer. Shortcut deforestation in calculational form. In Proc. of International Conference on Functional Programming Languages and Computer Architecture (FPCA'95), pages 306--313. ACM Press, 1995.
[20]
J. Voigtländer. Using circular programs to deforest in accumulating parameters. Higher-Order and Symbolic Computation, 17(1), 2004.
[21]
P. Wadler. Theorems for free! In International Conference on Functional Programming and Computer Architecture (FPCA'89), pages 347--359. Addison-Wesley, 1989.
[22]
P. Wadler. Deforestation: transforming programs to eliminate trees. Theoretical Computer Science, 73(2):231--248, June 1990.
Index Terms
- Algebraic fusion of functions with an accumulating parameter and its improvement
Recommendations
Algebraic fusion of functions with an accumulating parameter and its improvement
ICFP '06: Proceedings of the eleventh ACM SIGPLAN international conference on Functional programmingWe present a unifying solution to the problem of fusion of functions, where both the producer function and the consumer function have one accumulating parameter. The key idea in this development is to formulate the producer function as a function which ...
Algebraic fusion of functions with an accumulating parameter and its improvement
This paper develops a new framework for fusion that is designed for eliminating the intermediate data structures involved in the composition of functions that have one accumulating parameter. The new fusion framework comprises two steps: algebraic ...
Algebraic Functions
Let A be an algebra. We say that the functions f 1, . . . , f m : A n A are algebraic on A provided there is a finite system of term-equalities $${{\bigwedge t_{k}(\overline{x}, \overline{z}) = s_{k}(\overline{x}, \overline{z})}}$$ satisfying that for each $${{\overline{a} \in A^{n}}}$$ , the m -tuple $${{(f_{1}(\overline{a}), \ldots , f_{m}(\overline{a}))}}$$ is the unique solution in A m to the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2006308 pages
Copyright © 2006 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 16 September 2006
Published in SIGPLAN Volume 41, Issue 9
Check for updates
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations4Total Citations
- 234Total Downloads
- Downloads (Last 12 months)5
- Downloads (Last 6 weeks)0
Reflects downloads up to 06 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in