Add two intermezzo's and shuffle some floats around.
authorMatthijs Kooijman <matthijs@stdin.nl>
Tue, 8 Dec 2009 15:03:06 +0000 (16:03 +0100)
committerMatthijs Kooijman <matthijs@stdin.nl>
Tue, 8 Dec 2009 15:03:06 +0000 (16:03 +0100)
One intermezzo about reading Cλash and one about null, head and tail.

Chapters/HardwareDescription.tex

index eab0a49..db469c5 100644 (file)
@@ -5,8 +5,6 @@
   the implementation. The prototype implementation will be discussed in
   \in{chapter}[chap:prototype].
 
-  \todo{Shortshort introduction to Cλash (Bit, Word, and, not, etc.)}
-
   To translate Haskell to hardware, every Haskell construct needs a
   translation to \VHDL. There are often multiple valid translations
   possible. When faced with choices, the most obvious choice has been
   possible.
    
   \placeintermezzo{}{
-    \defref{top level binder}
-    \defref{top level function}
-    \startframedtext[width=8cm,background=box,frame=no]
+    \defref{reading examples}
+    \startframedtext[width=9cm,background=box,frame=no]
     \startalignment[center]
-      {\tfa Top level binders and functions}
+      {\tfa Reading the examples}
     \stopalignment
     \blank[medium]
-      A top level binder is any binder (variable) that is declared in
-      the \quote{global} scope of a Haskell program (as opposed to a
-      binder that is bound inside a function.
-
-      In Haskell, there is no sharp distinction between a variable and a
-      function: a function is just a variable (binder) with a function
-      type. This means that a top level function is just any top level
-      binder with a function type.
-
-      As an example, consider the following Haskell snippet:
-
-      \starthaskell
-        foo :: Int -> Int
-        foo x = inc x
-          where
-            inc = \y -> y + 1
-      \stophaskell
-
-      Here, \hs{foo} is a top level binder, whereas \hs{inc} is a
-      function (since it is bound to a lambda extraction, indicated by
-      the backslash) but is not a top level binder or function.  Since
-      the type of \hs{foo} is a function type, namely \hs{Int -> Int},
-      it is also a top level function.
+      In this thesis, a lot of functional code will be presented. Part of this
+      will be valid Cλash code, but others will just be small Haskell or Core
+      snippets to illustrate a concept.
+
+      In these examples, some functions and types will be used, without
+      properly defining every one of them. These functions (like \hs{and},
+      \hs{not}, \hs{add}, \hs{+}, etc.) and types (like \hs{Bit}, \hs{Word},
+      \hs{Bool}, etc.) are usually pretty self-explanatory.
+
+      The special type \hs{[t]} means \quote{list of \hs{t}'s}, where \hs{t}
+      can be any other type.
+
+      Of particular note is the use of the \hs{::} operator. It is used in
+      Haskell to explicitly declare the type of function or let binding. In
+      these examples and the text, we will occasionally use this operator to
+      show the type of arbitrary expressions, even where this would not
+      normally be valid. Just reading the \hs{::} operator as \quote{and also
+      note that \emph{this} expression has \emph{this} type} should work out.
     \stopframedtext
   }
+
   In this chapter we describe how to interpret a Haskell program from a
   hardware perspective. We provide a description of each Haskell language
   element that needs translation, to provide a clear picture of what is
@@ -115,12 +108,45 @@ and3 a b c = and (and a b) c
     ncline(andb)(out);
   \stopuseMPgraphic
 
-  \placeexample[here][ex:And3]{Simple three input and gate.}
+  \placeexample[][ex:And3]{Simple three input and gate.}
     \startcombination[2*1]
       {\typebufferhs{And3}}{Haskell description using function applications.}
       {\boxedgraphic{And3}}{The architecture described by the Haskell description.}
     \stopcombination
 
+  \placeintermezzo{}{
+    \defref{top level binder}
+    \defref{top level function}
+    \startframedtext[width=8cm,background=box,frame=no]
+    \startalignment[center]
+      {\tfa Top level binders and functions}
+    \stopalignment
+    \blank[medium]
+      A top level binder is any binder (variable) that is declared in
+      the \quote{global} scope of a Haskell program (as opposed to a
+      binder that is bound inside a function.
+
+      In Haskell, there is no sharp distinction between a variable and a
+      function: a function is just a variable (binder) with a function
+      type. This means that a top level function is just any top level
+      binder with a function type.
+
+      As an example, consider the following Haskell snippet:
+
+      \starthaskell
+        foo :: Int -> Int
+        foo x = inc x
+          where
+            inc = \y -> y + 1
+      \stophaskell
+
+      Here, \hs{foo} is a top level binder, whereas \hs{inc} is a
+      function (since it is bound to a lambda extraction, indicated by
+      the backslash) but is not a top level binder or function.  Since
+      the type of \hs{foo} is a function type, namely \hs{Int -> Int},
+      it is also a top level function.
+    \stopframedtext
+  }
   \section{Choice}
     Although describing components and connections allows us to describe a lot of
     hardware designs already, there is an obvious thing missing: choice. We
@@ -144,8 +170,22 @@ and3 a b c = and (and a b) c
     simply be translated to a conditional assignment, where the conditions use
     equality comparisons against the constructors in the \hs{case} expressions.
 
+    In \in{example}[ex:CaseInv] a simple \hs{case} expression is shown,
+    scrutinizing a boolean value. The corresponding architecture has a
+    comparator to determine which of the constructors is on the \hs{in}
+    input. There is a multiplexer to select the output signal. The two options
+    for the output signals are just constants, but these could have been more
+    complex expressions (in which case also both of them would be working in
+    parallel, regardless of which output would be chosen eventually).
+
+    If we would translate a Boolean to a bit value, we could of course remove
+    the comparator and directly feed 'in' into the multiplexer (or even use an
+    inverter instead of a multiplexer).  However, we will try to make a
+    general translation, which works for all possible \hs{case} expressions.
+    Optimizations such as these are left for the \VHDL\ synthesizer, which
+    handles them very well.
+
     \placeintermezzo{}{
-      \defref{substitution notation}
       \startframedtext[width=8cm,background=box,frame=no]
       \startalignment[center]
         {\tfa Arguments / results vs. inputs / outputs}
@@ -165,20 +205,23 @@ and3 a b c = and (and a b) c
       \stopframedtext
     }
 
-    In \in{example}[ex:CaseInv] a simple \hs{case} expression is shown,
-    scrutinizing a boolean value. The corresponding architecture has a
-    comparator to determine which of the constructors is on the \hs{in}
-    input. There is a multiplexer to select the output signal. The two options
-    for the output signals are just constants, but these could have been more
-    complex expressions (in which case also both of them would be working in
-    parallel, regardless of which output would be chosen eventually).
-    
-    If we would translate a Boolean to a bit value, we could of course remove
-    the comparator and directly feed 'in' into the multiplexer (or even use an
-    inverter instead of a multiplexer).  However, we will try to make a
-    general translation, which works for all possible \hs{case} expressions.
-    Optimizations such as these are left for the \VHDL\ synthesizer, which
-    handles them very well.
+    A slightly more complex (but very powerful) form of choice is pattern
+    matching. A function can be defined in multiple clauses, where each clause
+    specifies a pattern. When the arguments match the pattern, the
+    corresponding clause will be used.
+
+    The architecture described by \in{example}[ex:PatternInv] is of course the
+    same one as the one in \in{example}[ex:CaseInv]. The general interpretation
+    of pattern matching is also similar to that of \hs{case} expressions: generate
+    hardware for each of the clauses (like each of the clauses of a \hs{case}
+    expression) and connect them to the function output through (a number of
+    nested) multiplexers. These multiplexers are driven by comparators and
+    other logic, that check each pattern in turn.
+
+    In these examples we have seen only binary case expressions and pattern
+    matches (\ie, with two alternatives). In practice, case expressions can
+    choose between more than two values, resulting in a number of nested
+    multiplexers.
 
     \startbuffer[CaseInv]
     inv :: Bool -> Bool
@@ -221,40 +264,22 @@ and3 a b c = and (and a b) c
       ncline(mux)(out) "posA(out)";
     \stopuseMPgraphic
 
-    \placeexample[here][ex:CaseInv]{Simple inverter.}
+    \placeexample[][ex:CaseInv]{Simple inverter.}
       \startcombination[2*1]
         {\typebufferhs{CaseInv}}{Haskell description using a Case expression.}
         {\boxedgraphic{CaseInv}}{The architecture described by the Haskell description.}
       \stopcombination
 
-    A slightly more complex (but very powerful) form of choice is pattern
-    matching. A function can be defined in multiple clauses, where each clause
-    specifies a pattern. When the arguments match the pattern, the
-    corresponding clause will be used.
-
     \startbuffer[PatternInv]
     inv :: Bool -> Bool
     inv True = False
     inv False = True
     \stopbuffer
 
-    \placeexample[here][ex:PatternInv]{Simple inverter using pattern matching.
+    \placeexample[][ex:PatternInv]{Simple inverter using pattern matching.
     Describes the same architecture as \in{example}[ex:CaseInv].}
         {\typebufferhs{PatternInv}}
 
-    The architecture described by \in{example}[ex:PatternInv] is of course the
-    same one as the one in \in{example}[ex:CaseInv]. The general interpretation
-    of pattern matching is also similar to that of \hs{case} expressions: generate
-    hardware for each of the clauses (like each of the clauses of a \hs{case}
-    expression) and connect them to the function output through (a number of
-    nested) multiplexers. These multiplexers are driven by comparators and
-    other logic, that check each pattern in turn.
-
-    In these examples we have seen only binary case expressions and pattern
-    matches (\ie, with two alternatives). In practice, case expressions can
-    choose between more than two values, resulting in a number of nested
-    multiplexers.
-
   \section{Types}
     Translation of two most basic functional concepts has been
     discussed: function application and choice. Before looking further
@@ -549,7 +574,7 @@ quadruple n = mul (mul n)
     ncline(mulb)(out);
   \stopuseMPgraphic
 
-  \placeexample[here][ex:Quadruple]{Simple three port and.}
+  \placeexample[][ex:Quadruple]{Simple three port and.}
     \startcombination[2*1]
       {\typebufferhs{Quadruple}}{Haskell description using function applications.}
       {\boxedgraphic{Quadruple}}{The architecture described by the Haskell description.}
@@ -852,7 +877,7 @@ acc in = out
 \stopuseMPgraphic
 
 
-        \placeexample[here][ex:DelayAcc]{Simple accumulator architecture.}
+        \placeexample[][ex:DelayAcc]{Simple accumulator architecture.}
           \startcombination[2*1]
             {\typebufferhs{DelayAcc}}{Haskell description using streams.}
             {\boxedgraphic{DelayAcc}}{The architecture described by the Haskell description.}
@@ -887,7 +912,7 @@ acc in s = (s', out)
     s'  = out
 \stopbuffer
 
-        \placeexample[here][ex:ExplicitAcc]{Simple accumulator architecture.}
+        \placeexample[][ex:ExplicitAcc]{Simple accumulator architecture.}
           \startcombination[2*1]
             {\typebufferhs{ExplicitAcc}}{Haskell description using explicit state arguments.}
             % Picture is identical to the one we had just now.
@@ -1045,6 +1070,23 @@ acc in s = (s', out)
   cycle (at best, we could generate hardware that needs an infinite number of
   cycles to complete).
   
+  \placeintermezzo{}{
+    \startframedtext[width=8cm,background=box,frame=no]
+    \startalignment[center]
+      {\tfa \hs{null}, \hs{head} and \hs{tail}}
+    \stopalignment
+    \blank[medium]
+      The functions \hs{null}, \hs{head} and \hs{tail} are common list
+      functions in Haskell. The \hs{null} function simply checks if a list is
+      empty. The \hs{head} function returns the first element of a list. The
+      \hs{tail} function returns containing everything \emph{except} the first
+      element of a list.
+
+      In Cλash, there are vector versions of these functions, which do exactly
+      the same.
+    \stopframedtext
+  }
+
   However, most recursive definitions will describe finite
   recursion. This is because the recursive call is done conditionally. There
   is usually a \hs{case} expression where at least one alternative does not contain