\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 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. 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.
- 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.
+ 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.
-TODO: Define (E)DSL
-TODO: References
+ 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 language like
+ 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,
- mostly caused by the ability to abstract just about any behaviour into a
- helper function. 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. This is
- probably not only directly caused by the type system, so perhaps this
- advantage does not apply in hardware descriptions.
+ \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{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:
+ \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 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 and
- loops are non-trivial do 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?).
+ 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:
projects / matthijs / master-project / report.git / blobdiff