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.
- An example of a simple program using only function application would be:
-
- \starthaskell
- -- | A simple function that returns the and of three bits
- and3 :: Bit -> Bit -> Bit -> Bit
- and3 a b c = and (and a b) c
- \stophaskell
-
- This results in the following hardware:
-
- TODO: Pretty picture
+ \in{Example}[ex:And3] shows a simple program using only function
+ application and the corresponding architecture.
+
+\startbuffer[And3]
+-- | A simple function that returns
+-- the and of three bits
+and3 :: Bit -> Bit -> Bit -> Bit
+and3 a b c = and (and a b) c
+\stopbuffer
+
+ \startuseMPgraphic{And3}
+ save a, b, c, anda, andb, out;
+
+ % I/O ports
+ newCircle.a(btex $a$ etex) "framed(false)";
+ newCircle.b(btex $b$ etex) "framed(false)";
+ newCircle.c(btex $c$ etex) "framed(false)";
+ newCircle.out(btex $out$ etex) "framed(false)";
+
+ % Components
+ newCircle.anda(btex $and$ etex);
+ newCircle.andb(btex $and$ etex);
+
+ a.c = origin;
+ b.c = a.c + (0cm, 1cm);
+ c.c = b.c + (0cm, 1cm);
+ anda.c = midpoint(a.c, b.c) + (2cm, 0cm);
+ andb.c = midpoint(b.c, c.c) + (4cm, 0cm);
+
+ out.c = andb.c + (2cm, 0cm);
+
+ % Draw objects and lines
+ drawObj(a, b, c, anda, andb, out);
+
+ ncarc(a)(anda) "arcangle(-10)";
+ ncarc(b)(anda);
+ ncarc(anda)(andb);
+ ncarc(c)(andb);
+ ncline(andb)(out);
+ \stopuseMPgraphic
+
+ \placeexample[here][ex:And3]{Simple three port and.}
+ \startcombination[2*1]
+ {\typebufferhs{And3}}{Haskell description using function applications.}
+ {\boxedgraphic{And3}}{The architecture described by the Haskell description.}
+ \stopcombination
\subsection{Partial application}
It should be obvious that we cannot generate hardware signals for all
represented as a signal or i/o port to a component.
From this, we can see that the above translation rules do not apply to a
- partial application. Let's look at an example:
-
- \starthaskell
- -- | Multiply the input word by four.
- quadruple :: Word -> Word
- quadruple n = mul (mul n)
- where
- mul = (*) 2
- \stophaskell
-
- It should be clear that the above code describes the following hardware:
-
- TODO: Pretty picture
+ partial application. \in{Example}[ex:Quadruple] shows an example use of
+ partial application and the corresponding architecture.
+
+\startbuffer[Quadruple]
+-- | Multiply the input word by four.
+quadruple :: Word -> Word
+quadruple n = mul (mul n)
+ where
+ mul = (*) 2
+\stopbuffer
+
+ \startuseMPgraphic{Quadruple}
+ save in, two, mula, mulb, out;
+
+ % I/O ports
+ newCircle.in(btex $n$ etex) "framed(false)";
+ newCircle.two(btex $2$ etex) "framed(false)";
+ newCircle.out(btex $out$ etex) "framed(false)";
+
+ % Components
+ newCircle.mula(btex $\times$ etex);
+ newCircle.mulb(btex $\times$ etex);
+
+ two.c = origin;
+ in.c = two.c + (0cm, 1cm);
+ mula.c = in.c + (2cm, 0cm);
+ mulb.c = mula.c + (2cm, 0cm);
+ out.c = mulb.c + (2cm, 0cm);
+
+ % Draw objects and lines
+ drawObj(in, two, mula, mulb, out);
+
+ nccurve(two)(mula) "angleA(0)", "angleB(45)";
+ nccurve(two)(mulb) "angleA(0)", "angleB(45)";
+ ncline(in)(mula);
+ ncline(mula)(mulb);
+ ncline(mulb)(out);
+ \stopuseMPgraphic
+
+ \placeexample[here][ex:Quadruple]{Simple three port and.}
+ \startcombination[2*1]
+ {\typebufferhs{Quadruple}}{Haskell description using function applications.}
+ {\boxedgraphic{Quadruple}}{The architecture described by the Haskell description.}
+ \stopcombination
Here, the definition of mul is a partial function application: It applies
\hs{2 :: Word} to the function \hs{(*) :: Word -> Word -> Word} resulting in
completely applied.
\section{State}
- \subsection{Introduction}
- Provide some examples
-
+ A very important concept in hardware designs is \emph{state}. In a
+ stateless (or, \emph{combinatoric}) design, every output is a directly and solely dependent on the
+ inputs. In a stateful design, the outputs can depend on the history of
+ inputs, or the \emph{state}. State is usually stored in \emph{registers},
+ which retain their value during a clockcycle, and are typically updated at
+ the start of every clockcycle. Since the updating of the state is tightly
+ coupled (synchronized) to the clock signal, these state updates are often
+ called \emph{synchronous}.
+
+ To make our hardware description language useful to describe more that
+ simple combinatoric designs, we'll need to be able to describe state in
+ some way.
\subsection{Approaches to state}
- Explain impact of state (or rather, temporal behaviour) on function signature.
+ In Haskell, functions are always pure (except when using unsafe
+ functions like \hs{unsafePerformIO}, which should be prevented whenever
+ possible). This means that the output of a function solely depends on
+ its inputs. If you evaluate a given function with given inputs, it will
+ always provide the same output.
+
+ TODO: Define pure
+
+ This is a perfect match for a combinatoric circuit, where the output
+ also soley depend on the inputs. However, when state is involved, this
+ no longer holds. Since we're in charge of our own language, we could
+ remove this purity constraint and allow a function to return different
+ values depending on the cycle in which it is evaluated (or rather, the
+ current state). However, this means that all kinds of interesting
+ properties of our functional language get lost, and all kinds of
+ transformations and optimizations might no longer be meaning preserving.
+
+ Provided that we want to keep the function pure, the current state has
+ to be present in the function's arguments in some way. There seem to be
+ two obvious ways to do this: Adding the current state as an argument, or
+ including the full history of each argument.
+
\subsubsection{Stream arguments and results}
+ Including the entire history of each input (\eg, the value of that
+ input for each previous clockcycle) is an obvious way to make outputs
+ depend on all previous input. This is easily done by making every
+ input a list instead of a single value, containing all previous values
+ as well as the current value.
+
+ An obvious downside of this solution is that on each cycle, all the
+ previous cycles must be resimulated to obtain the current state. To do
+ this, it might be needed to have a recursive helper function as well,
+ wich might be hard to properly analyze by the compiler.
+
+ A slight variation on this approach is one taken by some of the other
+ functional \small{HDL}s in the field (TODO: References to Lava,
+ ForSyDe, ...): Make functions operate on complete streams. This means
+ that a function is no longer called on every cycle, but just once. It
+ takes stream as inputs instead of values, where each stream contains
+ all the values for every clockcycle since system start. This is easily
+ modeled using an (infinite) list, with one element for each clock
+ cycle. Since the funciton is only evaluated once, its output is also a
+ stream. Note that, since we are working with infinite lists and still
+ want to be able to simulate the system cycle-by-cycle, this relies
+ heavily on the lazy semantics of Haskell.
+
+ Since our inputs and outputs are streams, all other (intermediate)
+ values must be streams. All of our primitive operators (\eg, addition,
+ substraction, bitwise operations, etc.) must operate on streams as
+ well (note that changing a single-element operation to a stream
+ operation can done with \hs{map}, \hs{zipwith}, etc.).
+
+ Note that the concept of \emph{state} is no more than having some way
+ to communicate a value from one cycle to the next. By introducing a
+ \hs{delay} function, we can do exactly that: Delay (each value in) a
+ stream so that we can "look into" the past. This \hs{delay} function
+ simply outputs a stream where each value is the same as the input
+ value, but shifted one cycle. This causes a \quote{gap} at the
+ beginning of the stream: What is the value of the delay output in the
+ first cycle? For this, the \hs{delay} function has a second input
+ (which is a value, not a stream!).
+
+ \in{Example}[ex:DelayAcc] shows a simple accumulator expressed in this
+ style.
+
+\startbuffer[DelayAcc]
+acc :: Stream Word -> Stream Word
+acc in = out
+ where
+ out = (delay out 0) + in
+\stopbuffer
+
+\startuseMPgraphic{DelayAcc}
+ save in, out, add, reg;
+
+ % I/O ports
+ newCircle.in(btex $in$ etex) "framed(false)";
+ newCircle.out(btex $out$ etex) "framed(false)";
+
+ % Components
+ newReg.reg("") "dx(4mm)", "dy(6mm)", "reflect(true)";
+ newCircle.add(btex + etex);
+
+ in.c = origin;
+ add.c = in.c + (2cm, 0cm);
+ out.c = add.c + (2cm, 0cm);
+ reg.c = add.c + (0cm, 2cm);
+
+ % Draw objects and lines
+ drawObj(in, out, add, reg);
+
+ nccurve(add)(reg) "angleA(0)", "angleB(180)", "posB(d)";
+ nccurve(reg)(add) "angleA(180)", "angleB(-45)", "posA(out)";
+ ncline(in)(add);
+ ncline(add)(out);
+\stopuseMPgraphic
+
+
+ \placeexample[here][ex:DelayAcc]{Simple accumulator architecture.}
+ \startcombination[2*1]
+ {\typebufferhs{DelayAcc}}{Haskell description using streams.}
+ {\boxedgraphic{DelayAcc}}{The architecture described by the Haskell description.}
+ \stopcombination
+
+
+ This notation can be confusing (especially due to the loop in the
+ definition of out), but is essentially easy to interpret. There is a
+ single call to delay, resulting in a circuit with a single register,
+ whose input is connected to \hs{outl (which is the output of the
+ adder)}, and it's output is the \hs{delay out 0} (which is connected
+ to one of the adder inputs).
+
+ This notation has a number of downsides, amongst which are limited
+ readability and ambiguity in the interpretation. TODO: Reference
+ Christiaan.
+
\subsubsection{Explicit state arguments and results}
- Nested state for called functions.
+ A more explicit way to model state, is to simply add an extra argument
+ containing the current state value. This allows an output to depend on
+ both the inputs as well as the current state while keeping the
+ function pure (letting the result depend only on the arguments), since
+ the current state is now an argument.
+
+ In Haskell, this would look like \in{example}[ex:ExplicitAcc].
+
+\startbuffer[ExplicitAcc]
+acc :: Word -> (State Word) -> (State Word, Word)
+acc in (State s) = (State s', out)
+ where
+ out = s + in
+ s' = out
+\stopbuffer
+
+ \placeexample[here][ex:ExplicitAcc]{Simple accumulator architecture.}
+ \startcombination[2*1]
+ {\typebufferhs{ExplicitAcc}}{Haskell description using explicit state arguments.}
+ % Picture is identical to the one we had just now.
+ {\boxedgraphic{DelayAcc}}{The architecture described by the Haskell description.}
+ \stopcombination
+
+ This approach makes a function's state very explicit, which state
+ variables are used by a function can be completely determined from its
+ type signature (as opposed to the stream approach, where a function
+ looks the same from the outside, regardless of what state variables it
+ uses (or wether it's stateful at all).
+
+ A direct consequence of this, is that if a function calls other
+ stateful functions (\eg, has subcircuits), it has to somehow know the
+ current state for these called functions. The only way to do this, is
+ to put these \emph{substates} inside the caller's state. This means
+ that a function's state is the sum of the states of all functions it
+ calls, and its own state.
+
+ This approach is the one chosen for Cλash and will be examined more
+ closely below.
\subsection{Explicit state specification}
Note about semantic correctness of top level state.
Implementation issues: state splitting, linking input to output state,
checking usage constraints on state variables.
- \section{Recursion}
+
+ \section[sec:recursion]{Recursion}
An import concept in functional languages is recursion. In it's most basic
form, recursion is a function that is defined in terms of itself. This
usually requires multiple evaluations of this function, with changing
projects / matthijs / master-project / report.git / blobdiff