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

[Nils Anders Danielsson]

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
  http://sneezy.cs.nott.ac.uk/fplunch/weblog/?p=271

--
/NAD


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.