X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Fdsd-paper.git;a=blobdiff_plain;f=c%CE%BBash.lhs;h=a83750ba69b3c7dbf1b339d2913c759c4add756c;hp=5819c83dd48d7da7398a0c20748dd62278d876d2;hb=380b879df0cc5c8826f9a3731687311d8840011d;hpb=9acd9933a384365a3859ba4cc0fc29b53c2737d5

diff --git "a/c\316\273ash.lhs" "b/c\316\273ash.lhs"
index 5819c83..a83750b 100644
--- "a/c\316\273ash.lhs"
+++ "b/c\316\273ash.lhs"
@@ -63,6 +63,7 @@
 % should be used if it is desired that the figures are to be displayed in
 % draft mode.
 %
+
 \documentclass[conference,pdf,a4paper,10pt,final,twoside,twocolumn]{IEEEtran}
 % Add the compsoc option for Computer Society conferences.
 %
@@ -93,9 +94,6 @@
 
 
 
-
-
-
 % *** CITATION PACKAGES ***
 %
 \usepackage{cite}
@@ -371,6 +369,12 @@
 \usepackage{xcolor}
 \def\comment#1{{\color[rgb]{1.0,0.0,0.0}{#1}}}
 
+\usepackage{cleveref}
+\crefname{figure}{figure}{figures}
+\newcommand{\fref}[1]{\cref{#1}} 
+\newcommand{\Fref}[1]{\Cref{#1}}
+
+
 %include polycode.fmt
 %include clash.fmt
 
@@ -526,43 +530,44 @@ by an optimizing \VHDL\ synthesis tools.
 
   \subsection{Function application}
     The basic syntactic elements of a functional program are functions
-    and function application. These have a single obvious \VHDL\
-    translation: each top level function becomes a hardware component,
-    where each argument is an input port and the result value is the
-    (single) output port. This output port can have a complex type (such
-    as a tuple), so having just a single output port does not create a
-    limitation.
-
-    Each function application in turn becomes a component instantiation.
-    Here, the result of each argument expression is assigned to a
-    signal, which is mapped to the corresponding input port. The output
-    port of the function is also mapped to a signal, which is used as
-    the result of the application itself.
+    and function application. These have a single obvious translation to a 
+    netlist: every function becomes a component, every function argument is an
+    input port and the result value is of a function is an output port. This 
+    output port can have a complex type (such as a tuple), so having just a 
+    single output port does not create a limitation. Each function application 
+    in turn becomes a component instantiation. Here, the result of each 
+    argument expression is assigned to a signal, which is mapped to the 
+    corresponding input port. The output port of the function is also mapped 
+    to a signal, which is used as the result of the application itself.
 
     Since every top level function generates its own component, the
-    hierarchy of function calls is reflected in the final \VHDL\
-    output as well, creating a hierarchical \VHDL\ description of the
-    hardware.  This separation in different components makes the
-    resulting \VHDL\ output easier to read and debug.
-
-    Example that defines the \texttt{mac} function by applying the
-    \texttt{add} and \texttt{mul} functions to calculate $a * b + c$:
-
-\begin{code}
-mac a b c = add (mul a b) c
-\end{code}
-
-\begin{figure}
-\centerline{\includegraphics{mac}}
-\caption{Combinatorial Multiply-Accumulate (curried)}
-\label{img:mac-comb}
-\end{figure}
-
-\begin{figure}
-\centerline{\includegraphics{mac-nocurry}}
-\caption{Combinatorial Multiply-Accumulate (uncurried)}
-\label{img:mac-comb-nocurry}
-\end{figure}
+    hierarchy of function calls is reflected in the final netlist aswell, 
+    creating a hierarchical description of the hardware. This separation in 
+    different components makes the resulting \VHDL\ output easier to read and 
+    debug.
+
+    As an example we can see the netlist of the |mac| function in
+    \Cref{img:mac-comb}; the |mac| function applies both the |mul| and |add|
+    function to calculate $a * b + c$:
+    \begin{code}
+    mac a b c = add (mul a b) c
+    \end{code}
+    \begin{figure}
+    \centerline{\includegraphics{mac}}
+    \caption{Combinatorial Multiply-Accumulate}
+    \label{img:mac-comb}
+    \end{figure}
+    The result of using a complex input type can be seen in 
+    \cref{img:mac-comb-nocurry} where the |mac| function now uses a single
+    input tuple for the |a|, |b|, and |c| arguments:
+    \begin{code}
+    mac (a, b, c) = add (mul a b) c
+    \end{code}
+    \begin{figure}
+    \centerline{\includegraphics{mac-nocurry}}
+    \caption{Combinatorial Multiply-Accumulate (complex input)}
+    \label{img:mac-comb-nocurry}
+    \end{figure}
 
   \subsection{Choices}
     Although describing components and connections allows describing a
@@ -613,7 +618,17 @@ mac a b c = add (mul a b) c
     sumif _ _ _     = 0
     \end{code}
 
-  \comment{TODO: Pretty picture}
+    \begin{figure}
+    \centerline{\includegraphics{choice-ifthenelse}}
+    \caption{Choice - \emph{if-then-else}}
+    \label{img:choice}
+    \end{figure}
+
+    \begin{figure}
+    \centerline{\includegraphics{choice-case}}
+    \caption{Choice - \emph{case-statement / pattern matching}}
+    \label{img:choice}
+    \end{figure}
 
   \subsection{Types}
     Translation of two most basic functional concepts has been
@@ -810,6 +825,120 @@ data IntPair = IntPair Int Int
     of the builtin ones for its builtin functions (like \hs{Num} and
     \hs{Eq}).
 
+  \subsection{Higher order}
+    Another powerful abstraction mechanism in functional languages, is
+    the concept of \emph{higher order functions}, or \emph{functions as
+    a first class value}. This allows a function to be treated as a
+    value and be passed around, even as the argument of another
+    function. Let's clarify that with an example:
+    
+    \begin{code}
+    notList xs = map not xs
+    \end{code}
+
+    This defines a function \hs{notList}, with a single list of booleans
+    \hs{xs} as an argument, which simply negates all of the booleans in
+    the list. To do this, it uses the function \hs{map}, which takes
+    \emph{another function} as its first argument and applies that other
+    function to each element in the list, returning again a list of the
+    results.
+
+    As you can see, the \hs{map} function is a higher order function,
+    since it takes another function as an argument. Also note that
+    \hs{map} is again a polymorphic function: It does not pose any
+    constraints on the type of elements in the list passed, other than
+    that it must be the same as the type of the argument the passed
+    function accepts. The type of elements in the resulting list is of
+    course equal to the return type of the function passed (which need
+    not be the same as the type of elements in the input list). Both of
+    these can be readily seen from the type of \hs{map}:
+
+    \begin{code}
+    map :: (a -> b) -> [a] -> [b]
+    \end{code}
+    
+    As an example from a common hardware design, let's look at the
+    equation of a FIR filter.
+
+    \begin{equation}
+    y_t  = \sum\nolimits_{i = 0}^{n - 1} {x_{t - i}  \cdot h_i } 
+    \end{equation}
+
+    A FIR filter multiplies fixed constants ($h$) with the current and
+    a few previous input samples ($x$). Each of these multiplications
+    are summed, to produce the result at time $t$.
+
+    This is easily and directly implemented using higher order
+    functions. Consider that the vector \hs{hs} contains the FIR
+    coefficients and the vector \hs{xs} contains the current input sample
+    in front and older samples behind. How \hs{xs} gets its value will be
+    show in the next section about state.
+
+    \begin{code}
+    fir ... = foldl1 (+) (zipwith (*) xs hs)
+    \end{code}
+
+    Here, the \hs{zipwith} function is very similar to the \hs{map}
+    function: It takes a function two lists and then applies the
+    function to each of the elements of the two lists pairwise
+    (\emph{e.g.}, \hs{zipwith (+) [1, 2] [3, 4]} becomes 
+    \hs{[1 + 3, 2 + 4]}.
+
+    The \hs{foldl1} function takes a function and a single list and applies the
+    function to the first two elements of the list. It then applies to
+    function to the result of the first application and the next element
+    from the list. This continues until the end of the list is reached.
+    The result of the \hs{foldl1} function is the result of the last
+    application.
+
+    As you can see, the \hs{zipwith (*)} function is just pairwise
+    multiplication and the \hs{foldl1 (+)} function is just summation.
+
+    To make the correspondence between the code and the equation even
+    more obvious, we turn the list of input samples in the equation
+    around. So, instead of having the the input sample received at time
+    $t$ in $x_t$, $x_0$ now always stores the current sample, and $x_i$
+    stores the $ith$ previous sample. This changes the equation to the
+    following (Note that this is completely equivalent to the original
+    equation, just with a different definition of $x$ that better suits
+    the \hs{x} from the code):
+
+    \begin{equation}
+    y_t  = \sum\nolimits_{i = 0}^{n - 1} {x_i  \cdot h_i } 
+    \end{equation}
+
+    So far, only functions have been used as higher order values. In
+    Haskell, there are two more ways to obtain a function-typed value:
+    partial application and lambda abstraction. Partial application
+    means that a function that takes multiple arguments can be applied
+    to a single argument, and the result will again be a function (but
+    that takes one argument less). As an example, consider the following
+    expression, that adds one to every element of a vector:
+
+    \begin{code}
+    map ((+) 1) xs
+    \end{code}
+
+    Here, the expression \hs{(+) 1} is the partial application of the
+    plus operator to the value \hs{1}, which is again a function that
+    adds one to its argument.
+
+    A labmda expression allows one to introduce an anonymous function
+    in any expression. Consider the following expression, which again
+    adds one to every element of a list:
+
+    \begin{code}
+    map (\x -> x + 1) xs
+    \end{code}
+
+    Finally, higher order arguments are not limited to just builtin
+    functions, but any function defined in \CLaSH can have function
+    arguments. This allows the hardware designer to use a powerful
+    abstraction mechanism in his designs and have an optimal amount of
+    code reuse.
+
+    TODO: Describe ALU example (no code)
+
   \subsection{State}
     A very important concept in hardware it the concept of state. In a 
     stateful design, the outputs depend on the history of the inputs, or the