I've written about what Template Haskell is, and given an example of what it can be used for, it's time to explain why I was looking at it in the context of my PhD work.

Encoding stream-processing programs

StrIoT is an experimental distributed stream-processing system that myself and others are building in order to explore our research questions. A user of StrIoT writes a stream-processing program, using a set of 8 functional operators provided for the purpose. A simple example is

streamFn :: Stream Int -> Stream Int
streamFn = streamFilter (<15)
         . streamFilter (>5)
         . streamMap (*2)

Our system is distributed: we take a stream-processing program and partition it into sub-programs, which are distributed to and run on separate nodes (perhaps cloud instances, or embedded devices like Raspberry Pis etc.). In order to do that, we need to be able to manipulate the stream-processing program as data. We've initially opted for a graph data-structure, with the vertices in the graph defined as

data StreamVertex = StreamVertex
    { vertexId   :: Int
    , operator   :: StreamOperator
    , parameters :: [String]
    , intype     :: String
    , outtype    :: String
    } deriving (Eq,Show)

A stream-processing program encoded this way, equivalent to the first example

path [ StreamVertex 0 Map    ["(*2)"]  "Int" "Int"
     , StreamVertex 1 Filter ["(>5)"]  "Int" "Int"
     , StreamVertex 2 Filter ["(<15)"] "Int" "Int"
     ]

We can easily manipulate instances of such types, rewrite them, partition them and generate code from them. Unfortunately, this is quite a departure from the first simple code example from the perspective of a user writing their program.

Template Haskell gives us the ability to manipulate code as a data structure, and also to inspect names to gather information about them (their type, etc.). I started looking at TH to see if we could build something where the user-supplied program was as close to that first case as possible.

TH limitations

There are two reasons that we can't easily manipulate a stream-processing definition written as in the first example. The following expressions are equivalent, in some sense, but are not equal, and so yield completely different expression trees when quasi-quoted:

[| streamFilter (<15) . streamFilter (>5) . streamMap (*2) |]
| \s -> streamFilter (<15) (streamFilter (>5) (streamMap (*2) s)) |]
[| streamMap (*2) >>> streamFilter (>5) >>> streamFilter (<15) |]
[| \s -> s & streamMap (*2) & streamFilter (>5) & streamFilter (<15) |]
[| streamFn |] -- a named expression, defined outside the quasi-quotes

In theory, reify can give you the definition of a function from its name, but in practice it doesn't, because this was never implemented. So at the very least we would need to insist that a user included the entirety of a stream-processing program within quasi-quotes, and not split it up into separate bits, with some bits defined outside the quotes and references within (as in the last case above). We would probably have to insist on a consistent approach for composing operators together, such as always use (.) and never >>>, &, etc. which is limiting.

Incremental approach

After a while ruminating on this, and before moving onto something else, I thought I'd try approaching it from the other side. Could I introduce some TH into the existing approach, and improve it? The first thing I've tried is to change the parameters field to TH's ExpQ, meaning the map instance example above would be

StreamVertex 0 Map [ [| (*2) |] ] "Int" "Int"

I worked this through. It's an incremental improvement ease and clarity for the user writing a stream-processing program. It catches a class of programming bugs that would otherwise slip through: the expressions in the brackets have to be syntactically valid (although they aren't type checked). Some of the StrIoT internals are also much improved, particularly the logical operator. Here's an excerpt from a rewrite rule that involves composing code embedded in strings, dealing with all the escaping rules and hoping we've accounted for all possible incoming expression encodings:

let f' = "(let f = ("++f++"); p = ("++p++"); g = ("++g++") in\
         \ \\ (a,b) v -> (f a v, if p v a then g b v else b))"
    a' = "("++a++","++b++")"
    q' = "(let p = ("++p++"); q = ("++q++") in \\v (y,z) -> p v y && q v z)"

And the same section after, manipulating ExpQ types:

let f' = [| \ (a,b) v -> ($(f) a v, if $(p) v a then $(g) b v else b) |]
    a' = [| ($(a), $(b)) |]
    q' = [| \v (y,z) -> $(p) v y && $(q) v z |]

I think the code-generation part of StrIoT could be radically refactored to take advantage of this change but I have not made huge inroads into that.

Next steps

This is, probably, where I am going to stop. This work is very interesting to me but not the main thrust of my research. But incrementally improving the representation gave me some ideas of what I could try next:

  • intype and outtype could be TH Types instead of Strings. This would catch some simple problems like typos, etc., but we could possibly go further, and
  • remove the explicit in-and-out-types and infer their values from the parameters field, as its an expression with some type that should match
  • parameters is a list, because the different stream operators have different arities. streamFilter has one parameter (the filter predicate), so the list should have one element in that case, but streamExpand has none, so it should be empty. We could collapse this to a single ExpQ, which encoded however many parameters are necessary, either in an internal list, or…
  • the operator field could be merged in too, so that the parameters expression was actually a call to the relevant operator with its parameters supplied.

The type would have collapsed down to

data StreamVertex = StreamVertex
    { vertexId   :: Int
    , opAndParams :: ExpQ
    } deriving (Eq,Show)

Example instances might be

StreamVertex 0 [| streamMap (*2) |]
StreamVertex 1 [| streamExpand |]
StreamVertex 2 [| streamScan (\c _ -> c+1) 0 |]

The vertexId field is a bit of wart, but we require that due to the graph data structure that we are using. A change there could eliminate it, too. By this point we are not that far away from where we started, and certainly much closer to the "pure" function application in the very first example.


Comments