Template Haskell for EDSLs

Application to Embedded Domain Specific Languages

Optimisation

Compilers can only reason about and optimise over structures that they are familiar with. When a user writes a module they may define functions which conform (provably) to various algebraic laws. Meta-programming can be used to write optimisation passes that understand the relationship between user defined functions and transform them.

As an example consider the image overlay function from Pan.

type Colour = (Double, Double, Double, Double)
type Point  = (Double, Double)
type Image a = Point -> a

cOver :: Colour -> Colour -> Colour
cOver (r1,g1,b1,a1) (r2,g2,b2,a2) =  (h r1 r2, h g1 g2, h b1 b2, h a1 a2)
   where h x1 x2 = x1 + (1 - a1) * x2

lift2 :: (a -> a -> a) -> (p -> a) -> (p -> a) -> (p -> a)
lift2 h f1 f2 = \p -> h (f1 p) (f2 p)

over :: Image Colour -> Image Colour -> Image Colour
over = lift2 cOver

invisible :: Image Colour
invisible (x,y) = (0,0,0,0)

Now consider the expression invisible `over` im We can prove that this is the same as im (exercise for the reader). But this is not something that the compiler knows or even feasibly could know. Given a compiler one can always think of more optimisations it could do. (There are theorems which prove this to be the case.)

Yet with Template Haskell transforming such an expression is entirely feasible.

Semantic extension

Tool support

More general meta-programing considerations

• Is run-time meta-programming something we desire. Since it can conceivably subsume such other areas as partial evaluation, just-in-time compilation and run-time optimisation, is it something that is worth the complexity of implementation. Further, does the run-time overhead outweigh the benefits?
• Do we reify too much or too little. Have we chosen an appropriate "vantage point" for meta-programming? For instance, I believe that Template Haskell could benefit from a primitive for reifying top-level function declarations. I also believe the solution to the scoping and type-checking problems that arise from allowing the splicing of top-level declarations to be messy.
• Can further improvements be made to the representation of meta-programs? Quasi-quote like mechanisms are an easy to understand means of presenting meta-programs. Can we improve them?
• Can we remove the need for name generation? Template Haskell uses the quotation monad to encapsulate name generation but can we remove the need for this entirely as has been done in some versions of MetaML?
• Should we have access to other parts of the compiler such as the type-checker? While writing some optimisations I found that I did not know the type of literals. The type checker would have been useful at this stage. However, type checking of a fragement of a program may be impossible without further context. With the addition of type classes to Haskell, annotations are sometimes necessary to disambiguate types. Thus it may well occur that a program fragment will be untypable without surrounding context.