X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Fdsd-paper.git;a=blobdiff_plain;f=c%CE%BBash.lhs;h=5553760b957cfeb82083f2a6e68940693534830b;hp=3cbf3016d4f63a40f6fbc66b99e8732d44888ca7;hb=311d4b7f61e3aa289a5110ed0836d3f4eedc4b3f;hpb=567bd3d2345281a3796ccf4fb66f79c50e3558ed diff --git "a/c\316\273ash.lhs" "b/c\316\273ash.lhs" index 3cbf301..5553760 100644 --- "a/c\316\273ash.lhs" +++ "b/c\316\273ash.lhs" @@ -63,7 +63,9 @@ % should be used if it is desired that the figures are to be displayed in % draft mode. % + \documentclass[conference,pdf,a4paper,10pt,final,twoside,twocolumn]{IEEEtran} +\IEEEoverridecommandlockouts % Add the compsoc option for Computer Society conferences. % % If IEEEtran.cls has not been installed into the LaTeX system files, @@ -93,9 +95,6 @@ - - - % *** CITATION PACKAGES *** % \usepackage{cite} @@ -344,9 +343,12 @@ % Macro for certain acronyms in small caps. Doesn't work with the % default font, though (it contains no smallcaps it seems). \def\acro#1{{\small{#1}}} +\def\acrop#1{\acro{#1}s} +\def\acrotiny#1{{\scriptsize{#1}}} \def\VHDL{\acro{VHDL}} \def\GHC{\acro{GHC}} \def\CLaSH{{\small{C}}$\lambda$a{\small{SH}}} +\def\CLaSHtiny{{\scriptsize{C}}$\lambda$a{\scriptsize{SH}}} % Macro for pretty printing haskell snippets. Just monospaced for now, perhaps % we'll get something more complex later on. @@ -356,9 +358,10 @@ \newenvironment{xlist}[1][\rule{0em}{0em}]{% \begin{list}{}{% \settowidth{\labelwidth}{#1:} - \setlength{\labelsep}{0.5cm} + \setlength{\labelsep}{0.5em} \setlength{\leftmargin}{\labelwidth} \addtolength{\leftmargin}{\labelsep} + \addtolength{\leftmargin}{\parindent} \setlength{\rightmargin}{0pt} \setlength{\listparindent}{\parindent} \setlength{\itemsep}{0 ex plus 0.2ex} @@ -371,9 +374,31 @@ \usepackage{xcolor} \def\comment#1{{\color[rgb]{1.0,0.0,0.0}{#1}}} +\usepackage{cleveref} +\crefname{figure}{figure}{figures} +\newcommand{\fref}[1]{\cref{#1}} +\newcommand{\Fref}[1]{\Cref{#1}} + +\usepackage{epstopdf} + +\epstopdfDeclareGraphicsRule{.svg}{pdf}{.pdf}{rsvg-convert --format=pdf < #1 > \noexpand\OutputFile} + %include polycode.fmt %include clash.fmt +\newcounter{Codecount} +\setcounter{Codecount}{0} + +\newenvironment{example} + { + \refstepcounter{equation} + } + { + \begin{flushright} + (\arabic{equation}) + \end{flushright} + } + \begin{document} % % paper title @@ -384,10 +409,13 @@ % author names and affiliations % use a multiple column layout for up to three different % affiliations -\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\\ +\author{\IEEEauthorblockN{Matthijs Kooijman, Christiaan P.R. Baaij, Jan Kuper, Marco E.T. Gerards}%, Bert Molenkamp, Sabih H. Gerez} +\IEEEauthorblockA{%Computer Architecture for Embedded Systems (CAES)\\ +Department of EEMCS, University of Twente\\ P.O. Box 217, 7500 AE, Enschede, The Netherlands\\ -c.p.r.baaij@@utwente.nl, matthijs@@stdin.nl}} +matthijs@@stdin.nl, c.p.r.baaij@@utwente.nl, j.kuper@@utwente.nl} +% \thanks{Supported through the FP7 project: S(o)OS (248465)} +} % \and % \IEEEauthorblockN{Homer Simpson} % \IEEEauthorblockA{Twentieth Century Fox\\ @@ -434,10 +462,24 @@ c.p.r.baaij@@utwente.nl, matthijs@@stdin.nl}} % make the title area \maketitle - \begin{abstract} %\boldmath -The abstract goes here. +\CLaSH\ is a functional hardware description language that borrows both its +syntax and semantics from the functional programming language Haskell. +Polymorphism and higher-order functions provide a level of abstraction and +generality that allow a circuit designer to describe circuits in a more +natural way than possible in a traditional hardware description language. + +Circuit descriptions can be translated to synthesizable VHDL using the +prototype \CLaSH\ compiler. As the circuit descriptions, simulation code, and +test input are also valid Haskell, complete simulations can be compiled as an +executable binary by a Haskell compiler allowing high-speed simulation and +analysis. + +% \CLaSH\ supports stateful descriptions by explicitly making the current +% state an argument of the function, and the updated state part of the result. +% This makes \CLaSH\ descriptions in essence the combinational parts of a +% mealy machine. \end{abstract} % IEEEtran.cls defaults to using nonbold math in the Abstract. % This preserves the distinction between vectors and scalars. However, @@ -461,438 +503,556 @@ The abstract goes here. % creates the second title. It will be ignored for other modes. \IEEEpeerreviewmaketitle - \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~\cite{VHDL2008} and +Hardware description languages (\acrop{HDL}) have allowed the productivity of +hardware engineers to keep pace with the development of chip technology. +Traditional \acrop{HDL}, 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 +`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}. 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 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. +functional languages has been proposed \cite{Cardelli1981,muFP,DAISY, +T-Ruby,HML2,Hydra,Hawk1,Lava,Wired,ForSyDe1,reFLect}. The idea of using +functional languages for hardware descriptions started in the early 1980s +\cite{Cardelli1981,muFP,DAISY}, a time which also saw the birth of the +currently popular \acrop{HDL}, such as \VHDL. Functional +languages are especially well suited to describe hardware because +combinational circuits can be directly modeled as mathematical functions and +functional languages are very good at describing and composing these +functions. + +In an attempt to decrease the amount of work involved in creating all the +required tooling, such as parsers and type-checkers, many functional +\acrop{HDL} \cite{Hydra,Hawk1,Lava,Wired} are embedded as a domain +specific language (\acro{DSL}) within the functional language Haskell +\cite{Haskell}. This means that a developer is given a library of Haskell +functions and types that together form the language primitives of the +\acro{DSL}. The primitive functions used to describe a circuit do not actually +process any signals, they instead compose a large domain-specific datatype +(which is usually hidden from the designer). This datatype is then further +processed by an embedded circuit compiler which can perform for example +simulation or synthesis. As Haskell's choice elements (\hs{if}-expressions, +\hs{case}-expressions, etc.) are evaluated at the time the domain-specific +datatype is being build, they are no longer visible to the embedded compiler +that processes the datatype. Consequently, it is impossible to capture +Haskell's choice elements within a circuit description when taking the +embedded language approach. This does not mean that circuits specified in an +embedded language can not contain choice, just that choice elements only +exists as functions, e.g. a multiplexer function, and not as language +elements. + +The approach taken in this research is not to make another \acro{DSL} embedded +in Haskell, but to use (a subset of) the Haskell language \emph{itself} for +the purpose of describing hardware. By taking this approach, this research +\emph{can} capture certain language constructs, such as Haskell's choice +elements, within circuit descriptions. To the best knowledge of the authors, +supporting polymorphism, higher-order functions and such an extensive array of +choice-elements, combined with a very concise way of specifying circuits is +new in the domain of (functional) \acrop{HDL}. +% As the hardware descriptions are plain Haskell +% functions, these descriptions can be compiled to an executable binary +% for simulation using an optimizing Haskell compiler such as the Glasgow +% Haskell Compiler (\GHC)~\cite{ghc}. + +Where descriptions in a conventional \acro{HDL} have an explicit clock for the +purposes state and synchronicity, the clock is implied in the context of the +research presented in this paper. A circuit designer describes the behavior of +the hardware between clock cycles. Many functional \acrop{HDL} model 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 an additional input and the updated state a part of the output of a +function. This abstraction of state and time limits the descriptions to +synchronous hardware, there is however room within the language to eventually +add a different abstraction mechanism that will allow for the modeling of +asynchronous systems. + +Like the traditional \acrop{HDL}, descriptions made in a functional \acro{HDL} +must eventually be converted into a netlist. This research also features a +prototype translator, which has the same name as the language: +\CLaSH\footnote{\CLaSHtiny: \acrotiny{CAES} Language for Synchronous Hardware} +(pronounced: clash). This compiler converts the Haskell code to equivalently +behaving synthesizable \VHDL\ code, ready to be converted to an actual netlist +format by an (optimizing) \VHDL\ synthesis tool. + +Besides trivial circuits such as variants of both the \acro{FIR} filter and +the simple \acro{CPU} shown in \Cref{sec:usecases}, the \CLaSH\ compiler has +also been able to successfully translate non-trivial functional descriptions +such as a streaming reduction circuit~\cite{reductioncircuit} for floating +point numbers. \section{Hardware description in Haskell} +The following section describes the basic language elements of \CLaSH\ and the +extensiveness of the support of these elements within the \CLaSH\ compiler. In +various subsections, the relation between the language elements and their +eventual netlist representation is also highlighted. \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 create a - limitation. - - 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 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. - - Example that defines the \texttt{mac} function by applying the - \texttt{add} and \texttt{mul} functions 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 (curried)} -\label{img:mac-comb} -\end{figure} - -\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 - 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. - + Two basic syntactic elements of a functional program are functions + and function application. These have a single obvious translation to a + netlist format: + \begin{inparaenum} + \item every function is translated to a component, + \item every function argument is translated to an input port, + \item the result value of a function is translated to an output port, + and + \item function applications are translated to component instantiations. + \end{inparaenum} + The result value can have a composite type (such as a tuple), so having + just a single result value does not pose any limitation. The actual + arguments of a function application are assigned to signals, which are + then mapped to the corresponding input ports of the component. 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 function calls is reflected in the + final netlist. %, creating a hierarchical description of the hardware. + % The separation in different components makes it easier for a developer + % to understand and possibly hand-optimize the resulting \VHDL\ output of + % the \CLaSH\ compiler. + + The short example (\ref{lst:code1}) demonstrated below gives an indication + of the level of conciseness that can be achieved with functional hardware + description languages when compared with the more traditional hardware + description languages. The example is a combinational multiply-accumulate + circuit that works for \emph{any} word length (this type of polymorphism + will be further elaborated in \Cref{sec:polymorhpism}). The corresponding + netlist is depicted in \Cref{img:mac-comb}. + + \hspace{-1.7em} + \begin{minipage}{0.93\linewidth} + \begin{code} + mac a b c = add (mul a b) c + \end{code} + \end{minipage} + \begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code1} + \end{example} + \end{minipage} + + \begin{figure} + \centerline{\includegraphics{mac.svg}} + \caption{Combinational Multiply-Accumulate} + \label{img:mac-comb} + \vspace{-1.5em} + \end{figure} + + The use of a composite result value is demonstrated in the next example + (\ref{lst:code2}), where the multiply-accumulate circuit not only returns + the accumulation result, but also the intermediate multiplication result. + Its corresponding netlist can be seen in \Cref{img:mac-comb-composite}. + + \hspace{-1.7em} + \begin{minipage}{0.93\linewidth} + \begin{code} + mac a b c = (z, add z c) + where + z = mul a b + \end{code} + \end{minipage} + \begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code2} + \end{example} + \end{minipage} + + \begin{figure} + \centerline{\includegraphics{mac-nocurry.svg}} + \caption{Combinational Multiply-Accumulate (composite output)} + \label{img:mac-comb-composite} + \vspace{-1.5em} + \end{figure} + + \subsection{Choice} + In Haskell, choice can be achieved by a large set of syntactic elements, + consisting of: \hs{case} expressions, \hs{if-then-else} expressions, + pattern matching, and guards. The most general of these are the \hs{case} + expressions (\hs{if} expressions can be directly translated to + \hs{case} expressions). When transforming a \CLaSH\ description to a + netlist, a \hs{case} expression is translated to a multiplexer. The + control value of the \hs{case} expression is fed into a number of + comparators and their combined output forms the selection port of the + multiplexer. The result of each alternative in the \hs{case} expression is + linked to the corresponding input port of the multiplexer. + % 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. + Two versions of a contrived example are displayed below, the first + (\ref{lst:code3}) using a \hs{case} expression and the second + (\ref{lst:code4}) using an \hs{if-then-else} expression. Both examples + sum two values when they are equal or non-equal (depending on the given + predicate, the \hs{pred} variable) and return 0 otherwise. The \hs{pred} + variable is of the following, user-defined, enumeration datatype: + \begin{code} - sumif pred a b = if pred == Eq && a == b || - pred == Neq && a != b - then a + b - else 0 + data Pred = Equal | NotEqual + \end{code} + The naive netlist corresponding to both versions of the example is + depicted in \Cref{img:choice}. Note that the \hs{pred} variable is only + compared to \hs{Equal}, as an inequality immediately implies that + \hs{pred} is \hs{NotEqual}. + + \hspace{-1.7em} + \begin{minipage}{0.93\linewidth} + \begin{code} 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 + Equal -> case a == b of + True -> a + b + False -> 0 + NotEqual -> case a != b of + True -> a + b + False -> 0 \end{code} - - \comment{TODO: Pretty picture} + \end{minipage} + \begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code3} + \end{example} + \end{minipage} + + \hspace{-1.7em} + \begin{minipage}{0.93\linewidth} + \begin{code} + sumif pred a b = + if pred == Equal then + if a == b then a + b else 0 + else + if a != b then a + b else 0 + \end{code} + \end{minipage} + \begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code4} + \end{example} + \end{minipage} + + \begin{figure} + \vspace{1em} + \centerline{\includegraphics{choice-case.svg}} + \caption{Choice - sumif} + \label{img:choice} + \vspace{-1.5em} + \end{figure} + + A user-friendly and also very powerful form of choice that is not found in + the traditional hardware description languages is pattern matching. A + function can be defined in multiple clauses, where each clause corresponds + to a pattern. When an argument matches a pattern, the corresponding clause + will be used. Expressions can also contain guards, where the expression is + only executed if the guard evaluates to true, and continues with the next + clause if the guard evaluates to false. Like \hs{if-then-else} + expressions, pattern matching and guards have a (straightforward) + translation to \hs{case} expressions and can as such be mapped to + multiplexers. A third version (\ref{lst:code5}) of the earlier example, + now using both pattern matching and guards, can be seen below. The guard + is the expression that follows the vertical bar (\hs{|}) and precedes the + assignment operator (\hs{=}). The \hs{otherwise} guards always evaluate to + \hs{true}. + + The version using pattern matching and guards corresponds to the same + naive netlist representation (\Cref{img:choice}) as the earlier two + versions of the example. + + \hspace{-1.7em} + \begin{minipage}{0.93\linewidth} + \begin{code} + sumif Equal a b | a == b = a + b + | otherwise = 0 + sumif NotEqual a b | a != b = a + b + | otherwise = 0 + \end{code} + \end{minipage} + \begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code5} + \end{example} + \end{minipage} + + % \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 - into less obvious concepts like higher-order expressions and - polymorphism, the possible types that can be used in hardware - descriptions will be discussed. - - Some way is needed to translate every value used to its hardware - equivalents. In particular, this means a hardware equivalent for - 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 - define his own types, which will be translated into hardware types - using translation rules that are discussed later on. - - \subsection{Built-in types} + Haskell is a statically-typed language, meaning that the type of a + variable or function is determined at compile-time. Not all of Haskell's + typing constructs have a clear translation to hardware, this section will + therefore only deal with the types that do have a clear correspondence + to hardware. The translatable types are divided into two categories: + \emph{built-in} types and \emph{user-defined} types. Built-in types are + those types for which a fixed translation is defined within the \CLaSH\ + compiler. The \CLaSH\ compiler has generic translation rules to + translate the user-defined types, which are described later on. + + The \CLaSH\ compiler is able to infer unspecified (polymorphic) types, + meaning that a developer does not have to annotate every function with a + type signature. % (even if it is good practice to do so). + Given that the top-level entity of a circuit design is annotated with + concrete/monomorphic types, the \CLaSH\ compiler can specialize + polymorphic functions to functions with concrete types. + + % Translation of two most basic functional concepts has been + % discussed: function application and choice. Before looking further + % into less obvious concepts like higher-order expressions and + % polymorphism, the possible types that can be used in hardware + % descriptions will be discussed. + % + % Some way is needed to translate every value used to its hardware + % equivalents. In particular, this means a hardware equivalent for + % 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 + % define his own types, which will be translated into hardware types + % using translation rules that are discussed later on. + + \subsubsection{Built-in types} + The following types have fixed translations defined within the \CLaSH\ + compiler: \begin{xlist} - \item[\hs{Bit}] - This is the most basic type available. It can have two values: - \hs{Low} and \hs{High}. It is mapped directly onto the - \texttt{std\_logic} \VHDL\ type. - \item[\hs{Bool}] - This is a basic logic type. It can have two values: \hs{True} - and \hs{False}. It is translated to \texttt{std\_logic} exactly - like the \hs{Bit} type (where a value of \hs{True} corresponds - to a value of \hs{High}). Supporting the Bool type is - particularly useful to support \hs{if ... then ... else ...} - expressions, which always have a \hs{Bool} value for the - condition. - \item[\hs{SizedWord}, \hs{SizedInt}] - These are types to represent integers. A \hs{SizedWord} is unsigned, - while a \hs{SizedInt} is signed. These types are parametrized by a - length type, so you can define an unsigned word of 32 bits wide as - follows: - - \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. - \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 + \item[\bf{Bit}] + the most basic type available. It can have two values: + \hs{Low} or \hs{High}. + % It is mapped directly onto the \texttt{std\_logic} \VHDL\ type. + \item[\bf{Bool}] + this is a basic logic type. It can have two values: \hs{True} + or \hs{False}. + % It is translated to \texttt{std\_logic} exactly like the \hs{Bit} + % type (where a value of \hs{True} corresponds to a value of + % \hs{High}). + Supporting the Bool type is required in order to support the + \hs{if-then-else} expression, which requires a \hs{Bool} value for + the condition. + \item[\bf{Signed}, \bf{Unsigned}] + these are types to represent integers and both are parametrizable in + their size. The overflow behavior of the numeric operators defined for + these types is \emph{wrap-around}. + % , so you can define an unsigned word of 32 bits wide as follows: + + % \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. + \item[\bf{Vector}] + this is a vector type that can contain elements of any other type and + has a static 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{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. - \item[\hs{RangedWord}] - This is another type to describe integers, but unlike the previous + contained in it. The short-hand notation used for the vector type in + the rest of paper is: \hs{[a|n]}, where \hs{a} is the element + type, and \hs{n} is the length of the vector. Note that this is + a notation used in this paper only, vectors are slightly more + verbose in real \CLaSH\ descriptions. + % The state type of an 8 element register bank would then for example + % be: + + % \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. + \item[\bf{Index}] + 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}. - - \comment{TODO: Perhaps remove this example?} To define an index for - the 8 element vector above, we would do: - - \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. + An \hs{Index} only has an upper bound, its lower bound is + implicitly zero. If a value of this type exceeds either bounds, an + error will be thrown at simulation-time. The main purpose of the + \hs{Index} type is to be used as an index into a \hs{Vector}. + + % \comment{TODO: Perhaps remove this example?} To define an index for + % the 8 element vector above, we would do: + + % \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. \end{xlist} - \subsection{User-defined types} + \subsubsection{User-defined types} There are three ways to define new types in Haskell: algebraic data-types with the \hs{data} keyword, type synonyms with the \hs{type} - keyword and type renamings with the \hs{newtype} keyword. \GHC\ - offers a few more advanced ways to introduce types (type families, - existential typing, {\small{GADT}}s, etc.) which are not standard - Haskell. These are not currently supported. + keyword and datatype renaming constructs with the \hs{newtype} keyword. + % \GHC\ offers a few more advanced ways to introduce types (type families, + % existential typing, {\acro{GADT}}s, etc.) which are not standard + % Haskell. As it is currently unclear how these advanced type constructs + % correspond to hardware, they are for now unsupported by the \CLaSH\ + % compiler. Only an algebraic datatype declaration actually introduces a - completely new type, for which we provide the \VHDL\ translation - below. Type synonyms and renamings only define new names for - existing types (where synonyms are completely interchangeable and - renamings need explicit conversion). Therefore, these do not need - any particular \VHDL\ translation, a synonym or renamed type will - just use the same representation as the original type. The - distinction between a renaming and a synonym does no longer matter - in hardware and can be disregarded in the generated \VHDL. - - For algebraic types, we can make the following distinction: - + completely new type. Type synonyms and type renaming only define new + names for existing types, where synonyms are completely interchangeable + and a type renaming requires an explicit conversion. Type synonyms and + type renaming do not need any particular translation, a synonym or + renamed type will just use the same representation as the original type. + + For algebraic types, we can make the following distinctions: \begin{xlist} \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. An example of such a type is the following pair - of integers: - -\begin{code} -data IntPair = IntPair Int Int -\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. + record-like structure. Haskell's built-in tuple types are also defined + as single constructor algebraic types (but with a bit of + syntactic sugar). An example of a single constructor type with + multiple fields is the following pair of integers: + \begin{code} + data IntPair = IntPair Int Int + \end{code} + % 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. + defined as an enumeration type, but that there is a fixed translation + for that type within the \CLaSH\ compiler. An example of such an + enumeration type is the type that represents the colors in a traffic + light: + \begin{code} + data TrafficLight = Red | Orange | Green + \end{code} + % 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. + one of these constructors has one or more fields are currently not + 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: + \subsection{Polymorphism}\label{sec:polymorhpism} + A powerful feature of most (functional) programming languages is + polymorphism, it allows a function to handle values of different data + types in a uniform way. Haskell supports \emph{parametric + polymorphism}~\cite{polymorphism}, meaning functions can be written + without mention of any specific type and can be used transparently with + any number of new types. + + As an example of a parametric polymorphic function, consider the type of + the following \hs{append} function, which appends an element to a + vector:\footnote{The \hs{::} operator is used to annotate a function + with its type.} - TODO: Use vectors instead of lists? - \begin{code} - append :: [a] -> a -> [a] + append :: [a|n] -> a -> [a|n + 1] \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: - + all. This means that \hs{append} can append an element to a vector, + regardless of the type of the elements in the list (as long as the type of + the value to be added is of the same type as the values in the vector). + 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. + + Another type of polymorphism is \emph{ad-hoc + polymorphism}~\cite{polymorphism}, which refers to polymorphic + functions which can be applied to arguments of different types, but which + behave differently depending on the type of the argument to which they are + applied. In Haskell, ad-hoc polymorphism is achieved through the use of + type classes, where a class definition provides the general interface of a + function, and class instances define the functionality for the specific + types. An example of such a type class is the \hs{Num} class, which + contains all of Haskell's numerical operations. A designer can make use + of this ad-hoc polymorphism by adding a constraint to a parametrically + polymorphic type variable. Such a constraint indicates that the type + variable can only be instantiated to a type whose members supports the + overloaded functions associated with the type class. + + An example of a type signature that includes such a constraint if the + signature of the \hs{sum} function, which sums the values in a vector: \begin{code} - (+) :: Num a => a -> a -> a + sum :: Num a => [a|n] -> 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{Higher order} + types that are \emph{instances} of the \emph{type class} \hs{Num}, so that + the compiler knows that the addition (+) operator is defined for that + type. + % \CLaSH's built-in numerical types are also instances of the \hs{Num} + % class. + % so we can use the addition operator (and thus the \hs{sum} + % function) with \hs{Signed} as well as with \hs{Unsigned}. + + \CLaSH\ supports both parametric polymorphism and ad-hoc polymorphism. Any + function defined can have any number of unconstrained type parameters. A + developer can also specify his own type classes and corresponding + instances. The \CLaSH\ compiler will infer the type of every polymorphic + argument depending on how the function is applied. There is however one + constraint: the top level function that is being translated can not have + any polymorphic arguments. The arguments of the top-level can not be + polymorphic as the function is never applied and consequently there is no + way to determine the actual types for the type parameters. + + With regard to the built-in types, it should be noted that members of + some of the standard Haskell type classes are supported as built-in + functions. These include: the numerial operators of \hs{Num}, the equality + operators of \hs{Eq}, and the comparison/order operators of \hs{Ord}. + + \subsection{Higher-order functions \& values} Another powerful abstraction mechanism in functional languages, is - the concept of \emph{higher order functions}, or \emph{functions as - a first class value}. This allows a function to be treated as a + the concept of \emph{functions as a first class value}, also called + \emph{higher-order functions}. This allows a function to be treated as a value and be passed around, even as the argument of another - function. Let's clarify that with an example: + function. The following example should clarify this concept: + \hspace{-1.7em} + \begin{minipage}{0.93\linewidth} + %format not = "\mathit{not}" \begin{code} - notList xs = map not xs + negateVector xs = map not xs \end{code} - - This defines a function \hs{notList}, with a single list of booleans - \hs{xs} as an argument, which simply negates all of the booleans in - the list. To do this, it uses the function \hs{map}, which takes - \emph{another function} as its first argument and applies that other - function to each element in the list, returning again a list of the - results. - - As you can see, the \hs{map} function is a higher order function, - since it takes another function as an argument. Also note that - \hs{map} is again a polymorphic function: It does not pose any - constraints on the type of elements in the list passed, other than - that it must be the same as the type of the argument the passed - function accepts. The type of elements in the resulting list is of - course equal to the return type of the function passed (which need - not be the same as the type of elements in the input list). Both of - these can be readily seen from the type of \hs{map}: + \end{minipage} + \begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code6} + \end{example} + \end{minipage} + + The code above defines the \hs{negateVector} function, which takes a + vector of booleans, \hs{xs}, and returns a vector where all the values are + negated. It achieves this by calling the \hs{map} function, and passing it + \emph{another function}, boolean negation, and the vector of booleans, + \hs{xs}. The \hs{map} function applies the negation function to all the + elements in the vector. + + The \hs{map} function is called a higher-order function, since it takes + another function as an argument. Also note that \hs{map} is again a + parametric polymorphic function: it does not pose any constraints on the + type of the input vector, other than that its elements must have the same + type as the first argument of the function passed to \hs{map}. The element + type of the resulting vector is equal to the return type of the function + passed, which need not necessarily be the same as the element type of the + input vector. All of these characteristics can readily be inferred from + the type signature belonging to \hs{map}: \begin{code} - map :: (a -> b) -> [a] -> [b] + map :: (a -> b) -> [a|n] -> [b|n] \end{code} - - As an example from a common hardware design, let's look at the - equation of a FIR filter. - \begin{equation} - y_t = \sum\nolimits_{i = 0}^{n - 1} {x_{t - i} \cdot h_i } - \end{equation} - - A FIR filter multiplies fixed constants ($h$) with the current and - a few previous input samples ($x$). Each of these multiplications - are summed, to produce the result at time $t$. - - This is easily and directly implemented using higher order - functions. 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. How \hs{xs} gets its value will be - show in the next section about state. - - \begin{code} - fir ... = foldl1 (+) (zipwith (*) xs hs) - \end{code} - - Here, the \hs{zipwith} function is very similar to the \hs{map} - function: It takes a function two lists and then applies the - function to each of the elements of the two lists pairwise - (\emph{e.g.}, \hs{zipwith (+) [1, 2] [3, 4]} becomes - \hs{[1 + 3, 2 + 4]}. - - The \hs{foldl1} function takes a function and a single list and applies the - function to the first two elements of the list. It then applies to - function to the result of the first application and the next element - from the list. This continues until the end of the list 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 just pairwise - multiplication and the \hs{foldl1 (+)} function is just summation. - - To make the correspondence between the code and the equation even - more obvious, we turn the list of input samples in the equation - around. So, instead of having the the input sample received at time - $t$ 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 better suits - the \hs{x} from the code): - - \begin{equation} - y_t = \sum\nolimits_{i = 0}^{n - 1} {x_i \cdot h_i } - \end{equation} - - So far, only functions have been used as higher order values. In + So far, only functions have been used as higher-order values. In Haskell, there are two more ways to obtain a function-typed value: partial application and lambda abstraction. Partial application means that a function that takes multiple arguments can be applied @@ -900,36 +1060,51 @@ data IntPair = IntPair Int Int that takes one argument less). As an example, consider the following expression, that adds one to every element of a vector: + \hspace{-1.7em} + \begin{minipage}{0.93\linewidth} \begin{code} - map ((+) 1) xs + map (add 1) xs \end{code} - - 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 labmda expression allows one to introduce an anonymous function - in any expression. Consider the following expression, which again - adds one to every element of a list: - + \end{minipage} + \begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code7} + \end{example} + \end{minipage} + + Here, the expression \hs{(add 1)} is the partial application of the + addition function to the value \hs{1}, which is again a function that + 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: + + \hspace{-1.7em} + \begin{minipage}{0.93\linewidth} \begin{code} map (\x -> x + 1) xs \end{code} - - Finally, higher order arguments are not limited to just builtin - functions, but any function defined in \CLaSH can have function - arguments. This allows the hardware designer to use a powerful - abstraction mechanism in his designs and have an optimal amount of - code reuse. - - TODO: Describe ALU example (no code) + \end{minipage} + \begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code8} + \end{example} + \end{minipage} + + Finally, not only built-in functions can have higher order arguments (such + as the \hs{map} function), but any function defined in \CLaSH\ may have + functions as arguments. This allows the circuit designer to use a + powerful amount of code reuse. The only exception is again the top-level + function: if a function-typed argument is not applied with an actual + function, no hardware can be generated. + + % \comment{TODO: Describe ALU example (no code)} \subsection{State} - A very important concept in hardware it the concept of state. In a + A very important concept in hardware is the concept of state. In a stateful design, the outputs depend on the history of the inputs, or the state. State is usually stored in registers, which retain their value during a clock cycle. As we want to describe more than simple - combinatorial designs, \CLaSH\ needs an abstraction mechanism for state. + combinational 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 @@ -937,81 +1112,430 @@ data IntPair = IntPair Int Int \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. + \item that the function has no 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. + % 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 combinational circuits, + 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 \CLaSH\ we deal with the concept of state in pure functions by making + the current state an additional argument of the function, and the + updated state part of result. In this sense the descriptions made in + \CLaSH\ are the combinational parts of a mealy machine. - A simple example is the description of an accumulator circuit: + A simple example is adding an accumulator register to the earlier + multiply-accumulate circuit, of which the resulting netlist can be seen in + \Cref{img:mac-state}: + + \hspace{-1.7em} + \begin{minipage}{0.93\linewidth} \begin{code} - acc :: Word -> State Word -> (State Word, Word) - acc inp (State s) = (State s', outp) + macS (State c) a b = (State c', c') where - outp = s + inp - s' = outp + c' = mac a b c \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} + \end{minipage} + \begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code9} + \end{example} + \end{minipage} + + \begin{figure} + \centerline{\includegraphics{mac-state.svg}} + \caption{Stateful Multiply-Accumulate} + \label{img:mac-state} + \vspace{-1.5em} + \end{figure} + + Note that the \hs{macS} function returns both the new state and the value + of the output port. The \hs{State} keyword indicates which arguments are + part of the current state, and what part of the output is part of the + updated state. This aspect will also be reflected in the type signature of + the function. Abstracting the state of a circuit in this way makes it 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 elements, as state values are just normal values. We can simulate + stateful descriptions using the recursive \hs{run} function: + + \hspace{-1.7em} + \begin{minipage}{0.93\linewidth} + \begin{code} + run f s (i : inps) = o : (run f s' inps) + where + (s', o) = f s i + \end{code} + \end{minipage} + \begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code10} + \end{example} + \end{minipage} + + The \hs{(:)} operator is the list concatenation operator, where the + left-hand side is the head of a list and the right-hand side is the + remainder of the list. The \hs{run} function applies the function the + developer wants to simulate, \hs{f}, to the current state, \hs{s}, and the + first input value, \hs{i}. The result is the first output value, \hs{o}, + and the updated state \hs{s'}. The next iteration of the \hs{run} function + is then called with the updated state, \hs{s'}, and the rest of the + inputs, \hs{inps}. For the time being, and in the context of this paper, + it is assumed that there is one input per clock cycle. Also note how the + order of the input, output, and state in the \hs{run} function corresponds + with the order of the input, output and state of the \hs{macS} function + described earlier. + + As the \hs{run} function, the hardware description, and the test + inputs are also valid Haskell, the complete simulation can be compiled to + an executable binary by an optimizing Haskell compiler, or executed in an + Haskell interpreter. Both simulation paths are much faster than first + translating the description to \VHDL\ and then running a \VHDL\ + simulation. + +\section{The \CLaSH\ compiler} +An important aspect in this research is the creation of the prototype +compiler, which allows us to translate descriptions made in the \CLaSH\ +language as described in the previous section to synthesizable \VHDL. +% , allowing a designer to actually run a \CLaSH\ design on an \acro{FPGA}. + +The Glasgow Haskell Compiler (\GHC)~\cite{ghc} is an open-source Haskell +compiler that also provides a high level API to most of its internals. The +availability of this high-level API obviated the need to design many of the +tedious parts of the prototype compiler, such as the parser, semantics +checker, and especially the type-checker. These parts together form the +front-end of the prototype compiler pipeline, as seen in +\Cref{img:compilerpipeline}. -foo\par bar +\begin{figure} +\centerline{\includegraphics{compilerpipeline.svg}} +\caption{\CLaSHtiny\ compiler pipeline} +\label{img:compilerpipeline} +\vspace{-1.5em} +\end{figure} + +The output of the \GHC\ front-end consists of the translation of the original +Haskell description in \emph{Core}~\cite{Sulzmann2007}, which is a smaller, +typed, functional language. This \emph{Core} language is relatively easy to +process compared to the larger Haskell language. A description in \emph{Core} +can still contain elements 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 elements 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 and lambda +calculus~\cite{lambdacalculus}, such as $\beta$-reduction and +$\eta$-expansion. It also includes self-defined transformations that are +responsible for the reduction of higher-order functions to `regular' +first-order functions, and specializing polymorphic types to concrete types. + +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} +\label{sec:usecases} +\subsection{FIR Filter} +As an example of a common hardware design where the use of higher-order +functions leads to a very natural description is a \acro{FIR} filter, which is +basically the dot-product of two vectors: + +\begin{equation} +y_t = \sum\nolimits_{i = 0}^{n - 1} {x_{t - i} \cdot h_i } +\end{equation} + +A \acro{FIR} filter multiplies fixed constants ($h$) with the current +and a few previous input samples ($x$). Each of these multiplications +are summed, to produce the result at time $t$. The equation of a \acro{FIR} +filter is indeed equivalent to the equation of the dot-product, which is +shown below: + +\begin{equation} +\mathbf{a}\bullet\mathbf{b} = \sum\nolimits_{i = 0}^{n - 1} {a_i \cdot b_i } +\end{equation} + +We can easily and directly implement the equation for the dot-product +using higher-order functions: + +\hspace{-1.7em} +\begin{minipage}{0.93\linewidth} +\begin{code} +as *+* bs = foldl1 (+) (zipWith (*) as bs) +\end{code} +\end{minipage} +\begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code13} + \end{example} +\end{minipage} + +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]}). + +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 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 pairwise multiplication and that the +\hs{foldl1 (+)} function is summation. +% Returning to the actual \acro{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} +The complete definition of the \acro{FIR} filter in code then becomes: + +\hspace{-1.7em} +\begin{minipage}{0.93\linewidth} +\begin{code} +fir (State (xs,hs)) x = + (State (x >> xs,hs), (x +> xs) *+* hs) +\end{code} +\end{minipage} +\begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code14} + \end{example} +\end{minipage} + +Where the vector \hs{xs} contains the previous input samples, the vector +\hs{hs} contains the \acro{FIR} coefficients, and \hs{x} is the current input +sample. The concatenate operator (\hs{+>}) creates a new vector by placing the +current sample (\hs{x}) in front of the previous samples vector (\hs{xs}). 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: + +\hspace{-1.7em} +\begin{minipage}{0.93\linewidth} +\begin{code} +x >> xs = x +> init xs +\end{code} +\end{minipage} +\begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code15} + \end{example} +\end{minipage} + +Where the \hs{init} function returns all but the last element of a vector. +The resulting netlist of a 4-taps \acro{FIR} filter, created by specializing +the vectors of the \acro{FIR} code to a length of 4, is depicted in +\Cref{img:4tapfir}. + +\begin{figure} +\centerline{\includegraphics{4tapfir.svg}} +\caption{4-taps \acrotiny{FIR} Filter} +\label{img:4tapfir} +\vspace{-1.5em} +\end{figure} + +\subsection{Higher-order CPU} +The following simple \acro{CPU} is an example of user-defined higher order +functions and pattern matching. The \acro{CPU} consists of four function +units, of which three have a fixed function and one can perform certain less +common operations. + +The \acro{CPU} contains a number of data sources, represented by the +horizontal wires in \Cref{img:highordcpu}. These data sources offer the +previous outputs of each function units, along with the single data input the +\acro{CPU} has and two fixed initialization values. + +Each of the function units has both its operands connected to all data +sources, and can be programmed to select any data source for either +operand. In addition, the leftmost function unit has an additional +opcode input to select the operation it performs. The output of the rightmost +function unit is also the output of the entire \acro{CPU}. + +Looking at the code, the function unit (\hs{fu}) is the most simple. It +arranges the operand selection for the function unit. Note that it does not +define the actual operation that takes place inside the function unit, +but simply accepts the (higher-order) argument \hs{op} which is a function +of two arguments that defines the operation. + +\hspace{-1.7em} +\begin{minipage}{0.93\linewidth} +\begin{code} +fu op inputs (addr1, addr2) = regIn + where + in1 = inputs!addr1 + in2 = inputs!addr2 + regIn = op in1 in2 +\end{code} +\end{minipage} +\begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code16} + \end{example} +\end{minipage} + +The \hs{multiop} function defines the operation that takes place in the +leftmost function unit. It is essentially a simple three operation \acro{ALU} +that makes good use of pattern matching and guards in its description. +The \hs{shift} function used here shifts its first operand by the number +of bits indicated in the second operand, the \hs{xor} function produces +the bitwise xor of its operands. + +\hspace{-1.7em} +\begin{minipage}{0.93\linewidth} +\begin{code} +data Opcode = Shift | Xor | Equal + +multiop :: Opcode -> Word -> Word -> Word +multiop Shift a b = shift a b +multiop Xor a b = xor a b +multiop Equal a b | a == b = 1 + | otherwise = 0 +\end{code} +\end{minipage} +\begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code17} + \end{example} +\end{minipage} + +The \acro{CPU} function ties everything together. It applies the \hs{fu} +function four times, to create a different function unit each time. The +first application is interesting, because it does not just pass a +function to \hs{fu}, but a partial application of \hs{multiop}. This +shows how the first function unit effectively gets an extra input, +compared to the others. + +The vector \hs{inputs} is the set of data sources, which is passed to +each function unit as a set of possible operants. The \acro{CPU} also receives +a vector of address pairs, which are used by each function unit to select +their operand. The application of the function units to the \hs{inputs} and +\hs{addrs} arguments seems quite repetitive and could be rewritten to use +a combination of the \hs{map} and \hs{zipwith} functions instead. +However, the prototype compiler does not currently support working with lists +of functions, so a more explicit version of the code is given instead. + +\hspace{-1.7em} +\begin{minipage}{0.93\linewidth} +\begin{code} +type CpuState = State [Word | 4] + +cpu :: CpuState -> Word -> [(Index 6, Index 6) | 4] + -> Opcode -> (CpuState, Word) +cpu (State s) input addrs opc = (State s', out) + where + s' = [ fu (multiop opc) inputs (addrs!0) + , fu add inputs (addrs!1) + , fu sub inputs (addrs!2) + , fu mul inputs (addrs!3) + ] + inputs = 0 +> (1 +> (input +> s)) + out = head s' +\end{code} +\end{minipage} +\begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code18} + \end{example} +\end{minipage} + +This is still a simple example, but it could form the basis +of an actual design, in which the same techniques can be reused. \section{Related work} -Many functional hardware description languages have been developed over the -years. Early work includes such languages as $\mu$\acro{FP}~\cite{muFP}, an -extension of Backus' \acro{FP} language to synchronous streams, designed -particularly for describing and reasoning about regular circuits. The -Ruby~\cite{Ruby} language uses relations, instead of functions, to describe -circuits, and has a particular focus on layout. \acro{HML}~\cite{HML2} is a -hardware modeling language based on the strict functional language -\acro{ML}, and has support for polymorphic types and higher-order functions. -Published work suggests that there is no direct simulation support for -\acro{HML}, and that the translation to \VHDL\ is only partial. - -Like this work, many functional hardware description languages have some sort -of foundation in the functional programming language Haskell. -Hawk~\cite{Hawk1} uses Haskell to describe system-level executable -specifications used to model the behavior of superscalar microprocessors. Hawk -specifications can be simulated, but there seems to be no support for -automated circuit synthesis. The ForSyDe~\cite{ForSyDe2} system uses Haskell -to specify abstract system models, which can (manually) be transformed into an -implementation model using semantic preserving transformations. ForSyDe has -several simulation and synthesis backends, though synthesis is restricted to -the synchronous subset of the ForSyDe language. - -Lava~\cite{Lava} is a hardware description language that focuses on the -structural representation of hardware. Besides support for simulation and -circuit synthesis, Lava descriptions can be interfaced with formal method -tools for formal verification. Lava descriptions are actually circuit -generators when viewed from a synthesis viewpoint, in that the language -elements of Haskell, such as choice, can be used to guide the circuit -generation. If a developer wants to insert a choice element inside an actual -circuit he will have to specify this explicitly as a component. In this -respect \CLaSH\ differs from Lava, in that all the choice elements, such as -case-statements and pattern matching, are synthesized to choice elements in the -eventual circuit. As such, richer control structures can both be specified and -synthesized in \CLaSH\ compared to any of the languages mentioned in this -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 -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 -\CLaSH. +This section describes the features of existing (functional) hardware +description languages and highlights the advantages that this research has +over existing work. + +% Many functional hardware description languages have been developed over the +% years. Early work includes such languages as $\mu$\acro{FP}~\cite{muFP}, an +% extension of Backus' \acro{FP} language to synchronous streams, designed +% particularly for describing and reasoning about regular circuits. The +% Ruby~\cite{Ruby} language uses relations, instead of functions, to describe +% circuits, and has a particular focus on layout. + +\acro{HML}~\cite{HML2} is a hardware modeling language based on the strict +functional language \acro{ML}, and has support for polymorphic types and +higher-order functions. Published work suggests that there is no direct +simulation support for \acro{HML}, but that a description in \acro{HML} has to +be translated to \VHDL\ and that the translated description can then be +simulated in a \VHDL\ simulator. Certain aspects of HML, such as higher-order +functions are however not supported by the \VHDL\ translator~\cite{HML3}. The +\CLaSH\ compiler on the other hand can correctly translate all of the language +constructs mentioned in this paper. % to a netlist format. + +\begin{figure} +\centerline{\includegraphics{highordcpu.svg}} +\caption{CPU with higher-order Function Units} +\label{img:highordcpu} +\vspace{-1.5em} +\end{figure} + +Like the research presented in this paper, many functional hardware +description languages have some sort of foundation in the functional +programming language Haskell. Hawk~\cite{Hawk1} uses Haskell to describe +system-level executable specifications used to model the behavior of +superscalar microprocessors. Hawk specifications can be simulated; to the best +knowledge of the authors there is however no support for automated circuit +synthesis. + +The ForSyDe~\cite{ForSyDe2} system uses Haskell to specify abstract system +models. A designer can model systems using heterogeneous models of +computation, which include continuous time, synchronous and untimed models of +computation. Using so-called domain interfaces a designer can simulate +electronic systems which have both analog as digital parts. ForSyDe has +several backends including simulation and automated synthesis, though +automated synthesis is restricted to the synchronous model of computation. +Though ForSyDe offers higher-order functions and polymorphism, ForSyDe's +choice elements are limited to \hs{if} and \hs{case} expressions. ForSyDe's +explicit conversions, where function have to be wrapped in processes and +processes have to be wrapped in systems, combined with the explicit +instantiations of components, also makes ForSyDe more verbose than \CLaSH. + +Lava~\cite{Lava} is a hardware description language, embedded in Haskell, and +focuses on the structural representation of hardware. Like \CLaSH, Lava has +support for polymorphic types and higher-order functions. Besides support for +simulation and circuit synthesis, Lava descriptions can be interfaced with +formal method tools for formal verification. As discussed in the introduction, +taking the embedded language approach does not allow for Haskell's choice +elements to be captured within the circuit descriptions. In this respect +\CLaSH\ differs from Lava, in that all of Haskell's choice elements, such as +\hs{case}-expressions and pattern matching, are synthesized to choice elements +in the eventual circuit. Consequently, descriptions containing rich control +structures can be specified in a more user-friendly way in \CLaSH\ than possible within Lava, and are hence less error-prone. + +Bluespec~\cite{Bluespec} is a high-level synthesis language that features +guarded atomic transactions and allows for the automated derivation of control +structures based on these atomic transactions. Bluespec, like \CLaSH, supports +polymorphic typing and function-valued arguments. Bluespec's syntax and +language features \emph{had} their basis in Haskell. However, in order to +appeal to the users of the traditional \acrop{HDL}, Bluespec has adapted +imperative features and a syntax that resembles Verilog. As a result, Bluespec +is (unnecessarily) verbose when compared to \CLaSH. + +The merits of polymorphic typing and function-valued arguments are now also +recognized in the traditional \acrop{HDL}, exemplified by the new \VHDL-2008 +standard~\cite{VHDL2008}. \VHDL-2008 support for generics has been extended to +types and subprograms, allowing a designer to describe components with +polymorphic ports and function-valued arguments. Note that the types and +subprograms still require an explicit generic map, whereas types can be +automatically inferred, and function-values can be automatically propagated +by the \CLaSH\ compiler. There are also no (generally available) \VHDL\ +synthesis tools that currently support the \VHDL-2008 standard. % Wired~\cite{Wired},, T-Ruby~\cite{T-Ruby}, Hydra~\cite{Hydra}. % @@ -1104,29 +1628,53 @@ generic map, whereas type-inference and type-specialization are implicit in \section{Conclusion} -The conclusion goes here. - - - +This research demonstrates once more that functional languages are well suited +for hardware descriptions: function applications provide an elegant notation +for component instantiation. Where this research goes beyond the existing +(functional) hardware descriptions languages is the inclusion of various +choice elements, such as pattern matching, that are well suited to describe +the conditional assignments in control-oriented circuits. Besides being able +to translate these basic constructs to synthesizable \VHDL, the prototype +compiler can also correctly translate descriptions that contain both +polymorphic types and function-valued arguments. + +Where recent functional hardware description languages have mostly opted to +embed themselves in an existing functional language, this research features a +`true' compiler. As a result there is a clear distinction between compile-time +and run-time, which allows a myriad of choice constructs to be part of the +actual circuit description; a feature the embedded hardware description +languages do not offer. + +\section{Future Work} +The choice of describing state explicitly as extra arguments and results can +be seen as a mixed blessing. Even though the description that use state are +usually very clear, one finds that dealing with unpacking, passing, receiving +and repacking can become tedious and even error-prone, especially in the case +of sub-states. Removing this boilerplate, or finding a more suitable +abstraction mechanism would make \CLaSH\ easier to use. + +The transformations in normalization phase of the prototype compiler were +developed in an ad-hoc manner, which makes the existence of many desirable +properties unclear. Such properties include whether the complete set of +transformations will always lead to a normal form or if the normalization +process always terminates. Though various use cases suggests that these +properties usually hold, they have not been formally proven. A systematic +approach to defining the set of transformations allows one to proof that the +earlier mentioned properties do indeed exist. % conference papers do not normally have an appendix % use section* for acknowledgement -\section*{Acknowledgment} - - -The authors would like to thank... - - - - +% \section*{Acknowledgment} +% +% The authors would like to thank... % trigger a \newpage just before the given reference % number - used to balance the columns on the last page % adjust value as needed - may need to be readjusted if % the document is modified later -%\IEEEtriggeratref{8} +% \IEEEtriggeratref{14} % The "triggered" command can be changed if desired: %\IEEEtriggercmd{\enlargethispage{-5in}} @@ -1139,7 +1687,7 @@ The authors would like to thank... % http://www.michaelshell.org/tex/ieeetran/bibtex/ \bibliographystyle{IEEEtran} % argument is your BibTeX string definitions and bibliography database(s) -\bibliography{IEEEabrv,clash.bib} +\bibliography{clash} % % manually copy in the resultant .bbl file % set second argument of \begin to the number of references