X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Fdsd-paper.git;a=blobdiff_plain;f=c%CE%BBash.lhs;h=5819c83dd48d7da7398a0c20748dd62278d876d2;hp=5efc96176f9b56f6508b07d22867db0177e6d789;hb=9acd9933a384365a3859ba4cc0fc29b53c2737d5;hpb=38a92f9980362c4e99f1d3143dbc8dbcc84be766 diff --git "a/c\316\273ash.lhs" "b/c\316\273ash.lhs" index 5efc961..5819c83 100644 --- "a/c\316\273ash.lhs" +++ "b/c\316\273ash.lhs" @@ -122,7 +122,7 @@ % *** GRAPHICS RELATED PACKAGES *** % \ifCLASSINFOpdf - % \usepackage[pdftex]{graphicx} + \usepackage[pdftex]{graphicx} % declare the path(s) where your graphic files are % \graphicspath{{../pdf/}{../jpeg/}} % and their extensions so you won't have to specify these with @@ -360,7 +360,7 @@ \setlength{\leftmargin}{\labelwidth} \addtolength{\leftmargin}{\labelsep} \setlength{\rightmargin}{0pt} - \setlength{\parsep}{0.5ex plus 0.2ex minus 0.1ex} + \setlength{\listparindent}{\parindent} \setlength{\itemsep}{0 ex plus 0.2ex} \renewcommand{\makelabel}[1]{##1:\hfil} } @@ -368,6 +368,8 @@ {\end{list}} \usepackage{paralist} +\usepackage{xcolor} +\def\comment#1{{\color[rgb]{1.0,0.0,0.0}{#1}}} %include polycode.fmt %include clash.fmt @@ -463,38 +465,62 @@ 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. +Hardware description languages, like \VHDL~\cite{VHDL2008} and +Verilog~\cite{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. In an attempt to raise the +abstraction level of the descriptions, 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 for hardware +descriptions 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. The merit of using a functional language to describe +hardware comes from the fact that basic combinatorial circuits are equivalent +to mathematical functions and that functional languages are very good at +describing and composing 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. +functional language Haskell \cite{Hydra,Hawk1,Lava,ForSyDe1,Wired}. This +means that a developer is given a library of Haskell~\cite{Haskell} functions +and types that together form the language primitives of the domain specific +language. As a result of how the signals are modeled and abstracted, the +functions used to describe a circuit also build a large domain-specific +datatype (hidden from the designer) 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. +language embedded in Haskell, but to use (a subset of) the Haskell language +itself for the purpose of describing hardware. By taking this approach, we can +capture certain language constructs, such as Haskell's choice elements +(if-constructs, case-constructs, pattern matching, etc.), which are not +available in the functional hardware description languages that are embedded +in Haskell as a domain specific languages. As far as the authors know, such +extensive support for choice-elements is new in the domain of functional +hardware description language. As the hardware descriptions are plain Haskell +functions, these descriptions can be compiled for simulation using using the +optimizing Haskell compiler \GHC. + +Where descriptions in a conventional hardware description language have an +explicit clock for the purpose state and synchronicity, the clock is implied +in this research. The functions describe the behavior of the hardware between +clock cycles, as such, only synchronous systems can be described. Many +functional hardware description models signals as a stream of all values over +time; state is then modeled as a delay on this stream of values. The approach +taken in this research is to make the current state of a circuit part of the +input of the function and the updated state part of the output. + +Like the standard hardware description languages, descriptions made in a +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. \section{Hardware description in Haskell} @@ -507,14 +533,14 @@ itself to be used as hardware description language. as a tuple), so having just a single output port does not create a limitation. - Each function application in turn becomes component instantiation. + Each function application in turn becomes a 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 itself. Since every top level function generates its own component, the - hierarchy of of function calls is reflected in the final \VHDL\ + hierarchy of function calls is reflected in the final \VHDL\ output as well, creating a hierarchical \VHDL\ description of the hardware. This separation in different components makes the resulting \VHDL\ output easier to read and debug. @@ -522,11 +548,21 @@ itself to be used as hardware description language. Example that defines the \texttt{mac} function by applying the \texttt{add} and \texttt{mul} functions to calculate $a * b + c$: -\begin{verbatim} +\begin{code} mac a b c = add (mul a b) c -\end{verbatim} +\end{code} + +\begin{figure} +\centerline{\includegraphics{mac}} +\caption{Combinatorial Multiply-Accumulate (curried)} +\label{img:mac-comb} +\end{figure} - TODO: Pretty picture +\begin{figure} +\centerline{\includegraphics{mac-nocurry}} +\caption{Combinatorial Multiply-Accumulate (uncurried)} +\label{img:mac-comb-nocurry} +\end{figure} \subsection{Choices} Although describing components and connections allows describing a @@ -558,26 +594,26 @@ mac a b c = add (mul a b) c expression, one using only case expressions and one using pattern matching and guards. -\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 - 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} + \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 + 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 + \comment{TODO: Pretty picture} \subsection{Types} Translation of two most basic functional concepts has been @@ -591,7 +627,7 @@ sumif _ _ _ = 0 every \emph{type} used in a hardware description is needed. The following types are \emph{built-in}, meaning that their hardware - translation is fixed into the \CLaSH compiler. A designer can also + translation is fixed into the \CLaSH\ compiler. A designer can also define his own types, which will be translated into hardware types using translation rules that are discussed later on. @@ -615,61 +651,54 @@ sumif _ _ _ = 0 length type, so you can define an unsigned word of 32 bits wide as follows: -\begin{verbatim} -type Word32 = SizedWord D32 -\end{verbatim} + \begin{code} + type Word32 = SizedWord D32 + \end{code} Here, a type synonym \hs{Word32} is defined that is equal to the \hs{SizedWord} type constructor applied to the type \hs{D32}. \hs{D32} is the \emph{type level representation} of the decimal number 32, - making the \hs{Word32} type a 32-bit unsigned word. - - These types are translated to the \VHDL\ \texttt{unsigned} and - \texttt{signed} respectively. + making the \hs{Word32} type a 32-bit unsigned word. These types are + translated to the \VHDL\ \texttt{unsigned} and \texttt{signed} + respectively. \item[\hs{Vector}] This is a vector type, that can contain elements of any other type and - has a fixed length. - - The \hs{Vector} type constructor takes two type arguments: the length - of the vector and the type of the elements contained in it. The state - type of an 8 element register bank would then for example be: + has a fixed length. The \hs{Vector} type constructor takes two type + arguments: the length of the vector and the type of the elements + contained in it. The state type of an 8 element register bank would + then for example be: -\begin{verbatim} -type RegisterState = Vector D8 Word32 -\end{verbatim} + \begin{code} + type RegisterState = Vector D8 Word32 + \end{code} Here, a type synonym \hs{RegisterState} is defined that is equal to - the \hs{Vector} type constructor applied to the types \hs{D8} (The type - level representation of the decimal number 8) and \hs{Word32} (The 32 - bit word type as defined above). In other words, the - \hs{RegisterState} type is a vector of 8 32-bit words. - - A fixed size vector is translated to a \VHDL\ array type. + the \hs{Vector} type constructor applied to the types \hs{D8} (The + type level representation of the decimal number 8) and \hs{Word32} + (The 32 bit word type as defined above). In other words, the + \hs{RegisterState} type is a vector of 8 32-bit words. A fixed size + vector is translated to a \VHDL\ array type. \item[\hs{RangedWord}] This is another type to describe integers, but unlike the previous two it has no specific bit-width, but an upper bound. This means that its range is not limited to powers of two, but can be any number. A \hs{RangedWord} only has an upper bound, its lower bound is - implicitly zero. - - The main purpose of the \hs{RangedWord} type is to be used as an - index to a \hs{Vector}. + implicitly zero. The main purpose of the \hs{RangedWord} type is to be + used as an index to a \hs{Vector}. - TODO: Perhaps remove this example? + \comment{TODO: Perhaps remove this example?} To define an index for + the 8 element vector above, we would do: - To define an index for the 8 element vector above, we would do: - -\begin{verbatim} -type RegisterIndex = RangedWord D7 -\end{verbatim} + \begin{code} + type RegisterIndex = RangedWord D7 + \end{code} Here, a type synonym \hs{RegisterIndex} is defined that is equal to the \hs{RangedWord} type constructor applied to the type \hs{D7}. In other words, this defines an unsigned word with values from 0 to 7 (inclusive). This word can be be used to index the - 8 element vector \hs{RegisterState} above. - - This type is translated to the \texttt{unsigned} \VHDL type. + 8 element vector \hs{RegisterState} above. This type is translated to + the \texttt{unsigned} \VHDL type. \end{xlist} \subsection{User-defined types} @@ -696,37 +725,91 @@ type RegisterIndex = RangedWord D7 \item[\bf{Single constructor}] Algebraic datatypes with a single constructor with one or more fields, are essentially a way to pack a few values together in a - record-like structure. + record-like structure. An example of such a type is the following pair + of integers: - An example of such a type is the following pair of integers: - -\begin{verbatim} +\begin{code} data IntPair = IntPair Int Int -\end{verbatim} +\end{code} Haskell's builtin tuple types are also defined as single constructor algebraic types and are translated according to this - rule by the \CLaSH compiler. - - These types are translated to \VHDL\ record types, with one field for - every field in the constructor. + rule by the \CLaSH\ compiler. These types are translated to \VHDL\ + record types, with one field for every field in the constructor. \item[\bf{No fields}] Algebraic datatypes with multiple constructors, but without any fields are essentially a way to get an enumeration-like type - containing alternatives. - - Note that Haskell's \hs{Bool} type is also defined as an - enumeration type, but we have a fixed translation for that. - - 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. + containing alternatives. Note that Haskell's \hs{Bool} type is also + defined as an enumeration type, but we have a fixed translation for + that. 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[\bf{Multiple constructors with fields}] Algebraic datatypes with multiple constructors, where at least one of these constructors has one or more fields are not currently supported. \end{xlist} + \subsection{Polymorphic functions} + A powerful construct in most functional language is polymorphism. + This means the arguments of a function (and consequentially, values + within the function as well) do not need to have a fixed type. + Haskell supports \emph{parametric polymorphism}, meaning a + function's type can be parameterized with another type. + + As an example of a polymorphic function, consider the following + \hs{append} function's type: + + TODO: Use vectors instead of lists? + + \begin{code} + append :: [a] -> a -> [a] + \end{code} + + This type is parameterized by \hs{a}, which can contain any type at + all. This means that append can append an element to a list, + regardless of the type of the elements in the list (but the element + added must match the elements in the list, since there is only one + \hs{a}). + + This kind of polymorphism is extremely useful in hardware designs to + make operations work on a vector without knowing exactly what elements + are inside, routing signals without knowing exactly what kinds of + signals these are, or working with a vector without knowing exactly + how long it is. Polymorphism also plays an important role in most + higher order functions, as we will see in the next section. + + The previous example showed unconstrained polymorphism (TODO: How is + this really called?): \hs{a} can have \emph{any} type. Furthermore, + Haskell supports limiting the types of a type parameter to specific + class of types. An example of such a type class is the \hs{Num} + class, which contains all of Haskell's numerical types. + + Now, take the addition operator, which has the following type: + + \begin{code} + (+) :: Num a => a -> a -> a + \end{code} + + This type is again parameterized by \hs{a}, but it can only contain + types that are \emph{instances} of the \emph{type class} \hs{Num}. + Our numerical built-in types are also instances of the \hs{Num} + class, so we can use the addition operator on \hs{SizedWords} as + well as on {SizedInts}. + + In \CLaSH, unconstrained polymorphism is completely supported. Any + function defined can have any number of unconstrained type + parameters. The \CLaSH compiler will infer the type of every such + argument depending on how the function is applied. There is one + exception to this: The top level function that is translated, can + not have any polymorphic arguments (since it is never applied, so + there is no way to find out the actual types for the type + parameters). + + \CLaSH does not support user-defined type classes, but does use some + of the builtin ones for its builtin functions (like \hs{Num} and + \hs{Eq}). + \subsection{State} A very important concept in hardware it the concept of state. In a stateful design, the outputs depend on the history of the inputs, or the @@ -810,7 +893,7 @@ section. The merits of polymorphic typing, combined with higher-order functions, are now also recognized in the `main-stream' hardware description languages, -exemplified by the new \VHDL\-2008 standard~\cite{VHDL2008}. \VHDL-2008 has +exemplified by the new \VHDL-2008 standard~\cite{VHDL2008}. \VHDL-2008 has support to specify types as generics, thus allowing a developer to describe polymorphic components. Note that those types still require an explicit generic map, whereas type-inference and type-specialization are implicit in