Home » forums » LtU Forum

Denotational semantics of a DSL?

I am really at a loss here... I was just trying to understand if one can define more or less formally what is a DSL.

Is it semantics of DSLs that differentiates them from GP PLs? Or is it only pragmatics ("you can do the same in any GP but it's easier/faster/cheaper to do in this DSL")?

In other words, can we define as DSLs those PLs whose semantic domains are, uh, domain specific? By a semantic domain here I mean the range (or codomain) of a semantic function, and the domain of this function is a syntactic domain... All these puns are not really intended :-(

...

After several unsuccessful attempts to pursue this path, I came to another "definition" - DSLs are the PLs with the pragmatics massively dominating the semantics :-)

PS: I would be very interested in seeing any references to papers on denotational semantics of some DSL.

By Andris Birkmanis at 2005-04-14 18:14 | LtU Forum | previous forum topic | next forum topic | other blogs | 7810 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Found so far

A Denotational Semantics for Continuous Queries over Streams and Relations

A Denotational Semantics for the Starburst Production Rule Language

By Andris Birkmanis at Thu, 2005-04-14 18:20 | login or register to post comments

Built-in types, operators, limitations

In some of the DSLs I've worked on, values in the language are very specific and can be quite complex. The language syntax and semantics are designed to deal with these values as simply as possible.

For example, a simple expression like "a = b + c" might represent a complex compound calculation, in which b and c might be values of a built-in type representing trees of values, the addition operation may only apply to certain of those values, and 'a' may have a structure which depends on the structure of b and c.

You could achieve something similar in a language which supports things like overloaded operators, typeclasses, generic functions, and/or macros. Chances are high, though, that you'll end up with syntactic artifacts over which you have no control, which complicate the language unnecessarily. If you have to invest time trying to produce a clean syntax for an embedded language, and end up running into limitations anyway, why not just implement a parser?

More importantly, you may want to place limits on the computations that can be performed, and embedding a DSL in a general purpose language may not be sufficiently controllable. IOW, what the DSL can't do is also important.

Some Schemes, like PLT and I think Scheme 48, have module systems which allow you to limit the syntax and library code available to a module. I've used this in one case to implement a language for transmission of requests between a browser client and server. Again, being able to place strong limits on what the language can do is useful.

By Anton van Straaten at Thu, 2005-04-14 18:55 | login or register to post comments

Is lambda calculus a general purpose programming language?

Built-in types, operators, ...

But I think any PL has built-in types and operators? Even lambda calculus has some... Or do you mean that the differentiating criterion is not their existence but their nature?

..., limitations
Can this mean a prohibition to have a semantic domain as powerful as recursive functions? But then again, while being Turing-complete is probably necessary for a PL to qualify as a GP one, it's probably not sufficient.

Can we call lambda calculus a GP PL? Can we call any language that can define (only) functions a GP PL? May the difference between GP PLs and DSLs lie in the effects they can produce, or the way they interact with their environment?

By Andris Birkmanis at Thu, 2005-04-14 19:42 | login or register to post comments

Nature of types

Or do you mean that the differentiating criterion is not their existence but their nature?
Yes, I mean the nature of the built-in types and operations. In the cases I was referring to, both are very domain specific. Also, many of the general data types present in general purpose languages may not be present at all.

Can this mean a prohibition to have a semantic domain as powerful as recursive functions?
I would say yes, it can mean that. Some of the languages I'm thinking of don't have the ability to define functions at all -- each program essentially behaves like a function itself, but the format of its input is predefined, and it cannot define other functions to use in its implementation.
Can we call lambda calculus a GP PL?

I think it's a stretch to call pure, untyped LC a GP PL — perhaps you could call it the basis or core of one, but by itself it's certainly not a practical PL. However, once you add some data types to it, it can become quite usable. This seems to support my point: if you add GP types to LC, then you have a GP language; if you add domain specific types and operations (functions on the types), then you have a DSL (ignoring syntax).

Can we call any language that can define (only) functions a GP PL?

Again, defining functions alone, in the absence of GP types at least, probably isn't enough for practical purposes.

May the difference between GP PLs and DSLs lie in the effects they can produce, or the way they interact with their environment?
Quite likely. E.g. in the examples I was thinking of, I/O is very constrained — they're designed to fit into a specific place in a larger program.
By Anton van Straaten at Thu, 2005-04-14 20:39 | login or register to post comments

Is the early Pascal a general purpose language?

If not, then what disqualifies it?

Data types not general enough?

Interface to the environment not general enough?

It's definitely Turing-complete, though.

Excuse me, if I am abusing the blog.

By Andris Birkmanis at Fri, 2005-04-15 09:30 | login or register to post comments

Abuse?

You are not abusing the blog, and the subject is of course on topic for LtU.

However, I am not sure I understand what it is that is bothering you.

By Ehud Lamm at Fri, 2005-04-15 09:42 | login or register to post comments

Ok then

I was having a feeling I was beating a dead horse. After all, there are hundreds of web pages defining what it means to be a DSL. So I just felt I was trolling.

To summarize, is it possible to (formally or semiformally) classify a PL as either a DSL or a GP PL based on its syntax and semantics, or is it not an intrinsic property of a PL and is determined by a specific implementation of the PL, a historical context, popular trends, available tools, existing tasks, etc.

By Andris Birkmanis at Fri, 2005-04-15 10:09 | login or register to post comments

My take

I'd say it's thelatter (i.e., pragmatics, not syntax/semantics).

Obviously, in most cases you'll have syntax and semantic features that are domain specific, but I don't think it would be a valuabe exercise to try to formally define a general meaning for "domain specific".

By Ehud Lamm at Fri, 2005-04-15 10:20 | login or register to post comments

Domain Specific

I agree with Ehud; I don't think that we can find an airtight formal definition of "domain specific".

I think that, rather than as a formal property of a language, a better way to think about it is as a design philosophical goal or constraint.

A DSL is one that is designed for a specific purpose and for which no weight is given to general problem solving outside that domain.

Note that this definition doesn't exclude Turing-completeness or general utility, it just suggests that these possibilities were not emphasized in the core design criteria when the language was worked out.

By Marc Hamann at Fri, 2005-04-15 13:12 | login or register to post comments

me too

Andris, I think you might be getting caught up by the word "domain" -- AFAIK, it has nothing to do with domain theory, but is simply the informal notion of a "problem domain." For example, if you're writing software for filling out tax forms (it's that time of the year on my side of the pond...), having an intimate knowledge of tax law would be considered "domain knowledge."

I agree with Ehud and Marc: I don't see any particularly strong motivation for formalizing the notion of domain-specific. There's not much point to formalism for its own sake; the point is when you have some useful properties, i.e., theorems, you want to prove.

For me, the more frustrating difficulty in formalizing DSL's is when they are embedded. Say you have a regular expression language embedded in a functional language. How do you specify that it operates on the datatypes of the host language (characters, strings, lists) without sucking in the entire semantics of the host language?

By Dave Herman at Fri, 2005-04-15 15:43 | login or register to post comments

Thanks to everybody

Um, I should have mentioned that I know a DSL when I see it, I just hoped to define it. :-)

My idea was that if I check several papers defining denotational semantics of several DSLs I would see some patterns (or antipatterns). Of course, these would be patterns of how people formalize DSLs, not patterns of DSL design.

By Andris Birkmanis at Fri, 2005-04-15 16:16 | login or register to post comments

Um, I should have mentioned t

Um, I should have mentioned that I know a DSL when I see it...

Perhaps, then, you should think of a DSL a bit like Justice Potter Stewart of the U.S. Supreme Court thought of pornography.

It has always seemed, to me, one of those "floating" definitions.

By Geoff Wozniak at Fri, 2005-04-15 18:17 | login or register to post comments

YAMTR

I too agree with Ehud, Marc, and Dave. I think Dave brought up the most deciding aspect by mentioning EDSLs (or DSELs). An embedded domain specific languages are considered DSLs, but they obviously have access to the full power of a general purpose language. So the difference between an API, a EDSDL, and a DSL is usually a question of intent. However, languages that have some untenable restrictions (especially lack of Turing-completeness) can definitely be called "not general purpose" which usually means domain or application specific.

By Derek Elkins at Fri, 2005-04-15 19:14 | login or register to post comments