Skip to main content
Springer Nature Link
Log in

Semantics and Pragmatics of New Shortcut Fusion Rules

  • Conference paper
Functional and Logic Programming (FLOPS 2008)

Part of the book series: Lecture Notes in Computer Science ((LNPSE,volume 4989))

Included in the following conference series:

  • 383 Accesses

Abstract

We study various shortcut fusion rules for languages like Haskell. Following a careful semantic account of a recently proposed rule for circular program transformation, we propose a new rule that trades circularity for higher-orderedness, and thus attains better semantic properties. This also leads us to revisit the original foldr/build-rule, as well as its dual, and to develop variants that do not suffer from detrimental impacts of Haskell’s mixed strict/nonstrict semantics. Throughout, we offer pragmatic insights about our new rules to investigate also their relative effectiveness, rather than just their semantic correctness.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Coutts, D., Leshchinskiy, R., Stewart, D.: Stream fusion: From lists to streams to nothing at all. In: International Conference on Functional Programming, Proceedings, pp. 315–326. ACM Press, New York (2007)

    Chapter  Google Scholar 

  2. Domínguez, F., Pardo, A.: Program fusion with paramorphisms. In: Mathematically Structured Functional Programming, Proceedings. Electronic Workshops in Computing, British Computer Society (2006)

    Google Scholar 

  3. Fernandes, J.P., Pardo, A., Saraiva, J.: A shortcut fusion rule for circular program calculation. In: Haskell Workshop, Proceedings, pp. 95–106. ACM Press, New York (2007)

    Chapter  Google Scholar 

  4. Gill, A., Launchbury, J., Peyton Jones, S.L.: A short cut to deforestation. In: Functional Programming Languages and Computer Architecture, Proceedings, pp. 223–232. ACM Press, New York (1993)

    Chapter  Google Scholar 

  5. Johann, P.: A generalization of short-cut fusion and its correctness proof. Higher-Order and Symbolic Computation 15(4), 273–300 (2002)

    Article  MATH  Google Scholar 

  6. Johann, P., Voigtländer, J.: The impact of \(\mathit{seq}\) on free theorems-based program transformations. Fundamenta Informaticae 69(1–2), 63–102 (2006)

    MathSciNet  MATH  Google Scholar 

  7. Pettorossi, A., Proietti, M.: Importing and exporting information in program development. In: Partial Evaluation and Mixed Computation, Proceedings, pp. 405–425. North-Holland, Amsterdam (1987)

    Google Scholar 

  8. Peyton Jones, S.L.: Call-pattern specialisation for Haskell programs. In: International Conference on Functional Programming, Proceedings, pp. 327–337. ACM Press, New York (2007)

    Chapter  Google Scholar 

  9. Peyton Jones, S.L., Lester, D.: A modular fully-lazy lambda lifter in Haskell. Software Practice and Experience 21(5), 479–506 (1991)

    Article  Google Scholar 

  10. Svenningsson, J.: Shortcut fusion for accumulating parameters & zip-like functions. In: International Conference on Functional Programming, Proceedings, pp. 124–132. ACM Press, New York (2002)

    Google Scholar 

  11. Takano, A., Meijer, E.: Shortcut deforestation in calculational form. In: Functional Programming Languages and Computer Architecture, Proceedings, pp. 306–313. ACM Press, New York (1995)

    Chapter  Google Scholar 

  12. Voigtländer, J.: Concatenate, reverse and map vanish for free. In: International Conference on Functional Programming, Proceedings, pp. 14–25. ACM Press, New York (2002)

    Google Scholar 

  13. Voigtländer, J.: Using circular programs to deforest in accumulating parameters. Higher-Order and Symbolic Computation 17(1–2), 129–163 (2004)

    Article  MATH  Google Scholar 

  14. Voigtländer, J.: Proving correctness via free theorems: The case of the destroy/build-rule. In: Partial Evaluation and Semantics-Based Program Manipulation, Proceedings, pp. 13–20. ACM Press, New York (2008)

    Google Scholar 

  15. Wadler, P.: Theorems for free! In: Functional Programming Languages and Computer Architecture, Proceedings, pp. 347–359. ACM Press, New York (1989)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Theoretische Informatik, Technische Universität Dresden, 01062, Dresden, Germany

    Janis Voigtländer

Authors
  1. Janis Voigtländer
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Jacques Garrigue Manuel V. Hermenegildo

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Voigtländer, J. (2008). Semantics and Pragmatics of New Shortcut Fusion Rules. In: Garrigue, J., Hermenegildo, M.V. (eds) Functional and Logic Programming. FLOPS 2008. Lecture Notes in Computer Science, vol 4989. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78969-7_13

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-78969-7_13

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-78968-0

  • Online ISBN: 978-3-540-78969-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation