\newcommand{\fref}[1]{\cref{#1}}
\newcommand{\Fref}[1]{\Cref{#1}}
+\usepackage{epstopdf}
+
+\epstopdfDeclareGraphicsRule{.svg}{pdf}{.pdf}{rsvg-convert --format=pdf < #1 > \noexpand\OutputFile}
%include polycode.fmt
%include clash.fmt
\begin{abstract}
%\boldmath
-The abstract goes here.
+\CLaSH\ is a functional hardware description language that borrows both its
+syntax and semantics from the functional programming language Haskell. Circuit
+descriptions can be translated to synthesizable VHDL using the prototype
+\CLaSH\ compiler. As the circuit descriptions are made in plain Haskell,
+simulations can also be compiled by a Haskell compiler.
+
+The use of polymorphism and higher-order functions allow a circuit designer to
+describe more abstract and general specifications than are possible in the
+traditional hardware description languages.
\end{abstract}
% IEEEtran.cls defaults to using nonbold math in the Abstract.
% This preserves the distinction between vectors and scalars. However,
extensive support for choice-elements is new in the domain of functional
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).
+optimizing Haskell compiler such as the Glasgow Haskell Compiler (\GHC)~\cite{ghc}.
Where descriptions in a conventional hardware description language have an
explicit clock for the purpose state and synchronicity, the clock is implied
\end{code}
\begin{figure}
- \centerline{\includegraphics{mac}}
+ \centerline{\includegraphics{mac.svg}}
\caption{Combinatorial Multiply-Accumulate}
\label{img:mac-comb}
\end{figure}
\end{code}
\begin{figure}
- \centerline{\includegraphics{mac-nocurry}}
+ \centerline{\includegraphics{mac-nocurry.svg}}
\caption{Combinatorial Multiply-Accumulate (complex input)}
\label{img:mac-comb-nocurry}
\end{figure}
% against the constructors in the \hs{case} expressions.
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. Both versions of the example roughly correspond to the same
- netlist, which is depicted in \Cref{img:choice}.
+ constructs, in the code below.
\begin{code}
sumif pred a b = case pred of
\end{code}
\begin{figure}
- \centerline{\includegraphics{choice-case}}
+ \centerline{\includegraphics{choice-case.svg}}
\caption{Choice - sumif}
\label{img:choice}
\end{figure}
+
+ The example sums two values when they are equal or non-equal (depending on
+ the predicate given) and returns 0 otherwise. Both versions of the example
+ roughly correspond to the same netlist, which is depicted in
+ \Cref{img:choice}.
A slightly more complex (but very powerful) form of choice is pattern
matching. A function can be defined in multiple clauses, where each clause
for numerical operations, \hs{Eq} for the equality operators, and
\hs{Ord} for the comparison/order operators.
- \subsection{Higher-order functions}
+ \subsection{Higher-order functions \& values}
Another powerful abstraction mechanism in functional languages, is
the concept of \emph{higher-order functions}, or \emph{functions as
a first class value}. This allows a function to be treated as a
\begin{code}
map :: (a -> b) -> [a|n] -> [b|n]
\end{code}
-
- 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}
-
- We can easily and directly implement the equation for the dot-product
- using higher-order functions:
-
- \begin{code}
- xs *+* ys = foldl1 (+) (zipwith (*) xs hs)
- \end{code}
-
- 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.
So far, only functions have been used as higher-order values. In
Haskell, there are two more ways to obtain a function-typed value:
\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
\end{code}
\begin{figure}
- \centerline{\includegraphics{mac-state}}
+ \centerline{\includegraphics{mac-state.svg}}
\caption{Stateful Multiply-Accumulate}
\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. We can simulate
+ stateful descriptions using the recursive \hs{run} function:
- \comment{
- 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}
- \comment{
- 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.}
+ \begin{code}
+ run f s (i:inps) = o : (run f s' inps)
+ where
+ (s', o) = f s i
+ \end{code}
+
+ The \hs{run} function maps a list of inputs over the function that a
+ developer wants to simulate, passing the state to each new iteration. Each
+ value in the input list corresponds to exactly one cycle of the (implicit)
+ clock. The result of the simulation is a list of outputs for every clock
+ cycle. As both the \hs{run} function and the hardware description are
+ plain hardware, the complete simulation can be compiled by an optimizing
+ Haskell compiler.
\section{\CLaSH\ prototype}
foo\par bar
+\section{Use cases}
+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 a 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}
+
+We can easily and directly implement the equation for the dot-product
+using higher-order functions:
+
+\begin{code}
+xs *+* ys = foldl1 (+) (zipWith (*) xs hs)
+\end{code}
+
+The \hs{zipWith} function is very similar to the \hs{map} function seen
+earlier: 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.
+
+Returning to the actual 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 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 shifts the input samples is shown below:
+
+\begin{code}
+x >> xs = x +> tail xs
+\end{code}
+
+Where the \hs{tail} function returns all but the first element of a
+vector, and the concatenate operator ($\succ$) adds a 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.svg}}
+\caption{4-taps FIR Filter}
+\label{img:4tapfir}
+\end{figure}
+
\section{Related work}
Many functional hardware description languages have been developed over the
years. Early work includes such languages as $\mu$\acro{FP}~\cite{muFP}, an
extension of Backus' \acro{FP} language to synchronous streams, designed
particularly for describing and reasoning about regular circuits. The
Ruby~\cite{Ruby} language uses relations, instead of functions, to describe
-circuits, and has a particular focus on layout. \acro{HML}~\cite{HML2} is a
-hardware modeling language based on the strict functional language
-\acro{ML}, and has support for polymorphic types and higher-order functions.
-Published work suggests that there is no direct simulation support for
-\acro{HML}, and that the translation to \VHDL\ is only partial.
+circuits, and has a particular focus on layout.
+
+\acro{HML}~\cite{HML2} is a hardware modeling language based on the strict
+functional language \acro{ML}, and has support for polymorphic types and
+higher-order functions. Published work suggests that there is no direct
+simulation support for \acro{HML}, but that a description in \acro{HML} has to
+be translated to \VHDL\ and that the translated description can than be
+simulated in a \VHDL\ simulator. Also not all of the mentioned language
+features of \acro{HML} could be translated to hardware. The \CLaSH\ compiler
+on the other hand can correctly translate all of the language constructs
+mentioned in this paper to a netlist format.
Like this work, many functional hardware description languages have some sort
of foundation in the functional programming language Haskell.
Hawk~\cite{Hawk1} uses Haskell to describe system-level executable
specifications used to model the behavior of superscalar microprocessors. Hawk
specifications can be simulated, but there seems to be no support for
-automated circuit synthesis. The ForSyDe~\cite{ForSyDe2} system uses Haskell
-to specify abstract system models, which can (manually) be transformed into an
-implementation model using semantic preserving transformations. ForSyDe has
-several simulation and synthesis backends, though synthesis is restricted to
-the synchronous subset of the ForSyDe language.
+automated circuit synthesis.
+
+The ForSyDe~\cite{ForSyDe2} system uses Haskell to specify abstract system
+models, which can (manually) be transformed into an implementation model using
+semantic preserving transformations. A designer can model systems using
+heterogeneous models of computation, which include continuous time,
+synchronous and untimed models of computation. Using so-called domain
+interfaces a designer can simulate electronic systems which have both analog
+as digital parts. ForSyDe has several simulation and synthesis backends,
+though synthesis is restricted to the synchronous subset of the ForSyDe
+language. Unlike \CLaSH\ there is no support for the automated synthesis of description that contain polymorphism or higher-order functions.
Lava~\cite{Lava} is a hardware description language that focuses on the
structural representation of hardware. Besides support for simulation and
generators when viewed from a synthesis viewpoint, in that the language
elements of Haskell, such as choice, can be used to guide the circuit
generation. If a developer wants to insert a choice element inside an actual
-circuit he will have to specify this explicitly as a component. In this
-respect \CLaSH\ differs from Lava, in that all the choice elements, such as
-case-statements and pattern matching, are synthesized to choice elements in the
-eventual circuit. As such, richer control structures can both be specified and
-synthesized in \CLaSH\ compared to any of the languages mentioned in this
-section.
+circuit he will have to specify this explicitly as a component.
+
+In this respect \CLaSH\ differs from Lava, in that all the choice elements,
+such as case-statements and pattern matching, are synthesized to choice
+elements in the eventual circuit. As such, richer control structures can both
+be specified and synthesized in \CLaSH\ compared to any of the languages
+mentioned in this section.
The merits of polymorphic typing, combined with higher-order functions, are
now also recognized in the `main-stream' hardware description languages,