Domain-Specific Languages and Code Synthesis Using Haskell

 

There are many ways to give instructions to a computer: an electrical engineer might write a MATLAB program; a database administrator might write an SQL script; a hardware engineer might write in Verilog; and an accountant might write a spreadsheet with embedded formulas. Aside from the difference in language used in each of these examples, there is an important difference in form and idiom. Each uses a language customized to the job at hand, and each builds computational requests in a form both familiar and productive for programmers (although accountants may not think of themselves as programmers). In short, each of these examples uses a Domain-Specific Language (DSL).

A DSL is a special-purpose language, designed to encapsulate possible computations in a specific domain. In the earlier examples of MATLAB, SQL, Verilog, and spreadsheets, the domains would be scientific modeling, database queries and updates, hardware circuits, and financial computations, respectively. Considering SQL specifically, there is nothing it does that could not be done in Java or C, or any other general-purpose programming language. SQL simply bundles the actions needed to interact with a database into a usable and productive package, and the language becomes the interface to communicate requests to the database engine.

There are two fundamental types of DSLs. The first is a first-class language, shown in Figure 1(1), with its own compiler or interpreter, and it is often used in its own ecosystem. All the examples mentioned so far fall into this category. The primary difference between the SQL DSL and, for example, Java is one of scope and focus, although sometimes DSLs grow to be as large as general-purpose languages.

The other class of DSL is a language embedded in a host language, as shown in Figure 1(2). Such languages can have the look and feel of being their own language, but they leverage the host language’s existing ecosystem and initial semantics. This article is concerned with this second class of DSLs.

Back to Top

Haskell Primer

An embedded DSL (EDSL) is a language inside a language. Haskell,¹⁷ the premier pure functional programming language, is a great host for EDSLs because of flexible overloading, a powerful type system, and lazy semantics. This section provides a terse introduction to Haskell, sufficient to make this article self-contained. It is an extended version of the Haskell primer I gave in 2011 at the International Conference on Engineering of Reconfigurable Systems and Algorithms.¹⁰

Haskell is all about types. Types in Haskell, like those in other languages, are constraining summaries of structural values. For example, in Haskell Bool is the type of the values True and False; Int is the type of machine-sized words; Double is the type of double-precision IEEE floating-point values; and this list goes on in the same manner as C, C++, Java, and other traditional languages. All of these type names in Haskell start with an uppercase letter.

On top of these basic types, Haskell has two syntactic forms for expressing compound types. First, pairs, triples, and larger structures can be written using tuple-syntax, comma-separated types inside parentheses. Thus, (Int,Bool) is a structure with both an Int and a Bool component. Second, lists have a syntactic shortcut, using square brackets. Thus, [Int] is a list of Int.

Haskell also has other container types. A container that may contain one Int has the type Maybe Int, which is read Maybe of Int. These container names also start with uppercase letters.

Types can be nested to any depth. For example, you can have a [(Maybe (Int,Bool))], read as list of Maybe of (Int and Bool).

Polymorphic values are expressed using lowercase letters and play a similar role to void* pointers in C and polymorphic arguments in the Java generics facility. These polymorphic values can have constraints expressed over them, using the Haskell equivalent of an object hierarchy.

Finally, a function is written using an arrow from argument type to result type. Thus, in Haskell, a function that takes a list and returns a list is written as: [a] -> [a].

Here is an example of a Haskell function:

This function sorts a list using a variant of quicksort in which the pivot is the first element of the list:

• The first line is the type for sort. This is ∀a, such that a can be ordered (admits comparisons like <=); the function takes and return a list of such a‘s.
• The second line says that an empty list is already sorted.
• The remaining lines state that a non-empty list can be sorted by taking the first and rest of the list (called x and xs, respectively), sorting the values before this pivot and after this pivot, and concatenating these intermediate values together.
• Finally, intermediate values can be named using the where syntax; in this case the values of before and after.

Haskell is a concise and direct language. Structures in Haskell are denoted using types, constructed and deconstructed, but never updated. For example, the Maybe type can be defined using two constructors, Nothing and Just:

Nothing is a Maybe of anything; Just, with an argument, is a Maybe with the type of the argument. These constructors can be used to construct and deconstruct structures, but there is never any updating; all structures in Haskell are immutable.

It is possible to give specific types extra powers, such as equality and comparison, using the class-based overloading system. The Maybe type, for example, can be given the ability to test for equality, using an instance:

This states that for any type that can be tested for equality, you can also check Maybe of the same type. You take the Maybe apart, using pattern matching on Just, to check the internal value.

In Haskell, side effects such as writing to the screen or reading the keyboard are described using a do-notation:

In this example a value called main uses the do-notation to describe an interaction with a user. Actually, the do-notation captures this as a structure called a monad; purity is not compromised. More detailed information is available on how the do-notation and monads can provide an effectful interface inside a pure language such as Haskell.¹⁸ For the purposes of this article, do-notation is a way of providing syntax and structure that looks like interaction. There are many tutorials on Haskell; the Haskell website, (http://haskell.org) is a good starting point for further reading.

Back to Top

Embedded DSLs

An EDSL is a library in a host language that has the look, feel, and semantics of its own language, customized to a specific problem domain. By reusing the facilities and tools of the host language, an EDSL considerably lowers the cost of both developing and maintaining a DSL. Benefiting from Haskell’s concise syntax, the Haskell community—and the functional programming community in general—has taken the ideas of EDSLs and developed a large number of DSLs that provide higher-level interfaces and abstractions for well-understood systems. What follows are two examples of EDSLs: one for automatically generating test cases for software testing; and a second for specifying hardware-circuit behaviors.

Example EDSL: QuickCheck Properties. Consider the challenge of writing test cases—or more specifically, writing the properties that test cases need to satisfy:

In this example, prop_reverse_twice is a regular Haskell function that takes a list of Int and returns a Boolean, based on the validity of what is being proposed—specifically, that two reverses cancel each other out. Here is the neat part: prop_reverse_twice is also a domain-specific statement and as such can be considered a sublanguage inside Haskell. This style of using functions (in this case, functions with names prefixed with prop_, taking a number of typed arguments, and returning a conditional) is a small language. The property written in Haskell is also an EDSL for properties, called QuickCheck.⁴ This EDSL can be run using a function also called quickCheck:

By running quickCheck with this explicit and specific property, the EDSL executes inside Haskell. The quickCheck function generates 100 test cases for the property and executes them on the fly. If they all hold, then the system prints a message reflecting this. The test cases are generated using the type class system—QuickCheck gives specific types the power of test-case generation—and the quickCheck function uses this to generate random tests.

As an example of an incorrect property, consider this property for reverse.

This states that the reverse of two distinct lists is the same as the reverse of both lists appended together, but this property is false.

It turns out that this sort of mini-language is really useful in practice. Despite the simplicity of how Haskell is being used, the QuickCheck EDSL provides a way of thinking about and directly expressing properties. It has additional functionality, including the ability to generate random function arguments, to control the distribution of the random test cases, and to state preconditions of a property. From this DSL, many other implementations of these ideas have been constructed. There is even a Swedish company, QuviQ, that sells a QuickCheck for the concurrent programming language Erlang.

Example EDSL: Kansas Lava. To take another example, consider describing hardware. Hardware description languages and functional languages have long enjoyed a fruitful partnership. Lava is the name given to a class of Haskell DSLs that implement a function-based version of the hardware description language Ruby.^12,13 Not to be confused with the modern programming language of the same name, Ruby was based on relations, which was in turn inspired by the seminal work in μFP.²¹

Kansas Lava¹¹ is a Haskell-hosted DSL that follows the Lava line of research. It is a language for expressing gate-level circuits. Haskell abstractions allow the programmer to work at a slightly higher level of abstraction, where the model is one of recursive components communicating via synchronized streams. Kansas Lava has been used for the generation of high-performance circuits for telemetry decoders, though the model used is general.

As an example of Kansas Lava, consider Figure 2: This circuit connects two multiplexers (mux2), an adder, and a register to give a circuit that counts the number of clocked pulses on a signal inc. The circuit takes two clocked signals and returns a clocked signal that explicitly operates using the same clock, because they share the same type. The use of arithmetic is understated, but simply uses (via overloading) the standard syntax for addition; the Num constraint allows this. Figure 3 illustrates the circuit intended for this description.

You can simulate sequential circuits with the same directness as the combinational functions invoked (see Figure 4).

As well as basic signal types, you can build circuits that operate on Haskell functions directly, provided the domain of the function is finite. The Rep capability is used to signify that you can enumerate all possible representable values in a type, giving the funMap function:

The generated circuit is implemented using a ROM, and you can generate control logic directly in terms of Haskell functions and data structures. As an example, consider a small ROM that stores the square of a value:

In this way, direct Haskell functions can be lifted into the Signal world. Notice how the squareROM function is not specific about size but is completely generic, requiring only the type of the argument stream to be representable as a number.

The clock-squaring ROM can now be used at specific types. For example, at eight-bit you can generate the following:

This level of circuit specification has been used to great effect in many Lava and Lava-like languages. One notable instance is Hawk,¹⁵ a Lava-like EDSL that was used to specify the entire micro-architecture of the Pentium Pro, including the super-scaler design, and register bypass capabilities.

Now, if DSLs are so powerful as an idiom for library design, then why have they not taken over? As a means for expressing things that can be simulated, EDSLs are an invaluable design pattern; however, not everything is a simulation. What if you wanted to use an EDSL to express something you want to run somewhere else, not inside the Haskell system? Can Lava be used to generate circuits to be run on FPGAs (field-programmable gate arrays)? Can EDSLs be used to generate code for embedded processors or GPUs? Such an ability—to synthesize external solutions—would be extremely useful. The EDSL idiom can be extended to do so, with significant caveats. The remainder of this article is about how to capture and offshore work from inside an EDSL, what this capability can be used for, and what the limitations are.

Back to Top

Deeply Embedded Domain-Specific Languages

EDSLs are simply a way of thinking about a library of provided functions, often called combinators, because they combine their arguments into terms inside the DSL. In the previous Lava example, the register combinator takes an initial value—and an incoming stream of values—and provides the new stream, delayed by a single cycle, with the initial value occupying the initial cycle. Critically, register is compositional; it combines smaller parts of the DSL to make larger solutions. If a DSL follows this composability carefully by design, an important alternative implementation is possible.

The most common flavor of EDSL is one that uses so-called shallow embedding, as seen in Figure 1(2a), where values are computed directly. The result of a computation in a shallow EDSL is a value. All the examples so far are shallow. There is another class of EDSLs, however: specifically, those that use a deep embedding to build an abstract syntax tree, as shown in Figure 1(2b). The result of a computation inside a deeply embedded DSL (deep EDSL) is a structure, not a value, and this structure can be used to compute a value or be cross-compiled before being evaluated.⁷ Such deep EDSLs follow the composability mantra pedantically, by design and mandate.

Historically, EDSLs have been shallow—simply a way of structuring an API for a library. Deep EDSLs, however, have the ability to stage code—that is, executing a program can generate another program, much like the well-known YACC DSL, but at the cost of significantly restricting what forms of the DSL can generate valid output. There are a growing number of deep EDSLs, along with a body of research around their form and limitations. The unifying theme is that deep EDSLs can be pragmatic, productive, and useful.

This section investigates the basic structure of a deep EDSL compared with a shallow EDSL, and looks at three pragmatic tricks for improving the usefulness of deep EDSLs.

Building a deep EDSL. A deeply embedded DSL exposes its own composition and structure. Rather than using functions operating directly on values (a shallow DSL), a deep DSL builds a structure, then allows some secondary agent to provide interpretation of this structure. To make this idea concrete, consider a DSL for arithmetic, with addition, subtraction, multiplication, and constants. For a shallow embedding, running this DSL is trivial; you just use the built-in arithmetic. A deep embedding is where things get interesting. Consider a data type for our arithmetic:

Now overload the arithmetic to use this Expr data type; in Haskell, Num is the overloading for integral arithmetic:

By building expressions of type Expr, you can observe the structure of the computation:

This is profound, and it is the key idea that makes deep embeddings work. You can write an expression and extract a tree of what to do, not a direct result. With deep embeddings, it is common also to write a run function that computes the result of a captured computation:

Figure 5 illustrates the differences between shallow and deep DSLs, and how a deep embedding combined with a specific run function gives the same result. For a deep embedded DSL, the run function restores the capability of the shallow embedding, but another function takes the embedded structure and uses it in some creative way.

To make deep DSLs practical, there are two additional tricks in the DSL folklore that are almost always used. The first trick allows the capture of functions, via dummy arguments. The second trick can observe loops, via some form of observable sharing.

How to extract a deep embedding from a function. Expressing function calls in terms of constructors and building expression trees is useful, but by itself is a gimmick. With careful construction, however, you can also capture function definitions, as well as other syntactical structures, directly from a deep embedding. It is at this point that the idea of capturing code, then using the captured code to execute code on a different target, becomes possible. Consider a simple function to add one to its argument:

Here is a function that acts over the new type Expr and returns a new Expr. How can you capture this function? The trick is to invent a unique Expr and pass it as a (dummy) argument to f:

You can now run the function directly and see the result in your deep embedding, or pass in the Var argument and see the actual function in Figure 6: This is remarkable! You have run a function with a dummy argument (called the prototypical argument) and extracted the body of the function.

This idea scales to multi-argument functions. Consider g:

Two prototypical arguments to g will capture the function:

There are many places this design pattern can be used. One example is the specification of surface textures as functions; it is possible to export these into code executable on GPUs, simultaneously lifting the abstractions used to write textures and speeding up how fast an implementation of the same operations would run. There is nothing that is specific about Haskell or even functional languages here. Indeed, the same ideas have been used in Java for a VHSIC Hardware Description Language (VHDL) generator.² Haskell, with its powerful abstractions, allows deep DSLs almost to feel like a straightforward shallow embedding.

How to spot a loop. Lava programs are written as equations of recursive bindings. An attempt to build a deep embedding of Lava directly will lead to an infinite cycle of structures. To illustrate the challenge, let’s build a deep embedding of Lava, see where it goes wrong, and fix it using a technique called observable sharing.

First the Lava language needs a structure. In Figure 7, we define the functions used before but give them a deep embedding, called Signal.

The output tree is infinite. What has happened is the recursive definitions are unrolling during attempts to reify the function, or more specifically, the body of counter is looping. At this point, the EDSL community was stymied. There were efforts to use monadic structure, where the loop was expressed using do-notation,⁸ making the loop an observable effect. There was an unsafe extension to observe a limited form of sharing by circumventing part of the purity of Haskell, called observable sharing.⁵ There was also an extension of the Haskell I/O mechanism that allowed loops to be observed indirectly, called I/O-based observable sharing.⁹ The net effect of all three mechanisms is that the observed tree is rendered as a graph with named edges.

At this point Haskell rescues us from some complexity. Advanced type-system mechanisms, such as higher-kinded arguments, allow a structure to be either a tree or graph, depending on type-level instantiation. Omitting the details here, the reified function is a tree with sharing, then translated into a graph with explicit sharing. The final result for this example entity counter is:

In this output, each uppercase constructor corresponds to its deep-embedding constructor. A quick inspection shows that the circuit has been captured, as shown in Figure 3. From this netlist-style structure, generating VHDL is straightforward. For the example of four-bit numbers, the VHDL is provided in Figure 8.

These two tricks (prototypical argument and I/O-based observable sharing) are the technical fundamentals of Kansas Lava. On top of this base, and with help from the Haskell type system, an entire ecosystem for circuit generation has been developed. The DSL idiom allows programmers to use high-level abstraction in Haskell and generate efficient circuits. Not all is rosy, however; writing a Lava program is not the same as writing a Haskell program because of the limitations of deep embeddings.

Back to Top

A Deep Embedding Is Only Half a Program

The basis of a deep EDSL is one of constructiveness. Functional programming is about constructing and deconstructing values. Because of this, a deep embedding cannot reify any pattern matching—or even direct usage of if-then-else—and other control flow. Kansas Lava sidestepped this—for example, by using a mux2 constructor, which encodes choice. How much further can the idiom be pushed if you need to be deconstructive? The result is surprising. Let’s start with the three capabilities:

• Basic expressions can be captured by constructing a tree that is an analogue to your syntax.
• Functions can be captured using a fake unique argument.
• Local bindings can be observed using some form of observable sharing.

With these three comes an automatic fourth capability:

• The host language provides a built-in macro capability to the embedded language. Any part of Haskell (including control flow and pattern matching) can be used to generate the embedded language.

There are also extensions to the basic techniques. The principal ones are:

• Internal function calls can be captured as nodes on a graph, rather than directly inlined.¹⁴ This helps compilation of large programs, giving a basic separate compilation capability.
• The do statement can be reified by normalization.^16,19,22 This result, called monadic reification, is surprising. There are strong technical reasons to believe monadic reification should be impossible; however, the normalization refactors the constraints that, by themselves, would be impossible to solve and matches them up, one-on-one, with a matching witness, allowing the whole do-notation to be solved and reified. Monadic reification is a recent discovery but has already been used in several deep DSLs, including Feldspar¹ and Sunroof.³
• Control flow is problematic and cannot be used directly, but there is a generalization of Haskell Boolean that does allow deep-embedding capture.⁶ Using this library, a DSL with control flow can be constructed, but it needs to be explicit code, at the DSL level, using constructors. The mux2 function used previously is a simplification of this idea. The usage is clumsy but workable, and we should be able to do better.

Where does this leave deep DSLs? They are clearly a useful design pattern for the language implementer, but they come with costs and limitations. How can we therefore push the state of the art and allow more of the Haskell language to be reified? There are two primary shortcomings. One we have discussed already: control flow and pattern matching remain a thorn in deep DSLs.

Parametric polymorphism, one of the strengths of a functional program, is the other issue for deep DSLs. A specific structure is needed to represent what has been captured, and arbitrary polymorphism interferes with this. Current systems sidestep this issue by always instantiating at a specific type, but this is expensive because the size of the captured program can expand exponentially. Polymorphism was the technical reason it was thought that monadic reification was not possible, but in that case it was sidestepped by normalization; this technique does not generalize to all polymorphism.

A deep DSL is a value-level way of extracting an expression, but there are other ways. Quasi-quoting is a mechanism for extracting expressions, but at the syntactic level. Haskell comes with an extensive template system called Template Haskell²⁰, which is often used for DSLs. There is a sense of unease with such solutions; however, in much the same way the C preprocessor is used even though it is not considered elegant. The principal issue is that the syntax of Haskell is huge, consisting of around 100 syntactical terms. An expression-based solution, such as a deep embedding, can avoid the need to rewrite front translations. Quasi-quoting has one important advantage: specifically, it can cope with control flow and deconstruction of values. Perhaps the future of deep DSLs is some hybrid between expression generation and quasi-quoting, combining the best of both systems.

Back to Top

Acknowledgments

This article is based upon work supported by the National Science Foundation under Grant No. CCF-1117569, and was originally presented as a master class under the Scottish Informatics & Computer Science Alliance Visiting Fellow program in Nov. 2013. The Kansas Lava examples and description were adapted from an earlier article about Lava written by the author.¹⁰

Related articles
on queue.acm.org

OCaml for the Masses
Yaron Minsky
http://queue.acm.org/detail.cfm?id=2038036

The World According to LINQ
Erik Meijer
http://queue.acm.org/detail.cfm?id=2024658

DSL for the Uninitiated
Debasish Ghosh
http://queue.acm.org/detail.cfm?id=198975

Back to Top

Back to Top

Back to Top

Back to top