expression, that adds one to every element of a vector:
\begin{code}
- map ((+) 1) xs
+ map (+ 1) xs
\end{code}
- Here, the expression \hs{(+) 1} is the partial application of the
+ Here, the expression \hs{(+ 1)} is the partial application of the
plus operator to the value \hs{1}, which is again a function that
adds one to its argument. A lambda expression allows one to introduce an
anonymous function in any expression. Consider the following expression,
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}. Each value in the input list corresponds to exactly one
- cycle of the (implicit) clock.
+ inputs, \hs{inps}. It is assumed that there is one input per clock cycle.
+ Also note how the order of the input, output, and state in the \hs{run}
+ function corresponds with the order of the input, output and state of the
+ \hs{macS} function described earlier.
As both the \hs{run} function, the hardware description, and the test
inputs are plain Haskell, the complete simulation can be compiled to an
simulation, where the executable binary has an additional simulation speed
bonus in case there is a large set of test inputs.
-\section{\CLaSH\ prototype}
+\section{\CLaSH\ compiler}
+An important aspect in this research is the creation of the prototype compiler, which allows us to translate 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 \CLaSH\ language as presented above can be translated to \VHDL\ using
-the prototype \CLaSH\ compiler. This compiler allows experimentation with
-the \CLaSH\ language and allows for running \CLaSH\ designs on actual FPGA
-hardware.
+The Glasgow Haskell Compiler (\GHC) is an open-source Haskell compiler that
+also provides a high level API to most of its internals. The availability of
+this high-level API obviated the need to design many of the tedious parts of
+the prototype compiler, such as the parser, semantic checker, and especially
+the type-checker. The parser, semantic checker, and type-checker together form
+the front-end of the prototype compiler pipeline, as depicted in
+\Cref{img:compilerpipeline}.
\begin{figure}
\centerline{\includegraphics{compilerpipeline.svg}}
\label{img:compilerpipeline}
\end{figure}
-The prototype heavily uses \GHC, the Glasgow Haskell Compiler.
-\Cref{img:compilerpipeline} shows the \CLaSH\ compiler pipeline. As you can
-see, the front-end is completely reused from \GHC, which allows the \CLaSH\
-prototype to support most of the Haskell Language. The \GHC\ front-end
-produces the program in the \emph{Core} format, which is a very small,
-functional, typed language which is relatively easy to process.
-
-The second step in the compilation process is \emph{normalization}. This
-step runs a number of \emph{meaning preserving} transformations on the
-Core program, to bring it into a \emph{normal form}. This normal form
-has a number of restrictions that make the program similar to hardware.
-In particular, a program in normal form no longer has any polymorphism
-or higher order functions.
-
-The final step is a simple translation to \VHDL.
+The output of the \GHC\ front-end is the original Haskell description
+translated to \emph{Core}~\cite{Sulzmann2007}, which is smaller, functional,
+typed language that is relatively easier to process than the larger Haskell
+language. A description in \emph{Core} can still contain properties 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 only contains properties that have a direct
+translation. 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 for lambda calculus, such a $\beta$-reduction and
+$\eta$-expansion, but also includes \emph{defunctionalization} transformations
+which reduce higher-order functions to `regular' first-order functions.
+
+The final step in the compiler pipeline is the translation to a \VHDL\
+\emph{netlist}, which is a straightforward process due to resemblance of a
+normalized description and a set of concurrent signal assignments. We call the
+end-product of the \CLaSH\ compiler a \VHDL\ \emph{netlist} as the resulting
+\VHDL\ resembles an actual netlist description and not idiomatic \VHDL.
\section{Use cases}
\label{sec:usecases}
\label{img:4tapfir}
\end{figure}
+
+\subsection{Higher order CPU}
+
+
+\begin{code}
+type FuState = State Word
+fu :: (a -> a -> a)
+ -> [a]:n
+ -> (RangedWord n, RangedWord n)
+ -> FuState
+ -> (FuState, a)
+fu op inputs (addr1, addr2) (State out) =
+ (State out', out)
+ where
+ in1 = inputs!addr1
+ in2 = inputs!addr2
+ out' = op in1 in2
+\end{code}
+
+\begin{code}
+type CpuState = State [FuState]:4
+cpu :: Word
+ -> [(RangedWord 7, RangedWord 7)]:4
+ -> CpuState
+ -> (CpuState, Word)
+cpu input addrs (State fuss) =
+ (State fuss', out)
+ where
+ fures = [ fu const inputs!0 fuss!0
+ , fu (+) inputs!1 fuss!1
+ , fu (-) inputs!2 fuss!2
+ , fu (*) inputs!3 fuss!3
+ ]
+ (fuss', outputs) = unzip fures
+ inputs = 0 +> 1 +> input +> outputs
+ out = head outputs
+\end{code}
+
\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
projects / matthijs / master-project / dsd-paper.git / blobdiff