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.