1 \chapter[chap:context]{Context}
5 \startframedtext[width=8.5cm,background=box,frame=no]
6 \startalignment[center]
7 {\tfa Embedded domain-specific languages (\small{EDSL})}
11 \startcitedquotation[deursen00]
12 A domain-specific language (\small{DSL}) is a programming language
13 or executable specification language that offers, through
14 appropriate notations and abstractions, expressive power focused
15 on, and usually restricted to, a particular problem domain.
18 An embedded \small{DSL} is a \small{DSL} that is embedded in
19 another language. Haskell is commonly used to embed \small{DSL}s
20 in, which typically means a number of Haskell functions and types
21 are made available that can be called to construct a large value
22 of some domain-specific datatype (\eg, a circuit datatype). This
23 generated datatype can then be processed further by the
24 \small{EDSL} \quote{compiler} (which runs in the same environment
25 as the \small{EDSL} itself. The embedded language is then a, mostly
26 applicative, subset of Haskell where the library functions are the
27 primitives. Sometimes advanced Haskell features such as
28 polymorphism, higher-order values or type classes can be used in
29 the embedded language. \cite[hudak96]
31 For an \small{EDSL}, the definitions of compile-time and run-time
32 are typically fuzzy (and thus hard to define here), since the
33 \small{EDSL} \quote{compiler} is usually compiled by the same
34 Haskell compiler as the \small{EDSL} program itself.
38 An obvious question that arises when starting any research is \quote{Has
39 this not been done before?}. Using a functional language for describing hardware
40 is not a new idea at all. In fact, there has been research into functional
41 hardware description even before the conventional hardware description
42 languages were created. Examples of these are µFP \cite[sheeran83]\ and
43 Ruby \cite[jones90]. Functional languages were not nearly as advanced
44 as they are now, and functional hardware description never really got
47 Recently, there have been some renewed efforts, especially using the
48 Haskell functional language. Examples are Lava \cite[claessen00]\ (an
49 \small{EDSL}) and ForSyde \cite[sander04]\ (an \small{EDSL} using
50 Template Haskell). \cite[baaij09]\ has a more complete overview of the
53 We will now have a look at the existing hardware description languages,
54 both conventional and functional to see the fields in which Cλash is
57 \section{Conventional hardware description languages}
58 Considering that we already have some hardware description languages like
59 \small{VHDL} and Verilog, why would we need anything else? By introducing
60 the functional style to hardware description, we hope to obtain a hardware
61 description language that is:
63 \item More concise. Functional programs are known for their conciseness
64 and ability to provide reusable functions that are abstractions of
65 common patterns. This is largely enabled by features like an
66 advanced type system with polymorphism and higher-order functions.
67 \item Type-safer. Functional programs typically have a highly
68 expressive type system, which allows a programmer to more strictly
69 define limitations on values, making it easier to find violations
71 \item Easy to process. Functional languages have nice properties like
72 purity \refdef{purity} and single binding behavior, which make it easy
73 to apply program transformations and optimizations and could potentially
74 simplify program verification.
77 \section[sec:context:fhdls]{Existing functional hardware description languages}
78 As noted above, this path has been explored before. However, current
79 embedded functional hardware description languages (in particular
80 those using Haskell) are limited. Below a number of downsides are
81 sketched of the recent attempts using the Haskell language.
82 \cite[baaij09]\ has a more complete overview of these and other
85 This list uses Lava and ForSyDe as examples, but tries to generalize
86 the conclusions to the techniques of embedding a \small{DSL} and
87 using Template Haskell.
90 \defref{Template Haskell}
91 \startframedtext[width=8.5cm,background=box,frame=no]
92 \startalignment[center]
93 {\tfa Template Haskell}
97 Template Haskell is an extension to the \GHC\ compiler that allows
98 a program to mark some parts to be evaluated \emph{at compile
99 time}. These \emph{templates} can then access the abstract syntax
100 tree (\small{AST}) of the program that is being compiled and
101 generate parts of this \small{AST}.
103 Template Haskell is a very powerful, but also complex mechanism.
104 It was intended to simplify the generation of some repetitive pieces
105 of code, but its introspection features have inspired all sorts of
106 applications, such as hardware description compilers.
111 \item Not all of Haskell's constructs can be captured by embedded domain
112 specific languages. For example, an \hs{if} or \hs{case}
113 expression is typically executed once when the Haskell description
114 is processed and only the result is reflected in the generated
115 data-structure (and thus in the final program). In Lava, for
116 example, conditional assignment can only be described by using
117 explicit multiplexer components, not using any of Haskell's
118 compact mechanisms (such as \hs{case} expressions or pattern
121 Also, sharing of variables (\eg, using the same variable twice
122 while only calculating it once) and cycles in circuits are
123 non-trivial to properly and safely translate (though there is some
124 work to fix this, but that has not been possible in a completely
125 reliable way yet \cite[gill09]).
126 \item Template Haskell makes descriptions verbose. Template
127 Haskell needs extra annotations to move things around between
128 \small{TH} and the normal program. When \small{TH} is combined
129 with an \small{EDSL} approach, it can get confusing when to use
130 \small{TH} and when not to.
131 \item Function hierarchies cannot be observed in an \small{EDSL}.
132 For example, Lava generates a single flat \VHDL\ architecture,
133 which has no structure whatsoever. Even though this is strictly
134 correct, it offers no support to the synthesis software about
135 which parts of the system can best be placed together and makes
136 debugging the system very hard.
138 It is possible to add explicit annotation to overcome this
139 limitation (ForSyDe does this using Template Haskell), but this
140 adds extra verbosity again.
141 \item Processing in Template Haskell can become very complex,
142 since it works on the Haskell \small{AST} directly. This means
143 that every part of the Haskell syntax that is used must be
144 supported explicitly by the Template Haskell code.
145 \in{Chapter}[chap:prototype] shows that working on a smaller
146 \small{AST} is much more efficient.
149 % vim: set sw=2 sts=2 expandtab: