Domain-Specific Embedded Languages (DSELs) | Part 1 | Introduction

29 07 2009

Hi to all, I decided to try once more at this blog thing. I want to share my thoughts with the people out there but it seems that I am able to do so in bursts, and random ones unfortunately. I decided to try once more, this time using WordPress.

I just finished my second draft of a literature review about Domain-Specific Embedded Languages (DSELs or EDSL in short, depending where you come from). For those of you who are unfamiliar with the notion, these are basically languages related to one particular domain (often referred to as Domain-Specific Languages or DSLs) which are embedded within another language. More often the host language is a fully-fledged language which acts as a compiler or interpreter for the embedded language. The embedded language itself usually consists of a data structure of the host language which adequately abstracts to the domain at hand and represents it completely. By means of appropriate functions the data structure is given a number of semantics related to the domain. A common example of a DSEL is one for creating circuits but the number of possible applications of the approach is dependent on the number of domains existent (so more or less infinite). There are DSELs for geometric region analysis, geometric constructions, images, animations, music composition, financial contracts, query languages, hardware description languages, testing, robotics, firewalls, business processes and so on. (Let me know if you want a number of papers about these and I will provide references.)

Let us make use of a circuit-creating domain-specific language embedded in the functional language, Haskell. Haskell has been used often for embedding due to many advantages it has which facilitate the embedding approach. (A post for another time maybe?) We start off with the syntax of our DSEL which we create by making use of a Haskell data type that we are going to call Wire. We shall make use of a high-valued wires, low-valued wires and two basic gates: a NOT gate and an AND gate, described in Haskell as follows:

data Wire
  = High
  | Low
  | Not Wire
  | And Wire Wire

Using this syntax we can describe circuits such as an OR gate as follows (using DeMorgan’s Theorem):

orGate wire0 wire1 = answer
  where not0   = Not wire0
        not1   = Not wire1
        and0   = And not0 not1
        answer = Not and0

This is pure Haskell code but which is now domain-focused on describing circuits. But what can we do with this code? As it is, on its own, well… nothing, apart from maybe describing how a circuit is composed. How can we render this code more useful? The answer is by means of functions which traverse the programs created using the above data type. In this way we attach semantics to the syntax. An example of this is a simulation function which when supplied with a circuit along with its input wires, gives us the result of the circuit:

simulate :: Wire -> Wire
simulate Low = Low
simulate High = High
simulate (Not w) =
  case (simulate w) of
    Low  -> High
    High -> Low
simulate (And w1 w2) =
  case (simulate w1, simulate w2) of
    (Low , _ )   -> Low
    (_ , Low)    -> Low
    (High, High) -> High

Calling simulate on orGate supplied with a Low and High input returns a High-valued wire:

> simulate (orGate Low High)
High

(Note: you need to derive the type-class Show or provide an instance of said type-class to view this in GHCI or Hugs)

Another possible semantics is counting the gates in the circuit or translating it into VHDL or Verilog. The possibilities are endless – one program may be interpretted in a million ways as long as the right function is supplied written in the host language.

I hope this blog post serves as a simplified starter to those who would like to know what a domain-specific embedded language is and how to create one quickly in Haskell. I also hope that in the next few days I can introduce other related stuff. Please feel free to comment on any mistakes, on what you think, or if you need any references to material on this.

About these ads

Actions

Information

9 responses

7 08 2009
Alp

Very interesting !

What’ll be Part 2’s studied DSEL ?

7 08 2009
drewcalleja

I am not sure I have understood properly but part 2 will probably be about making DSEL constructs polymorphic using type-classes. :)

Probably the DSEL in the next section will be an expansion of this current one. I might try to think of another possible language.

7 08 2009
Alp

Ok. My question was about the concrete example described along the article.

7 08 2009
nonixace

I don`t know what this is all about as I have no experience of embedding such code.

7 08 2009
drewcalleja

You can come up with any embedded language you want, if circuits is not good for you. :) The approach is the same for all embedded languages in Haskell.

7 08 2009
Alp

The main idea is to provide data types and/or typeclasses and/or functions and/or operators, so that you can play with these stuffs just like if you were in a sublanguage of Haskell (well, it’s the case).

7 08 2009
drewcalleja

Yes. Essentially what is required is a data type modelling your domain of choice and a number of functions which give meaning to your structures in the data type. Typeclasses and operators can be added to make the language more accessible.

Btw nice blog Alp :)

7 08 2009
Alp

Yeah, but the next blog articles will be about Haskell and Maths… I left OCaml, I feel more confortable with Haskell :-)

I think it’d be *very* interesting for readers to have advices about designing the DSEL, along with the implementation advices.

7 08 2009
drewcalleja

I am planning to add such stuff in later parts. Hopefully it’s what you wish to see. :)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




Follow

Get every new post delivered to your Inbox.

%d bloggers like this: