\chapter[chap:context]{Context}
- An obvious question that arises when starting any research is \quote{Hasn't
- this been done before?} Using a functional language for describing hardware
+
+ \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 programming language
+ or executable specification language that offers, through
+ appropriate notations and abstractions, expressive power focused
+ on, and usually 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 compile-time and run-time
+ 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. However, 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
- 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, but only 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.
-
-TODO: Define (E)DSL
-TODO: References
-
- Advantages over conventional HDLs
- - More consise
- - More expressive
- - Easy to transform / optimize / etc.
-
- Advantages over existing FHDLs
- - More control
- - Full Haskell available
- - Concise notation
-
- Disadvantages over existing FHDLs
- - More work to implement advanced things
+ 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 behavior, 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 intended to simplify the generation of some repetitive 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
+ data-structure (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:
projects / matthijs / master-project / report.git / blobdiff