+ Using this set of types, all types in basic Haskell can be represented.
+ \todo{Overview of polymorphism with more examples (or move examples
+ here)}
+
+ \section[sec:prototype:statetype]{State annotations in Haskell}
+ As noted in \in{section}[sec:description:stateann], Cλash needs some
+ way to let the programmer explicitly specify which of a function's
+ arguments and which part of a function's result represent the
+ function's state.
+
+ Using the Haskell type systems, there are a few ways we can tackle this.
+
+ \subsection{Type synonyms}
+ Haskell provides type synonyms as a way to declare a new type that is
+ equal to an existing type (or rather, a new name for an existing type).
+ This allows both the original type and the synonym to be used
+ interchangedly in a Haskell program. This means no explicit conversion
+ is needed. For example, a simple accumulator would become:
+
+ \starthaskell
+ -- This type synonym would become part of Cλash, it is shown here
+ -- just for clarity.
+ type State s = s
+
+ acc :: Word -> State Word -> (State Word, Word)
+ acc i s = let sum = s + i in (sum, sum)
+ \stophaskell
+
+ This looks nice in Haskell, but turns out to be hard to implement. There
+ is no explicit conversion in Haskell, but not in Core either. This
+ means the type of a value might be shown as \hs{State Word} in
+ some places, but \hs{Word} in others (and this can even change due
+ to transformations). Since every binder has an explicit type
+ associated with it, the type of every function type will be
+ properly preserved and could be used to track down the
+ statefulness of each value by the compiler. However, this would make
+ the implementation a lot more complicated than when using type
+ renamings as described in the next section.
+
+ % Use \type instead of \hs here, since the latter breaks inside
+ % section headings.
+ \subsection{Type renaming (\type{newtype})}
+ Haskell also supports type renamings as a way to declare a new type that
+ has the same (runtime) representation as an existing type (but is in
+ fact a different type to the typechecker). With type renaming,
+ explicit conversion between values of the two types is needed. The
+ accumulator would then become:
+
+ \starthaskell
+ -- This type renaming would become part of Cλash, it is shown here
+ -- just for clarity.
+ newtype State s = State s
+
+ acc :: Word -> State Word -> (State Word, Word)
+ acc i (State s) = let sum = s + i in (State sum, sum)
+ \stophaskell
+
+ The \hs{newtype} line declares a new type \hs{State} that has one type
+ argument, \hs{s}. This type contains one \quote{constructor} \hs{State}
+ with a single argument of type \hs{s}. It is customary to name the
+ constructor the same as the type, which is allowed (since types can
+ never cause name collisions with values). The difference with the type
+ synonym example is in the explicit conversion between the \hs{State
+ Word} and \hs{Word} types by pattern matching and by using the explicit
+ the \hs{State} constructor.
+
+ This explicit conversion makes the \VHDL\ generation easier: whenever we
+ remove (unpack) the \hs{State} type, this means we are accessing the
+ current state (\ie, accessing the register output). Whenever we are
+ adding (packing) the \hs{State} type, we are producing a new value for
+ the state (\ie, providing the register input).
+
+ When dealing with nested states (a stateful function that calls stateful
+ functions, which might call stateful functions, etc.) the state type
+ could quickly grow complex because of all the \hs{State} type constructors
+ needed. For example, consider the following state type (this is just the
+ state type, not the entire function type):
+
+ \starthaskell
+ State (State Bit, State (State Word, Bit), Word)
+ \stophaskell
+
+ We cannot leave all these \hs{State} type constructors out, since that
+ would change the type (unlike when using type synonyms). However, when
+ using type synonyms to hide away substates (see
+ \in{section}[sec:prototype:substatesynonyms] below), this
+ disadvantage should be limited.
+
+ \subsubsection{Different input and output types}
+ An alternative could be to use different types for input and output
+ state (\ie\ current and updated state). The accumulator example would
+ then become something like:
+
+ \starthaskell
+ -- These type renaminges would become part of Cλash, it is shown
+ -- here just for clarity.
+ newtype StateIn s = StateIn s
+ newtype StateOut s = StateOut s
+
+ acc :: Word -> StateIn Word -> (StateIn Word, Word)
+ acc i (StateIn s) = let sum = s + i in (StateIn sum, sum)
+ \stophaskell
+
+ This could make the implementation easier and the hardware
+ descriptions less error-prone (you can no longer \quote{forget} to
+ unpack and repack a state variable and just return it directly, which
+ can be a problem in the current prototype). However, it also means we
+ need twice as many type synonyms to hide away substates, making this
+ approach a bit cumbersome. It also makes it harder to compare input
+ and output state types, possible reducing the type-safety of the
+ descriptions.
+
+ \subsection[sec:prototype:substatesynonyms]{Type synonyms for substates}
+ As noted above, when using nested (hierarchical) states, the state types
+ of the \quote{upper} functions (those that call other functions, which
+ call other functions, etc.) quickly become complicated. Also, when the
+ state type of one of the \quote{lower} functions changes, the state
+ types of all the upper functions changes as well. If the state type for
+ each function is explicitly and completely specified, this means that a
+ lot of code needs updating whenever a state type changes.
+
+ To prevent this, it is recommended (but not enforced) to use a type
+ synonym for the state type of every function. Every function calling
+ other functions will then use the state type synonym of the called
+ functions in its own type, requiring no code changes when the state type
+ of a called function changes. This approach is used in
+ \in{example}[ex:AvgState] below. The \hs{AccState} and \hs{AvgState}
+ are examples of such state type synonyms.
+
+ \subsection{Chosen approach}
+ To keep implementation simple, the current prototype uses the type
+ renaming approach, with a single type for both input and output
+ states. In the future, it might be worthwhile to revisit this
+ approach if more complicated flow analysis is implemented for
+ state variables. This analysis is needed to add proper error
+ checking anyway and might allow the use of type synonyms without
+ losing any expressivity.