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.