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:
+ \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
- \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
+ \startuseMPgraphic{And3}
+ save a, b, c, anda, andb, out;
- This results in the following hardware:
-
- TODO: Pretty picture
+ % 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
+
+ TODO: Define top level function and subfunctions/circuits.
\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:
+ partial application. \in{Example}[ex:Quadruple] shows an example use of
+ partial application and the corresponding architecture.
- \starthaskell
- -- | Multiply the input word by four.
- quadruple :: Word -> Word
- quadruple n = mul (mul n)
- where
- mul = (*) 2
- \stophaskell
+\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);
- It should be clear that the above code describes the following hardware:
+ nccurve(two)(mula) "angleA(0)", "angleB(45)";
+ nccurve(two)(mulb) "angleA(0)", "angleB(45)";
+ ncline(in)(mula);
+ ncline(mula)(mulb);
+ ncline(mulb)(out);
+ \stopuseMPgraphic
- TODO: Pretty picture
+ \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
In Haskell, this would look like \in{example}[ex:ExplicitAcc].
\startbuffer[ExplicitAcc]
-acc :: Word -> (State Word) -> (State Word, Word)
+-- input -> current state -> (new state, output)
+acc :: Word -> Word -> (Word, Word)
acc in (State s) = (State s', out)
where
out = s + in
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.
-
- Note about automatic ``down-pushing'' of state.
-
- Note about explicit state specification as the best solution.
-
- Note about substates
-
- Note about conditions on state variables and checking them.
+ We've seen the concept of explicit state in a simple example below, but
+ what are the implications of this approach?
+
+ \subsubsection{Substates}
+ Since a function's state is reflected directly in its type signature,
+ 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 also means that the type of a function (at least the "state"
+ part) is dependent on its implementation and the functions it calls.
+ This is the major downside of this approach: The separation between
+ interface and implementation is limited. However, since Cλash is not
+ very suitable for separate compilation (see
+ \in{section}[sec:prototype:separate]) this is not a big problem in
+ practice. Additionally, when using a type synonym for the state type
+ of each function, we can still provide explicit type signatures
+ while keeping the state specification for a function near its
+ definition only.
+
+ \subsubsection{...}
+ We need some way to know which arguments should become input ports and
+ which argument(s?) should become the current state (\eg, be bound to
+ the register outputs). This does not hold holds not just for the top
+ level function, but also for any subfunctions. Or could we perhaps
+ deduce the statefulness of subfunctions by analyzing the flow of data
+ in the calling functions?
+
+ To explore this matter, we make an interesting observation: We get
+ completely correct behaviour when we put all state registers in the
+ top level entity (or even outside of it). All of the state arguments
+ and results on subfunctions are treated as normal input and output
+ ports. Effectively, a stateful function results in a stateless
+ hardware component that has one of its input ports connected to the
+ output of a register and one of its output ports connected to the
+ input of the same register.
+
+ TODO: Example?
+
+ Of course, even though the hardware described like this has the
+ correct behaviour, unless the layout tool does smart optimizations,
+ there will be a lot of extra wire in the design (since registers will
+ not be close to the component that uses them). Also, when working with
+ the generated \small{VHDL} code, there will be a lot of extra ports
+ just to pass one state values, which can get quite confusing.
+
+ To fix this, we can simply \quote{push} the registers down into the
+ subcircuits. When we see a register that is connected directly to a
+ subcircuit, we remove the corresponding input and output port and put
+ the register inside the subcircuit instead. This is slightly less
+ trivial when looking at the Haskell code instead of the resulting
+ circuit, but the idea is still the same.
+
+ TODO: Example?
+
+ However, when applying this technique, we might push registers down
+ too far. When you intend to store a result of a stateless subfunction
+ in the caller's state and pass the current value of that state
+ variable to that same function, the register might get pushed down too
+ far. It is impossible to distinguish this case from similar code where
+ the called function is in fact stateful. From this we can conclude
+ that we have to either:
+
+ \startitemize
+ \item accept that the generated hardware might not be exactly what we
+ intended, in some specific cases. In most cases, the hardware will be
+ what we intended.
+ \item explicitely annotate state arguments and results in the input
+ description.
+ \stopitemize
+
+ The first option causes (non-obvious) exceptions in the language
+ intepretation. Also, automatically determining where registers should
+ end up is easier to implement correctly with explicit annotations, so
+ for these reasons we will look at how this annotations could work.
+
+
+ TODO: Note about conditions on state variables and checking them.
\subsection{Explicit state implementation}
Recording state variables at the type level.
projects / matthijs / master-project / report.git / blobdiff