X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Freport.git;a=blobdiff_plain;f=Chapters%2FContext.tex;h=45c16864d17abc38cb0f0a114abce1a5c1527c60;hp=ca65c1233eec2e9b8d017c4b1245d6c16d1ddbf5;hb=a0a2821832d86271ffc8efdb3774440191f3e10e;hpb=3fc7078e3369d9e916b3663f04c51bb587434d14 diff --git a/Chapters/Context.tex b/Chapters/Context.tex index ca65c12..45c1686 100644 --- a/Chapters/Context.tex +++ b/Chapters/Context.tex @@ -1,3 +1,150 @@ \chapter[chap:context]{Context} -Other FHDLs (short, Christiaan has details) -Advantages of clash / why clash? + + \placeintermezzo{}{ + \defref{EDSL} + \startframedtext[width=8.5cm,background=box,frame=no] + \startalignment[center] + {\tfa Embedded domain-specific languages (\small{EDSL})} + \stopalignment + \blank[medium] + + \startcitedquotation[deursen00] + A domain-specific language (\small{DSL}) is a program- + ming language or executable specification language + that offers, through appropriate notations and ab- + stractions, expressive power focused on, and usu- + ally restricted to, a particular problem domain. + \stopcitedquotation + + An embedded \small{DSL} is a \small{DSL} that is embedded in + another language. Haskell is commonly used to embed \small{DSL}s + in, which typically means a number of Haskell functions and types + are made available that can be called to construct a large value + of some domain-specific datatype (\eg, a circuit datatype). This + generated datatype can then be processed further by the + \small{EDSL} \quote{compiler} (which runs in the same environment + as the \small{EDSL} itself. The embedded language is then a, mostly + applicative, subset of Haskell where the library functions are the + primitives. Sometimes advanced Haskell features such as + polymorphism, higher-order values or type classes can be used in + the embedded language. \cite[hudak96] + + For an \small{EDSL}, the definitions of compiletime and runtime + are typically fuzzy (and thus hard to define here), since the + \small{EDSL} \quote{compiler} is usually compiled by the same + Haskell compiler as the \small{EDSL} program itself. + \stopframedtext + } + + An obvious question that arises when starting any research is \quote{Has + this not been done before?}. Using a functional language for describing hardware + is not a new idea at all. In fact, there has been research into functional + hardware description even before the conventional hardware description + languages were created. Examples of these are µFP \cite[sheeran83] and + Ruby \cite[jones90]. Functional languages were not nearly as advanced + as they are now, and functional hardware description never really got + off. + + Recently, there have been some renewed efforts, especially using the + Haskell functional language. Examples are Lava \cite[claessen00] (an + \small{EDSL}) and ForSyde \cite[sander04] (an \small{EDSL} using + Template Haskell). \cite[baaij09] has a more complete overview of the + current field. + + We will now have a look at the existing hardware description languages, + both conventional and functional to see the fields in which Cλash is + operating. + + \section{Conventional hardware description languages} + Considering that we already have some hardware description languages like + \small{VHDL} and Verilog, why would we need anything else? By introducing + the functional style to hardware description, we hope to obtain a hardware + description language that is: + \startitemize + \item More concise. Functional programs are known for their conciseness + and ability to provide reusable functions that are abstractions of + common patterns. This is largely enabled by features like an + advanced type system with polymorphism and higher-order functions. + \item Type-safer. Functional programs typically have a highly + expressive type system, which allows a programmer to more strictly + define limitations on values, making it easier to find violations + and thus bugs. + \item Easy to process. Functional languages have nice properties like + purity \refdef{purity} and single binding behaviour, which make it easy + to apply program transformations and optimizations and could potentially + simplify program verification. + \stopitemize + + \section[sec:context:fhdls]{Existing functional hardware description languages} + As noted above, this path has been explored before. However, current + embedded functional hardware description languages (in particular + those using Haskell) are limited. Below a number of downsides are + sketched of the recent attempts using the Haskell language. + \cite[baaij09] has a more complete overview of these and other + languages. + + This list uses Lava and ForSyDe as examples, but tries to generalize + the conclusions to the techniques of embedding a \small{DSL} and + using Template Haskell. + + \placeintermezzo{}{ + \defref{Template Haskell} + \startframedtext[width=8.5cm,background=box,frame=no] + \startalignment[center] + {\tfa Template Haskell} + \stopalignment + \blank[medium] + + Template Haskell is an extension to the \GHC compiler that allows + a program to mark some parts to be evaluated \emph{at compile + time}. These \emph{templates} can then access the abstract syntax + tree (\small{AST}) of the program that is being compiled and + generate parts of this \small{AST}. + + Template Haskell is a very powerful, but also complex mechanism. + It was inteded to simplify the generation of some repetive pieces + of code, but its introspection features have inspired all sorts of + applications, such as hardware description compilers. + \stopframedtext + } + + \startitemize + \item Not all of Haskell's constructs can be captured by embedded domain + specific languages. For example, an \hs{if} or \hs{case} + expression is typically executed once when the Haskell description + is processed and only the result is reflected in the generated + datastructure (and thus in the final program). In Lava, for + example, conditional assignment can only be described by using + explicit multiplexer components, not using any of Haskell's + compact mechanisms (such as \hs{case} expressions or pattern + matching). + + Also, sharing of variables (\eg, using the same variable twice + while only calculating it once) and cycles in circuits are + non-trivial to properly and safely translate (though there is some + work to fix this, but that has not been possible in a completely + reliable way yet \cite[gill09]). + \item Template Haskell makes descriptions verbose. Template + Haskell needs extra annotations to move things around between + \small{TH} and the normal program. When \small{TH} is combined + with an \small{EDSL} approach, it can get confusing when to use + \small{TH} and when not to. + \item Function hierarchies cannot be observed in an \small{EDSL}. + For example, Lava generates a single flat \VHDL architecture, + which has no structure whatsoever. Even though this is strictly + correct, it offers no support to the synthesis software about + which parts of the system can best be placed together and makes + debugging the system very hard. + + It is possible to add explicit annotation to overcome this + limitation (ForSyDe does this using Template Haskell), but this + adds extra verbosity again. + \item Processing in Template Haskell can become very complex, + since it works on the Haskell \small{AST} directly. This means + that every part of the Haskell syntax that is used must be + supported explicitly by the Template Haskell code. + \in{Chapter}[chap:prototype] shows that working on a smaller + \small{AST} is much more efficient. + \stopitemize + +% vim: set sw=2 sts=2 expandtab: