research-article

The HERMIT in the stream: fusing stream fusion's concatMap

Authors:

Christian Hoener zu Siederdissen,

Andy GillAuthors Info & Claims

PEPM '14: Proceedings of the ACM SIGPLAN 2014 Workshop on Partial Evaluation and Program Manipulation

Pages 97 - 108

https://doi.org/10.1145/2543728.2543736

Published: 11 January 2014 Publication History

Abstract

Stream Fusion, a popular deforestation technique in the Haskell community, cannot fuse the concatMap combinator. This is a serious limitation, as concatMap represents computations on nested streams. The original implementation of Stream Fusion used the Glasgow Haskell Compiler's user-directed rewriting system. A transformation which allows the compiler to fuse many uses of concatMap has previously been proposed, but never implemented, because the host rewrite system was not expressive enough to implement the proposed transformation. In this paper, we develop a custom optimization plugin which implements the proposed concatMap transformation, and study the effectiveness of the transformation in practice. We also provide a new translation scheme for list comprehensions which enables them to be optimized. Within this framework, we extend the transformation to monadic streams. Code featuring uses of concatMap experiences significant speedup when compiled with this optimization. This allows Stream Fusion to outperform its rival, foldr/build, on many list computations, and enables performance-sensitive code to be expressed at a higher level of abstraction.

References

[1]

D. Burkett, J. Blitzer, and D. Klein. Joint Parsing and Alignment with Weakly Synchronized Grammars. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 127--135. Association for Computational Linguistics, 2010.

Digital Library

[2]

D. Coutts. phStream Fusion: Practical Shortcut Fusion for Coinductive Sequence Types. PhD thesis, University of Oxford, 2010.

[3]

D. Coutts, R. Leshchinskiy, and D. Stewart. Stream fusion: From lists to streams to nothing at all. In Proceedings of the 12th ACM SIGPLAN International Conference on Functional Programming, pages 315--326, Freiburg, Germany, 2007. ACM.

Digital Library

[4]

A. Farmer, A. Gill, E. Komp, and N. Sculthorpe. The HERMIT in the machine: A plugin for the interactive transformation of GHC core language programs. In Proceedings of the ACM SIGPLAN Haskell Symposium, Haskell '12, pages 1--12. ACM, 2012. 10.1145/2364506.2364508.

Digital Library

[5]

A. Gill. Cheap deforestation for non-strict functional languages. PhD thesis, The University of Glasgow, January 1996.

[6]

A. Gill. A Haskell hosted DSL for writing transformation systems. In Proceedings of the IFIP TC 2 Working Conference on Domain-Specific Languages, DSL '09, pages 285--309. Springer-Verlag, July 2009.

Digital Library

[7]

A. Gill, J. Launchbury, and S. L. Peyton Jones. A short cut to deforestation. pages 223--232. ACM Press, 1993.

Digital Library

[8]

J.-Y. Girard. Interprétation fonctionelle et élimination des coupures de l'arithmétique d'ordre supérieur. PhD thesis, Université Paris VII, 1972.

[9]

T. Grosser, H. Zheng, R. Aloor, A. Simbürger, A. Größlinger, and L.-N. Pouchet. Polly - Polyhedral optimization in LLVM. In First International Workshop on Polyhedral Compilation Techniques, 2011.

[10]

D. Grune and C. J. Jacobs. Parsing Techniques: A Practical Guide. Springer-Verlag New York Inc, 2008.

Digital Library

[11]

R. Hinze, T. Harper, and D. W. James. Theory and Practice of Fusion. Implementation and Application of Functional Languages, pages 19--37, 2011.

Digital Library

[12]

C. Höner zu Siederdissen. Sneaking around concatMap: Efficient combinators for dynamic programming. In Proceedings of the 17th ACM SIGPLAN International Conference on Functional Programming, pages 215--226, Copenhagen, Denmark, 2012. ACM.

Digital Library

[13]

C. Höner zu Siederdissen, I. L. Hofacker, and P. F. Stadler. How to Multiply Dynamic Programming Algorithms. In Brazilian Symposium on Bioinformatics (BSB 2013), Lecture Notes in Bioinformatics, volume 8213. Springer, Heidelberg, 2013.

Digital Library

[14]

F. W. Huang, J. Qin, C. M. Reidys, and P. F. Stadler. Partition function and base pairing probabilities for RNA--RNA interaction prediction. Bioinformatics, 25 (20): 2646--2654, 2009.

Digital Library

[15]

C. Lattner and V. Adve. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. In Code Generation and Optimization, 2004. CGO 2004. International Symposium on, pages 75--86. IEEE, 2004.

Digital Library

[16]

B. Lippmeier, M. M. Chakravarty, G. Keller, and A. Robinson. Data Flow Fusion with Series Expressions in Haskell. In Proceedings of the 2013 ACM SIGPLAN Haskell Symposium, Haskell '13, pages 93--104. ACM, 2013.

Digital Library

[17]

G. Mainland, R. Leshchinskiy, and S. Peyton Jones. Exploiting Vector Instructions with Generalized Stream Fusion. In Proceedings of the 18th ACM SIGPLAN International Conference on Functional Programming, pages 37--48, 2013.

Digital Library

[18]

B. O'Sullivan. http://hackage.haskell.org/package/criterion.

[19]

W. Partain. The nofib Benchmark Suite of Haskell Programs. In Proceedings of the 1992 Glasgow Workshop on Functional Programming, pages 195--202, 1993.

Digital Library

[20]

S. Peyton Jones, editor. phHaskell 98 Language and Libraries -- The Revised Report. Cambridge University Press, Cambridge, England, 2003.

[21]

S. Peyton Jones. Call-pattern Specialisation for Haskell Programs. In Proceedings of the 12th ACM SIGPLAN International Conference on Functional Programming, ICFP '07, pages 327--337. ACM, 2007.

Digital Library

[22]

J. C. Reynolds. Towards a theory of type structure. In Colloque sur la Programmation, volume 19 of Lecture Notes in Computer Science, pages 408--423. Springer-Verlag, 1974.

Digital Library

[23]

A. Santos. Compilation by Transformation in Non-Strict Functional Languages. PhD thesis, University of Glasgow, 1995.

[24]

N. Sculthorpe, A. Farmer, and A. Gill. The HERMIT in the tree: Mechanizing program transformations in the GHC core language. In Implementation and Application of Functional Languages 2012, volume 8241 of Lecture Notes in Computer Science. Springer, 2013.

[25]

N. Sculthorpe, N. Frisby, and A. Gill. The Kansas University Rewrite Engine: A Haskell-embedded strategic programming language with custom closed universes. Submitted to the Journal of Functional Programming, 2013.

[26]

M. Sulzmann, M. M. T. Chakravarty, S. Peyton Jones, and K. Donnelly. System F with type equality coercions. In Types in Language Design and Implementaion, pages 53--66. ACM, 2007.

Digital Library

[27]

J. Svenningsson. Shortcut Fusion for Accumulating Parameters Zip-like Functions. PhD thesis, 2002.

[28]

D. A. Terei and M. M. Chakravarty. An LLVM Backend for GHC. In Proceedings of the third ACM Haskell Symposium, pages 109--120. ACM, 2010.

Digital Library

[29]

P. Wadler. List comprehensions. In S. Peyton Jones, editor, The Implementation of Functional Programming Languages, chapter 7. Prentice Hall International, 1987.

[30]

P. Wadler. Deforestation: Transforming programs to eliminate trees. In Proceedings of the 2nd European Symposium on Programming, pages 344--358, London, UK, UK, 1988. Springer-Verlag.

Digital Library

[31]

R. C. Waters. Automatic transformation of series expressions into loops. ACM Trans. Program. Lang. Syst., 13 (1): 52--98, Jan. 1991.

Digital Library

[32]

B. A. Yorgey, S. Weirich, J. Cretin, S. Peyton Jones, D. Vytiniotis, and J. P. Magalhaes. Giving Haskell a promotion. In Types in Language Design and Implementation, pages 53--66. ACM, 2012.

Digital Library

Cited By

Reinders JVazou NMorris J(2024)Higher Order Patterns for Rewrite RulesProceedings of the 17th ACM SIGPLAN International Haskell Symposium10.1145/3677999.3678275(14-26)Online publication date: 29-Aug-2024
https://dl.acm.org/doi/10.1145/3677999.3678275
Shaikhha AScholz BKameyama Y(2022)Deep Fusion for Efficient Nested Recursive ComputationsProceedings of the 21st ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3564719.3568698(33-44)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3564719.3568698
Mohan SVenkatakrishnan AHartzler A(2020)Designing an AI Health Coach and Studying Its Utility in Promoting Regular Aerobic ExerciseACM Transactions on Interactive Intelligent Systems10.1145/336650110:2(1-30)Online publication date: 30-May-2020
https://dl.acm.org/doi/10.1145/3366501
Show More Cited By

Index Terms

The HERMIT in the stream: fusing stream fusion's concatMap
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Source code generation

Recommendations

Stream fusion: from lists to streams to nothing at all
Proceedings of the ICFP '07 conference

This paper presents an automatic deforestation system, stream fusion, based on equational transformations, that fuses a wider range of functions than existing short-cut fusion systems. In particular, stream fusion is able to fuse zips, left folds and ...
Stream fusion: from lists to streams to nothing at all
ICFP '07: Proceedings of the 12th ACM SIGPLAN international conference on Functional programming

This paper presents an automatic deforestation system, stream fusion, based on equational transformations, that fuses a wider range of functions than existing short-cut fusion systems. In particular, stream fusion is able to fuse zips, left folds and ...
A library writer's guide to shortcut fusion
Haskell '11: Proceedings of the 4th ACM symposium on Haskell

There are now a variety of shortcut fusion techniques in the wild for removing intermediate data structures in Haskell. They are often presented, however, specialised to a specific data structure and interface. This can make it difficult to transfer ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PEPM '14: Proceedings of the ACM SIGPLAN 2014 Workshop on Partial Evaluation and Program Manipulation

January 2014

202 pages

ISBN:9781450326193

DOI:10.1145/2543728

Program Chairs:
Wei-Ngan Chin
National University of Singapore, Singapore
,
Jurriaan Hage
Utrecht University, Netherlands

Copyright © 2014 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 the author(s) 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

SIGPLAN: ACM Special Interest Group on Programming Languages

In-Cooperation

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 January 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

POPL '14

Sponsor:

SIGPLAN

POPL '14: The 41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

January 20 - 21, 2014

California, San Diego, USA

Acceptance Rates

PEPM '14 Paper Acceptance Rate 17 of 22 submissions, 77%;

Overall Acceptance Rate 66 of 120 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
142
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)1

Reflects downloads up to 23 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Reinders JVazou NMorris J(2024)Higher Order Patterns for Rewrite RulesProceedings of the 17th ACM SIGPLAN International Haskell Symposium10.1145/3677999.3678275(14-26)Online publication date: 29-Aug-2024
https://dl.acm.org/doi/10.1145/3677999.3678275
Shaikhha AScholz BKameyama Y(2022)Deep Fusion for Efficient Nested Recursive ComputationsProceedings of the 21st ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3564719.3568698(33-44)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3564719.3568698
Mohan SVenkatakrishnan AHartzler A(2020)Designing an AI Health Coach and Studying Its Utility in Promoting Regular Aerobic ExerciseACM Transactions on Interactive Intelligent Systems10.1145/336650110:2(1-30)Online publication date: 30-May-2020
https://dl.acm.org/doi/10.1145/3366501
Anderson ADodge JSadarangani AJuozapaitis ZNewman EIrvine JChattopadhyay SOlson MFern ABurnett M(2020)Mental Models of Mere Mortals with Explanations of Reinforcement LearningACM Transactions on Interactive Intelligent Systems10.1145/336648510:2(1-37)Online publication date: 30-May-2020
https://dl.acm.org/doi/10.1145/3366485
Handley MHutton G(2019)Improving HaskellTrends in Functional Programming10.1007/978-3-030-18506-0_6(114-135)Online publication date: 24-Apr-2019
https://doi.org/10.1007/978-3-030-18506-0_6
Parreaux LShaikhha AKoch C(2017)Quoted staged rewriting: a practical approach to library-defined optimizationsACM SIGPLAN Notices10.1145/3170492.313604352:12(131-145)Online publication date: 23-Oct-2017
https://dl.acm.org/doi/10.1145/3170492.3136043
Parreaux LShaikhha AKoch CFlatt MErdweg S(2017)Quoted staged rewriting: a practical approach to library-defined optimizationsProceedings of the 16th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3136040.3136043(131-145)Online publication date: 23-Oct-2017
https://dl.acm.org/doi/10.1145/3136040.3136043
Scherer G(2017)Deciding equivalence with sums and the empty typeACM SIGPLAN Notices10.1145/3093333.300990152:1(374-386)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1145/3093333.3009901
Kiselyov OBiboudis APalladinos NSmaragdakis Y(2017)Stream fusion, to completenessACM SIGPLAN Notices10.1145/3093333.300988052:1(285-299)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1145/3093333.3009880
Brown MPalsberg J(2017)Typed self-evaluation via intensional type functionsACM SIGPLAN Notices10.1145/3093333.300985352:1(415-428)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1145/3093333.3009853
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents