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 any (optimizing) \VHDL\ synthesis tool.
+by an (optimizing) \VHDL\ synthesis tool.
\section{Hardware description in Haskell}
\subsubsection{User-defined types}
There are three ways to define new types in Haskell: algebraic
data-types with the \hs{data} keyword, type synonyms with the \hs{type}
- keyword and datatype renamings with the \hs{newtype} keyword. \GHC\
- offers a few more advanced ways to introduce types (type families,
- existential typing, {\small{GADT}}s, etc.) which are not standard
- Haskell. These are not currently supported.
+ keyword and datatype renaming constructs with the \hs{newtype} keyword.
+ \GHC\ offers a few more advanced ways to introduce types (type families,
+ existential typing, {\small{GADT}}s, etc.) which are not standard Haskell.
+ As it is currently unclear how these advanced type constructs correspond
+ with hardware, they are for now unsupported by the \CLaSH\ compiler
Only an algebraic datatype declaration actually introduces a
- completely new type, for which we provide the \VHDL\ translation
- below. Type synonyms and renamings only define new names for
- existing types, where synonyms are completely interchangeable and
- renamings need explicit conversiona. Therefore, these do not need
- any particular \VHDL\ translation, a synonym or renamed type will
- just use the same representation as the original type. The
- distinction between a renaming and a synonym does no longer matter
- in hardware and can be disregarded in the generated \VHDL. For algebraic
- types, we can make the following distinction:
+ completely new type. Type synonyms and renaming constructs only define new
+ names for existing types, where synonyms are completely interchangeable
+ and renaming constructs need explicit conversions. Therefore, these do not
+ need any particular translation, a synonym or renamed type will just use
+ the same representation as the original type. For algebraic types, we can
+ make the following distinctions:
\begin{xlist}
\item[\bf{Single constructor}]
Algebraic datatypes with a single constructor with one or more
fields, are essentially a way to pack a few values together in a
- record-like structure. An example of such a type is the following pair
- of integers:
-
+ record-like structure. Haskell's built-in tuple types are also defined
+ as single constructor algebraic types An example of a single
+ constructor type is the following pair of integers:
\begin{code}
data IntPair = IntPair Int Int
\end{code}
-
- Haskell's builtin tuple types are also defined as single
- constructor algebraic types and are translated according to this
- rule by the \CLaSH\ compiler.
% These types are translated to \VHDL\ record types, with one field
% for every field in the constructor.
\item[\bf{No fields}]
fields are essentially a way to get an enumeration-like type
containing alternatives. Note that Haskell's \hs{Bool} type is also
defined as an enumeration type, but we have a fixed translation for
- that.
+ that. An example of such an enum type is the type that represents the
+ colors in a traffic light:
+ \begin{code}
+ data TrafficLight = Red | Orange | Green
+ \end{code}
% These types are translated to \VHDL\ enumerations, with one
% value for each constructor. This allows references to these
% constructors to be translated to the corresponding enumeration
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:
-
- \comment{TODO: Use vectors instead of lists?}
+ \subsection{Polymorphism}
+ A powerful construct in most functional languages is polymorphism, it
+ allows a function to handle values of different data types in a uniform
+ way. Haskell supports \emph{parametric polymorphism}~\cite{polymorphism},
+ meaning functions can be written without mention of any specific type and
+ can be used transparently with any number of new types.
+ As an example of a parametric polymorphic function, consider the type of
+ the following \hs{append} function, which appends an element to a vector:
\begin{code}
append :: [a|n] -> a -> [a|n + 1]
\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 \comment{(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:
-
+ all. This means that \hs{append} can append an element to a vector,
+ regardless of the type of the elements in the list (as long as the type of
+ the value to be added is of the same type as the values in the vector).
+ 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.
+
+ Another type of polymorphism is \emph{ad-hoc
+ polymorphism}~\cite{polymorphism}, which refers to polymorphic
+ functions which can be applied to arguments of different types, but which
+ behave differently depending on the type of the argument to which they are
+ applied. In Haskell, ad-hoc polymorphism is achieved through the use of
+ type classes, where a class definition provides the general interface of a
+ function, and class instances define the functionality for the specific
+ types. An example of such a type class is the \hs{Num} class, which
+ contains all of Haskell's numerical operations. A developer can make use
+ of this ad-hoc polymorphism by adding a constraint to a parametrically
+ polymorphic type variable. Such a constraint indicates that the type
+ variable can only be instantiated to a type whose members supports the
+ overloaded functions associated with the type class.
+
+ As an example we will take a look at type signature of the function
+ \hs{sum}, which sums the values in a vector:
\begin{code}
- (+) :: Num a => a -> a -> a
+ sum :: Num a => [a|n] -> 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}
+ types that are \emph{instances} of the \emph{type class} \hs{Num}, so that
+ we know that the addition (+) operator is defined for that type.
+ \CLaSH's built-in numerical types are also instances of the \hs{Num}
class, so we can use the addition operator on \hs{SizedWords} as
- well as on {SizedInts}.
+ well as on \hs{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).
+ In \CLaSH, parametric 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 (as
+ they are 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}).
+ of the built-in type classes for its built-in function, such as: \hs{Num}
+ for numerical operations, \hs{Eq} for the equality operators, and
+ \hs{Ord} for the comparison/order operators.
- \subsection{Higher order}
+ \subsection{Higher-order functions \& values}
Another powerful abstraction mechanism in functional languages, is
- the concept of \emph{higher order functions}, or \emph{functions as
+ 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:
+ function. The following example should clarify this concept:
\begin{code}
- notList xs = map not xs
+ negVector 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}:
+ The code above defines a function \hs{negVector}, which takes a vector of
+ booleans, and returns a vector where all the values are negated. It
+ achieves this by calling the \hs{map} function, and passing it
+ \emph{another function}, boolean negation, and the vector of booleans,
+ \hs{xs}. The \hs{map} function applies the negation function to all the
+ elements in the vector.
+
+ The \hs{map} function is called a higher-order function, since it takes
+ another function as an argument. Also note that \hs{map} is again a
+ parametric polymorphic function: It does not pose any constraints on the
+ type of the vector elements, other than that it must be the same type as
+ the input type of the function passed to \hs{map}. The element type of the
+ resulting vector is equal to the return type of the function passed, which
+ need not necessarily be the same as the element type of the input vector.
+ All of these characteristics can readily be inferred from the type
+ signature belonging to \hs{map}:
\begin{code}
- map :: (a -> b) -> [a] -> [b]
+ map :: (a -> b) -> [a|n] -> [b|n]
\end{code}
- As an example from a common hardware design, let's look at the
- equation of a FIR filter.
+ As an example of a common hardware design where the use of higher-order
+ functions leads to a very natural description is a FIR filter, which is
+ basically the dot-product of two vectors:
\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$. The equation of the FIR
+ filter is indeed equivalent to the equation of the dot-product, which is
+ shown below:
+
+ \begin{equation}
+ \mathbf{x}\bullet\mathbf{y} = \sum\nolimits_{i = 0}^{n - 1} {x_i \cdot y_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.
+ We can easily and directly implement the equation for the dot-product
+ using higher-order functions:
\begin{code}
- fir ... = foldl1 (+) (zipwith (*) xs hs)
+ xs *+* ys = 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
+ The \hs{zipWith} function is very similar to the \hs{map} function: It
+ takes a function, two vectors, and then applies the function to each of
+ the elements in the two vectors pairwise (\emph{e.g.}, \hs{zipWith (*) [1,
+ 2] [3, 4]} becomes \hs{[1 * 3, 2 * 4]} $\equiv$ \hs{[3,8]}).
+
+ The \hs{foldl1} function takes a function, a single vector, and applies
+ the function to the first two elements of the vector. It then applies the
+ function to the result of the first application and the next element from
+ the vector. This continues until the end of the vector 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
+ 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
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:
+ adds one to its argument. A lambda expression allows one to introduce an
+ anonymous function in any expression. Consider the following expression,
+ which again adds one to every element of a vector:
\begin{code}
map (\x -> x + 1) xs
\end{code}
- Finally, higher order arguments are not limited to just builtin
+ Finally, higher order arguments are not limited to just built-in
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
\item when the function is called, it should not have observable
side-effects.
\end{inparaenum}
- This purity property is important for functional languages, since it
- enables all kinds of mathematical reasoning that could not be guaranteed
- correct for impure functions. Pure functions are as such a perfect match
- for a combinatorial circuit, where the output solely depends on the
- inputs. When a circuit has state however, it can no longer be simply
- described by a pure function. Simply removing the purity property is not a
- valid option, as the language would then lose many of it mathematical
- properties. In an effort to include the concept of state in pure
+ % This purity property is important for functional languages, since it
+ % enables all kinds of mathematical reasoning that could not be guaranteed
+ % correct for impure functions.
+ Pure functions are as such a perfect match or a combinatorial circuit,
+ where the output solely depends on the inputs. When a circuit has state
+ however, it can no longer be simply described by a pure function.
+ % Simply removing the purity property is not a valid option, as the
+ % language would then lose many of it mathematical properties.
+ In an effort to include the concept of state in pure
functions, the current value of the state is made an argument of the
- function; the updated state becomes part of the result. A simple example
- is adding an accumulator register to the earlier multiply-accumulate
- circuit, of which the resulting netlist can be seen in
+ function; the updated state becomes part of the result. In this sense the
+ descriptions made in \CLaSH are the describing the combinatorial parts of
+ a mealy machine.
+
+ A simple example is adding an accumulator register to the earlier
+ multiply-accumulate circuit, of which the resulting netlist can be seen in
\Cref{img:mac-state}:
\begin{code}
- macS a b (State c) = (State c', outp)
+ macS (State c) a b = (State c', outp)
where
outp = mac a b c
c' = outp
\label{img:mac-state}
\end{figure}
- This approach makes the state of a circuit very explicit: which variables
- are part of the state is completely determined by the type signature. This
- approach to state is well suited to be used in combination with the
- existing code and language features, such as all the choice constructs, as
- state values are just normal values.
+ The \hs{State} keyword indicates which arguments are part of the current
+ state, and what part of the output is part of the updated state. This
+ aspect will also reflected in the type signature of the function.
+ Abstracting the state of a circuit in this way makes it very explicit:
+ which variables are part of the state is completely determined by the
+ type signature. This approach to state is well suited to be used in
+ combination with the existing code and language features, such as all the
+ choice constructs, as state values are just normal values.
+
+ Returning to the example of the FIR filter, we will slightly change the
+ equation belong to it, so as to make the translation to code more obvious.
+ What we will do is change the definition of the vector of input samples.
+ So, instead of having the input sample received at time
+ $t$ stored 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 will better suit
+ the the transformation to code):
+
+ \begin{equation}
+ y_t = \sum\nolimits_{i = 0}^{n - 1} {x_i \cdot h_i }
+ \end{equation}
+
+ 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. The function that does this shifting of the input samples
+ is shown below:
+
+ \begin{code}
+ x >> xs = x +> tail xs
+ \end{code}
+
+ Where the \hs{tail} functions returns all but the first element of a
+ vector, and the concatenate operator ($\succ$) adds the new element to the
+ left of a vector. The complete definition of the FIR filter then becomes:
+
+ \begin{code}
+ fir (State (xs,hs)) x = (State (x >> xs,hs), xs *+* hs)
+ \end{code}
+
+ The resulting netlist of a 4-taps FIR filter based on the above definition
+ is depicted in \Cref{img:4tapfir}.
+
+ \begin{figure}
+ \centerline{\includegraphics{4tapfir}}
+ \caption{4-taps FIR Filter}
+ \label{img:4tapfir}
+ \end{figure}
+
\section{\CLaSH\ prototype}
foo\par bar
projects / matthijs / master-project / dsd-paper.git / blobdiff