Publications - Published papers

Please find below publications of our group. Currently, we list 565 papers. Some of the publications are in collaboration with the group of Sonja Prohaska and are also listed in the publication list for her individual group. Access to published papers (access) is restricted to our local network and chosen collaborators. If you have problems accessing electronic information, please let us know:

©NOTICE: All papers are copyrighted by the authors; If you would like to use all or a portion of any paper, please contact the author.

The HERMIT in the Stream

Andrew Farmer, Christian Höner zu Siederdissen, and Andy Gill

Download


PREPRINT 14-002: [ PDF ]
[ Publishers's page ]  paperID

Status: Published


Proceedings of the ACM SIGPLAN 2014 workshop on Partial evaluation and program manipulation: 97--108

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.

Keywords


keywords