skip to main content
10.1145/1190216.1190241acmconferencesArticle/Chapter ViewAbstractPublication PagespoplConference Proceedingsconference-collections
Article

Lightweight fusion by fixed point promotion

Published: 17 January 2007 Publication History

Abstract

This paper proposes a lightweight fusion method for general recursive function definitions. Compared with existing proposals, our method has several significant practical features: it works for general recursive functions on general algebraic data types; it does not produce extra runtime overhea (except for possible code size increase due to the success of fusion); and it is readily incorporated in standard inlining optimization. This is achieved by extending the ordinary inlining process with a new fusion law that transforms a term of the form f o (fixgλx.E) to a new fixed point term fixhλx.E′ by promoting the function f through the fixed point operator. This is a sound syntactic transformation rule that is not sensitive to the types of f and g. This property makes our method applicable to wide range of functions including those with multi-parameters in both curried and uncurried forms. Although this method does not guarantee any form of completeness, it fuses typical examples discussed in the literature and others that involve accumulating parameters, either in the tt foldl-like specific forms or in general recursive forms, without any additional machinery. In order to substantiate our claim, we have implemented our method in a compiler. Although it is preliminary, it demonstrates practical feasibility of this method.

References

[1]
R. Burstall and J. Darlington. A transformation system for developing recursive programs. Journal of the ACM, 24(1):44--67, 1977.
[2]
M. Chakravarty and G. Keller. Functional array fusion. In Proc. ACM International Conference on Functional Programming, pages 205--216, 2001.
[3]
W-N. Chin. Safe fusion on functional expression. In Proc. ACM Conference on Lisp and Functional Programming, pages 11--20, 1992.
[4]
O. Chitil. Type inference builds a short cut to deforestation. In Proc. ACM International Conference on Functional Programming, pages 249--260, 1999.
[5]
N. Ghani, P. Johann, T. Uustalu, and V. Vene. Monadic augment and generalised short cut fusion. In Proc. ACM International Conference on Functional Programming, pages 294--305, 2005.
[6]
A. Gill, J. Launchbury, and S. Peyton Jones. A short cut to deforestation. In Proc. International Conference on Functional Programming Languages and Computer Architecture, pages 223--232, 1993.
[7]
A. Gill. Cheap Deforestation for Non-strict Functional Languages. Ph.D thesis, University of Glasgow, 1996.
[8]
M. Hasegawa and Y. Kakutani. Axioms for recursion in call-by-value. Higher-Order and Symbolic Computation, 15(2-3):235--264, 2002.
[9]
Z. Hu, H. Iwasaki, and M. Takeichi. Deriving structural hylomorphisms from recursive definitions. In Proc. ACM International Conference on Functional Programming, pages 73--82, 1996.
[10]
P. Johann and E. Visser. Warm fusion in Stratego: A case study in generation of program transformation systems. Annals of Mathematics and Artificial Intelligence, 29(1-4):1--34, 2000.
[11]
S. Katsumata and S. Nishimura. Algebraic fusion of functions with an accumulating parameter and its improvement. In Proc. ACM International Conference on Functional Programming, pages 227--238, 2006.
[12]
J. Launchbury and T. Sheard. Warm fusion: Deriving build-catas from recursive definitions. In Proc. ACM Conference on Functional Programming Languages and Computer Architecture, pages 314--323, 1995.
[13]
G. Malcolm. Homomorphism and promotability. In Proc. Mathematics of Program Construction, pages 335--347, 1989.
[14]
E. Meijer, M. Fokkinga, and R. Paterson. Functional programming with bananas, lenses, envelopes and barbed wire. In Proc. International Conference on Functional Programming Languages and Computer Architecture (FPCA'91), Lecture Notes in Computer Science 523, pages 124--144, 1991.
[15]
L. Nemeth and S. Peyton Jones. A design for warm fusion. In Proc. International Workshop on Implementation of Functional Languages, pages 381--393, 1998.
[16]
Y. Onoue, Z. Hu, H. Iwasaki, and M. Takeichi. Verification of practical effectiveness of program fusion (in Japanese). Computer Software, 17(3):81--85, 2000.
[17]
S. Peyton Jones, A. Tolmach, and T. Hoare. Playing by the rules: rewriting as a practical optimisation technique in GHC. In Proc. ACM Haskell workshop, 2001.
[18]
D. Sands. Proving the correctness of recursion-based automatic program transformations. Theoretical Computer Science, 167(1-2):193--233, 1996.
[19]
T. Sheard and L. Fegaras. A fold for all seasons. In Proc. Functional Programming Languages and Computer Architecture, pages 233--242, 1993.
[20]
SML# home page. http://www.riec.tohoku.ac.jp/smlsharp/, 2006.
[21]
J. Svenningsson. Shortcut fusion for accumulating parameters & zip-like functions. In Proc. ACM International Conference on Functional Programming, pages 124--132, 2002.
[22]
A. Takano and E. Meijer. Shortcut deforestation in calculational form. In Proc. ACM/IFIP Conference on Functional Programming Languages and Computer Architecture, pages 306--313, 1995.
[23]
P. Wadler. Deforestation: transforming programs to eliminate trees. Theoretical Computer Science, 73:231--248, 1990. Special issue of selected papers from 2'nd European Symposium on Programming.

Cited By

View all
  • (2024)The Long Way to Deforestation: A Type Inference and Elaboration Technique for Removing Intermediate Data StructuresProceedings of the ACM on Programming Languages10.1145/36746348:ICFP(249-283)Online publication date: 15-Aug-2024
  • (2024)Fusing Direct Manipulations into Functional ProgramsProceedings of the ACM on Programming Languages10.1145/36328838:POPL(1211-1238)Online publication date: 5-Jan-2024
  • (2023)The Tortoise and the Hare Algorithm for Finite Lists, CompositionallyACM Transactions on Programming Languages and Systems10.1145/356461945:1(1-35)Online publication date: 3-Mar-2023
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
POPL '07: Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages
January 2007
400 pages
ISBN:1595935754
DOI:10.1145/1190216
  • cover image ACM SIGPLAN Notices
    ACM SIGPLAN Notices  Volume 42, Issue 1
    Proceedings of the 2007 POPL Conference
    January 2007
    379 pages
    ISSN:0362-1340
    EISSN:1558-1160
    DOI:10.1145/1190215
    Issue’s Table of Contents
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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 January 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. fixed point
  2. fusion
  3. inlining

Qualifiers

  • Article

Conference

POPL07

Acceptance Rates

POPL '07 Paper Acceptance Rate 36 of 198 submissions, 18%;
Overall Acceptance Rate 860 of 4,328 submissions, 20%

Upcoming Conference

POPL '26

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)15
  • Downloads (Last 6 weeks)2
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)The Long Way to Deforestation: A Type Inference and Elaboration Technique for Removing Intermediate Data StructuresProceedings of the ACM on Programming Languages10.1145/36746348:ICFP(249-283)Online publication date: 15-Aug-2024
  • (2024)Fusing Direct Manipulations into Functional ProgramsProceedings of the ACM on Programming Languages10.1145/36328838:POPL(1211-1238)Online publication date: 5-Jan-2024
  • (2023)The Tortoise and the Hare Algorithm for Finite Lists, CompositionallyACM Transactions on Programming Languages and Systems10.1145/356461945:1(1-35)Online publication date: 3-Mar-2023
  • (2023)Folding left and right matters: Direct style, accumulators, and continuationsJournal of Functional Programming10.1017/S095679682200015633Online publication date: 14-Feb-2023
  • (2021)Efficient compilation of algebraic effect handlersProceedings of the ACM on Programming Languages10.1145/34854795:OOPSLA(1-28)Online publication date: 15-Oct-2021
  • (2018)Refunctionalization of abstract abstract machines: bridging the gap between abstract abstract machines and abstract definitional interpreters (functional pearl)Proceedings of the ACM on Programming Languages10.1145/32368002:ICFP(1-28)Online publication date: 30-Jul-2018
  • (2017)A functional reformulation of UnCAL graph-transformations: or, graph transformation as graph reductionProceedings of the 2017 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation10.1145/3018882.3018883(71-82)Online publication date: 2-Jan-2017
  • (2014)Deriving interpretations of the gradually-typed lambda calculusProceedings of the ACM SIGPLAN 2014 Workshop on Partial Evaluation and Program Manipulation10.1145/2543728.2543742(157-168)Online publication date: 11-Jan-2014
  • (2014)Context-preserving XQuery fusionMathematical Structures in Computer Science10.1017/S096012951300008X25:4(916-941)Online publication date: 10-Nov-2014
  • (2013)A synthetic operational account of call-by-need evaluationProceedings of the 15th Symposium on Principles and Practice of Declarative Programming10.1145/2505879.2505898(97-108)Online publication date: 16-Sep-2013
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media