• INLIN(E)ing: A case study May 17, 2017

    Ollie Charles recently popped into #ghc to ask about a small program which was taking a long time to compile. In fact, the compiler was taking so long in the simplifier he had to increase the tick factor (a measure of how much work the simplifier is allowed to do) to get compilation to finish. Oleg and I quickly set to work working out what was going on in his program.

    It turned out that a misplaced INLINE pragma was causing a lot of simplification work to be duplicated. Removing the pragma allowed the compiler to operate faster whilst producing the same code.

    Read more

  • Indexed Optics April 10, 2017

    What is an indexed optic? It is an optic which gives you access to an index whilst performing updates.

    It is a simple clear generalisation of a lens but the implementation looks quite complicated. This is due to the desire to reuse the same combinators for both non-indexed and indexed variants. We we will start by explaining a simplified implementation of indexed optics before the technique used in order to reuse the same combinators as ordinary optics.

    Read more

  • Inlining and Specialisation March 20, 2017

    The inliner and specialiser are the two parts of the optimiser which are crucial to writing performant functional programs. They ensure that we can write programs at a high-level of abstraction which are simplified when eventually used with concrete arguments.

    The inliner’s job is to replace a function with its definition. This removes one layer of indirection and most importantly allows other optimisations to fire. The specialiser is important for optimising code which uses type classes. Type classes are desugared into dictionary passing style but the specialiser removes a layer of indirection by creating new functions with the relevant dictionaries already supplied.

    This document will explain the basics of these two parts of the optimiser and some user-facing options which can be used to control them.

    Read more

  • Motivating the Foldable Type Class September 16, 2016

    Something I have never seen articulated is why the Foldable type class exists. It is lawless apart from the free theorems which leads to ad-hoc definitions of its methods. What use is the abstraction if not to enable us to reason more easily about our programs? This post aims to articulate some justification stemming from the universality of folds.

    In brief, here is the argument.

    1. For inductive data types, the fold is unique defined as a consequence of initiality.
    2. The Foldable type class is a way to exploit this universality without having to define all of our data types as the fixed points of base functors.
    3. The uneasiness comes from this impedence mismatch between points 1 and 2.
    Read more

  • Why do pattern synonyms not cause type refinement? June 18, 2016

    Pattern synonyms can’t (safely) cause any additional type refinement than their definition dictates. This means that they can’t be used to provide a GADT-like interface when the underlying representation is not a GADT. The purpose of this note is to explain this restriction.

    Read more