From: Christiaan Baaij Date: Mon, 22 Feb 2010 13:16:54 +0000 (+0100) Subject: Update section on choice elements X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Fdsd-paper.git;a=commitdiff_plain;h=4d57af0ef2a2221567f3c2812acf227e05094add Update section on choice elements --- diff --git a/choice-case.svg b/choice-case.svg index 7d6c9d6..1eea0a7 100644 --- a/choice-case.svg +++ b/choice-case.svg @@ -11,7 +11,7 @@ xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" width="172.75" - height="124.93002" + height="124.43002" id="svg2" version="1.1" inkscape:version="0.47 r22583" @@ -24,8 +24,8 @@ inkscape:pageopacity="0.0" inkscape:pageshadow="2" inkscape:zoom="2.1106557" - inkscape:cx="100.30358" - inkscape:cy="11.570164" + inkscape:cx="228.11635" + inkscape:cy="26.631212" inkscape:document-units="px" inkscape:current-layer="layer1" showgrid="true" @@ -102,7 +102,7 @@ image/svg+xml - + @@ -110,7 +110,7 @@ inkscape:label="Layer 1" inkscape:groupmode="layer" id="layer1" - transform="translate(-367.86,-538.2295)"> + transform="translate(-367.86,-538.7295)"> + transform="translate(-368.36,-547.9495)"> diff --git "a/c\316\273ash.lhs" "b/c\316\273ash.lhs" index 67cd589..c56eebc 100644 --- "a/c\316\273ash.lhs" +++ "b/c\316\273ash.lhs" @@ -524,7 +524,7 @@ functional hardware description language must eventually be converted into a netlist. This research also features a prototype translator called \CLaSH\ (pronounced: clash), which converts the Haskell code to equivalently behaving synthesizable \VHDL\ code, ready to be converted to an actual netlist format -by an optimizing \VHDL\ synthesis tools. +by an optimizing \VHDL\ synthesis tool. \section{Hardware description in Haskell} @@ -549,62 +549,46 @@ by an optimizing \VHDL\ synthesis tools. As an example we can see the netlist of the |mac| function in \Cref{img:mac-comb}; the |mac| function applies both the |mul| and |add| function to calculate $a * b + c$: + \begin{code} mac a b c = add (mul a b) c \end{code} + \begin{figure} \centerline{\includegraphics{mac}} \caption{Combinatorial Multiply-Accumulate} \label{img:mac-comb} \end{figure} + The result of using a complex input type can be seen in \cref{img:mac-comb-nocurry} where the |mac| function now uses a single input tuple for the |a|, |b|, and |c| arguments: + \begin{code} mac (a, b, c) = add (mul a b) c \end{code} + \begin{figure} \centerline{\includegraphics{mac-nocurry}} \caption{Combinatorial Multiply-Accumulate (complex input)} \label{img:mac-comb-nocurry} \end{figure} - \subsection{Choices} - Although describing components and connections allows describing a - lot of hardware designs already, there is an obvious thing missing: - choice. We need some way to be able to choose between values based - on another value. In Haskell, choice is achieved by \hs{case} - expressions, \hs{if} expressions, pattern matching and guards. - - The easiest of these are of course case expressions (and \hs{if} - expressions, which can be very directly translated to \hs{case} - expressions). A \hs{case} expression can in turn simply be - translated to a conditional assignment in \VHDL, where the - conditions use equality comparisons against the constructors in the - \hs{case} expressions. - - A slightly more complex (but very powerful) form of choice is - pattern matching. A function can be defined in multiple clauses, - where each clause specifies a pattern. When the arguments match the - pattern, the corresponding clause will be used. - - A pattern match (with optional guards) can also be implemented using - conditional assignments in \VHDL, where the condition is the logical - and of comparison results of each part of the pattern as well as the - guard. - - Contrived example that sums two values when they are equal or - non-equal (depending on the predicate given) and returns 0 - otherwise. This shows three implementations, one using and if - expression, one using only case expressions and one using pattern - matching and guards. - + \subsection{Choice} + In Haskell, choice can be achieved by a large set of language constructs, + consisting of: \hs{case} constructs, \hs{if-then-else} constructs, + pattern matching, and guards. The easiest of these are the \hs{case} + constructs (and \hs{if} expressions, which can be very directly translated + to \hs{case} expressions). A \hs{case} expression can in turn simply be + translated to a conditional assignment in \VHDL, where the conditions use + equality comparisons against the constructors in the \hs{case} + expressions. We can see two versions of a contrived example, 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. + \begin{code} - sumif pred a b = if pred == Eq && a == b || - pred == Neq && a != b - then a + b - else 0 - sumif pred a b = case pred of Eq -> case a == b of True -> a + b @@ -612,24 +596,52 @@ by an optimizing \VHDL\ synthesis tools. Neq -> case a != b of True -> a + b False -> 0 + \end{code} - sumif Eq a b | a == b = a + b - sumif Neq a b | a != b = a + b - sumif _ _ _ = 0 + \begin{code} + sumif pred a b = + if pred == Eq then + if a == b then a + b else 0 + else + if a != b then a + b else 0 \end{code} - \begin{figure} - \centerline{\includegraphics{choice-ifthenelse}} - \caption{Choice - \emph{if-then-else}} - \label{img:choice} - \end{figure} + Both versions of the example correspond to the same netlist, which is + depicted in \Cref{img:choice} \begin{figure} \centerline{\includegraphics{choice-case}} - \caption{Choice - \emph{case-statement / pattern matching}} + \caption{Choice - sumif} \label{img:choice} \end{figure} + A slightly more complex (but very powerful) form of choice is pattern + matching. A function can be defined in multiple clauses, where each clause + specifies a pattern. When the arguments match the pattern, the + corresponding clause will be used. Expressions can also contain guards, + where the expression is only executed if the guard evaluates to true. A + pattern match (with optional guards) can be to a conditional assignments + in \VHDL, where the conditions are an equality test of the argument and + one of the patterns (combined with the guard if was present). A third + version of the earlier example, using both pattern matching and guards, + can be seen below: + + \begin{code} + sumif Eq a b | a == b = a + b + sumif Neq a b | a != b = a + b + sumif _ _ _ = 0 + \end{code} + + The version using pattern matching and guards has the same netlist + representation (\Cref{img:choice}) as the earlier two versions of the + example. + + % \begin{figure} + % \centerline{\includegraphics{choice-ifthenelse}} + % \caption{Choice - \emph{if-then-else}} + % \label{img:choice} + % \end{figure} + \subsection{Types} Translation of two most basic functional concepts has been discussed: function application and choice. Before looking further diff --git a/mac-nocurry.svg b/mac-nocurry.svg index bc3450d..2b9653b 100644 --- a/mac-nocurry.svg +++ b/mac-nocurry.svg @@ -11,7 +11,7 @@ xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" width="167.75" - height="62.049969" + height="62.249371" id="svg2" version="1.1" inkscape:version="0.47 r22583" @@ -24,16 +24,16 @@ inkscape:pageopacity="0.0" inkscape:pageshadow="2" inkscape:zoom="4.3338301" - inkscape:cx="83.875" - inkscape:cy="31.024985" + inkscape:cx="41.187586" + inkscape:cy="31.224388" inkscape:document-units="px" inkscape:current-layer="layer1" showgrid="false" inkscape:snap-grids="true" inkscape:window-width="1091" inkscape:window-height="838" - inkscape:window-x="575" - inkscape:window-y="194" + inkscape:window-x="253" + inkscape:window-y="212" inkscape:window-maximized="0"> + style="fill:#ffffff;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none" />