X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Freport.git;a=blobdiff_plain;f=Chapters%2FContext.tex;h=45c16864d17abc38cb0f0a114abce1a5c1527c60;hp=3c09d95316e5c9aacd4479be0af9cbc9a77a01c8;hb=a0a2821832d86271ffc8efdb3774440191f3e10e;hpb=8ec0a2193fa53fd7bc15c2118e676f82e904f493 diff --git a/Chapters/Context.tex b/Chapters/Context.tex index 3c09d95..45c1686 100644 --- a/Chapters/Context.tex +++ b/Chapters/Context.tex @@ -1,24 +1,55 @@ \chapter[chap:context]{Context} + + \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 + 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. \todo{Reference about early FHDLs} However, - functional languages were not nearly as advanced as they are now, and - functional hardware description never really got off. + 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. -\todo{Add references} - Recently, there have been some renewed efforts, especially using the Haskell - functional language. Examples are Lava, ForSyde, ..., which are all a form of an - embedded domain specific language. Each of these have a slightly different - approach, but all of these do some trickery inside the Haskell language - itself, meaning you write a program that generates a hardware circuit, - instead of describing the circuit directly (either by running the haskell - code after compilation, or using Template Haskell to inspect parts of the - code you have written). This allows the full power of Haskell for generating - a circuit. However it also creates severe limitations in the use of the - language (you can't use case statements in Lava, since they would be - executed only once during circuit generation) and extra notational overhead. + 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 @@ -30,83 +61,90 @@ the functional style to hardware description, we hope to obtain a hardware description language that is: \startitemize - \item More consise. Functional programs are known for their conciseness - and ability to abstract away common patterns. This is largely enabled - by features like an advanced type system with polymorphism and higher - order functions. - \todo{Does this apply to FHDLs equally?} - \item Type-safer. Functional programs typically have a highly expressive - type system, which makes it harder to write incorrect code. + \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{EDSL} + \defref{Template Haskell} \startframedtext[width=8.5cm,background=box,frame=no] \startalignment[center] - {\tfa Embedded domain-specific languages (\small{EDSL})} + {\tfa Template Haskell} \stopalignment \blank[medium] - - \startcitedquotation[hudak96] - 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 - - \todo{ref: http://portal.acm.org/citation.cfm?id=352035\&dl=} - 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. + 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 } - \section[sec:context:fhdls]{Existing functional hardware description languages} - As noted above, we're not the first to walk this path. However, current - embedded functional hardware description languages (in particular those - using Haskell) are limited by:\todo{Separate TH and EDSL approaches - better} \startitemize \item Not all of Haskell's constructs can be captured by embedded domain - specific languages. For example, an if or case expression is typically - executed only once and only its result is reflected in the embedded - description, not the if or case expression itself. 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. \todo{ref - http://www.ittc.ku.edu/~andygill/paper.php?label=DSLExtract09} - \item Some things are verbose to express. Especially ForSyDe suffers - from a lot of notational overhead due to the Template Haskell approach - used. Since conditional statements are not supported, a lot of Haskell's - syntax sugar (if expressions, pattern matching, guards) cannot be used - either, leading to more verbose notation as well. - \item Polymorphism and higher order values are not supported within the - embedded language. The use of Haskell as a host language allows the use - of polymorphism and higher order functions at circuit generation time - (even for free, without any additional cost on the \small{EDSL} - programmers), but the described circuits do not have any polymorphism - or higher order functions, which can be limiting. \todo{How true or - appropriate is this point?} - \todo[left]{Function structure gets lost (in Lava)} - \stopitemize + 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. - \todo[text]{Complete translation in TH is complex: Works with Haskell AST - instead of Core} + 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: