- As noted above, any component of a function's state that is a substate,
- \eg passed on as the state of another function, should have no influence
- on the hardware generated for the calling function. Any state-specific
- \small{VHDL} for this component can be generated entirely within the called
- function. So,we can completely leave out substates from any function.
-
- From this observation, we might think to remove the substates from a
- function's states alltogether, and leave only the state components which
- are actual states of the current function. While doing this would not
- remove any information needed to generate \small{VHDL} from the function, it would
- cause the function definition to become invalid (since we won't have any
- substate to pass to the functions anymore). We could solve the syntactic
- problems by passing \type{undefined} for state variables, but that would
- still break the code on the semantic level (\ie, the function would no
- longer be semantically equivalent to the original input).
-
- To keep the function definition correct until the very end of the process,
- we will not deal with (sub)states until we get to the \small{VHDL} generation.
- Here, we are translating from Core to \small{VHDL}, and we can simply not generate
- \small{VHDL} for substates, effectively removing the substate components
- alltogether.
-
- There are a few important points when ignore substates.
-
- First, we have to have some definition of "substate". Since any state
- argument or return value that represents state must be of the \type{State}
- type, we can simply look at its type. However, we must be careful to
- ignore only {\em substates}, and not a function's own state.
-
- In the example above, this means we should remove \type{accums'} from
- \type{s'}, but not throw away \type{s'} entirely. We should, however,
- remove \type{s'} from the output port of the function, since the state
- will be handled by a \small{VHDL} procedure within the function.
-
- When looking at substates, these can appear in two places: As part of an
- argument and as part of a return value. As noted above, these substates
- can only be used in very specific ways.
-
- \desc{State variables can appear as an argument.} When generating \small{VHDL}, we
- completely ignore the argument and generate no input port for it.
-
- \desc{State variables can be extracted from other state variables.} When
- extracting a state variable from another state variable, this always means
- we're extracting a substate, which we can ignore. So, we simply generate no
- \small{VHDL} for any extraction operation that has a state variable as a result.
-
- \desc{State variables can be passed to functions.} When passing a
- state variable to a function, this always means we're passing a substate
- to a subcomponent. The entire argument can simply be ingored in the
- resulting port map.
-
- \desc{State variables can be returned from functions.} When returning a
- state variable from a function (probably as a part of an algebraic
- datatype), this always mean we're returning a substate from a
- subcomponent. The entire state variable should be ignored in the resulting
- port map. The type binder of the binder that the function call is bound
- to should not include the state type either.
-
- \startdesc{State variables can be inserted into other variables.} When inserting
- a state variable into another variable (usually by constructing that new
- variable using its constructor), we can identify two cases:
+ 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.