What *is* a DSL?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
40 messages Options
12
Reply | Threaded
Open this post in threaded view
|

What *is* a DSL?

Günther Schmidt
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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: What *is* a DSL?

Emil Axelsson-2
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
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: What *is* a DSL?

jfredett
In reply to this post by Günther Schmidt
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
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: What *is* a DSL?

Günther Schmidt
In reply to this post by Emil Axelsson-2
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 <[hidden email]>:

> 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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: What *is* a DSL?

jfredett
In reply to this post by Emil Axelsson-2
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
>> [hidden email]
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: What *is* a DSL?

Günther Schmidt
In reply to this post by jfredett
Hi Joe
Am 07.10.2009, 17:26 Uhr, schrieb Joe Fredette <[hidden email]>:

> 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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: What *is* a DSL?

Vo Minh Thu
In reply to this post by jfredett
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 <[hidden email]>:

> 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
>> [hidden email]
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: What *is* a DSL?

Robert Atkey-2
In reply to this post by jfredett
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
>   =           Stop        a
>   |           Terminal    Char   (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
> myGrm Value   =     ENum     <$> posInt
>                 <|> id       <$  char '(' <*> nt Sum <* char ')'
>
> myGrm Product =     EProduct <$> nt Value <* char '*' <*> nt Product
>                 <|> id       <$> nt Value
>
> myGrm Sum     =     ESum     <$> nt Product <* char '+' <*> nt Sum
>                 <|> id       <$> nt Product

This needs a couple of simple functions to make things look nice:

> char :: Char -> Rule nt ()
> char c = Rule [Terminal c $ Stop ()]

> nt :: nt a -> Rule nt a
> nt nonterminal = Rule [NonTerminal nonterminal $ Stop id]

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:

> choice :: Alternative f => [f a] -> f a
> choice = foldl (<|>) empty
>
> digit :: Rule nt Int
> digit = choice [ x <$ char (intToDigit x) | x <- [0..9] ]
>
> posInt :: Rule nt Int
> posInt = fix 1 . reverse <$> some digit
>     where fix n []     = 0
>           fix n (d:ds) = d*n + fix (n*10) ds



Bob


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

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: What *is* a DSL?

Dan Piponi-2
In reply to this post by jfredett
2009/10/7 Joe Fredette <[hidden email]>:
> 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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: What *is* a DSL?

Don Stewart-2
dpiponi:

> 2009/10/7 Joe Fredette <[hidden email]>:
> > 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.

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.

Basic DSLs may only have a few charateristics of languages though -- a
(partial) grammar. That's closer to a well-defined API in my books.

-- Don
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: What *is* a DSL?

Günther Schmidt
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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: What *is* a DSL?

Vo Minh Thu
2009/10/7 Günther Schmidt <[hidden email]>:

> 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
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>

Hi,

Programming abstractions at the DSL level, not to further abstract
what the DSL covers.

Functions, for instance, are typical abstraction means offered by
programming languages. Even if your language is specific to some
domain, being able to create your own functions, and not only rely on
those provided by the DSL implementation, is important.

Imagine a (E)DSL for 3D programming (e.g. shading language): the
language is designed to fit well the problem (e.g. in this case, 3D
linear algebra, color operations, ...) but you'll agree it would be a
shame to not be able to provide your own functions.

Cheers,
Thu
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: What *is* a DSL?

Ben Franksen
minh thu wrote:

> 2009/10/7 Günther Schmidt <[hidden email]>:
>>> 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.
>
> Programming abstractions at the DSL level, not to further abstract
> what the DSL covers.
>
> Functions, for instance, are typical abstraction means offered by
> programming languages. Even if your language is specific to some
> domain, being able to create your own functions, and not only rely on
> those provided by the DSL implementation, is important.
>
> Imagine a (E)DSL for 3D programming (e.g. shading language): the
> language is designed to fit well the problem (e.g. in this case, 3D
> linear algebra, color operations, ...) but you'll agree it would be a
> shame to not be able to provide your own functions.

But isn't one of the advantages of an _E_DSL that we can use the host
language (Haskell) as a meta or macro language for the DSL? I would think
that this greatly reduces the need to provide abstraction
facilities /inside/ the DSL. In fact most existing (and often cited
examples of) EDSLs in Haskell do not provide abstraction.

Cheers
Ben

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: What *is* a DSL?

John Van Enk
On Wed, Oct 7, 2009 at 2:52 PM, Ben Franksen

But isn't one of the advantages of an _E_DSL that we can use the host language (Haskell) as a meta or macro language for the DSL?

Substantially so. I've used brief examples where the EDSL syntax is basically the data declaration (perhaps with some operators overloading constructors) to demonstrate Haskell's fitness as a host language for EDSLs.

This is also a credit to the expressiveness of Haskell's data declarations.

/jve

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: What *is* a DSL?

Vo Minh Thu
In reply to this post by Ben Franksen
2009/10/7 Ben Franksen <[hidden email]>:

> minh thu wrote:
>> 2009/10/7 Günther Schmidt <[hidden email]>:
>>>> 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.
>>
>> Programming abstractions at the DSL level, not to further abstract
>> what the DSL covers.
>>
>> Functions, for instance, are typical abstraction means offered by
>> programming languages. Even if your language is specific to some
>> domain, being able to create your own functions, and not only rely on
>> those provided by the DSL implementation, is important.
>>
>> Imagine a (E)DSL for 3D programming (e.g. shading language): the
>> language is designed to fit well the problem (e.g. in this case, 3D
>> linear algebra, color operations, ...) but you'll agree it would be a
>> shame to not be able to provide your own functions.
>
> But isn't one of the advantages of an _E_DSL that we can use the host
> language (Haskell) as a meta or macro language for the DSL?

It is.

> I would think
> that this greatly reduces the need to provide abstraction
> facilities /inside/ the DSL. In fact most existing (and often cited
> examples of) EDSLs in Haskell do not provide abstraction.

Even when you have good macro supports, you don't code everything at
the macro level. But it all depends on the particular EDSL we talk
about. If the EDSL is close to a regular programming language, it is
likely to provide the ability to create functions.

Cheers,
Thu
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: What *is* a DSL?

Robert Atkey-2
In reply to this post by Günther Schmidt

> 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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: What *is* a DSL?

Emil Axelsson-2
In reply to this post by Ben Franksen
Ben Franksen skrev:

> minh thu wrote:
>> 2009/10/7 Günther Schmidt <[hidden email]>:
>>>> 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.
>> Programming abstractions at the DSL level, not to further abstract
>> what the DSL covers.
>>
>> Functions, for instance, are typical abstraction means offered by
>> programming languages. Even if your language is specific to some
>> domain, being able to create your own functions, and not only rely on
>> those provided by the DSL implementation, is important.
>>
>> Imagine a (E)DSL for 3D programming (e.g. shading language): the
>> language is designed to fit well the problem (e.g. in this case, 3D
>> linear algebra, color operations, ...) but you'll agree it would be a
>> shame to not be able to provide your own functions.
>
> But isn't one of the advantages of an _E_DSL that we can use the host
> language (Haskell) as a meta or macro language for the DSL? I would think
> that this greatly reduces the need to provide abstraction
> facilities /inside/ the DSL. In fact most existing (and often cited
> examples of) EDSLs in Haskell do not provide abstraction.

I would say that the DSL is what the user sees. In this view, I think
it's correct to say that many (or most) DSLs need function abstraction.
Whether or not the internal data structure has function abstraction is
an implementation detail.

/ Emil


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: What *is* a DSL?

Creighton Hogg-4
In reply to this post by Robert Atkey-2
2009/10/7 Robert Atkey <[hidden email]>:

>
>> 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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: What *is* a DSL?

George Pollard
I'd also like to note that the canonical pronunciation of DSL ends in "-izzle".
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: What *is* a DSL?

Colin Paul Adams
>>>>> "George" == George Pollard <[hidden email]> 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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
12