Fusing Effectful Comprehensions

Olli Saarikivi, Margus Veanes, Todd Mytkowicz, Madan Musuvathi

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

4 Citations (Scopus)

Abstract

List comprehensions provide a powerful abstraction mechanism for expressing computations over ordered collections of data declaratively without having to use explicit iteration constructs. This paper puts forth effectful comprehensions as an elegant way to describe list comprehensions that incorporate loop-carried state. This is motivated by operations such as compression/decompression and serialization/deserialization that are common in log/data processing pipelines and require loop-carried state when processing an input stream of data. We build on the underlying theory of symbolic transducers to fuse pipelines of effectful comprehensions into a single representation, from which efficient code can be generated. Using background theory reasoning with an SMT solver, our fusion and subsequent reachability based branch elimination algorithms can significantly reduce the complexity of the fused pipelines. Our implementation shows significant speedups over reasonable hand-written code (3.4×, on average) and traditionally fused version of the pipeline (2.6×, on average) for a variety of examples, including scenarios for extracting fields with regular expressions, processing XML with XPath, and running queries over encoded data.
Original languageEnglish
Title of host publicationPLDI 2017 - Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation
PublisherACM
Pages17-32
Number of pages16
ISBN (Electronic)9781450349888
DOIs
Publication statusPublished - 2017
MoE publication typeA4 Article in a conference publication
EventACM SIGPLAN Conference on Programming Language Design and Implementation - Barcelona, Spain
Duration: 18 Jun 201723 Jun 2017
Conference number: 38

Conference

ConferenceACM SIGPLAN Conference on Programming Language Design and Implementation
Abbreviated titlePLDI
CountrySpain
CityBarcelona
Period18/06/201723/06/2017

Keywords

  • transducers
  • comprehensions
  • fusion
  • deforestation
  • reachability analysis
  • monads

Fingerprint Dive into the research topics of 'Fusing Effectful Comprehensions'. Together they form a unique fingerprint.

Cite this