X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Fdsd-paper.git;a=blobdiff_plain;f=c%CE%BBash.lhs;h=99d2b9a68f8e815ab703b616c22a26e31f345731;hp=9c0fb6b82f057fb8e305fefecd0f96accc6808b5;hb=82fbaedde6f9c1789576d0f715fc3a0686b2d20f;hpb=64a90253f6e0a97204415d78612bc828e83a313f diff --git "a/c\316\273ash.lhs" "b/c\316\273ash.lhs" index 9c0fb6b..99d2b9a 100644 --- "a/c\316\273ash.lhs" +++ "b/c\316\273ash.lhs" @@ -960,10 +960,10 @@ circuit~\cite{reductioncircuit} for floating point numbers. 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 (next) argument. A lambda expression allows one to introduce an anonymous function in any expression. Consider the following expression, @@ -1051,8 +1051,10 @@ circuit~\cite{reductioncircuit} for floating point numbers. 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 @@ -1062,12 +1064,16 @@ circuit~\cite{reductioncircuit} for floating point numbers. 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}} @@ -1075,23 +1081,31 @@ hardware. \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, -typed, functional 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, typed, +functional 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~\cite{lambdacalculus}, such a +$\beta$-reduction and $\eta$-expansion, but also includes self-defined +transformations that are responsible for the reduction of 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} + +\subsection{FIR Filter} \label{sec:usecases} 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 @@ -1121,48 +1135,48 @@ as *+* bs = foldl1 (+) (zipWith (*) as bs) 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]}). +[1, 2] [3, 4]} becomes \hs{[1 * 3, 2 * 4]}). -The \hs{foldl1} function takes a function, a single vector, and applies +The \hs{foldl1} function takes a binary 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 pairwise -multiplication and the \hs{foldl1 (+)} function is 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): +function to the result of the first application and the next element in 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. It is obvious +that the \hs{zipWith (*)} function is pairwise multiplication and that the +\hs{foldl1 (+)} function is summation. + +Returning to the actual FIR filter, we will slightly change the equation +describing it, so as to make the translation to code more obvious and concise. +What we do is change the definition of the vector of input samples and delay +the computation by one sample. Instead of having the input sample received at +time $t$ stored in $x_t$, $x_0$ now always stores the newest 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: +The complete definition of the FIR filter in code then becomes: \begin{code} -x >> xs = x +> tail xs +fir (State (xs,hs)) x = (State (x >> xs,hs), xs *+* hs) \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 -front of a vector. The complete definition of the FIR filter then becomes: +Where the vector \hs{hs} contains the FIR coefficients and the vector \hs{xs} +contains the latest input sample in front and older samples behind. The code +for the shift (\hs{>>}) operator that adds the new input sample (\hs{x}) to +the list of previous input samples (\hs{xs}) and removes the oldest sample is +shown below: \begin{code} -fir (State (xs,hs)) x = (State (x >> xs,hs), xs *+* hs) +x >> xs = x +> init xs \end{code} -The resulting netlist of a 4-taps FIR filter based on the above definition -is depicted in \Cref{img:4tapfir}. +The \hs{init} function returns all but the last element of a vector, and the +concatenate operator ($\succ$) adds a new element to the front of a vector. The +resulting netlist of a 4-taps FIR filter, created by specializing the vectors of the above definition to a length of 4, is depicted in \Cref{img:4tapfir}. \begin{figure} \centerline{\includegraphics{4tapfir.svg}} @@ -1170,10 +1184,8 @@ is depicted in \Cref{img:4tapfir}. \label{img:4tapfir} \end{figure} - \subsection{Higher order CPU} - \begin{code} type FuState = State Word fu :: (a -> a -> a)