%
\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,
% 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}}
%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
% 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}
+\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, j.kuper@@utwente.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\\
% make the title area
\maketitle
-
\begin{abstract}
%\boldmath
\CLaSH\ is a functional hardware description language that borrows both its
-syntax and semantics from the functional programming language Haskell. Circuit
-descriptions can be translated to synthesizable VHDL using the prototype
-\CLaSH\ compiler. As the circuit descriptions are made in plain Haskell,
-simulations can also be compiled by a Haskell compiler.
-
-The use of polymorphism and higher-order functions allow a circuit designer to
-describe more abstract and general specifications than are possible in the
-traditional hardware description languages.
+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,
% creates the second title. It will be ignored for other modes.
\IEEEpeerreviewmaketitle
-
\section{Introduction}
-Hardware description languages have 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 combinatorial circuits can be directly
-modeled as 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 then be processed further 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 language. As far as the authors know, such
-extensive support for choice-elements is new in the domain of functional
-hardware description languages. As the hardware descriptions are plain Haskell
-functions, these descriptions can be compiled for simulation using an
-optimizing Haskell compiler such as the Glasgow Haskell Compiler (\GHC)~\cite{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. A developer describes the behavior of the hardware between
-clock cycles. Many functional hardware description 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 of a
-circuit part of the input of the function and the updated state part of the
-output. The current abstraction of state and time limits the descriptions to
-synchronous hardware, there however is room within the language to eventually
+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 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, 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 FIR filter and the
-simple CPU shown in \Cref{sec:usecases}, the \CLaSH\ compiler has also been
-shown to work for non-trivial descriptions. \CLaSH\ has been able to
-successfully translate the functional description of a streaming reduction
-circuit~\cite{reductioncircuit} for floating point numbers.
+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
+ 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}
and
\item function applications are translated to component instantiations.
\end{inparaenum}
- The output port can have a structured type (such as a tuple), so having
- just a single output port does not pose any limitation. The 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,% aswell,
- 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.
-
- As an example we can see the netlist of the |mac| function in
- \Cref{img:mac-comb}; the |mac| function applies both the |mul| and |add|
- function to calculate $a * b + c$:
+ 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{Combinatorial Multiply-Accumulate}
+ \caption{Combinational Multiply-Accumulate}
\label{img:mac-comb}
+ \vspace{-1.5em}
\end{figure}
- The result of using a structural input type can be seen in
- \cref{img:mac-comb-nocurry} where the |mac| function now uses a single
- input tuple for the |a|, |b|, and |c| arguments:
+ 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) = add (mul a b) c
+ 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{Combinatorial Multiply-Accumulate (complex input)}
- \label{img:mac-comb-nocurry}
+ \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 language constructs,
- consisting of: \hs{case} constructs, \hs{if-then-else} constructs,
+ 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}
- constructs (\hs{if} expressions can be very directly translated to
- \hs{case} expressions). A \hs{case} construct is translated to a
- multiplexer, where the control value is linked to the selection port and
- the output of each case is linked to the corresponding input port on the
- multiplexer.
+ 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.
- We can see two versions of a contrived example below, the first
- using a \hs{case} construct and the other using an \hs{if-then-else}
- construct, in the code below. The examples sums two values when they are
- equal or non-equal (depending on the given predicate, the \hs{pred}
- variable) and returns 0 otherwise. The \hs{pred} variable has the
- following, user-defined, enumeration datatype:
+ 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}
- data Pred = Equiv | NotEquiv
+ data Pred = Equal | NotEqual
\end{code}
The naive netlist corresponding to both versions of the example is
- depicted in \Cref{img:choice}.
+ 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
- Equiv -> case a == b of
+ Equal -> case a == b of
True -> a + b
False -> 0
- NotEquiv -> case a != b of
+ NotEqual -> case a != b of
True -> a + b
False -> 0
\end{code}
-
+ \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 == Eq then
+ 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 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} constructs, pattern matching and guards have a
- (straightforward) translation to \hs{case} constructs and can as such be
- mapped to multiplexers. A third version of the earlier example, using both
- pattern matching and guards, can be seen below. The guard is the
- expression that follows the vertical bar (\hs{|}) and precedes the
+ 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}.
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 Eq a b | a == b = a + b
- | otherwise = 0
- sumif Neq a b | a != b = a + b
- | otherwise = 0
+ 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}}
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
- therefor only deal with the types that do have a clear correspondence
+ 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 direct translation is defined within the \CLaSH\
- compiler; the term user-defined types should not require any further
- elaboration. The translatable types are also inferable by the compiler,
+ 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.
+ 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
% using translation rules that are discussed later on.
\subsubsection{Built-in types}
- The following types have direct translations defined within the \CLaSH\
+ The following types have fixed translations defined within the \CLaSH\
compiler:
\begin{xlist}
\item[\bf{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} construct, which requires a \hs{Bool} value for
+ \hs{if-then-else} expression, which requires a \hs{Bool} value for
the condition.
- \item[\bf{SizedWord}, \bf{SizedInt}]
- these are types to represent integers. A \hs{SizedWord} is unsigned,
- while a \hs{SizedInt} is signed. Both are parametrizable in their
- size.
+ \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}
% \texttt{signed} respectively.
\item[\bf{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
+ 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 short-hand notation used for the vector type in
- the rest of paper is: \hs{[a|n]}. Where the \hs{a} is the element
- type, and \hs{n} is the length of the vector.
+ 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:
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.
An \hs{Index} only has an upper bound, its lower bound is
- implicitly zero. The main purpose of the \hs{Index} type is to be
- used as an index to a \hs{Vector}.
+ 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:
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 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.
+ % \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. Type synonyms and type renaming only define new
names for existing types, where synonyms are completely interchangeable
- and type renaming requires explicit conversions. Therefore, these 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:
-
+ 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. Haskell's built-in tuple types are also defined
- as single constructor algebraic types An example of a single
- constructor type is the following pair of integers:
+ 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}
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 that there a fixed translation for
- that type within the \CLaSH\ compiler. An example of such an
+ 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}
supported.
\end{xlist}
- \subsection{Polymorphism}
+ \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
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:
+ 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.}
\begin{code}
append :: [a|n] -> a -> [a|n + 1]
variable can only be instantiated to a type whose members supports the
overloaded functions associated with the type class.
- As an example we will take a look at type signature of the function
- \hs{sum}, which sums the values in a vector:
+ 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}
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}, so that
- we know 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 on \hs{SizedWords} as
- well as on \hs{SizedInts}.
-
- In \CLaSH, parametric 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 however one constraint: the top level
- function that is being translated can not have any polymorphic arguments.
- The arguments can not be polymorphic as they are never applied and
- consequently there is no way to determine the actual types for the type
- parameters.
-
- \CLaSH\ does not support user-defined type classes, but does use some
- of the standard Haskell type classes for its built-in function, such as:
- \hs{Num} for numerical operations, \hs{Eq} for the equality operators, and
- \hs{Ord} for the comparison/order operators.
+ 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. The following example should clarify this concept:
+ \hspace{-1.7em}
+ \begin{minipage}{0.93\linewidth}
+ %format not = "\mathit{not}"
\begin{code}
- negVector xs = map not xs
+ negateVector xs = map not xs
\end{code}
-
- The code above defines a function \hs{negVector}, which takes a vector of
- booleans, and returns a vector where all the values are negated. It
- achieves this by calling the \hs{map} function, and passing it
+ \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 vector elements, other than that it must be the same type as
- the input type 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}:
+ 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|n] -> [b|n]
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 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:
-
+ \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 built-in
- 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.
-
- \comment{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
\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 or a combinatorial circuit,
- where the output solely depends on the inputs. When a circuit has state
+ 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 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. In this sense the
- descriptions made in \CLaSH are the describing the combinatorial parts of
- a mealy machine.
+ 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 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}
- macS (State c) a b = (State c', outp)
+ macS (State c) a b = (State c', c')
where
- outp = mac a b c
- c' = outp
+ c' = mac a b c
\end{code}
+ \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}
- 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 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
+ 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 constructs, as state values are just normal values. We can simulate
+ 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)
+ 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{run} function maps a list of inputs over the function that a
- developer wants to simulate, passing the state to each new iteration. Each
- value in the input list corresponds to exactly one cycle of the (implicit)
- clock. The result of the simulation is a list of outputs for every clock
- cycle. As both the \hs{run} function and the hardware description are
- plain Haskell, the complete simulation can be compiled by an optimizing
- Haskell compiler.
+ 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.
-\section{\CLaSH\ prototype}
-
-The \CLaSH\ language as presented above can be translated to \VHDL\ using
-the prototype \CLaSH\ compiler. This compiler allows experimentation with
-the \CLaSH\ language and allows for running \CLaSH\ designs on actual FPGA
-hardware.
+ 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}.
\begin{figure}
\centerline{\includegraphics{compilerpipeline.svg}}
\caption{\CLaSHtiny\ compiler pipeline}
\label{img:compilerpipeline}
+\vspace{-1.5em}
\end{figure}
-The prototype heavily uses \GHC, the Glasgow Haskell Compiler.
-\Cref{img:compilerpipeline} shows the \CLaSH\ compiler pipeline. As you can
-see, the front-end is completely reused from \GHC, which allows the \CLaSH\
-prototype to support most of the Haskell Language. The \GHC\ front-end
-produces the program in the \emph{Core} format, which is a very small,
-functional, typed language which is relatively easy to process.
-
-The second step in the compilation process is \emph{normalization}. This
-step runs a number of \emph{meaning preserving} transformations on the
-Core program, to bring it into a \emph{normal form}. This normal form
-has a number of restrictions that make the program similar to hardware.
-In particular, a program in normal form no longer has any polymorphism
-or higher order functions.
-
-The final step is a simple translation to \VHDL.
+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 FIR filter, which is
+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 FIR filter multiplies fixed constants ($h$) with the current
+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 FIR
+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{x}\bullet\mathbf{y} = \sum\nolimits_{i = 0}^{n - 1} {x_i \cdot y_i }
+\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}
-xs *+* ys = foldl1 (+) (zipWith (*) xs hs)
+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]} $\equiv$ \hs{[3,8]}).
+[1, 2] [3, 4]} becomes \hs{[1 * 3, 2 * 4]}).
-The \hs{foldl1} function takes a function, a single vector, and applies
+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 from
-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.
-As you can see, the \hs{zipWith (*)} function is just pairwise
-multiplication and the \hs{foldl1 (+)} function is just summation.
-
-Returning to the actual FIR filter, we will slightly change the
-equation belong to it, so as to make the translation to code more obvious.
-What we will do is change the definition of the vector of input samples.
-So, instead of having the input sample received at time
-$t$ stored 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 will better suit
-the transformation to code):
-
-\begin{equation}
-y_t = \sum\nolimits_{i = 0}^{n - 1} {x_i \cdot h_i }
-\end{equation}
-
-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. The function that shifts the input samples is shown below:
+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}
-x >> xs = x +> tail xs
+fir (State (xs,hs)) x =
+ (State (x >> xs,hs), (x +> xs) *+* hs)
\end{code}
-
-Where the \hs{tail} function returns all but the first element of a
-vector, and the concatenate operator ($\succ$) adds a new element to the
-left of a vector. The complete definition of the FIR filter then becomes:
-
+\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}
-fir (State (xs,hs)) x = (State (x >> xs,hs), xs *+* hs)
+x >> xs = x +> init xs
\end{code}
-
-The resulting netlist of a 4-taps FIR filter based on the above definition
-is depicted in \Cref{img:4tapfir}.
+\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.
+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 than be
-simulated in a \VHDL\ simulator. Also not all of the mentioned language
-features of \acro{HML} could be translated to hardware. The \CLaSH\ compiler
-on the other hand can correctly translate all of the language constructs
-mentioned in this paper to a netlist format.
-
-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.
+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, which can (manually) be transformed into an implementation model using
-semantic preserving transformations. 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 within ForSyDe. Unlike \CLaSH\ there is no
-support for the automated synthesis of descriptions that contain polymorphism
-or higher-order functions.
-
-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 explicitly instantiate a multiplexer-like 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 support for generics has been extended to types, allowing a developer to describe
-polymorphic components. Note that those types still require an explicit
-generic map, whereas types can be automatically inferred in \CLaSH.
+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}.
%
\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}}
projects / matthijs / master-project / dsd-paper.git / blobdiff