\newenvironment{xlist}[1][\rule{0em}{0em}]{%
\begin{list}{}{%
\settowidth{\labelwidth}{#1:}
- \setlength{\labelsep}{0.5cm}
+ \setlength{\labelsep}{0.5em}
\setlength{\leftmargin}{\labelwidth}
\addtolength{\leftmargin}{\labelsep}
+ \addtolength{\leftmargin}{\parindent}
\setlength{\rightmargin}{0pt}
\setlength{\listparindent}{\parindent}
\setlength{\itemsep}{0 ex plus 0.2ex}
descriptions started in the early 1980s \cite{Cardelli1981, muFP,DAISY,FHDL},
a time which also saw the birth of the currently popular hardware description
languages such as \VHDL. The merit of using a functional language to describe
-hardware comes from the fact that basic combinatorial circuits are equivalent
-to mathematical functions and that functional languages are very good at
-describing and composing mathematical functions.
+hardware comes from the fact that combinatorial circuits can be directly
+modeled as mathematical functions and that functional languages are very good
+at describing and composing mathematical functions.
In an attempt to decrease the amount of work involved with creating all the
required tooling, such as parsers and type-checkers, many functional hardware
available in the functional hardware description languages that are embedded
in Haskell as a domain specific languages. As far as the authors know, such
extensive support for choice-elements is new in the domain of functional
-hardware description language. As the hardware descriptions are plain Haskell
-functions, these descriptions can be compiled for simulation using using the
-optimizing Haskell compiler \GHC.
+hardware description languages. As the hardware descriptions are plain Haskell
+functions, these descriptions can be compiled for simulation using an
+optimizing Haskell compiler such as the Glasgow Haskell Compiler (\GHC).
Where descriptions in a conventional hardware description language have an
explicit clock for the purpose state and synchronicity, the clock is implied
-in this research. The functions describe the behavior of the hardware between
+in this research. A developer describes the behavior of the hardware between
clock cycles, as such, only synchronous systems can be described. Many
-functional hardware description models signals as a stream of all values over
+functional hardware description model signals as a stream of all values over
time; state is then modeled as a delay on this stream of values. The approach
taken in this research is to make the current state of a circuit part of the
input of the function and the updated state part of the output.
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 an optimizing \VHDL\ synthesis tool.
+by any (optimizing) \VHDL\ synthesis tool.
\section{Hardware description in Haskell}
netlist format:
\begin{inparaenum}
\item every function is translated to a component,
- \item every function argument is translated to an input port, and
- \item the result value of a function is translated to an output port.
+ \item every function argument is translated to an input port,
+ \item the result value of a function is translated to an output port,
+ and
+ \item function applications are translated to component instantiations.
\end{inparaenum}
- 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.
+ The output port can have a complex type (such as a tuple), so having just
+ a single output port does not pose any limitation. The arguments of a
+ function applications are assigned to a signal, which are then mapped to
+ the corresponding input ports of the component. 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 netlist,% aswell,
consisting of: \hs{case} constructs, \hs{if-then-else} constructs,
pattern matching, and guards. The easiest of these are the \hs{case}
constructs (\hs{if} expressions can be very directly translated to
- \hs{case} expressions).
+ \hs{case} expressions). A \hs{case} construct is translated to a
+ multiplexer, where the control value is linked to the selection port and
+ the output of each case is linked to the corresponding input port on the
+ multiplexer.
% 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
+ We can see two versions of a contrived example below, 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.
+ otherwise. Both versions of the example roughly correspond to the same
+ netlist, which is depicted in \Cref{img:choice}.
\begin{code}
sumif pred a b = case pred of
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}
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:
+ where the expression is only executed if the guard evaluates to true. Like
+ \hs{if-then-else} constructs, pattern matching and guards have a
+ (straightforward) translation to \hs{case} constructs and can as such be
+ mapped to multiplexers. A third version of the earlier example, using both
+ pattern matching and guards, can be seen below. The version using pattern
+ matching and guards also has roughly the same netlist representation
+ (\Cref{img:choice}) as the earlier two versions of the example.
\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.
% \begin{figure}
% \centerline{\includegraphics{choice-ifthenelse}}
% \end{figure}
\subsection{Types}
- Haskell is a strongly-typed language, meaning that the type of a variable
- or function is determined at compile-time. Not all of Haskell's typing
- constructs have a clear translation to hardware, as such this section will
- only deal with the types that do have a clear correspondence to hardware.
- The translatable types are divided into two categories: \emph{built-in}
- types and \emph{user-defined} types. Built-in types are those types for
- which a direct translation is defined within the \CLaSH\ compiler; the
- term user-defined types should not require any further elaboration.
+ Haskell is a statically-typed language, meaning that the type of a
+ variable or function is determined at compile-time. Not all of Haskell's
+ typing constructs have a clear translation to hardware, as such this
+ section will only deal with the types that do have a clear correspondence
+ to hardware. The translatable types are divided into two categories:
+ \emph{built-in} types and \emph{user-defined} types. Built-in types are
+ those types for which a direct translation is defined within the \CLaSH\
+ compiler; the term user-defined types should not require any further
+ elaboration. The translatable types are also inferable by the compiler,
+ meaning that a developer does not have to annotate every function with a
+ type signature.
% Translation of two most basic functional concepts has been
% discussed: function application and choice. Before looking further
% using translation rules that are discussed later on.
\subsubsection{Built-in types}
+ The following types have direct translation defined within the \CLaSH\
+ compiler:
\begin{xlist}
\item[\bf{Bit}]
This is the most basic type available. It can have two values:
This is a vector type that can contain elements of any other type and
has a fixed length. The \hs{Vector} type constructor takes two type
arguments: the length of the vector and the type of the elements
- contained in it.
+ contained in it. The short-hand notation used for the vector type in
+ the rest of paper is: \hs{[a|n]}. Where the \hs{a} is the element
+ type, and \hs{n} is the length of the vector.
% The state type of an 8 element register bank would then for example
% be:
% (The 32 bit word type as defined above). In other words, the
% \hs{RegisterState} type is a vector of 8 32-bit words. A fixed size
% vector is translated to a \VHDL\ array type.
- \item[\bf{RangedWord}]
+ \item[\bf{Index}]
This is another type to describe integers, but unlike the previous
two it has no specific bit-width, but an upper bound. This means that
its range is not limited to powers of two, but can be any number.
- A \hs{RangedWord} only has an upper bound, its lower bound is
- implicitly zero. The main purpose of the \hs{RangedWord} type is to be
+ An \hs{Index} only has an upper bound, its lower bound is
+ implicitly zero. The main purpose of the \hs{Index} type is to be
used as an index to a \hs{Vector}.
% \comment{TODO: Perhaps remove this example?} To define an index for
\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] -> a -> [a]
+ 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 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 operation. 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 asL \hs{Num}
+ for numerical operations, \hs{Eq} for the equality operators, and
+ \hs{Ord} for the comparison/order operators.
\subsection{Higher order}
Another powerful abstraction mechanism in functional languages, is
projects / matthijs / master-project / dsd-paper.git / blobdiff