X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Freport.git;a=blobdiff_plain;f=Chapters%2FContext.tex;h=7e620a073e3cd648459b274e23d7543ea5283c9b;hp=f07f1d9cd8a13da4052001a9232315fd8f4830d4;hb=58a5aa7ca5edc07ba1070f4f4ed384b42e36e8f3;hpb=124f838008d9e63d36d6626ebeb453d9f83129dc diff --git a/Chapters/Context.tex b/Chapters/Context.tex index f07f1d9..7e620a0 100644 --- a/Chapters/Context.tex +++ b/Chapters/Context.tex @@ -1,47 +1,5 @@ \chapter[chap:context]{Context} - 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. \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. -\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 expressions in Lava, since they would be - executed only once during circuit generation) and extra notational overhead. - - 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 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. - \item Type-safer. Functional programs typically have a highly expressive - type system, which makes it harder to write incorrect code. - \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 - \placeintermezzo{}{ \defref{EDSL} \startframedtext[width=8.5cm,background=box,frame=no] @@ -67,42 +25,126 @@ \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 + 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, 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} + 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 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 \cite[gill09]). - \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 expressions 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{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{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: