X-Git-Url: https://git.stderr.nl/gitweb?a=blobdiff_plain;f=c%CE%BBash.lhs;h=ab3c8e258d81f4b8a8aa19d35ae202d9106dc2f2;hb=ad8bfec91e5117f3f09f972909e05f97b359fa45;hp=a86cd63e4c2c9e6446be87e0f7161346ae8cbb0d;hpb=a29b7f38457301bcb6e49a7055f8c59a73bba80c;p=matthijs%2Fmaster-project%2Fdsd-paper.git diff --git "a/c\316\273ash.lhs" "b/c\316\273ash.lhs" index a86cd63..ab3c8e2 100644 --- "a/c\316\273ash.lhs" +++ "b/c\316\273ash.lhs" @@ -367,7 +367,10 @@ } {\end{list}} +\usepackage{paralist} + %include polycode.fmt +%include clash.fmt \begin{document} % @@ -382,7 +385,7 @@ \author{\IEEEauthorblockN{Christiaan P.R. Baaij, Matthijs Kooijman, Jan Kuper, Marco E.T. Gerards, Bert Molenkamp, Sabih H. Gerez} \IEEEauthorblockA{University of Twente, Department of EEMCS\\ P.O. Box 217, 7500 AE, Enschede, The Netherlands\\ -c.p.r.baaij@utwente.nl, matthijs@stdin.nl}} +c.p.r.baaij@@utwente.nl, matthijs@@stdin.nl}} % \and % \IEEEauthorblockN{Homer Simpson} % \IEEEauthorblockA{Twentieth Century Fox\\ @@ -470,12 +473,29 @@ 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. +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. + +In an attempt to decrease the amount of work involved with creating all the +required tooling, such as parsers and type-checkers, many functional hardware +description languages are embedded as a domain specific language inside the +functional language Haskell \cite{Hydra,Hawk1,Lava,ForSyDe1,Wired}. What this +means is that a developer is given a library of Haskell functions and types +that together form the language primitives of the domain specific language. +Using these functions, the designer does not only describes a circuit, but +actually builds a large domain-specific datatype which can be further +processed by an embedded compiler. This compiler actually runs in the same +environment as the description; as a result compile-time and run-time become +hard to define, as the embedded compiler is usually compiled by the same +Haskell compiler as the circuit description itself. + +The approach taken in this research is not to make another domain specific +language embedded in Haskell, but to use (a subset) of the Haskell language +itself to be used as hardware description language. -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} \subsection{Function application} @@ -508,7 +528,7 @@ mac a b c = add (mul a b) c TODO: Pretty picture - \subsection{Choices } + \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 @@ -538,27 +558,24 @@ mac a b c = add (mul a b) c 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{code} +sumif pred a b = + if pred == Eq && a == b || pred == Neq && a != b + then a + b + else 0 -\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} + Eq -> case a == b of + True -> a + b + False -> 0 + Neq -> case a != b of + True -> a + b + False -> 0 + +sumif Eq a b | a == b = a + b +sumif Neq a b | a != b = a + b +sumif _ _ _ = 0 +\end{code} TODO: Pretty picture @@ -687,7 +704,7 @@ type RegisterIndex = RangedWord D7 For algebraic types, we can make the following distinction: \begin{xlist} - \item[Product types] + \item[\textbf{Product types}] A product type is an algebraic datatype with a single constructor with two or more fields, denoted in practice like (a,b), (a,b,c), etc. This is essentially a way to pack a few values together in a record-like @@ -703,7 +720,7 @@ type RegisterIndex = RangedWord D7 constructor algebraic data-types, including those with just one field (which are technically not a product, but generate a VHDL record for implementation simplicity). - \item[Enumerated types] + \item[\textbf{Enumerated types}] An enumerated type is an algebraic datatype with multiple constructors, but none of them have fields. This is essentially a way to get an enumeration-like type containing alternatives. @@ -714,7 +731,7 @@ type RegisterIndex = RangedWord D7 These types are translated to \VHDL\ enumerations, with one value for each constructor. This allows references to these constructors to be translated to the corresponding enumeration value. - \item[Sum types] + \item[\textbf{Sum types}] A sum type is an algebraic datatype with multiple constructors, where the constructors have one or more fields. Technically, a type with more than one field per constructor is a sum of products type, but @@ -769,6 +786,39 @@ type Sum = (SumC, Bit, Word, Word) during a clock cycle. As we want to describe more than simple combinatorial designs, \CLaSH\ needs an abstraction mechanism for state. + An important property in Haskell, and in most other functional languages, + is \emph{purity}. A function is said to be \emph{pure} if it satisfies two + conditions: + \begin{inparaenum} + \item given the same arguments twice, it should return the same value in + both cases, and + \item when the function is called, it should not have observable + side-effects. + \end{inparaenum} + This purity property is important for functional languages, since it + enables all kinds of mathematical reasoning that could not be guaranteed + correct for impure functions. Pure functions are as such a perfect match + for a combinatorial circuit, where the output solely depends on the + inputs. When a circuit has state however, it can no longer be simply + described by a pure function. Simply removing the purity property is not a + valid option, as the language would then lose many of it mathematical + properties. In an effort to include the concept of state in pure + functions, the current value of the state is made an argument of the + function; the updated state becomes part of the result. + + A simple example is the description of an accumulator circuit: + \begin{code} + acc :: Word -> State Word -> (State Word, Word) + acc inp (State s) = (State s', outp) + where + outp = s + inp + s' = outp + \end{code} + This approach makes the state of a function very explicit: which variables + are part of the state is completely determined by the type signature. This + approach to state is well suited to be used in combination with the + existing code and language features, such as all the choice constructs, as + state values are just normal values. \section{\CLaSH\ prototype} foo\par bar @@ -818,11 +868,11 @@ polymorphic components. Note that those types still require an explicit generic map, whereas type-inference and type-specialization are implicit in \CLaSH. -Wired~\cite{Wired},, T-Ruby~\cite{T-Ruby}, Hydra~\cite{Hydra}. - -A functional language designed specifically for hardware design is -$re{\mathit{FL}}^{ect}$~\cite{reFLect}, which draws experience from earlier -language called \acro{FL}~\cite{FL} to la +% Wired~\cite{Wired},, T-Ruby~\cite{T-Ruby}, Hydra~\cite{Hydra}. +% +% A functional language designed specifically for hardware design is +% $re{\mathit{FL}}^{ect}$~\cite{reFLect}, which draws experience from earlier +% language called \acro{FL}~\cite{FL} to la % An example of a floating figure using the graphicx package. % Note that \label must occur AFTER (or within) \caption.