Re: [Haskell-cafe] What *is* a DSL?
On 22 okt 2009, at 15:56, Robert Atkey wrote:
Previously parsed input /can/ determine what the parser will accept
in
the future (as pointed out by Peter Ljunglöf in his licentiate
thesis).
Consider the following grammar for the context-sensitive language
{aⁿbⁿcⁿ| n ∈ ℕ}:
Yes, sorry, I was sloppy in what I said there. 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?
The answer is: all context-sensitive languages. This is a very old
insight which has come back in various forms in computer science. The
earliest conception in CS terms is the concept of an affix-grammar, in
which the infinite number of nonterminals is generated by
parameterising non-terminals by trees. They were invented by Kees
koster and Lambert Meertens (who applied them to generate music: http://en.wikipedia.org/wiki/index.html?curid=5314967)
in the beginning of the sixties of the last century. There is a long
follow up on this idea, of which the two most well-known versions are
the so-called two-level grammars which were used in the Algol68 report
and the attribute grammar formalism first described by Knuth. The full
Algol68 language is defined in terms of a two-level grammar. Key
publications/starting points if you want to learn more about these are:
- the Algol68 report:
http://burks.brighton.ac.uk/burks/language/other/a68rr/rrtoc.htm
- the wikipedia paper on affix grammars:
http://en.wikipedia.org/wiki/Affix_grammar
- a nice book about the basics od two-level grammars is the
Cleaveland Uzgalis book, Grammars for programming languages, which
may be hard to get,
but there is hope:
http://www.amazon.com/Grammars-Programming-Languages-languages/dp/0444001875
- http://www.agfl.cs.ru.nl/papers/agpl.ps
- http://comjnl.oxfordjournals.org/cgi/content/abstract/32/1/36
Doaitse Swierstra
And a general definition for parsing single-digit numbers. This
works
for any set of non-terminals, so it is a reusable component that
works
for any grammar:
Things become more complicated if the reusable component is defined
using non-terminals which take rules (defined using an arbitrary
non-terminal type) as arguments. Exercise: Define a reusable
variant of
the Kleene star, without using grammars of infinite depth.
I see that you have an answer in the paper you linked to above.
Another
possible answer is to consider open sets of rules in a grammar:
data OpenRuleSet inp exp =
forall hidden. OpenRuleSet (forall a. (exp :+: hidden) a -
Rule (exp :+: hidden :+: inp) a)
data (f :+: g) a = Left2 (f a) | Right2 (g a)
So OpenRuleSet inp exp, exports definitions of the nonterminals in
'exp', imports definitions of nonterminals in 'inp' (and has a
collection of hidden nonterminals).
It is then possible to combine them with a function of type:
combineG :: (inp1 := exp1 :+: inp) -
(inp2 := exp2 :+: inp) -
OpenRuleSet inp1 exp1 -
OpenRuleSet inp2 exp2 -
OpenRuleSet inp (exp1 :+: exp2)
One can then give a reusable Kleene star by stating it as an open rule
set:
star :: forall a nt. Rule nt a - OpenRuleSet nt (Equal [a])
where Equal is the usual equality GADT.
Obviously, this would be a bit clunky to use in practice, but maybe
more
specialised versions combineG could be given.
Bob
--
The University of Edinburgh is a charitable body, registered in
Scotland, with registration number SC005336.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What *is* a DSL?
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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What *is* a DSL?
On Tue, 2009-10-13 at 13:28 +0100, Nils Anders Danielsson wrote:
On 2009-10-07 17:29, Robert Atkey wrote:
A deep embedding of a parsing DSL (really a context-sensitive grammar
DSL) would look something like the following. I think I saw something
like this in the Agda2 code somewhere, but I stumbled across it when I
was trying to work out what free applicative functors were.
The Agda code you saw may have been due to Ulf Norell and me. There is a
note about it on my web page:
http://www.cs.nott.ac.uk/~nad/publications/danielsson-norell-parser-combinators.html
Yes, it might have been that, OTOH I'm sure I saw it in some Haskell
code. Maybe I was imagining it.
Note that these grammars are strictly less powerful than the ones that
can be expressed using Parsec because we only have a fixed range of
possibilities for each rule, rather than allowing previously parsed
input to determine what the parser will accept in the future.
Previously parsed input /can/ determine what the parser will accept in
the future (as pointed out by Peter Ljunglöf in his licentiate thesis).
Consider the following grammar for the context-sensitive language
{aⁿbⁿcⁿ| n ∈ ℕ}:
Yes, sorry, I was sloppy in what I said there. 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?
And a general definition for parsing single-digit numbers. This works
for any set of non-terminals, so it is a reusable component that works
for any grammar:
Things become more complicated if the reusable component is defined
using non-terminals which take rules (defined using an arbitrary
non-terminal type) as arguments. Exercise: Define a reusable variant of
the Kleene star, without using grammars of infinite depth.
I see that you have an answer in the paper you linked to above. Another
possible answer is to consider open sets of rules in a grammar:
data OpenRuleSet inp exp =
forall hidden. OpenRuleSet (forall a. (exp :+: hidden) a -
Rule (exp :+: hidden :+: inp) a)
data (f :+: g) a = Left2 (f a) | Right2 (g a)
So OpenRuleSet inp exp, exports definitions of the nonterminals in
'exp', imports definitions of nonterminals in 'inp' (and has a
collection of hidden nonterminals).
It is then possible to combine them with a function of type:
combineG :: (inp1 := exp1 :+: inp) -
(inp2 := exp2 :+: inp) -
OpenRuleSet inp1 exp1 -
OpenRuleSet inp2 exp2 -
OpenRuleSet inp (exp1 :+: exp2)
One can then give a reusable Kleene star by stating it as an open rule
set:
star :: forall a nt. Rule nt a - OpenRuleSet nt (Equal [a])
where Equal is the usual equality GADT.
Obviously, this would be a bit clunky to use in practice, but maybe more
specialised versions combineG could be given.
Bob
--
The University of Edinburgh is a charitable body, registered in
Scotland, with registration number SC005336.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What *is* a DSL?
On 2009-10-07 17:29, Robert Atkey wrote:
A deep embedding of a parsing DSL (really a context-sensitive grammar
DSL) would look something like the following. I think I saw something
like this in the Agda2 code somewhere, but I stumbled across it when I
was trying to work out what free applicative functors were.
The Agda code you saw may have been due to Ulf Norell and me. There is a
note about it on my web page:
http://www.cs.nott.ac.uk/~nad/publications/danielsson-norell-parser-combinators.html
Note that these grammars are strictly less powerful than the ones that
can be expressed using Parsec because we only have a fixed range of
possibilities for each rule, rather than allowing previously parsed
input to determine what the parser will accept in the future.
Previously parsed input /can/ determine what the parser will accept in
the future (as pointed out by Peter Ljunglöf in his licentiate thesis).
Consider the following grammar for the context-sensitive language
{aⁿbⁿcⁿ| n ∈ ℕ}:
data NT a where
Start ::NT () -- Start ∷= aⁿbⁿcⁿ
ABC :: Nat - NT () -- ABC n ∷= aˡbⁿ⁺ˡcⁿ⁺ˡ
X :: Char - Nat - NT () -- X x n ∷= xⁿ
g :: Grammar NT
g Start = nt (ABC 0)
g (ABC n) = char 'a' * nt (ABC (succ n))
| nt (X 'b' n) * nt (X 'c' n)
g (X c n)
| n == 0= pure ()
| otherwise = char c * nt (X c (pred n))
And a general definition for parsing single-digit numbers. This works
for any set of non-terminals, so it is a reusable component that works
for any grammar:
Things become more complicated if the reusable component is defined
using non-terminals which take rules (defined using an arbitrary
non-terminal type) as arguments. Exercise: Define a reusable variant of
the Kleene star, without using grammars of infinite depth.
--
/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.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What *is* a DSL?
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? greetings, Sjoerd On Oct 7, 2009, at 9:18 PM, Robert Atkey wrote: What is a DSL? How about this as a formal-ish definition, for at least a pretty big class of DSLs: A DSL is an algebraic theory in the sense of universal algebra. I.e. it is an API of a specific form, which consists of: a) a collection of abstract types, the carriers. Need not all be of kind *. b) a collection of operations, of type t1 - t2 - ... - tn where tn must be one of the carrier types from (a), but the others can be any types you like. c) (Optional) a collection of properties about the operations (e.g. equations that must hold) Haskell has a nice way of specifying such things (except part (c)): type classes. Examples of type classes that fit this schema include Monad, Applicative and Alternative. Ones that don't include Eq, Ord and Show. The Num type class would be, if it didn't specify Eq and Show as superclasses. An implementation of a DSL is just an implementation of corresponding type class. Shallowly embedded DSLs dispense with the type class step and just give a single implementation. Deeply embedded implementations are *initial* implementations: there is a unique function from the deep embedding to any of the other implementations that preserves all the operations. The good thing about this definition is that anything we do to the deep embedding, we can do to any of the other implementations via the unique map. Thanks to Church and Reynolds, we can always get a deep embedding for free (free as in Theorems for Free). If our DSL is defined by some type class T, then the deep embedding is: type DeepT = forall a. T a = a (and so on, for multiple carrier types, possibly with type parameterisation). Of course, there is often an easier and more efficient way of representing the initial algebra using algebraic data types. Conor McBride often goes on about how the initial algebra (i.e. the deep embedding) of a given specification is the one you should be worrying about, because it often has a nice concrete representation and gives you all you need to reason about any of the other implementations. Bob -- The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Sjoerd Visscher sjo...@w3future.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What *is* a DSL?
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: grammars and rules * rules support the applicative and alternative interfaces, and also two special operators for incorporating terminals and nonterminals into rules. * grammars 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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What *is* a DSL?
On Thu, Oct 8, 2009 at 6:08 AM, Colin Paul Adams co...@colina.demon.co.ukwrote: George == George Pollard por...@porg.es writes: George I'd also like to note that the canonical pronunciation of George DSL ends in -izzle. Whose canon? Interestingly, I have always assumed the canonical pronunciation of DSSSL was diesel, as JADE stands for JAmes's DSSSL Engine. I don't see why removing extra S-es should shorten the vowel. Wht vwl? U mst b Englsh. 2 n Amrcn, DSSSL is dissel; all short vowels. DSL is dee-ess-ell. Dizzle is a brbrzm. -grgg ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What *is* a DSL?
Gregg == Gregg Reynolds d...@mobileink.com writes: Gregg On Thu, Oct 8, 2009 at 6:08 AM, Colin Paul Adams Gregg co...@colina.demon.co.ukwrote: George == George Pollard por...@porg.es writes: George I'd also like to note that the canonical pronunciation of George DSL ends in -izzle. Whose canon? Interestingly, I have always assumed the canonical pronunciation of DSSSL was diesel, as JADE stands for JAmes's DSSSL Engine. I don't see why removing extra S-es should shorten the vowel. Wht vwl? U mst b Englsh. 2 n Amrcn, DSSSL is dissel; all short vowels. Certainly I am English, and so is James Clark. -- Colin Adams Preston Lancashire ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] What *is* a DSL?
Perhaps it would be appropriate to point out the IFIP conference on exactly that topic, DSL. The conference took place in July, here is the permanent record: http://dsl09.blogspot.com/ with pointers to the slides and the discussions. The panel discussion has debated that very question, what exactly is DSL. http://dsl09.blogspot.com/2009/07/panel.html As you can see, the agreement could not be reached on what is Domain. There will be another DSL conference, in Australia. Perhaps all the Haskell-Cafe debaters may want to participate. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What *is* a DSL?
I'd also like to note that the canonical pronunciation of DSL ends in -izzle. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What *is* a DSL?
George == George Pollard por...@porg.es writes: George I'd also like to note that the canonical pronunciation of George DSL ends in -izzle. Whose canon? Interestingly, I have always assumed the canonical pronunciation of DSSSL was diesel, as JADE stands for JAmes's DSSSL Engine. I don't see why removing extra S-es should shorten the vowel. -- Colin Adams Preston Lancashire ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] What *is* a DSL?
Hi all, for people that have followed my posts on the DSL subject this question probably will seem strange, especially asking it now. I have read quite a lot lately on the subject, most of it written by the great old ones, (come on guys you know whom I mean :)). What I could gather from their papers was, that a DSL is basically something entirely abstract as such, ie. it allows you build and combine expressions in a language which is specific for your problem domain. Irregardless of further details on how to do that, and there are quite a few, the crux as such is that they are abstract of meaning. The meaning depends how you *evaluate* the expression, which can be in more than merely one way, which is where, as far as I understand it, the true power lies. So, you might wonder, since I figured it out this far, why ask what a DSL is? Because out there I see quite a lot of stuff that is labeled as DSL, I mean for example packages on hackage, quite useuful ones too, where I don't see the split of assembling an expression tree from evaluating it, to me that seems more like combinator libraries. Thus: What is a DSL? Günther ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What *is* a DSL?
Hi, A DSL is just a domain-specific language. It doesn't imply any specific implementation technique. An *embedded* DSL is a library implemented in a more general language, which has been designed to give the feeling of a stand-alone language. Still nothing about implementation. A *shallow embedding* of a DSL is when the evaluation is done immediately by the functions and combinators of the DSL. I don't think it's possible to draw a line between a combinator library and a shallowly embedded DSL. A *deep embedding* is when interpretation is done on an intermediate data structure. / Emil Günther Schmidt skrev: Hi all, for people that have followed my posts on the DSL subject this question probably will seem strange, especially asking it now. I have read quite a lot lately on the subject, most of it written by the great old ones, (come on guys you know whom I mean :)). What I could gather from their papers was, that a DSL is basically something entirely abstract as such, ie. it allows you build and combine expressions in a language which is specific for your problem domain. Irregardless of further details on how to do that, and there are quite a few, the crux as such is that they are abstract of meaning. The meaning depends how you *evaluate* the expression, which can be in more than merely one way, which is where, as far as I understand it, the true power lies. So, you might wonder, since I figured it out this far, why ask what a DSL is? Because out there I see quite a lot of stuff that is labeled as DSL, I mean for example packages on hackage, quite useuful ones too, where I don't see the split of assembling an expression tree from evaluating it, to me that seems more like combinator libraries. Thus: What is a DSL? Günther ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What *is* a DSL?
Let me add to this, as I've used the term DSL without (*gasp*) fully understanding it before. In addition to What is a DSL, I'd like to ask: How is a DSL different from an API? -- in the sense that an API is a set of, say, combinators to filter email + a monad in which to combine them. Or even the API in the more traditional sense of the set of exposed operations on a given type. Is an API a kind of DSL? A kind of Embedded DSL? Also, What is the difference between an EDSL and a DSL? -- I've got a vague intuition of the difference, but am unsure how to particularly delineate them. Also, any good introductory papers/books/other resources on DSLs and how to design, build and use them would be _lovely_. /Joe On Oct 7, 2009, at 11:10 AM, Günther Schmidt wrote: Hi all, for people that have followed my posts on the DSL subject this question probably will seem strange, especially asking it now. I have read quite a lot lately on the subject, most of it written by the great old ones, (come on guys you know whom I mean :)). What I could gather from their papers was, that a DSL is basically something entirely abstract as such, ie. it allows you build and combine expressions in a language which is specific for your problem domain. Irregardless of further details on how to do that, and there are quite a few, the crux as such is that they are abstract of meaning. The meaning depends how you *evaluate* the expression, which can be in more than merely one way, which is where, as far as I understand it, the true power lies. So, you might wonder, since I figured it out this far, why ask what a DSL is? Because out there I see quite a lot of stuff that is labeled as DSL, I mean for example packages on hackage, quite useuful ones too, where I don't see the split of assembling an expression tree from evaluating it, to me that seems more like combinator libraries. Thus: What is a DSL? Günther ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What *is* a DSL?
Hi Emil, now that is an interpretation I could live with! Glad I posted the question. Günther Am 07.10.2009, 17:24 Uhr, schrieb Emil Axelsson e...@chalmers.se: Hi, A DSL is just a domain-specific language. It doesn't imply any specific implementation technique. An *embedded* DSL is a library implemented in a more general language, which has been designed to give the feeling of a stand-alone language. Still nothing about implementation. A *shallow embedding* of a DSL is when the evaluation is done immediately by the functions and combinators of the DSL. I don't think it's possible to draw a line between a combinator library and a shallowly embedded DSL. A *deep embedding* is when interpretation is done on an intermediate data structure. / Emil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What *is* a DSL?
So, if I understand this: Parsec is a DSL, I'm going to venture it's a Deep embedding -- I don't understand the internals, but if I were to build something like Parsec, I would probably build up a Parser datastructure and then apply optimizations to it, then run it with another function. Am I on the right track here? /Joe On Oct 7, 2009, at 11:24 AM, Emil Axelsson wrote: Hi, A DSL is just a domain-specific language. It doesn't imply any specific implementation technique. An *embedded* DSL is a library implemented in a more general language, which has been designed to give the feeling of a stand- alone language. Still nothing about implementation. A *shallow embedding* of a DSL is when the evaluation is done immediately by the functions and combinators of the DSL. I don't think it's possible to draw a line between a combinator library and a shallowly embedded DSL. A *deep embedding* is when interpretation is done on an intermediate data structure. / Emil Günther Schmidt skrev: Hi all, for people that have followed my posts on the DSL subject this question probably will seem strange, especially asking it now. I have read quite a lot lately on the subject, most of it written by the great old ones, (come on guys you know whom I mean :)). What I could gather from their papers was, that a DSL is basically something entirely abstract as such, ie. it allows you build and combine expressions in a language which is specific for your problem domain. Irregardless of further details on how to do that, and there are quite a few, the crux as such is that they are abstract of meaning. The meaning depends how you *evaluate* the expression, which can be in more than merely one way, which is where, as far as I understand it, the true power lies. So, you might wonder, since I figured it out this far, why ask what a DSL is? Because out there I see quite a lot of stuff that is labeled as DSL, I mean for example packages on hackage, quite useuful ones too, where I don't see the split of assembling an expression tree from evaluating it, to me that seems more like combinator libraries. Thus: What is a DSL? Günther ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What *is* a DSL?
Hi Joe Am 07.10.2009, 17:26 Uhr, schrieb Joe Fredette jfred...@gmail.com: Let me add to this, as I've used the term DSL without (*gasp*) fully understanding it before. Welcome to the club then! :) In addition to What is a DSL, I'd like to ask: How is a DSL different from an API? -- in the sense that an API is a set of, say, combinators to filter email + a monad in which to combine them. Or even the API in the more traditional sense of the set of exposed operations on a given type. Is an API a kind of DSL? A kind of Embedded DSL? Also, What is the difference between an EDSL and a DSL? -- I've got a vague intuition of the difference, but am unsure how to particularly delineate them. Well that part I think I can answer. An EDSL is when you don't start from scratch. IE. when you do not, let's say build a compiler that parses a String and then eventually executes it. Rather you define the Terms, ie. primitive Terms (Terminals) and Non-Terminals with the means of the host language (Haskell in my case). Also, any good introductory papers/books/other resources on DSLs and how to design, build and use them would be _lovely_. Well as a book I could recommend Paul Hudaks School of Expression. The way he abstracts is by means of using a DSL. He assembles objects, Geometrics Regions, Triangles, circles, squares etc. combines them with the help of functions and *later* evaluates them. Now he is definatly using a DSL here, but that is by no means the only way of implementing the abstract through a DSL. Once that has sunk in I suggest papers from Oleg and others on the subject, but to get started SOE would be a good idea. Günther ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What *is* a DSL?
Hi, Some random observation: A (E)DSL and an API fall on the same plane when they just expose functionality of a library. The difference between EDSL and a DSL is really just the E which means embedded into a host language so the embedded language can be built on top of some existing machinery, in Haskell typically the type system. Haskell is particularly good for EDSL (but also Scheme or CL) because the syntax of Haskell lets have a nice syntax for the embedded language and the type system makes it possible to have, with more or less simplicity, typing guarantees for the specifi language. A regular expression library comprises often a regexp language, which is considerd part of the API. That language is (or can be) parsed, compiled and executed. Some EDSL require to execute the Haskell program to output some object code, others require only the execution of some function equivalent to runState for the particular monad the EDSL uses. Providing a specialised language on top of a library is quite common, for instance command line tools to process images. Those command line tool can later be used in some progreams (think scripting languages). For instance, the dot program of the graphviz suite can be run with unsafePerformIO to get graphviz features inside Haskell. Parsing a String into some data structure is just a special case of transforming some data structure into other data structure because it easier to process that way. For instance HOAS into de Bruijn and vice versa. So for me, there is not a so strong distinction between API and language. Cheers, Thu 2009/10/7 Joe Fredette jfred...@gmail.com: Let me add to this, as I've used the term DSL without (*gasp*) fully understanding it before. In addition to What is a DSL, I'd like to ask: How is a DSL different from an API? -- in the sense that an API is a set of, say, combinators to filter email + a monad in which to combine them. Or even the API in the more traditional sense of the set of exposed operations on a given type. Is an API a kind of DSL? A kind of Embedded DSL? Also, What is the difference between an EDSL and a DSL? -- I've got a vague intuition of the difference, but am unsure how to particularly delineate them. Also, any good introductory papers/books/other resources on DSLs and how to design, build and use them would be _lovely_. /Joe On Oct 7, 2009, at 11:10 AM, Günther Schmidt wrote: Hi all, for people that have followed my posts on the DSL subject this question probably will seem strange, especially asking it now. I have read quite a lot lately on the subject, most of it written by the great old ones, (come on guys you know whom I mean :)). What I could gather from their papers was, that a DSL is basically something entirely abstract as such, ie. it allows you build and combine expressions in a language which is specific for your problem domain. Irregardless of further details on how to do that, and there are quite a few, the crux as such is that they are abstract of meaning. The meaning depends how you *evaluate* the expression, which can be in more than merely one way, which is where, as far as I understand it, the true power lies. So, you might wonder, since I figured it out this far, why ask what a DSL is? Because out there I see quite a lot of stuff that is labeled as DSL, I mean for example packages on hackage, quite useuful ones too, where I don't see the split of assembling an expression tree from evaluating it, to me that seems more like combinator libraries. Thus: What is a DSL? Günther ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What *is* a DSL?
On Wed, 2009-10-07 at 11:32 -0400, Joe Fredette wrote: So, if I understand this: Parsec is a DSL, I'm going to venture it's a Deep embedding -- I don't understand the internals, but if I were to build something like Parsec, I would probably build up a Parser datastructure and then apply optimizations to it, then run it with another function. Am I on the right track here? Parsec, like most other parser combinator libraries, is a shallowly embedded DSL. The Parser a type is a Haskell function that does parsing, i.e. a function of type String - Maybe (String, a). (Obviously, the real Parsec library allows more than strings, and has better error reporting than this type, but this is the basic idea). You can't analyse it further---you can't transform it into another grammar to optimise it or print it out---because the information about what things it accepts has been locked up into a non-analysable Haskell function. The only thing you can do with it is feed it input and see what happens. A deep embedding of a parsing DSL (really a context-sensitive grammar DSL) would look something like the following. I think I saw something like this in the Agda2 code somewhere, but I stumbled across it when I was trying to work out what free applicative functors were. First we define what a production with a semantic action is, parameterised by the type of non-terminals in our grammar and the result type: data Production nt a = Stopa | TerminalChar (Production nt a) | forall b. NonTerminal (nt b) (Production nt (b - a)) You can think of a production as a list of either terminals or non-terminals, terminated by the value of that production. The non-regular nested type argument in NonTerminal means that the final value can depend on the values that will be returned when parsing the strings that match other non-terminals. Productions are functors: instance Functor (Production nt) where fmap f (Stop a) = Stop (f a) fmap f (Terminal c p) = Expect c (fmap f p) fmap f (NonTerminal nt p) = NonTerminal nt (fmap (fmap f) p) They are also applicative functors: instance Applicative (Production nt) where pure = Stop (Stop f) * a = fmap f a (Terminal c t) * a = Terminal c (t * a) (NonTerminal nt t) * a = NonTerminal nt (fmap flip t * a) A rule in one of our grammars is just a list of alternative productions: newtype Rule nt a = Rule [Production nt a] Since lists are (applicative) functors and (applicative) functors compose, Rule nt is also a Functor and Applicative functor: instance Functor (Rule nt) where fmap f (Rule l) = Rule (fmap (fmap f) l) instance Applicative (Rule nt) where pure x = Rule $ pure (pure x) (Rule lf) * (Rule la) = Rule $ (*) $ lf * la It is also an instance of Alternative, because we composed with lists: instance Alternative (Rule nt) where empty = Rule [] (Rule r1) | (Rule r2) = Rule $ r1 | r2 A grammar is a map from nonterminals to rules, which are lists of alternative productions, which may themselves refer back to nonterminals in the grammar: type Grammar nt = forall a. nt a - Rule nt a Given a value of type Grammar nt, and a starting nonterminal in nt a for some a, one can easily write a function that translates it into a Parsec grammar to do actual parsing, or implement a different parsing strategy using memoisation or something similar. The translation to a traditional parser combinator library is actually a (indexed-)homomorphism of applicative functors + extra operations, which is pretty cool. If you also know some extra facts about the nt type (e.g. that it is finite), then it should be possible implement an CYK or Earley parser using this, or to print out the grammar (for documentation purposes, or for telling another node in a distributed network what things you accept, for instance). Note that these grammars are strictly less powerful than the ones that can be expressed using Parsec because we only have a fixed range of possibilities for each rule, rather than allowing previously parsed input to determine what the parser will accept in the future. This is the fundamental reason for using the applicative functor interface rather than the monad interface here. I'll give an example grammar for parsing expressions modelled by the following data type: data Expr = ENum Int | ESum Expr Expr | EProduct Expr Expr deriving Show To define a grammar in this formalism, one first has to define the set of nonterminals that one wants to use: data NT a where Value :: NT Expr Product :: NT Expr Sum :: NT Expr Now, a grammar is simply a function from members of this type to productions. We use the applicative/alternative functor interface to build up the productions. Conor's SHE would make this look a lot nicer, using idiom brackets. myGrm :: Grammar NT
Re: [Haskell-cafe] What *is* a DSL?
2009/10/7 Joe Fredette jfred...@gmail.com: Let me add to this, as I've used the term DSL without (*gasp*) fully understanding it before. In addition to What is a DSL, I'd like to ask: How is a DSL different from an API? I don't think there is a sharp divide here. A nice example was given by Pat Hanrahan at the recent nvidia GPU conference. He proposed the idea that OpenGL was a DSL. His reasoning was that he could give a formal grammar that accurately captured the structure of many fragments of code making calls to OpenGL. For example you have blocks of code bracketed by glBegin() and glEnd() with sequences of primitives in between. In fact, some people indent their code to reflect this structure as if glBegin() and glEnd() were control structures within the host language. I've argued that every monad gives a DSL. They all have the same syntax - do-notation, but each choice of monad gives quite different semantics for this notation. For example the list monad gives a DSL for non-determinism. -- Dan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What *is* a DSL?
Hi Don, I've informally argued that a true DSL -- separate from a good API -- should have semantic characteristics of a language: binding forms, control structures, abstraction, composition. Some have type systems. That is one requirement that confuses me, abstraction. I thought of DSLs as special purpose languages, ie. you give your DSL everything it needs for that purpose. Why would it also need the ability to express even further abstractions, it is supposed to *be* the abstraction. Günther ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What *is* a DSL?
What is a DSL? How about this as a formal-ish definition, for at least a pretty big class of DSLs: A DSL is an algebraic theory in the sense of universal algebra. I.e. it is an API of a specific form, which consists of: a) a collection of abstract types, the carriers. Need not all be of kind *. b) a collection of operations, of type t1 - t2 - ... - tn where tn must be one of the carrier types from (a), but the others can be any types you like. c) (Optional) a collection of properties about the operations (e.g. equations that must hold) Haskell has a nice way of specifying such things (except part (c)): type classes. Examples of type classes that fit this schema include Monad, Applicative and Alternative. Ones that don't include Eq, Ord and Show. The Num type class would be, if it didn't specify Eq and Show as superclasses. An implementation of a DSL is just an implementation of corresponding type class. Shallowly embedded DSLs dispense with the type class step and just give a single implementation. Deeply embedded implementations are *initial* implementations: there is a unique function from the deep embedding to any of the other implementations that preserves all the operations. The good thing about this definition is that anything we do to the deep embedding, we can do to any of the other implementations via the unique map. Thanks to Church and Reynolds, we can always get a deep embedding for free (free as in Theorems for Free). If our DSL is defined by some type class T, then the deep embedding is: type DeepT = forall a. T a = a (and so on, for multiple carrier types, possibly with type parameterisation). Of course, there is often an easier and more efficient way of representing the initial algebra using algebraic data types. Conor McBride often goes on about how the initial algebra (i.e. the deep embedding) of a given specification is the one you should be worrying about, because it often has a nice concrete representation and gives you all you need to reason about any of the other implementations. Bob -- The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What *is* a DSL?
2009/10/7 Robert Atkey bob.at...@ed.ac.uk: What is a DSL? How about this as a formal-ish definition, for at least a pretty big class of DSLs: A DSL is an algebraic theory in the sense of universal algebra. I.e. it is an API of a specific form, which consists of: a) a collection of abstract types, the carriers. Need not all be of kind *. b) a collection of operations, of type t1 - t2 - ... - tn where tn must be one of the carrier types from (a), but the others can be any types you like. c) (Optional) a collection of properties about the operations (e.g. equations that must hold) Haskell has a nice way of specifying such things (except part (c)): type classes. Examples of type classes that fit this schema include Monad, Applicative and Alternative. Ones that don't include Eq, Ord and Show. The Num type class would be, if it didn't specify Eq and Show as superclasses. An implementation of a DSL is just an implementation of corresponding type class. Shallowly embedded DSLs dispense with the type class step and just give a single implementation. Deeply embedded implementations are *initial* implementations: there is a unique function from the deep embedding to any of the other implementations that preserves all the operations. The good thing about this definition is that anything we do to the deep embedding, we can do to any of the other implementations via the unique map. Thanks to Church and Reynolds, we can always get a deep embedding for free (free as in Theorems for Free). If our DSL is defined by some type class T, then the deep embedding is: type DeepT = forall a. T a = a (and so on, for multiple carrier types, possibly with type parameterisation). Of course, there is often an easier and more efficient way of representing the initial algebra using algebraic data types. Conor McBride often goes on about how the initial algebra (i.e. the deep embedding) of a given specification is the one you should be worrying about, because it often has a nice concrete representation and gives you all you need to reason about any of the other implementations. It's funny, because I wouldn't have thought about this in terms of type classes from the top of my head. What I've been thinking about a lot lately (because I'm trying to prepare notes on it) is building classifying categories from signatures, then considering the category of all possible functorial models (read: dsl embeddings) into the target category.I guess we're essentially talking about the same thing. The difference from looking at it as type classes is that you really do get all your equations preserved with product preserving functors from your classifying category; however, the topic came up earlier today of what would a language look like if it had a built in notion of functorial semantics - my guess is that it'd be like a stronger version of ML functors, but I don't really know. Cheers, C ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
