From: Christiaan Baaij Date: Wed, 27 Jan 2010 08:12:12 +0000 (+0100) Subject: Merge branch 'master' of http://git.stderr.nl/matthijs/projects/cλash-paper X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Fdsd-paper.git;a=commitdiff_plain;h=eb7dcf95682cdea046240ea50407b6fff0e8e158;hp=0a1b86ee6c04e4280cb8ee6a55a7205f1940a1b1 Merge branch 'master' of git.stderr.nl/matthijs/projects/cλash-paper * 'master' of http://git.stderr.nl/matthijs/projects/cλash-paper: Improve the sections on application and choice a bit. Fix typo. Conflicts: cλash.tex --- diff --git "a/c\316\273ash.tex" "b/c\316\273ash.tex" index e1a8ba4..9d4fb22 100644 --- "a/c\316\273ash.tex" +++ "b/c\316\273ash.tex" @@ -443,33 +443,23 @@ The abstract goes here. \section{Introduction} Hardware description languages has allowed the productivity of hardware engineers to keep pace with the development of chip technology. Standard Hardware description languages, like \VHDL\ and Verilog, allowed an engineer to describe circuits using a programming language. These standard languages are very good at describing detailed hardware properties such as timing behavior, but are generally cumbersome in expressing higher-level abstractions. These languages also tend to have a complex syntax and a lack of formal semantics. To overcome these complexities, and raise the abstraction level, a great number of approaches based on functional languages has been proposed \cite{T-Ruby,Hydra,HML2,Hawk1,Lava,ForSyDe1,Wired,reFLect}. The idea of using functional languages started in the early 1980s \cite{Cardelli1981,muFP,DAISY,FHDL}, a time which also saw the birth of the currently popular hardware description languages such as \VHDL. -What gives functional languages as hardware description languages their merits is the fact that basic combinatorial circuits are equivalent to mathematical function, and that functional languages lend themselves very well to describe and compose these mathematical functions. - +What gives functional languages as hardware description languages their merits is the fact that basic combinatorial circuits are equivalent to mathematical function, and that functional languages lend themselves very well to describe and compose these mathematical functions. \section{Hardware description in Haskell} - To translate Haskell to hardware, every Haskell construct needs a - translation to \VHDL. There are often multiple valid translations - possible. When faced with choices, the most obvious choice has been - chosen wherever possible. In a lot of cases, when a programmer looks - at a functional hardware description it is completely clear what - hardware is described. We want our translator to generate exactly that - hardware whenever possible, to make working with \CLaSH\ as intuitive as - possible. - \subsection{Function application} The basic syntactic elements of a functional program are functions and function application. These have a single obvious \VHDL\ translation: each top level function becomes a hardware component, where each argument is an input port and the result value is the (single) output port. This output port can have a complex type (such - as a tuple), so having just a single output port does not pose a + as a tuple), so having just a single output port does not create a limitation. Each function application in turn becomes component instantiation. Here, the result of each argument expression is assigned to a signal, which is mapped to the corresponding input port. The output port of the function is also mapped to a signal, which is used as - the result of the application. + the result of the application itself. Since every top level function generates its own component, the hierarchy of of function calls is reflected in the final \VHDL\ @@ -477,28 +467,69 @@ What gives functional languages as hardware description languages their merits i hardware. This separation in different components makes the resulting \VHDL\ output easier to read and debug. - \subsection{Choice} - Although describing components and connections allows us to describe - 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. - - However, to be able to describe our hardware in a more convenient - way, we also want to translate Haskell's choice mechanisms. The - easiest of these are of course case expressions (and \hs{if} + Example that defines the \texttt{mac} function by applying the + \texttt{add} and \texttt{mul} functions to calculate $a * b + c$: + +\begin{verbatim} +mac a b c = add (mul a b) c +\end{verbatim} + + TODO: Pretty picture + + \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, where the conditions use - equality comparisons against the constructors in the \hs{case} - expressions. + 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. + +\begin{verbatim} +sumif pred a b = if pred == Eq && a == b || pred == Neq && a != b + then a + b + else 0 +\end{verbatim} + +\begin{verbatim} +sumif pred a b = case pred of + Eq -> case a == b of + True -> a + b + False -> 0 + Neq -> case a != b of + True -> a + b + False -> 0 +\end{verbatim} + +\begin{verbatim} +sumif Eq a b | a == b = a + b +sumif Neq a b | a != b = a + b +sumif _ _ _ = 0 +\end{verbatim} + + TODO: Pretty picture + \subsection{Types} Translation of two most basic functional concepts has been discussed: function application and choice. Before looking further