How do I create an internal DSL with Haskell's do notation?

Question

Haskell has a do notation for writing code that executes in a monad. I've seen that this is sometimes (ab?)used for creating embedded internal domain-specific languages, where code written in the language is put inside a do block within the Haskell source, but I'm not sure how that works.

Do I use an existing monad, or create my own? Does it need to really be a monad, or is just a Monad instance enough? What do I actually need to do to build a DSL this way?

Answer 1

You'll make a Monad instance, but it doesn't need to "be" a monad satisfying the laws (though when you interact with other functions they may expect it to be). There are a couple of direct routes.

In libraries like HaTeX and Blaze, the do notation is used to construct a syntax tree for a document, which can be processed later on. Something like this:

aDocument = do
  section "Top-level heading" $ do
    text "Multiple items can appear inside. "
    text "These can be nested"
    list $ do
      item $ text "Creating a tree"
      item $ text "Of values"
    section "A subsection" $ do
      text "Recursively"

is built out of functions like text :: String -> Doc () = Doc [Text s] (). We could imagine implementing it something like this:

data DocDSL = Text String | Section String (Doc ()) | List (Doc ()) | Item (Doc ())
data Doc v = Doc [DocDSL] v
-- Keywords of the DSL:
text s = Doc [Text s] ()
section title body = Doc [Section title body] ()
list body = Doc [List body] ()
item body = Doc [Item body] ()
-- ... Functor & Applicative instances elided here ...
instance Monad Doc where
  return v = Doc [] v
  (Doc l v) >>= f = case f v of (Doc l2 v2) -> Doc (l ++ l2) v2```

The bind operation >>= that's inserted between every line just builds up the syntax tree by joining consecutive items together into a list of sibling nodes, while constructs like section and list are given their own do block that produces another Doc to hold inside, creating a recursively-nested structure.

The resulting value can be processed like any other algebraic data type later on, to evaluate, transform, or optimise it. Here that value is

Doc [Section "Top-level heading" (Doc [Text "Multiple items can appear inside. ",Text "These can be nested",List (Doc [Item (Doc [Text "Creating a tree"] ()),Item (Doc [Text "Of values"] ())] ()),Section "A subsection" (Doc [Text "Recursively"] ())] ())] ()

and a typical syntax tree structure. A more complete language could do some more work here than purely building up lists, but you can see the general structure in play.

In some of these libraries the DSL is parameterised further by the evaluator in use later, uses overloaded strings, etc, but those are advanced elements. This same structure could be used for any tree structure, not just a document, so a programming language or other output format is viable too. A programming language might use some more features of the do notation, like variable bindings.

---

The case above is really just leveraging the do notation, and otherwise has essentially no connection to being a monad. A more complex DSL could make better use of that, and in particular do provides syntactic support for variables.

do
  ...
  x <- currentDepth
  if x > 10 then text "Deep" else text "Shallow"

These are regular Haskell variables, and can hold any type of data, be passed to other functions, used in conditionals or combined with other values, and so on.

The DSL might build on the state monad for storing and retrieving values, but any of your DSL functions can return a value to be put in a variable (going where () was written in the version above), with whatever meaning makes sense for the language you're building. There's still no requirement to adhere to the monad laws or to do anything beyond satisfying the typechecker.

---

There is also Control.Dsl, a set of modules specifically for making DSLs with do, but relying on the RebindableSyntax GHC extension and so outside of standard Haskell. They sidestep monads entirely and add additional functionality around do, so they are able to go a bit further with the language.

---

ApplicativeDo is another GHC option that uses the applicative operations in translating do instead of the monadic ones when possible. This is another way not to need a Monad instance, but limits your DSL to mostly a list of steps. This could work for simple cases of document trees, but not with variables.