Domain-Specific Languages and Code Synthesis Using Haskell (2014)

---

Monadic reification has to do with the difficulty of getting a data/AST representation of a monadic value. This seems possible since monads sort of by their virtue are about reifying some amount of a computation (i.e. the Free monad) but we get stuck because we can embed Haskell ("host" or "meta" language) functions into the Monads meaning that we cannot "see" into the binding structure there. If we want to use a monadic interface to create an AST fragment and then compile it later we get stuck. But, there are tricks people have discovered to get this done anyway:

http://www.ittc.ku.edu/csdlblog/?p=88 https://hackage.haskell.org/package/data-reify

As noted in the second link, this essentially boils down to recovering observable sharing which violates purity, so it ends up being an IO operation.

---

The second is similar to the first: we'd like to recover Boolean ASTs made of boolean operations on free variable markers so that we can reinterpret and compile them. The type of boolean ASTs is not `Bool` since Haskell have already normalized the language expression we're interested in. So we need to make another type `BoolEXP` which retains the whole operation so that we can get at it in a first-order/data-like way.

---

Both of these are specific verbalizations of pretty common issues with embedded DSLs. They're not obvious or easy, but definitely standard challenges you'll face when making Haskell embedded DSLs.

I haven't finished it, but it seems approachable so far.

The idea is that we're embedding a DSL in Haskell by evaluating Haskell expressions symbolically within the DSL. Instead of doing a computation in Haskell and providing a value, we want to output a program in some other language from Haskell and then run that. This other program can have totally different semantics from normal Haskell: it might be a description of hardware (like Kansas Lava), it might be efficient C code, it might be an SMT formula... etc.

A nice, lightweight way to do this is to define a type where operations produce expressions in your target language. We can overload a bunch of things like + to do this; 1 + 2 would be evaluate to an AST along the lines of `Plus (Literal 1) (Literal 2)` which can then be treated as a circuit or a logic formula or whatever. This is called a "deep embedding".

The problem with control flow is that it happens at the Haskell level, not at your symbolic level. So `if (x > y) then 1 else 2` will either evaluate to 1 or to 2, but we actually want it to evaluate to the AST representing the whole conditional expression. In a sense, we want to "take both branches" symbolically.

A good way to think about this is that actual Haskell computations become compile-time operations for your DSL. Compile-time control flow can change the result of the compilation, but it can't depend on runtime information—and, of course, we definitely want to have control flow at runtime!

In the case of `if` we can still make this work by defining our own symbolic boolean type and overloading the if-then-else syntax, but we simply can't do this for pattern matching within the confines of Haskell. Haskell patterns are not first-class citizens and the language does not give you any to talk about what pattern matching means within the language (except maybe something really hideous involving Template Haskell).

As to your broader question: deeply embedding DSLs in Haskell is a really broad and powerful technique, but it also has some real limitations. The control flow thing is one; another is dealing with common subexpression elimination. For example, if x gives you a big AST of some sort, you'd probably like x + x to give you an AST that realizes the two xs are the same and unifies them somehow but actually getting this structure from a Haskell expression is awkward at best[1].

However, the technique has one major advantage: it is really easy to use. It's much less work to build a nice deeply embedded DSL than it is to write a full compiler; if the above problems aren't a big deal, you're getting a lot of structure for free by relying on Haskell—you can rely on Haskell's types and type inference, you don't have to write a parser, you get Haskell as a powerful compile-time metaprogramming language and you can use things like Haskell's rewrite rules for lightweight optimizations.

It's a great tool to have in your arsenal because it really lowers the barrier to writing a DSL, which is an incredibly powerful technique for a whole host of real-world problems.