\newenvironment{xlist}[1][\rule{0em}{0em}]{%
\begin{list}{}{%
\settowidth{\labelwidth}{#1:}
- \setlength{\labelsep}{\parindent}
+ \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}
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). % Choice elements are translated to multiplexers
+ \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. The distinction between a
+ renaming and a synonym does no longer matter in hardware and can be
+ disregarded in the translation process. For algebraic types, we can make
+ the following distinction:
\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
\comment{TODO: Use vectors instead of lists?}
\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
projects / matthijs / master-project / dsd-paper.git / blobdiff