skip to main content
10.1145/1291201.1291216acmconferencesArticle/Chapter ViewAbstractPublication PagesicfpConference Proceedingsconference-collections
Article

A shortcut fusion rule for circular program calculation

Published: 30 September 2007 Publication History

Abstract

Circular programs are a powerful technique to express multiple traversal algorithms as a single traversal function in a lazy setting. In this paper, we present a shortcut deforestation technique to calculate circular programs. The technique we propose takes as input the composition of two functions, such that the first builds an intermediate structure and some additional context information which are then processed by the second one, to produce the final result. Our transformation into circular programs achieves intermediate structure deforestation and multiple traversal elimination. Furthermore, the calculated programs preserve the termination properties of the original ones.

References

[1]
S. Abramsky and A. Jung. Domain theory. In S. Abramsky, D. M. Gabbay, and T. S. E. Maibaum, editors, Handbook of Logic in Computer Science, volume 3, pages 1--168. Clarendon Press, 1994.
[2]
Lex Augusteijn. Sorting morphisms. In Doaitse Swierstra, Pedro Henriques, and José Oliveira, editors, Third Summer School on Advanced Functional Programming, volume 1608 of LNCS, pages 1--27, September 1998.
[3]
R. Bird. Introduction to Functional Programming using Haskell, 2nd edition. Prentice-Hall, UK, 1998.
[4]
Richard S. Bird. Using circular programs to eliminate multiple traversals of data. Acta Inf, 21: 239--250, 1984.
[5]
R. S. Bird and O. de Moor. Algebra of Programming. Prentice Hall, UK, 1997.
[6]
R. Cockett and T. Fukushima. About Charity. Technical Report 92/480/18, University of Calgary, June 1992.
[7]
R. Cockett and D. Spencer. Strong Categorical Datatypes I. In R.A.C. Seely, editor, International Meeting on Category Theory 1991, volume 13 of Canadian Mathematical Society Conference Proceedings, pages 141--169, 1991.
[8]
Nils Anders Danielsson, John Hughes, Patrik Jansson, and Jeremy Gibbons. Fast and loose reasoning is morally correct. In POPL '06: Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 206--217, New York, NY, USA, 2006. ACM Press.
[9]
Olivier Danvy and Mayer Goldberg. There and back again. In ICFP '02: Proceedings of the seventh ACM SIGPLAN international conference on Functional programming, pages 230--234, New York, NY, USA, 2002. ACM Press.
[10]
Oege de Moor, Kevin Backhouse, and S. Doaitse Swierstra. First-class attribute grammars. Informatica (Slovenia), 24(3), 2000.
[11]
Oege de Moor, Simon Peyton-Jones, and Eric Van Wyk. Aspect-oriented compilers. Lecture Notes in Computer Science, 1799, 2000.
[12]
Atze Dijkstra. Stepping through Haskell. PhD thesis, Department of Computer Science, Utrecht University, The Netherlands, November 2005.
[13]
Atze Dijkstra and Doaitse Swierstra. Typing haskell with an attribute grammar (part i). Technical Report UU-CS-2004-037, Institute of Information and Computing Sciences, Utrecht University, 2004.
[14]
João Fernandes and João Saraiva. Tools and Libraries to Model and Manipulate Circular Programs. In Proc. of the ACM SIGPLAN 2007 Workshop on Partial Evaluation and Program Manipulation (PEPM'07), pages 102--111. ACM Press, 2007.
[15]
J. Gibbons. Calculating Functional Programs. In Algebraic and Coalgebraic Methods in the Mathematics of Program Construction, LNCS 2297, pages 148--203. Springer-Verlag, January 2002.
[16]
A. Gill. Cheap Deforestation for Non-strict Functional Languages. PhD thesis, Department of Computing Science, University of Glasgow, UK, 1996.
[17]
Andrew Gill, John Launchbury, and Simon L. Peyton Jones. A short cut to deforestation. In Conference on Functional Programming Languages and Computer Architecture, pages 223--232, June 1993.
[18]
Patricia Johann and Janis Voigtländer. Free theorems in the presence of seq. In Neil D. Jones and Xavier Leroy, editors, 31st Symposium on Principles of Programming Languages, Venice, Italy, Proceedings, volume 39 of SIGPLAN Notices, pages 99--110. ACM Press, January 2004.
[19]
Thomas Johnsson. Attribute grammars as a functional programming paradigm. In Functional Programming Languages and Computer Architecture, pages 154--173, 1987.
[20]
Uwe Kastens, Anthony M. Sloane, and William M. Waite. Generating Software from Specifications. Jones and Bartlett, 2007.
[21]
Matthijs Kuiper and Doaitse Swierstra. Using attribute grammars to derive efficient functional programs. In Computing Science in the Netherlands CSN'87, November 1987.
[22]
John Launchbury and Tim Sheard. Warm fusion: Deriving build-catas from recursive definitions. In Int. Conf. on Functional Programming Languages and Computer Architecture, FPCA'95, La Jolla, San Diego, CA, USA, 25-28 June 1995, pages 314--323. ACM Press, New York, 1995.
[23]
Julia L. Lawall. Implementing Circularity Using Partial Evaluation. In Proceedings of the Second Symposium on Programs as Data Objects PADO II, volume 2053 of LNCS, May 2001.
[24]
Atsushi Ohori and Isao Sasano. Lightweight fusion by fixed point promotion. In POPL '07: Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 143--154, New York, NY, USA, 2007. ACM Press.
[25]
Chris Okasaki. Breadth-first numbering: lessons from a small exercise in algorithm design. ACM SIGPLAN Notices, 35(9):131--136, 2000.
[26]
A Calculational Fusion System HYLO. In IFIP TC 2 Working Conference on Algorithmic Languages and Calculi, Le Bischenberg, France, pages 76--106. Chapman & Hall, February 1997.
[27]
A. Pardo. Generic Accumulations. In IFIP WG2.1 Working Conference on Generic Programming, Dagstuhl, Germany, July 2002.
[28]
A. Pardo. A Calculational Approach to Recursive Programs with Effects. PhD thesis, Technische Universität Darmstadt, October 2001.
[29]
João Saraiva. Purely Functional Implementation of Attribute Grammars. PhD thesis, Department of Computer Science, Utrecht University, The Netherlands, December 1999.
[30]
Doaitse Swierstra, Pablo Azero, and João Saraiva. Designing and Implementing Combinator Languages. In Doaitse Swierstra, Pedro Henriques, and José Oliveira, editors, Third Summer School on Advanced Functional Programming, volume 1608 of LNCS Tutorial, pages 150--206, September 1999.
[31]
S. Doaitse Swierstra and Pablo Azero. Attribute grammars in a functional style. In Systems Implementation 2000, Berlin, 1998. Chapman & Hall.
[32]
A. Takano and E. Meijer. Shortcut to Deforestation in Calculational Form. In Functional Programming Languages and Computer Architecture'95, 1995.
[33]
Janis Voigtländer. Using circular programs to deforest in accumulating parameters. Higher-Order and Symbolic Computation, 17:129--163, 2004. Previous version appeared in ASIA-PEPM 2002, Proceedings, pages 126--137, ACM Press, 2002.
[34]
P. Wadler. Theorems for free! In 4th International Conference on Functional Programming and Computer Architecture, London, 1989.
[35]
P. Wadler. Deforestation: transforming programs to eliminate trees. Theoretical Computer Science, 73:231--248, 1990.

Cited By

View all
  • (2024)Compiling Haskell for Energy Efficiency: Empirical Analysis of Individual TransformationsProceedings of the 39th ACM/SIGAPP Symposium on Applied Computing10.1145/3605098.3635915(1104-1113)Online publication date: 8-Apr-2024
  • (2019)Java Stream FusionProceedings of the XXIII Brazilian Symposium on Programming Languages10.1145/3355378.3355386(30-37)Online publication date: 23-Sep-2019
  • (2019)Watch Out for that Tree! A Tutorial on Shortcut DeforestationCentral European Functional Programming School10.1007/978-3-030-28346-9_1(1-41)Online publication date: 14-Aug-2019
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
Haskell '07: Proceedings of the ACM SIGPLAN workshop on Haskell workshop
September 2007
126 pages
ISBN:9781595936745
DOI:10.1145/1291201
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: 30 September 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. circular programming
  2. deforestation
  3. program calculation
  4. shortcut fusion

Qualifiers

  • Article

Conference

ICFP07
Sponsor:

Acceptance Rates

Overall Acceptance Rate 57 of 143 submissions, 40%

Upcoming Conference

ICFP '25
ACM SIGPLAN International Conference on Functional Programming
October 12 - 18, 2025
Singapore , Singapore

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)1
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Compiling Haskell for Energy Efficiency: Empirical Analysis of Individual TransformationsProceedings of the 39th ACM/SIGAPP Symposium on Applied Computing10.1145/3605098.3635915(1104-1113)Online publication date: 8-Apr-2024
  • (2019)Java Stream FusionProceedings of the XXIII Brazilian Symposium on Programming Languages10.1145/3355378.3355386(30-37)Online publication date: 23-Sep-2019
  • (2019)Watch Out for that Tree! A Tutorial on Shortcut DeforestationCentral European Functional Programming School10.1007/978-3-030-28346-9_1(1-41)Online publication date: 14-Aug-2019
  • (2016)Multiple intermediate structure deforestation by shortcut fusionScience of Computer Programming10.1016/j.scico.2016.07.004132:P1(77-95)Online publication date: 15-Dec-2016
  • (2015)Zipper-Based Modular and Deforested ComputationsCentral European Functional Programming School10.1007/978-3-319-15940-9_10(407-427)Online publication date: 21-Mar-2015
  • (2013)Attribute grammars as tree transducers over cyclic representations of infinite trees and their descriptional compositionTheoretical Computer Science10.5555/2846456.2846501480:C(1-25)Online publication date: 8-Apr-2013
  • (2013)Attribute grammars as tree transducers over cyclic representations of infinite trees and their descriptional compositionTheoretical Computer Science10.1016/j.tcs.2013.02.007480(1-25)Online publication date: Apr-2013
  • (2013)Banana AlgebraScience of Computer Programming10.1016/j.scico.2012.11.00478:10(1845-1870)Online publication date: 1-Oct-2013
  • (2012)Manipulating accumulative functions by swapping call-time and return-time computations*Journal of Functional Programming10.1017/S095679681200011122:3(275-299)Online publication date: 1-May-2012
  • (2012)Program and aspect metrics for MATLABProceedings of the 12th international conference on Computational Science and Its Applications - Volume Part IV10.1007/978-3-642-31128-4_16(217-233)Online publication date: 18-Jun-2012
  • 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