Performant Polymorphism: Rewrite Rules in Haskell

A SkillsCast for this session is not available.

GHC usually does an excellent job of transforming well written Haskell code into efficient machine code, but sometimes “fast” is not “fast enough”. Common optimisation techniques when dealing with concrete data types often do not apply to polymorphic data and functions. A concise, generic algorithm may perform poorly for some types, but providing a faster version with a less polymorphic type sacrifices reusability and parametricity! What’s a principled programmer to do?

Fortunately GHC has got your back here, too. In this talk we will learn about GHC’s *rewrite rules* feature, which can be used for substituting alternative, better performing implementations of polymorphic functions at particular (less polymorphic) types, without changing the type signature that users see, preserving reuse and parametricity. We will see also how to define transformation rules that employ theorems (free or otherwise) to optimise programs.

We will also briefly examine how rules are applied by observing the firing of rules and changes effected in the produced Core (GHC’s fully desugared intermediate language), and see how to control the order of inlining and rewrite rules to achieve the desired outcome.

Finally, we’ll look at a real-world example of how rewrite rules are used in the ‘fresnel'[1] library, a unified parser-printer combinator library based on the ‘Cons’ abstraction from the ‘lens’ library, to dramatically speed up printing for certain output types.

This will be a hands-on talk with live coding, benchmarking and profiling (no optimising without metrics!) and Core spelunking. Audience members familiar with Haskell should expect to learn some basics of Haskell benchmarking and profiling, gain an understanding of when and how to use rewrite rules in their own code, and walk out feeling comfortable (or less trepidatious, perhaps) about reading and analysing their programs’ Core.

YOU MAY ALSO LIKE:

• Infinite Scroll: Lazy Lists in the Brick TUI Library (SkillsCast recorded in May 2019)
• Making Less of the Web with Feature Policy (SkillsCast recorded in July 2019)
• Experimenting with Distributed Data Processing in Haskell (SkillsCast recorded in May 2019)