Chapters/Context.tex

   1 \chapter[chap:context]{Context}
   2
   3     \placeintermezzo{}{
   4       \defref{EDSL}
   5       \startframedtext[width=8.5cm,background=box,frame=no]
   6       \startalignment[center]
   7         {\tfa Embedded domain-specific languages (\small{EDSL})}
   8       \stopalignment
   9       \blank[medium]
  10
  11       \startcitedquotation[deursen00]
  12       A domain-specific language (\small{DSL}) is a program-
  13       ming language or executable specification language
  14       that offers, through appropriate notations and ab-
  15       stractions, expressive power focused on, and usu-
  16       ally restricted to, a particular problem domain.
  17       \stopcitedquotation
  18
  19       An embedded \small{DSL} is a \small{DSL} that is embedded in
  20       another language. Haskell is commonly used to embed \small{DSL}s
  21       in, which typically means a number of Haskell functions and types
  22       are made available that can be called to construct a large value
  23       of some domain-specific datatype (\eg, a circuit datatype). This
  24       generated datatype can then be processed further by the
  25       \small{EDSL} \quote{compiler} (which runs in the same environment
  26       as the \small{EDSL} itself. The embedded language is then a, mostly
  27       applicative, subset of Haskell where the library functions are the
  28       primitives. Sometimes advanced Haskell features such as
  29       polymorphism, higher-order values or type classes can be used in
  30       the embedded language. \cite[hudak96]
  31
  32       For an \small{EDSL}, the definitions of compiletime and runtime
  33       are typically fuzzy (and thus hard to define here), since the
  34       \small{EDSL} \quote{compiler} is usually compiled by the same
  35       Haskell compiler as the \small{EDSL} program itself.
  36       \stopframedtext
  37     }
  38
  39   An obvious question that arises when starting any research is \quote{Has
  40   this not been done before?}. Using a functional language for describing hardware
  41   is not a new idea at all. In fact, there has been research into functional
  42   hardware description even before the conventional hardware description
  43   languages were created. Examples of these are µFP \cite[sheeran83]\ and
  44   Ruby \cite[jones90]. Functional languages were not nearly as advanced
  45   as they are now, and functional hardware description never really got
  46   off.
  47
  48   Recently, there have been some renewed efforts, especially using the
  49   Haskell functional language. Examples are Lava \cite[claessen00]\ (an
  50   \small{EDSL}) and ForSyde \cite[sander04]\ (an \small{EDSL} using
  51   Template Haskell). \cite[baaij09]\ has a more complete overview of the
  52   current field.
  53
  54   We will now have a look at the existing hardware description languages,
  55   both conventional and functional to see the fields in which Cλash is
  56   operating.
  57
  58   \section{Conventional hardware description languages}
  59     Considering that we already have some hardware description languages like
  60     \small{VHDL} and Verilog, why would we need anything else? By introducing
  61     the functional style to hardware description, we hope to obtain a hardware
  62     description language that is:
  63     \startitemize
  64       \item More concise. Functional programs are known for their conciseness
  65       and ability to provide reusable functions that are abstractions of
  66       common patterns. This is largely enabled by features like an
  67       advanced type system with polymorphism and higher-order functions.
  68       \item Type-safer. Functional programs typically have a highly
  69       expressive type system, which allows a programmer to more strictly
  70       define limitations on values, making it easier to find violations
  71       and thus bugs.
  72       \item Easy to process. Functional languages have nice properties like
  73       purity \refdef{purity} and single binding behaviour, which make it easy
  74       to apply program transformations and optimizations and could potentially
  75       simplify program verification.
  76     \stopitemize
  77
  78   \section[sec:context:fhdls]{Existing functional hardware description languages}
  79     As noted above, this path has been explored before. However, current
  80     embedded functional hardware description languages (in particular
  81     those using Haskell) are limited. Below a number of downsides are
  82     sketched of the recent attempts using the Haskell language.
  83     \cite[baaij09]\ has a more complete overview of these and other
  84     languages.
  85
  86     This list uses Lava and ForSyDe as examples, but tries to generalize
  87     the conclusions to the techniques of embedding a \small{DSL} and
  88     using Template Haskell.
  89
  90     \placeintermezzo{}{
  91       \defref{Template Haskell}
  92       \startframedtext[width=8.5cm,background=box,frame=no]
  93       \startalignment[center]
  94         {\tfa Template Haskell}
  95       \stopalignment
  96       \blank[medium]
  97
  98       Template Haskell is an extension to the \GHC\ compiler that allows
  99       a program to mark some parts to be evaluated \emph{at compile
 100       time}. These \emph{templates} can then access the abstract syntax
 101       tree (\small{AST}) of the program that is being compiled and
 102       generate parts of this \small{AST}.
 103
 104       Template Haskell is a very powerful, but also complex mechanism.
 105       It was inteded to simplify the generation of some repetive pieces
 106       of code, but its introspection features have inspired all sorts of
 107       applications, such as hardware description compilers.
 108       \stopframedtext
 109     }
 110
 111     \startitemize
 112       \item Not all of Haskell's constructs can be captured by embedded domain
 113       specific languages. For example, an \hs{if} or \hs{case}
 114       expression is typically executed once when the Haskell description
 115       is processed and only the result is reflected in the generated
 116       datastructure (and thus in the final program). In Lava, for
 117       example, conditional assignment can only be described by using
 118       explicit multiplexer components, not using any of Haskell's
 119       compact mechanisms (such as \hs{case} expressions or pattern
 120       matching).
 121
 122       Also, sharing of variables (\eg, using the same variable twice
 123       while only calculating it once) and cycles in circuits are
 124       non-trivial to properly and safely translate (though there is some
 125       work to fix this, but that has not been possible in a completely
 126       reliable way yet \cite[gill09]).
 127       \item Template Haskell makes descriptions verbose. Template
 128       Haskell needs extra annotations to move things around between
 129       \small{TH} and the normal program. When \small{TH} is combined
 130       with an \small{EDSL} approach, it can get confusing when to use
 131       \small{TH} and when not to.
 132       \item Function hierarchies cannot be observed in an \small{EDSL}.
 133       For example, Lava generates a single flat \VHDL\ architecture,
 134       which has no structure whatsoever. Even though this is strictly
 135       correct, it offers no support to the synthesis software about
 136       which parts of the system can best be placed together and makes
 137       debugging the system very hard.
 138
 139       It is possible to add explicit annotation to overcome this
 140       limitation (ForSyDe does this using Template Haskell), but this
 141       adds extra verbosity again.
 142       \item Processing in Template Haskell can become very complex,
 143       since it works on the Haskell \small{AST} directly. This means
 144       that every part of the Haskell syntax that is used must be
 145       supported explicitly by the Template Haskell code.
 146       \in{Chapter}[chap:prototype] shows that working on a smaller
 147       \small{AST} is much more efficient.
 148     \stopitemize
 149
 150 % vim: set sw=2 sts=2 expandtab: