A three-stage program you definitely want to write February 14, 2019

Writing programs explicitly in stages gives you guarantees that abstraction will be removed. A guarantee that the optimiser most certainly does not give you.

After spending the majority of my early 20s inside the optimiser, I decided enough was enough and it was time to gain back control over how my programs were partially evaluated.

So in this post I’ll give an example of how I took back control and eliminated two levels of abstraction for an interpreter by writing a program which runs in three stages.

Enter: An applicative interpreter for Hutton’s razor.

Written simply at one level, there are two levels of abstraction which could be failed to be eliminated.

  1. If we statically know the expression we can eliminate Expr.
  2. If we statically know which Applicative then we can remove the indirection from the typeclass.

Using typed Template Haskell we’ll work out how to remove both of these layers.

Read more

Implementing Nested Quotations January 31, 2019

Quotation is one of the key elements of metaprogramming. Quoting an expression e gives us a representation of e.

[| e |] :: Repr

What this representation is depends on the metaprogramming framework and what we can do with the representation depends on the representation. The most common choice is to dissallow any inspection of the representation type relying on the other primative operation, the splice, in order to insert quoted values into larger programs.

The purpose of this post is to explain how to implemented nested quotations. From our previous example, quoting a term e, gives us a term which represents e. It follows that we should be allowed to nest quotations so that quoting a quotation gives us a representation of that quotation.

[| [| 4 + 5 |] |]

However, nesting brackets in this manner has been disallowed in Template Haskell for a number of years despite nested splices being permitted. I wondered why this restriction was in place and it seemed that no one knew the answer. It turns out, there was no technical reason and implementing nested brackets is straightforward once you think about it correctly.

Read more

Packaging a Haskell library for artefact evaluation using nix September 19, 2018

This year I packaged two artefacts for the ICFP artefact evaluation process. This post explains the system I used to make it easy to produce the docker images using nix. I hope this documentation will be useful for anyone else submitting a Haskell library for evaluation.

The end result will be an artefact.nix file which is used to build a docker image to submit. It will be an entirely reproducible process as we will fix the versions of all the dependencies we use.

Read more

Using funflow to cache a nix based workflow September 12, 2018

My latest project has been to plot a map of orienteering maps in the UK. This post explains the technical aspects behind the project and primarily the use of funflow to turn my assortment of scripts into into a resumable workflow.

There was nothing wrong with my ad-hoc python and bash scripts but they downloaded and regenerated the whole output every time. The whole generation takes about 2 hours so it’s desirable to only recompute the necessary portions. This is where funflow comes in, by stringing together these scripts in their DSL, you get caching for free. The workflow is also highly parallelisable so in the future I could distribute the work across multiple machines if necessary.

The code for the project can be found here.

Read more

Specifying how a plugin affects recompilation August 10, 2018

Plugins have existed for a long time in GHC. The first plugins were implemented in 2008 by Max Bolingbroke. They enabled users to modify the optimisation pipeline. They ran after desugaring and hence were called “core” plugins. Later, Adam Gundry implemented what I shall refer to as “constraint solver” plugins which allow users to provide custom solver logic to solve additional constraints. Recently, Boldizsár Németh has extended the number of extension points again with a set of plugins which can inspect and modify the syntax AST. Plugins can run after parsing, renaming or type checking and hence are called “source” plugins.

The idea behind plugins was great - a user can extend the compiler in their own specific way without having to modify the source tree and rebuild the compiler from scratch. It is far more convenient to write a plugin than to use a custom compiler. However, if a user wants to use a plugin, they will find that every module where the plugin is enabled is always recompiled, even if the source code didn’t change at all. Why is this? Well, a plugin can do anything, it could read the value from a temperature sensor and insert the room temperature into the program. Thus, we would always need to recompile a module if the temperature reading changed as it would affect what our program did.

However, there are also “pure” plugins, whose output is only affected by the program which is passed as in input. For these plugins, if the source code doesn’t change then we don’t need to do any recompilation.

This post is about a new metadata field which I added to the Plugin data type which specifies how a plugin should affect recompilation. This feature will be present in GHC 8.6.

Read more