[Haskell-cafe] What *is* a DSL?

[Robert Atkey]

On Wed, 2009-10-07 at 11:32 -0400, Joe Fredette wrote:
> So, if I understand this:
> 
> Parsec is a DSL, I'm going to venture it's a "Deep embedding" -- I  
> don't understand the internals, but if I were to build something like  
> Parsec, I would probably build up a "Parser" datastructure and then  
> apply optimizations to it, then "run" it with another function.
> 
> Am I on the right track here?

Parsec, like most other parser combinator libraries, is a shallowly
embedded DSL. The "Parser a" type is a Haskell function that does
parsing, i.e. a function of type String -> Maybe (String, a).
(Obviously, the real Parsec library allows more than strings, and has
better error reporting than this type, but this is the basic idea).

You can't analyse it further---you can't transform it into another
grammar to optimise it or print it out---because the information about
what things it accepts has been locked up into a non-analysable Haskell
function. The only thing you can do with it is feed it input and see
what happens.

A deep embedding of a parsing DSL (really a context-sensitive grammar
DSL) would look something like the following. I think I saw something
like this in the Agda2 code somewhere, but I stumbled across it when I
was trying to work out what "free" applicative functors were.

First we define what a production with a semantic action is,
parameterised by the type of non-terminals in our grammar and the result
type:

> data Production nt a
>   =           Stop        a
>   |           Terminal    Char   (Production nt a)
>   | forall b. NonTerminal (nt b) (Production nt (b -> a))

You can think of a production as a list of either terminals or
non-terminals, terminated by the "value" of that production. The
non-regular nested type argument in NonTerminal means that the final
value can depend on the values that will be returned when parsing the
strings that match other non-terminals.

Productions are functors: 

> instance Functor (Production nt) where
>     fmap f (Stop a)           = Stop (f a)
>     fmap f (Terminal c p)     = Expect c (fmap f p)
>     fmap f (NonTerminal nt p) = NonTerminal nt (fmap (fmap f) p)

They are also applicative functors:

> instance Applicative (Production nt) where
>     pure = Stop
>     (Stop f)           <*> a = fmap f a
>     (Terminal c t)     <*> a = Terminal c (t <*> a)
>     (NonTerminal nt t) <*> a = NonTerminal nt (fmap flip t <*> a)

A rule in one of our grammars is just a list of alternative productions:

> newtype Rule nt a = Rule [Production nt a]

Since lists are (applicative) functors and (applicative) functors
compose, Rule nt is also a Functor and Applicative functor:

> instance Functor (Rule nt) where
>     fmap f (Rule l) = Rule (fmap (fmap f) l)

> instance Applicative (Rule nt) where
>    pure x                  = Rule $ pure (pure x)
>    (Rule lf) <*> (Rule la) = Rule $ (<*>) <$> lf <*> la

It is also an instance of Alternative, because we composed with lists:

> instance Alternative (Rule nt) where
>     empty                   = Rule []
>     (Rule r1) <|> (Rule r2) = Rule $ r1 <|> r2

A grammar is a map from nonterminals to rules, which are lists of
alternative productions, which may themselves refer back to nonterminals
in the grammar:

> type Grammar nt = forall a. nt a -> Rule nt a

Given a value of type "Grammar nt", and a starting nonterminal in "nt a"
for some "a", one can easily write a function that translates it into a
Parsec grammar to do actual parsing, or implement a different parsing
strategy using memoisation or something similar. The translation to a
traditional parser combinator library is actually a
(indexed-)homomorphism of applicative functors + extra operations, which
is pretty cool.

If you also know some extra facts about the "nt" type (e.g. that it is
finite), then it should be possible implement an CYK or Earley parser
using this, or to print out the grammar (for documentation purposes, or
for telling another node in a distributed network what things you
accept, for instance).

Note that these grammars are strictly less powerful than the ones that
can be expressed using Parsec because we only have a fixed range of
possibilities for each rule, rather than allowing previously parsed
input to determine what the parser will accept in the future. This is
the fundamental reason for using the applicative functor interface
rather than the monad interface here.


I'll give an example grammar for parsing expressions modelled by the
following data type:

> data Expr = ENum Int
>           | ESum Expr Expr
>           | EProduct Expr Expr
>           deriving Show

To define a grammar in this formalism, one first has to define the set
of nonterminals that one wants to use:

> data NT a where
>    Value   :: NT Expr
>    Product :: NT Expr
>    Sum     :: NT Expr

Now, a grammar is simply a function from members of this type to
productions. We use the applicative/alternative functor interface to
build up the productions. Conor's SHE would make this look a lot nicer,
using idiom brackets.

> myGrm :: Grammar NT
> myGrm Value   =     ENum     <$> posInt
>                 <|> id       <$  char '(' <*> nt Sum <* char ')'
> 
> myGrm Product =     EProduct <$> nt Value <* char '*' <*> nt Product
>                 <|> id       <$> nt Value
> 
> myGrm Sum     =     ESum     <$> nt Product <* char '+' <*> nt Sum
>                 <|> id       <$> nt Product

This needs a couple of simple functions to make things look nice:

> char :: Char -> Rule nt ()
> char c = Rule [Terminal c $ Stop ()]

> nt :: nt a -> Rule nt a
> nt nonterminal = Rule [NonTerminal nonterminal $ Stop id]

And a general definition for parsing single-digit numbers. This works
for any set of non-terminals, so it is a reusable component that works
for any grammar:

> choice :: Alternative f => [f a] -> f a
> choice = foldl (<|>) empty
> 
> digit :: Rule nt Int
> digit = choice [ x <$ char (intToDigit x) | x <- [0..9] ]
> 
> posInt :: Rule nt Int
> posInt = fix 1 . reverse <$> some digit
>     where fix n []     = 0
>           fix n (d:ds) = d*n + fix (n*10) ds



Bob


-- 
The University of Edinburgh is a charitable body, registered in
Scotland, with registration number SC005336.