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

[Robert Atkey]

On Mon, 2009-10-12 at 15:49 +0200, Sjoerd Visscher wrote:
> Hi Bob,
> 
> I tried to understand this by applying what you said here to your deep  
> embedding of a parsing DSL. But I can't figure out how to do that.  
> What things become the type class T?

Here's the "API" version of the grammar DSL:

class GrammarDSL grammar where
    type Rule grammar :: (* -> *) -> * -> *
    
    pure    :: a -> Rule grammar nt a
    (<*>)   :: Rule grammar nt (a -> b) -> Rule grammar nt a ->
                 Rule grammar nt b

    empty   :: Rule grammar nt a
    (<|>)   :: Rule grammar nt a -> Rule grammar nt a ->
                  Rule grammar nt a
    
    char    :: Char -> Rule grammar nt ()
    nt      :: nt a -> Rule grammar nt a

    grammar :: forall nt a. nt a ->
                   (forall a. nt a -> Rule grammar nt a) -> grammar nt a


The language of typed-grammars-with-actions is composed of:

* two sorts: "grammar"s and "rule"s

* "rule"s support the applicative and alternative interfaces, and also
two special operators for incorporating terminals and nonterminals into
rules.

* "grammar"s support a single operation: taking a nonterminal-indexed
collection of rules, and a starting non-terminal (as Ben Franksen
pointed out), producing a grammar.

Basically, the idea is to think 1) "what are the syntactic categories of
my DSL?", these become the sorts; 2) "what are the basic syntactic
constructions of my DSL?", these become the operations of the type
class. Because we are embedded in Haskell, we can have infinite syntax,
as demonstrated by the "grammar" operation.

WRT the recipe for getting deep embeddings in my previous post, it isn't
quite true that the type

  Grammar nt a = forall grammar. GrammarDSL grammar => grammar nt a

is isomorphic to the deep embedding I posted before, because it doesn't
guarantee that the applicative functor or alternative laws hold, while
the deep embedding does (and it also ensures that <*> and <|>
distribute). It isn't hard to come up with a deep embedding that is
initial for the completely free version though. The deep embedding from
the previous post is an instance of this type class. So is, as Ben
Franksen showed, a Parsec parser.


I ended up having to inline the applicative and alternative interfaces
into the class definition above. I wanted to write:

class (Applicative (Rule grammar nt), Alternative (Rule grammar nt)) =>
  Grammar grammar where ...

but GHC wouldn't let me, complaining that 'nt' wasn't bound. Is there
any reason this couldn't be made to work?

Bob


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