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

[Robert Atkey]

On Sat, 2009-10-10 at 20:12 +0200, Ben Franksen wrote:

> Since 'some' is defined recursively, this creates an infinite production for
> numbers that you can neither print nor otherwise analyse in finite time.

Yes, sorry, I should have been more careful there. One has to be careful
to handle EDSLs that have potentially infinite syntax properly.

> I can see at least two solutions: One is to parameterize everything over the
> type of terminals, too. 

> The second solution (which I followed) is to break the recursion by adding
> another nonterminal to the NT type:

A third solution is to add the Kleene star to the grammar DSL, so the
representation of productions becomes:

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

You also need to add the necessary parts for Alternative to the
Production type too, because they may be nested inside Star
constructors:

>   |           Zero
>   |           Choose (Production nt a) (Production nt a)

The type Production nt is now directly an Applicative and an Alternative
and also has the combinator:
> star :: Production nt a -> Production nt [a]
> star p = Star p $ Stop id

The type of grammars is changed to (with the additional of the starting
nonterminal, as you point out):

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

It is probably also possible to write a function that converts grammars
with “Star”s in to ones without by introducing new non-terminals in the
way you did.

Bob



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