From: Christiaan Baaij Date: Wed, 27 Jan 2010 15:32:56 +0000 (+0100) Subject: Merge branch 'master' of http://git.stderr.nl/matthijs/projects/cλash-paper X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Fdsd-paper.git;a=commitdiff_plain;h=38a92f9980362c4e99f1d3143dbc8dbcc84be766;hp=65710eed8d14ac473d4a2dacc32d5daa85f1b6db Merge branch 'master' of git.stderr.nl/matthijs/projects/cλash-paper * 'master' of http://git.stderr.nl/matthijs/projects/cλash-paper: Fix typos in related work. Make the sumif example fit in a column. Improve / shorten the section on types. Conflicts: cλash.lhs --- diff --git a/clash.fmt b/clash.fmt new file mode 100644 index 0000000..7521af2 --- /dev/null +++ b/clash.fmt @@ -0,0 +1 @@ +%format != = "\neq" \ No newline at end of file diff --git "a/c\316\273ash.lhs" "b/c\316\273ash.lhs" index b646e76..5efc961 100644 --- "a/c\316\273ash.lhs" +++ "b/c\316\273ash.lhs" @@ -343,9 +343,10 @@ % Macro for certain acronyms in small caps. Doesn't work with the % default font, though (it contains no smallcaps it seems). -\def\VHDL{{\small{VHDL}}} -\def\GHC{{\small{GHC}}} -\def\CLaSH{\textsc{C$\lambda$aSH}} +\def\acro#1{{\small{#1}}} +\def\VHDL{\acro{VHDL}} +\def\GHC{\acro{GHC}} +\def\CLaSH{{\small{C}}$\lambda$a{\small{SH}}} % Macro for pretty printing haskell snippets. Just monospaced for now, perhaps % we'll get something more complex later on. @@ -366,13 +367,16 @@ } {\end{list}} +\usepackage{paralist} + %include polycode.fmt +%include clash.fmt \begin{document} % % paper title % can use linebreaks \\ within to get better formatting as desired -\title{\CLaSH: Structural Descriptions \\ of Synchronous Hardware using Haskell} +\title{C$\lambda$aSH: Structural Descriptions \\ of Synchronous Hardware using Haskell} % author names and affiliations @@ -381,7 +385,7 @@ \author{\IEEEauthorblockN{Christiaan P.R. Baaij, Matthijs Kooijman, Jan Kuper, Marco E.T. Gerards, Bert Molenkamp, Sabih H. Gerez} \IEEEauthorblockA{University of Twente, Department of EEMCS\\ P.O. Box 217, 7500 AE, Enschede, The Netherlands\\ -c.p.r.baaij@utwente.nl, matthijs@stdin.nl}} +c.p.r.baaij@@utwente.nl, matthijs@@stdin.nl}} % \and % \IEEEauthorblockN{Homer Simpson} % \IEEEauthorblockA{Twentieth Century Fox\\ @@ -469,12 +473,29 @@ level, a great number of approaches based on functional languages has been proposed \cite{T-Ruby,Hydra,HML2,Hawk1,Lava,ForSyDe1,Wired,reFLect}. The idea of using functional languages started in the early 1980s \cite{Cardelli1981, muFP,DAISY,FHDL}, a time which also saw the birth of the currently popular -hardware description languages such as \VHDL. +hardware description languages such as \VHDL. What gives functional languages +as hardware description languages their merits is the fact that basic +combinatorial circuits are equivalent to mathematical function, and that +functional languages lend themselves very well to describe and compose these +mathematical functions. + +In an attempt to decrease the amount of work involved with creating all the +required tooling, such as parsers and type-checkers, many functional hardware +description languages are embedded as a domain specific language inside the +functional language Haskell \cite{Hydra,Hawk1,Lava,ForSyDe1,Wired}. What this +means is that a developer is given a library of Haskell functions and types +that together form the language primitives of the domain specific language. +Using these functions, the designer does not only describes a circuit, but +actually builds a large domain-specific datatype which can be further +processed by an embedded compiler. This compiler actually runs in the same +environment as the description; as a result compile-time and run-time become +hard to define, as the embedded compiler is usually compiled by the same +Haskell compiler as the circuit description itself. + +The approach taken in this research is not to make another domain specific +language embedded in Haskell, but to use (a subset) of the Haskell language +itself to be used as hardware description language. -What gives functional languages as hardware description languages their merits -is the fact that basic combinatorial circuits are equivalent to mathematical -function, and that functional languages lend themselves very well to describe -and compose these mathematical functions. \section{Hardware description in Haskell} \subsection{Function application} @@ -507,7 +528,7 @@ mac a b c = add (mul a b) c TODO: Pretty picture - \subsection{Choices } + \subsection{Choices} Although describing components and connections allows describing a lot of hardware designs already, there is an obvious thing missing: choice. We need some way to be able to choose between values based @@ -537,28 +558,24 @@ mac a b c = add (mul a b) c expression, one using only case expressions and one using pattern matching and guards. -\begin{verbatim} -sumif cmp a b = if cmp == Eq && a == b - || cmp == Neq && a != b - then a + b - else 0 -\end{verbatim} - -\begin{verbatim} -sumif cmp a b = case cmp of - Eq -> case a == b of - True -> a + b - False -> 0 - Neq -> case a != b of - True -> a + b - False -> 0 -\end{verbatim} - -\begin{verbatim} -sumif Eq a b | a == b = a + b -sumif Neq a b | a != b = a + b -sumif _ _ _ = 0 -\end{verbatim} +\begin{code} +sumif pred a b = if pred == Eq && a == b + || pred == Neq && a != b + then a + b + else 0 + +sumif pred a b = case pred of + Eq -> case a == b of + True -> a + b + False -> 0 + Neq -> case a != b of + True -> a + b + False -> 0 + +sumif Eq a b | a == b = a + b +sumif Neq a b | a != b = a + b +sumif _ _ _ = 0 +\end{code} TODO: Pretty picture @@ -708,24 +725,63 @@ data IntPair = IntPair Int Int Algebraic datatypes with multiple constructors, where at least one of these constructors has one or more fields are not currently supported. - \end{xlist} - + \end{xlist} + \subsection{State} + A very important concept in hardware it the concept of state. In a + stateful design, the outputs depend on the history of the inputs, or the + 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. + + An important property in Haskell, and in most other functional languages, + is \emph{purity}. A function is said to be \emph{pure} if it satisfies two + conditions: + \begin{inparaenum} + \item given the same arguments twice, it should return the same value in + both cases, and + \item when the function is called, it should not have observable + side-effects. + \end{inparaenum} + This purity property is important for functional languages, since it + enables all kinds of mathematical reasoning that could not be guaranteed + correct for impure functions. Pure functions are as such a perfect match + for a combinatorial circuit, where the output solely depends on the + inputs. When a circuit has state however, it can no longer be simply + described by a pure function. Simply removing the purity property is not a + valid option, as the language would then lose many of it mathematical + properties. In an effort to include the concept of state in pure + functions, the current value of the state is made an argument of the + function; the updated state becomes part of the result. + + A simple example is the description of an accumulator circuit: + \begin{code} + acc :: Word -> State Word -> (State Word, Word) + acc inp (State s) = (State s', outp) + where + outp = s + inp + s' = outp + \end{code} + This approach makes the state of a function very explicit: which variables + are part of the state is completely determined by the type signature. This + approach to state is well suited to be used in combination with the + existing code and language features, such as all the choice constructs, as + state values are just normal values. \section{\CLaSH\ prototype} foo\par bar \section{Related work} Many functional hardware description languages have been developed over the -years. Early work includes such languages as \textsc{$\mu$fp}~\cite{muFP}, an -extension of Backus' \textsc{fp} language to synchronous streams, designed +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. \textsc{hml}~\cite{HML2} is a +circuits, and has a particular focus on layout. \acro{HML}~\cite{HML2} is a hardware modeling language based on the strict functional language -\textsc{ml}, and has support for polymorphic types and higher-order functions. +\acro{ML}, and has support for polymorphic types and higher-order functions. Published work suggests that there is no direct simulation support for -\textsc{hml}, and that the translation to \VHDL\ is only partial. +\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. @@ -760,11 +816,11 @@ polymorphic components. Note that those types still require an explicit generic map, whereas type-inference and type-specialization are implicit in \CLaSH. -Wired~\cite{Wired},, T-Ruby~\cite{T-Ruby}, Hydra~\cite{Hydra}. - -A functional language designed specifically for hardware design is -$re{\mathit{FL}}^{ect}$~\cite{reFLect}, which draws experience from earlier -language called \textsc{fl}~\cite{FL} to la +% Wired~\cite{Wired},, T-Ruby~\cite{T-Ruby}, Hydra~\cite{Hydra}. +% +% A functional language designed specifically for hardware design is +% $re{\mathit{FL}}^{ect}$~\cite{reFLect}, which draws experience from earlier +% language called \acro{FL}~\cite{FL} to la % An example of a floating figure using the graphicx package. % Note that \label must occur AFTER (or within) \caption.