+ An important property in Haskell, and in many other functional languages,
+ is \emph{purity}. A function is said to be \emph{pure} if it satisfies two
+ conditions:
+ \begin{inparaenum}
+ \item given the same arguments twice, it should return the same value in
+ both cases, and
+ \item that the function has no 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 a perfect match for combinational circuits, where the
+ output solely depends on the inputs. When a circuit has state however, it
+ can no longer be 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.
+ \CLaSH\ deals with the concept of state by making the current state an
+ additional argument of the function, and the updated state part of the
+ result. In this sense the descriptions made in \CLaSH\ are the
+ combinational 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}:
+
+ \hspace{-1.7em}
+ \begin{minipage}{0.93\linewidth}
+ \begin{code}
+ macS (State c) (a, b) = (State c', c')
+ where
+ c' = mac a b c
+ \end{code}
+ \end{minipage}
+ \begin{minipage}{0.07\linewidth}
+ \begin{example}
+ \label{code:macstate}
+ \end{example}
+ \end{minipage}
+
+ Note that the \hs{macS} function returns both the new state and the value
+ of the output port. The \hs{State} wrapper 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 be 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 elements, as state values are just normal values from Haskell's
+ point of view. Stateful descriptions are simulated using the recursive
+ \hs{run} function:
+
+ \hspace{-1.7em}
+ \begin{minipage}{0.93\linewidth}
+ \begin{code}
+ run f s (i : inps) = o : (run f s' inps)
+ where
+ (s', o) = f s i
+ \end{code}
+ \end{minipage}
+ \begin{minipage}{0.07\linewidth}
+ \begin{example}
+ \label{code:run}
+ \end{example}
+ \end{minipage}
+
+ The \hs{(:)} operator is the list concatenation operator, where the
+ left-hand side is the head of a list and the right-hand side is the
+ remainder of the list. The \hs{run} function applies the function the
+ developer wants to simulate, \hs{f}, to the current state, \hs{s}, and the
+ first input value, \hs{i}. The result is the first output value, \hs{o},
+ and the updated state \hs{s'}. The next iteration of the \hs{run} function
+ is then called with the updated state, \hs{s'}, and the rest of the
+ inputs, \hs{inps}. In the context of this paper, it is assumed that there
+ is one input per clock cycle. Note that the order of \hs{s',o,s,i} in the
+ where clause of the \hs{run} functions corresponds with the order of the
+ input, output and state of the \hs{macS} function (\ref{code:macstate}).
+ Thus, in Haskell the expression \hs{run macS 0 inputs} simulates \hs{macS}
+ on \hs{inputs} starting with the value \hs{0}
+
+ \begin{figure}
+ \centerline{\includegraphics{mac-state.svg}}
+ \caption{Stateful Multiply-Accumulate}
+ \label{img:mac-state}
+ \vspace{-1.5em}
+ \end{figure}
+
+ The complete simulation can be compiled to an executable binary by a
+ Haskell compiler, or executed in an Haskell interpreter. Both
+ simulation paths require less effort from a circuit designer than first
+ translating the description to \VHDL\ and then running a \VHDL\
+ simulation; it is also very likely that both simulation paths are much
+ faster.
+
+\section{The \CLaSH\ compiler}
+\label{sec:compiler}
+The prototype \CLaSH\ compiler translates descriptions made in the \CLaSH\
+language as described in the previous section to synthesizable \VHDL.
+% , allowing a designer to actually run a \CLaSH\ design on an \acro{FPGA}.
+
+The Glasgow Haskell Compiler (\GHC)~\cite{ghc} is an open source Haskell
+compiler that also provides a high level \acro{API} to most of its internals.
+Furthermore, it provides several parts of the prototype compiler for free,
+such as the parser, the semantics checker, and the type checker. These parts
+together form the front-end of the prototype compiler pipeline, as seen in
+\Cref{img:compilerpipeline}.
+
+\begin{figure}
+\vspace{1em}
+\centerline{\includegraphics{compilerpipeline.svg}}
+\caption{\CLaSHtiny\ compiler pipeline}
+\label{img:compilerpipeline}
+\vspace{-1.5em}
+\end{figure}
+
+The output of the \GHC\ front-end consists of the translation of the original
+Haskell description to \emph{Core}~\cite{Sulzmann2007}, which is a small
+typed functional language. This \emph{Core} language is relatively easy to
+process compared to the larger Haskell language. A description in \emph{Core}
+can still contain elements which have no direct translation to hardware, such
+as polymorphic types and function-valued arguments. Such a description needs
+to be transformed to a \emph{normal form}, which corresponds directly to
+hardware. The second stage of the compiler, the \emph{normalization} phase,
+exhaustively applies a set of \emph{meaning-preserving} transformations on the
+\emph{Core} description until this description is in a \emph{normal form}.
+This set of transformations includes transformations typically found in
+reduction systems and lambda calculus~\cite{lambdacalculus}, such as
+$\beta$-reduction and $\eta$-expansion. It also includes transformations that
+are responsible for the specialization of higher-order functions to `regular'
+first-order functions, and specializing polymorphic types to concrete types.
+
+The final step in the compiler pipeline is the translation to a \VHDL\
+\emph{netlist}, which is a straightforward process due to the resemblance of a
+normalized description and a set of concurrent signal assignments. The
+end-product of the \CLaSH\ compiler is called a \VHDL\ \emph{netlist} as the
+result resembles an actual netlist description, and the fact that it is \VHDL\
+is only an implementation detail; e.g., the output could have been Verilog or
+even \acro{EDIF}.
+
+\section{Use cases}
+\label{sec:usecases}
+\subsection{FIR Filter}
+As an example of a common hardware design where the relation between
+functional languages and mathematical functions, combined with the use of
+higher-order functions leads to a very natural description is a \acro{FIR}
+filter:
+
+\begin{equation}
+y_t = \sum\nolimits_{i = 0}^{n - 1} {x_{t - i} \cdot h_i }
+\end{equation}
+
+A \acro{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 a \acro{FIR}
+filter is equivalent to the equation of the dot-product of two vectors, which
+is shown below:
+
+\begin{equation}
+\mathbf{a}\bullet\mathbf{b} = \sum\nolimits_{i = 0}^{n - 1} {a_i \cdot b_i }
+\end{equation}
+
+The equation for the dot-product is easily and directly implemented using
+higher-order functions:
+
+\hspace{-1.7em}
+\begin{minipage}{0.93\linewidth}