% 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.
%
-
-
-
% *** CITATION PACKAGES ***
%
\usepackage{cite}
% *** GRAPHICS RELATED PACKAGES ***
%
\ifCLASSINFOpdf
- % \usepackage[pdftex]{graphicx}
+ \usepackage[pdftex]{graphicx}
% declare the path(s) where your graphic files are
% \graphicspath{{../pdf/}{../jpeg/}}
% and their extensions so you won't have to specify these with
\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
netlist. This research also features a prototype translator called \CLaSH\
(pronounced: clash), which converts the Haskell code to equivalently behaving
synthesizable \VHDL\ code, ready to be converted to an actual netlist format
-by optimizing \VHDL\ synthesis tools.
+by an optimizing \VHDL\ synthesis tool.
\section{Hardware description in Haskell}
\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 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 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}
-
-\comment{TODO: Pretty picture}
-
- \subsection{Choices}
- Although describing components and connections allows describing a
- lot of hardware designs already, there is an obvious thing missing:
- choice. We need some way to be able to choose between values based
- on another value. In Haskell, choice is achieved by \hs{case}
- expressions, \hs{if} expressions, pattern matching and guards.
-
- The easiest of these are of course case expressions (and \hs{if}
- expressions, which can be very directly translated to \hs{case}
- expressions). A \hs{case} expression can in turn simply be
- translated to a conditional assignment in \VHDL, where the
- conditions use equality comparisons against the constructors in the
- \hs{case} expressions.
-
- 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.
-
- A pattern match (with optional guards) can also be implemented using
- conditional assignments in \VHDL, where the condition is the logical
- and of comparison results of each part of the pattern as well as the
- guard.
-
- Contrived example that sums two values when they are equal or
- non-equal (depending on the predicate given) and returns 0
- otherwise. This shows three implementations, one using and if
- expression, one using only case expressions and one using pattern
- matching and guards.
-
+ 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{Choice}
+ In Haskell, choice can be achieved by a large set of language constructs,
+ consisting of: \hs{case} constructs, \hs{if-then-else} constructs,
+ pattern matching, and guards. The easiest of these are the \hs{case}
+ constructs (and \hs{if} expressions, which can be very directly translated
+ to \hs{case} expressions). A \hs{case} expression can in turn simply be
+ translated to a conditional assignment in \VHDL, where the conditions use
+ equality comparisons against the constructors in the \hs{case}
+ expressions. We can see two versions of a contrived example, the first
+ using a \hs{case} construct and the other using a \hs{if-then-else}
+ constructs, in the code below. The example sums two values when they are
+ equal or non-equal (depending on the predicate given) and returns 0
+ otherwise.
+
\begin{code}
- sumif pred a b = if pred == Eq && a == b ||
- pred == Neq && a != b
- then a + b
- else 0
-
sumif pred a b = case pred of
Eq -> case a == b of
True -> a + b
Neq -> case a != b of
True -> a + b
False -> 0
+ \end{code}
+
+ \begin{code}
+ sumif pred a b =
+ if pred == Eq then
+ if a == b then a + b else 0
+ else
+ if a != b then a + b else 0
+ \end{code}
+ Both versions of the example correspond to the same netlist, which is
+ depicted in \Cref{img:choice}
+
+ \begin{figure}
+ \centerline{\includegraphics{choice-case}}
+ \caption{Choice - sumif}
+ \label{img:choice}
+ \end{figure}
+
+ 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. Expressions can also contain guards,
+ where the expression is only executed if the guard evaluates to true. A
+ pattern match (with optional guards) can be to a conditional assignments
+ in \VHDL, where the conditions are an equality test of the argument and
+ one of the patterns (combined with the guard if was present). A third
+ version of the earlier example, using both pattern matching and guards,
+ can be seen below:
+
+ \begin{code}
sumif Eq a b | a == b = a + b
sumif Neq a b | a != b = a + b
sumif _ _ _ = 0
\end{code}
+
+ The version using pattern matching and guards has the same netlist
+ representation (\Cref{img:choice}) as the earlier two versions of the
+ example.
- \comment{TODO: Pretty picture}
+ % \begin{figure}
+ % \centerline{\includegraphics{choice-ifthenelse}}
+ % \caption{Choice - \emph{if-then-else}}
+ % \label{img:choice}
+ % \end{figure}
\subsection{Types}
Translation of two most basic functional concepts has been
currently supported.
\end{xlist}
+ \subsection{Polymorphic functions}
+ A powerful construct in most functional language is polymorphism.
+ This means the arguments of a function (and consequentially, values
+ within the function as well) do not need to have a fixed type.
+ Haskell supports \emph{parametric polymorphism}, meaning a
+ function's type can be parameterized with another type.
+
+ As an example of a polymorphic function, consider the following
+ \hs{append} function's type:
+
+ TODO: Use vectors instead of lists?
+
+ \begin{code}
+ append :: [a] -> a -> [a]
+ \end{code}
+
+ This type is parameterized by \hs{a}, which can contain any type at
+ all. This means that append can append an element to a list,
+ regardless of the type of the elements in the list (but the element
+ added must match the elements in the list, since there is only one
+ \hs{a}).
+
+ This kind of polymorphism is extremely useful in hardware designs to
+ make operations work on a vector without knowing exactly what elements
+ are inside, routing signals without knowing exactly what kinds of
+ signals these are, or working with a vector without knowing exactly
+ how long it is. Polymorphism also plays an important role in most
+ higher order functions, as we will see in the next section.
+
+ The previous example showed unconstrained polymorphism (TODO: How is
+ this really called?): \hs{a} can have \emph{any} type. Furthermore,
+ Haskell supports limiting the types of a type parameter to specific
+ class of types. An example of such a type class is the \hs{Num}
+ class, which contains all of Haskell's numerical types.
+
+ Now, take the addition operator, which has the following type:
+
+ \begin{code}
+ (+) :: Num a => a -> a -> a
+ \end{code}
+
+ This type is again parameterized by \hs{a}, but it can only contain
+ types that are \emph{instances} of the \emph{type class} \hs{Num}.
+ Our numerical built-in types are also instances of the \hs{Num}
+ class, so we can use the addition operator on \hs{SizedWords} as
+ well as on {SizedInts}.
+
+ In \CLaSH, unconstrained polymorphism is completely supported. Any
+ function defined can have any number of unconstrained type
+ parameters. The \CLaSH\ compiler will infer the type of every such
+ argument depending on how the function is applied. There is one
+ exception to this: The top level function that is translated, can
+ not have any polymorphic arguments (since it is never applied, so
+ there is no way to find out the actual types for the type
+ parameters).
+
+ \CLaSH\ does not support user-defined type classes, but does use some
+ 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