Staging With Class

I recently watched Ningning Xie’s conference presentation about the Staging with Class: A Specification for Typed Template Haskell paper that she co-authored. The presentation was given almost a year ago, but the video was not released on YouTube until last week. The paper proposes use of a staged type class constraint (CodeC) to enable use of type classes in typed Template Haskell functions.

While I have used macros in Lisp to write optimized code generators, I had not done so using Template Haskell and did not realize that it was possible. The paper proposes an addition that is necessary to do so using type classes, but it is already possible to do so using concrete types! The presentation uses an odd syntax, however, and this blog entry simply translates the demonstration program to working syntax.

In Template Haskell, Code is a newtype wrapper around monadic computation over typed expressions (TExp). It is parameterized by an underlying monad, but for some reason neither the paper nor the presentation include this detail.

Typed Template Haskell uses typed quotations, which represents expressions to be evaluated in a future stage. The paper uses a fancy font that obscures the syntax, while the presentation uses angle brackets (< and >) for quotation. I have never seen angle brackets used for this in Haskell, and I wonder if they are just pseudocode or if perhaps there is an extension somewhere that uses them… If e is of type Int (e :: Int), then quoting e creates a representation of it ([|| e ||] :: Code m Int for some monad m).

Typed Template Haskell uses typed splices, which extracts expressions from their representations. The paper and presentation both use a single dollar sign ($) for this, but the single dollar sign is actually used for untyped splices while the double dollar sign ($$) is used for typed splices. If e is of type e :: Code m Int, then splicing e extracts the Int value ($$e :: Int).

The paper and presentation present function qpower, which generates unrolled code for computing the power of the passed Int values, a common minimal demonstration of optimized code generation. Translating the syntax as described above, the function is defined as follows.

qpower
  :: Quote m
  => Int
  -> Code m Int
  -> Code m Int
qpower 0 _n = [|| 1 ||]
qpower k  n = [|| $$n * $$(qpower (k - 1) n) ||]

The qpowerFive function is translated as follows.

qpowerFive :: Int -> Int
qpowerFive n = $$(qpower 5 [|| n ||])

The full source is available on GitHub.