Skip to content

Haskell

Finding the Right Shape: Implementing BLAS in Haskell

Based on a presentation given in March 2017. The slides contain the full source listings, the simplifier output, and the benchmark plots that this post summarises.

There is an idea, first articulated by Lex Augusteijn in his 1998 paper Sorting Morphisms and later made central to Jeremy Gibbons' 2003 chapter Origami Programming, that has stayed with me ever since: many divide-and-conquer algorithms are determined purely by their recursion pattern. Once you have fixed the right shape for the computation, there are essentially no further design decisions to be made. The algorithm writes itself. Fold the problem on the natural axis and the structure of the computation reveals itself; fold it wrong and you end up writing Fortran by hand, special-casing every traversal, unrolling every loop.

lambda-blas was a six-month attempt to test that claim against an unforgiving benchmark: dense numerical linear algebra. Could the inner loops of BLAS, the de facto reference for dense linear algebra since the 1970s, be expressed as simple compositions of folds and unfolds and still run as fast as the reference Fortran? The answer turned out to be yes. The library is lambda-blas and it is public on GitHub.