Fix spelling as suggested by aspell.

[matthijs/master-project/report.git] / Chapters / Context.tex

diff --git a/Chapters/Context.tex b/Chapters/Context.tex
index 9444a6e8e78b58ea9a25ec1214398456ccedab7f..7323b5b42f60b0f3d4243d4c523d30f3281ddcf8 100644 (file)
--- a/Chapters/Context.tex
+++ b/Chapters/Context.tex
@@ -1,24 +1,54 @@
 \chapter[chap:context]{Context}
 \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 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
   An obvious question that arises when starting any research is \quote{Has

-  this not been done before?} Using a functional language for describing hardware
+  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
   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. \todo{Reference about early FHDLs} 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. 

 
 

-\todo{Add references}
-  Recently, there have been some renewed efforts, especially using the Haskell
-  functional 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. However it also creates severe limitations in the use of the
-  language (you can't use case expressions 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.

 
   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
 
   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


@@ -30,79 +60,90 @@
     the functional style to hardware description, we hope to obtain a hardware
     description language that is:
     \startitemize
     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
-      and ability to abstract away  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 makes it harder to write incorrect code.
+      \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
       \item Easy to process. Functional languages have nice properties like

-      purity \refdef{purity} and single binding behaviour, which make it easy
+      purity \refdef{purity} and single binding behavior, which make it easy

       to apply program transformations and optimizations and could potentially
       simplify program verification.
     \stopitemize
   
       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{}{
     \placeintermezzo{}{

-      \defref{EDSL}
+      \defref{Template Haskell}

       \startframedtext[width=8.5cm,background=box,frame=no]
       \startalignment[center]
       \startframedtext[width=8.5cm,background=box,frame=no]
       \startalignment[center]

-        {\tfa Embedded domain-specific languages (\small{EDSL})}
+        {\tfa Template Haskell}

       \stopalignment
       \blank[medium]
       \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
+      
+      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}.

 
 

-      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]
+      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
     }
 
       \stopframedtext
     }
 

-  \section[sec:context:fhdls]{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:\todo{Separate TH and EDSL approaches
-    better}

     \startitemize
       \item Not all of Haskell's constructs can be captured by embedded domain
     \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 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 Some things are verbose to express. Especially ForSyDe suffers
-      from a lot of notational overhead due to the Template Haskell approach
-      used. Since conditional expressions 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?}
-      \todo[left]{Function structure gets lost (in Lava)}
-    \stopitemize
+      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).

 
 

-    \todo[text]{Complete translation in TH is complex: Works with Haskell AST
-    instead of Core}
+      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:
 
 % vim: set sw=2 sts=2 expandtab: