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

Nils Anders Danielsson nad at Cs.Nott.AC.UK
Tue Oct 27 21:39:55 EDT 2009

On 2009-10-22 14:56, Robert Atkey wrote:
> Yes, it might have been that, OTOH I'm sure I saw it in some Haskell
> code. Maybe I was imagining it.

There is some related Haskell code in the Agda repository.

> Do you know of a characterisation of what languages having a possibly
> infinite amount of nonterminals gives you. Is it all context-sensitive
> languages or a subset?

I found a PhD thesis by Marvin Solomon (Cornell, 1977) which mentions
the following, in retrospect obvious, fact: With an infinite set of
non-terminals you can represent /any/ (countable) language, by using one
non-terminal for every string in the language.

I adapted this argument to show that a total parser combinator library
which I have implemented in Agda has exactly the same expressive power
as (total) functions of type List Bool → List R (assuming the token type
is Bool):

  Parser combinators are as expressive as possible


This message has been checked for viruses but the contents of an attachment
may still contain software viruses, which could damage your computer system:
you are advised to perform your own checks. Email communications with the
University of Nottingham may be monitored as permitted by UK legislation.

More information about the Haskell-Cafe mailing list