- \item[\textbf{Product types}]
- A product type is an algebraic datatype with a single constructor with
- two or more fields, denoted in practice like (a,b), (a,b,c), etc. This
- is essentially a way to pack a few values together in a record-like
- structure. In fact, the built-in tuple types are just algebraic product
- types (and are thus supported in exactly the same way).
-
- The \quote{product} in its name refers to the collection of values
- belonging to this type. The collection for a product type is the
- Cartesian product of the collections for the types of its fields.
-
- These types are translated to \VHDL\ record types, with one field for
- every field in the constructor. This translation applies to all single
- constructor algebraic data-types, including those with just one
- field (which are technically not a product, but generate a VHDL
- record for implementation simplicity).
- \item[\textbf{Enumerated types}]
- An enumerated type is an algebraic datatype with multiple constructors, but
- none of them have fields. This is 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.
-
- 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 value.
- \item[\textbf{Sum types}]
- A sum type is an algebraic datatype with multiple constructors, where
- the constructors have one or more fields. Technically, a type with
- more than one field per constructor is a sum of products type, but
- for our purposes this distinction does not really make a
- difference, so this distinction is note made.
-
- The \quote{sum} in its name refers again to the collection of values
- belonging to this type. The collection for a sum type is the
- union of the the collections for each of the constructors.
-
- Sum types are currently not supported by the prototype, since there is
- no obvious \VHDL\ alternative. They can easily be emulated, however, as
- we will see from an example:
-
-\begin{verbatim}
-data Sum = A Bit Word | B Word
-\end{verbatim}
-
- An obvious way to translate this would be to create an enumeration to
- distinguish the constructors and then create a big record that
- contains all the fields of all the constructors. This is the same
- translation that would result from the following enumeration and
- product type (using a tuple for clarity):
-
-\begin{verbatim}
-data SumC = A | B
-type Sum = (SumC, Bit, Word, Word)
-\end{verbatim}
-
- Here, the \hs{SumC} type effectively signals which of the latter three
- fields of the \hs{Sum} type are valid (the first two if \hs{A}, the
- last one if \hs{B}), all the other ones have no useful value.
-
- An obvious problem with this naive approach is the space usage: the
- example above generates a fairly big \VHDL\ type. Since we can be
- sure that the two \hs{Word}s in the \hs{Sum} type will never be valid
- at the same time, this is a waste of space.
-
- Obviously, duplication detection could be used to reuse a
- particular field for another constructor, but this would only
- partially solve the problem. If two fields would be, for
- example, an array of 8 bits and an 8 bit unsigned word, these are
- different types and could not be shared. However, in the final
- hardware, both of these types would simply be 8 bit connections,
- so we have a 100\% size increase by not sharing these.
- \end{xlist}
+ \item[\bf{Single constructor}]
+ Algebraic datatypes with a single constructor with one or more
+ fields allow values to be packed together in a record-like structure.
+ Haskell's built-in tuple types are also defined as single constructor
+ algebraic types (using a bit of syntactic sugar). An example of a
+ single constructor type with multiple fields is the following pair of
+ integers:
+ \begin{code}
+ data IntPair = IntPair Int Int
+ \end{code}
+ % These types are translated to \VHDL\ record types, with one field
+ % for every field in the constructor.
+ \item[\bf{No fields}]
+ Algebraic datatypes with multiple constructors, but without any
+ fields are essentially enumeration types. Note that Haskell's
+ \hs{Bool} type is also defined as an enumeration type, but that there
+ is a fixed translation for that type within the \CLaSH\ compiler. An
+ example of an enumeration type definition is the definition for 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
+ % value.
+ \item[\bf{Multiple constructors with fields}]
+ Algebraic datatypes with multiple constructors, where at least
+ one of these constructors has one or more fields are currently not
+ supported. Additional research is required to allow for the overlap of
+ the fields belonging to the different constructors.
+ \end{xlist}
+
+ \subsection{Polymorphism}\label{sec:polymorhpism}
+ A powerful feature of most (functional) programming 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{first} function, which returns the first element of a
+ tuple:\footnote{The \hs{::} operator is used to annotate a function
+ with its type.}
+
+ \begin{code}
+ first :: (a,b) -> a
+ \end{code}
+
+ This type is parameterized in both \hs{a} and \hs{b}, which can both
+ represent any type at all (as long as that type is supported by the
+ \CLaSH\ compiler). This means that \hs{first} works for any tuple,
+ regardless of what elements it contains. This kind of polymorphism is
+ extremely useful in hardware designs, for example when routing signals
+ without knowing their exact type, or specifying vector operations that
+ work on vectors of any length and element type. Polymorphism also plays an
+ important role in most higher order functions, as will be shown 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
+ \emph{type classes}, where a class definition provides the general
+ interface of a function, and class \emph{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 designer can make use of this ad-hoc polymorphism by adding a
+ \emph{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.
+
+ An example of a type signature that includes such a constraint if the
+ signature of the \hs{sum} function, which sums the values in a vector:
+ \begin{code}
+ 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}, so that
+ the compiler knows that the addition (+) operator is defined for that
+ type.
+
+ A place where class constraints also play a role is in the size and range
+ parameters of the \hs{Vector} and numeric types. The reason being that
+ these parameters have to be limited to types that can represent
+ \emph{natural} numbers. This constraint will also be reflected in any of
+ the functions that work these types. The complete type of for example the
+ \hs{Vector} type is:
+ \begin{code}
+ Natural n => Vector n a
+ \end{code}
+
+ % \CLaSH's built-in numerical types are also instances of the \hs{Num}
+ % class.
+ % so we can use the addition operator (and thus the \hs{sum}
+ % function) with \hs{Signed} as well as with \hs{Unsigned}.
+
+ \CLaSH\ supports both parametric polymorphism and ad-hoc polymorphism. Any
+ function defined can have any number of unconstrained type parameters. A
+ developer can also specify his own type classes and corresponding
+ instances. The \CLaSH\ compiler will infer the type of every polymorphic
+ argument depending on how the function is applied. There is however one
+ constraint: the top level function that is being translated can not have
+ any polymorphic arguments. The arguments of the top-level can not be
+ polymorphic as the function is never applied and consequently there is no
+ way to determine the actual types for the type parameters.
+
+ With regard to the built-in types, it should be noted that members of
+ some of the standard Haskell type classes are supported as built-in
+ functions. These include: the numerial operators of \hs{Num}, the equality
+ operators of \hs{Eq}, and the comparison/order operators of \hs{Ord}.
+
+ \subsection{Higher-order functions \& values}
+ Another powerful abstraction mechanism in functional languages, is
+ the concept of \emph{functions as a first class value}, also called
+ \emph{higher-order functions}. This allows a function to be treated as a
+ value and be passed around, even as the argument of another
+ function. The following example should clarify this concept:
+
+ \hspace{-1.7em}
+ \begin{minipage}{0.93\linewidth}
+ %format not = "\mathit{not}"
+ \begin{code}
+ negateVector xs = map not xs
+ \end{code}
+ \end{minipage}
+ \begin{minipage}{0.07\linewidth}
+ \begin{example}
+ \label{lst:code6}
+ \end{example}
+ \end{minipage}
+
+ The code above defines the \hs{negateVector} function, which takes a
+ vector of booleans, \hs{xs}, 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 input vector, other than that its elements must have the same
+ type as the first argument 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 be inferred from the type
+ signature belonging to \hs{map}:
+
+ \begin{code}
+ map :: Natural n => (a -> b) -> [a|n] -> [b|n]
+ \end{code}
+
+ 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:
+
+ \hspace{-1.7em}
+ \begin{minipage}{0.93\linewidth}
+ \begin{code}
+ map (add 1) xs
+ \end{code}
+ \end{minipage}
+ \begin{minipage}{0.07\linewidth}
+ \begin{example}
+ \label{lst:code7}
+ \end{example}
+ \end{minipage}
+
+ Here, the expression \hs{(add 1)} is the partial application of the
+ addition function to the value \hs{1}, which is again a function that
+ adds one to its (next) 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:
+
+ \hspace{-1.7em}
+ \begin{minipage}{0.93\linewidth}
+ \begin{code}
+ map (\x -> x + 1) xs
+ \end{code}
+ \end{minipage}
+ \begin{minipage}{0.07\linewidth}
+ \begin{example}
+ \label{lst:code8}
+ \end{example}
+ \end{minipage}
+
+ Finally, not only built-in functions can have higher order arguments (such
+ as the \hs{map} function), but any function defined in \CLaSH\ may have
+ functions as arguments. This allows the circuit designer to use a
+ powerful amount of code reuse. The only exception is again the top-level
+ function: if a function-typed argument is not applied with an actual
+ function, no hardware can be generated.
+
+ % \comment{TODO: Describe ALU example (no code)}