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

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

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.