From: Christiaan Baaij Date: Tue, 2 Mar 2010 15:50:46 +0000 (+0100) Subject: Merge branch 'master' of http://git.stderr.nl/matthijs/master-project/paper X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Fdsd-paper.git;a=commitdiff_plain;h=82fbaedde6f9c1789576d0f715fc3a0686b2d20f;ds=sidebyside Merge branch 'master' of git.stderr.nl/matthijs/master-project/paper Conflicts: cλash.lhs --- 82fbaedde6f9c1789576d0f715fc3a0686b2d20f diff --cc "c\316\273ash.lhs" index 7eaf97f,9c0fb6b..99d2b9a --- "a/c\316\273ash.lhs" +++ "b/c\316\273ash.lhs" @@@ -950,12 -960,12 +960,12 @@@ circuit~\cite{reductioncircuit} for flo 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 + 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: @@@ -1071,31 -1075,23 +1081,31 @@@ the front-end of the prototype compile \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, functional, - typed language that is relatively easier to process than the larger Haskell ++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 @@@ -1125,48 -1121,48 +1135,48 @@@ as *+* bs = foldl1 (+) (zipWith (*) as 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 basically pairwise multiplication and - that the \hs{foldl1 (+)} function is just summation. ++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 left of a vector. 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}}