Higher Order Patterns for Rewrite Rules

Jaro Reinders

This is a practice presentation of my Haskell’24 talk. Abstract:

GHC’s rewrite rules enable programmers to write local program transformation rules for their own functions. The most notable use case are fusion optimizations, which merge multiple traversals of a data structure into one and avoids allocation of intermediate structures. However, GHC’s rewrite rules were too limited to express a rewrite rule that is necessary for proper fusion of the concatMap function in a variant of fusion called stream fusion.

We introduce higher order patterns as a simple extension of GHC’s rewrite rules. Higher order patterns substantially broaden the expressiveness of rewrite rules that involve local variables. In particular they enable the rewriting of concatMap such that it can be properly optimized. We implement a stream fusion framework to replace the existing fusion framework in GHC and evaluate it on GHC’s benchmark suite. Our stream fusion framework with higher order patterns show an average speedup of 7% compared to our stream fusion framework without it. However, our stream fusion framework is not yet able to match the performance of GHC’s existing fusion framework.

Additionally, we show that our higher order patterns can be used to simplify a GHC’s existing mechanism for rolling back failed attempts at fusion and at the same time solve a problem which prevented proper optimization in one example program. However, evaluating it on GHC’s benchmark suite shows a small regression in performance overall.

---

Previous: | Program Synthesis for Dependently Typed Programs
Next: Luka Janjić | Program Synthesis with Dependent Types