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