Update piece about state to show relation between the run function and the statefull...

[matthijs/master-project/dsd-paper.git] / cλash.lhs

diff --git a/cλash.lhs b/cλash.lhs
index 998e6a6896adbfb0fe7381a1ea3cc0271250bfcd..85709be26568b10604138c111cd659cca186f2b9 100644 (file)
--- a/cλash.lhs
+++ b/cλash.lhs
@@ -950,7 +950,7 @@ circuit~\cite{reductioncircuit} for floating point numbers.
     expression, that adds one to every element of a vector:
 
     \begin{code}
     expression, that adds one to every element of a vector:
 
     \begin{code}

-    map ((+) 1) xs
+    map (+ 1) xs

     \end{code}
 
     Here, the expression \hs{(+) 1} is the partial application of the
     \end{code}
 
     Here, the expression \hs{(+) 1} is the partial application of the


@@ -974,7 +974,7 @@ circuit~\cite{reductioncircuit} for floating point numbers.
     % \comment{TODO: Describe ALU example (no code)}
 
   \subsection{State}
     % \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 
     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 


@@ -992,26 +992,24 @@ circuit~\cite{reductioncircuit} for floating point numbers.
     % 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. 
     % 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 combinatorial 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. 
     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 
+    current value of the state an additional argument of the function and the 
+    updated state part of result. In this sense the descriptions made in 
+    \CLaSH\ are the combinatorial 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}:
     
     \begin{code}
     
     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}:
     
     \begin{code}

-    macS (State c) a b = (State c', outp)
+    macS (State c) a b = (State c', c')

       where
       where

-        outp  = mac a b c
-        c'    = outp
+        c' = mac a b c

     \end{code}
     
     \begin{figure}
     \end{code}
     
     \begin{figure}


@@ -1022,7 +1020,7 @@ circuit~\cite{reductioncircuit} for floating point numbers.
     
     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 
     
     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. 
+    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 
     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 


@@ -1031,20 +1029,32 @@ circuit~\cite{reductioncircuit} for floating point numbers.
     stateful descriptions using the recursive \hs{run} function:
     
     \begin{code}
     stateful descriptions using the recursive \hs{run} function:
     
     \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}
     
       where
         (s', o) = f s i
     \end{code}
     

-    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}. 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}
+    As both the \hs{run} function, the hardware description, and the test 
+    inputs are plain 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, where the executable binary has an additional simulation speed 
+    bonus in case there is a large set of test inputs.
+    
+\section{\CLaSH\ compiler}

 
 The \CLaSH\ language as presented above can be translated to \VHDL\ using
 the prototype \CLaSH\ compiler. This compiler allows experimentation with
 
 The \CLaSH\ language as presented above can be translated to \VHDL\ using
 the prototype \CLaSH\ compiler. This compiler allows experimentation with


@@ -1061,7 +1071,7 @@ 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 
 \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, 
+produces the program in the \emph{Core}~\cite{Sulzmann2007} 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
 functional, typed language which is relatively easy to process.
 
 The second step in the compilation process is \emph{normalization}. This


@@ -1152,6 +1162,44 @@ is depicted in \Cref{img:4tapfir}.
 \label{img:4tapfir}
 \end{figure}
 
 \label{img:4tapfir}
 \end{figure}
 

+
+\subsection{Higher order CPU}
+
+
+\begin{code}
+type FuState = State Word
+fu :: (a -> a -> a)
+      -> [a]:n
+      -> (RangedWord n, RangedWord n)
+      -> FuState
+      -> (FuState, a)
+fu op inputs (addr1, addr2) (State out) =
+  (State out', out)
+  where
+    in1  = inputs!addr1
+    in2  = inputs!addr2
+    out' = op in1 in2
+\end{code}
+
+\begin{code}
+type CpuState = State [FuState]:4
+cpu :: Word 
+       -> [(RangedWord 7, RangedWord 7)]:4
+       -> CpuState
+       -> (CpuState, Word)
+cpu input addrs (State fuss) =
+  (State fuss', out)
+  where
+    fures = [ fu const inputs!0 fuss!0
+            , fu (+)   inputs!1 fuss!1
+            , fu (-)   inputs!2 fuss!2
+            , fu (*)   inputs!3 fuss!3
+            ]
+    (fuss', outputs) = unzip fures
+    inputs = 0 +> 1 +> input +> outputs
+    out = head outputs
+\end{code}
+

 \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 
 \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