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