\chapter[chap:context]{Context}

    \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. 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, 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 \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:
