Chapters/State.tex

   1 \chapter[chap:state]{State}
   2   \section{Introduction}
   3     Provide some examples
   4
   5
   6   \section{Approaches to state}
   7     Explain impact of state (or rather, temporal behaviour) on function signature.
   8     \subsection{Stream arguments and results}
   9     \subsection{Explicit state arguments and results}
  10       Nested state for called functions.
  11
  12   \section{Explicit state specification}
  13     Note about semantic correctness of top level state.
  14
  15     Note about automatic ``down-pushing'' of state.
  16
  17     Note about explicit state specification as the best solution.
  18
  19     Note about substates
  20
  21     Note about conditions on state variables and checking them.
  22
  23   \section{Explicit state implementation}
  24     Recording state variables at the type level.
  25
  26     Ideal: Type synonyms, since there is no additional code overhead for
  27     packing and unpacking. Downside: there is no explicit conversion in Core
  28     either, so type synonyms tend to get lost in expressions (they can be
  29     preserved in binders, but this makes implementation harder, since that
  30     statefulness of a value must be manually tracked).
  31
  32     Less ideal: Newtype. Requires explicit packing and unpacking of function
  33     arguments. If you don't unpack substates, there is no overhead for
  34     (un)packing substates. This will result in many nested State constructors
  35     in a nested state type. \eg:
  36
  37 \starttyping
  38 State (State Bit, State (State Word, Bit), Word)
  39 \stoptyping
  40
  41     Alternative: Provide different newtypes for input and output state. This
  42     makes the code even more explicit, and typechecking can find even more
  43     errors. However, this requires defining two type synomyms for each
  44     stateful function instead of just one. \eg:
  45 \starttyping
  46 type AccumStateIn = StateIn Bit
  47 type AccumStateOut = StateOut Bit
  48 \stoptyping
  49     This also increases the possibility of having different input and output
  50     states. Checking for identical input and output state types is also
  51     harder, since each element in the state must be unpacked and compared
  52     separately.
  53
  54     Alternative: Provide a type for the entire result type of a stateful
  55     function, not just the state part. \eg:
  56
  57 \starttyping
  58 newtype Result state result = Result (state, result)
  59 \stoptyping
  60
  61     This makes it easy to say "Any stateful function must return a
  62     \type{Result} type, without having to sort out result from state. However,
  63     this either requires a second type for input state (similar to
  64     \type{StateIn} / \type{StateOut} above), or requires the compiler to
  65     select the right argument for input state by looking at types (which works
  66     for complex states, but when that state has the same type as an argument,
  67     things get ambiguous) or by selecting a fixed (\eg, the last) argument,
  68     which might be limiting.
  69
  70     \subsection{Example}
  71     As an example of the used approach, a simple averaging circuit, that lets
  72     the accumulation of the inputs be done by a subcomponent.
  73
  74     \starttyping
  75       newtype State s = State s
  76
  77       type AccumState = State Bit
  78       accum :: Word -> AccumState -> (AccumState, Word)
  79       accum i (State s) = (State (s + i), s + i)
  80
  81       type AvgState = (AccumState, Word)
  82       avg :: Word -> AvgState -> (AvgState, Word)
  83       avg i (State s) = (State s', o)
  84         where
  85           (accums, count) = s
  86           -- Pass our input through the accumulator, which outputs a sum
  87           (accums', sum) = accum i accums
  88           -- Increment the count (which will be our new state)
  89           count' = count + 1
  90           -- Compute the average
  91           o = sum / count'
  92           s' = (accums', count')
  93     \stoptyping
  94
  95     And the normalized, core-like versions:
  96
  97     \starttyping
  98       accum i spacked = res
  99         where
 100           s = case spacked of (State s) -> s
 101           s' = s + i
 102           spacked' = State s'
 103           o = s + i
 104           res = (spacked', o)
 105
 106       avg i spacked = res
 107         where
 108           s = case spacked of (State s) -> s
 109           accums = case s of (accums, \_) -> accums
 110           count = case s of (\_, count) -> count
 111           accumres = accum i accums
 112           accums' = case accumres of (accums', \_) -> accums'
 113           sum = case accumres of (\_, sum) -> sum
 114           count' = count + 1
 115           o = sum / count'
 116           s' = (accums', count')
 117           spacked' = State s'
 118           res = (spacked', o)
 119     \stoptyping
 120
 121
 122
 123     As noted above, any component of a function's state that is a substate,
 124     \eg passed on as the state of another function, should have no influence
 125     on the hardware generated for the calling function. Any state-specific
 126     \small{VHDL} for this component can be generated entirely within the called
 127     function. So,we can completely leave out substates from any function.
 128
 129     From this observation, we might think to remove the substates from a
 130     function's states alltogether, and leave only the state components which
 131     are actual states of the current function. While doing this would not
 132     remove any information needed to generate \small{VHDL} from the function, it would
 133     cause the function definition to become invalid (since we won't have any
 134     substate to pass to the functions anymore). We could solve the syntactic
 135     problems by passing \type{undefined} for state variables, but that would
 136     still break the code on the semantic level (\ie, the function would no
 137     longer be semantically equivalent to the original input).
 138
 139     To keep the function definition correct until the very end of the process,
 140     we will not deal with (sub)states until we get to the \small{VHDL} generation.
 141     Here, we are translating from Core to \small{VHDL}, and we can simply not generate
 142     \small{VHDL} for substates, effectively removing the substate components
 143     alltogether.
 144
 145     There are a few important points when ignore substates.
 146
 147     First, we have to have some definition of "substate". Since any state
 148     argument or return value that represents state must be of the \type{State}
 149     type, we can simply look at its type. However, we must be careful to
 150     ignore only {\em substates}, and not a function's own state.
 151
 152     In the example above, this means we should remove \type{accums'} from
 153     \type{s'}, but not throw away \type{s'} entirely. We should, however,
 154     remove \type{s'} from the output port of the function, since the state
 155     will be handled by a \small{VHDL} procedure within the function.
 156
 157     When looking at substates, these can appear in two places: As part of an
 158     argument and as part of a return value. As noted above, these substates
 159     can only be used in very specific ways.
 160
 161     \desc{State variables can appear as an argument.} When generating \small{VHDL}, we
 162     completely ignore the argument and generate no input port for it.
 163
 164     \desc{State variables can be extracted from other state variables.} When
 165     extracting a state variable from another state variable, this always means
 166     we're extracting a substate, which we can ignore. So, we simply generate no
 167     \small{VHDL} for any extraction operation that has a state variable as a result.
 168
 169     \desc{State variables can be passed to functions.} When passing a
 170     state variable to a function, this always means we're passing a substate
 171     to a subcomponent. The entire argument can simply be ingored in the
 172     resulting port map.
 173
 174     \desc{State variables can be returned from functions.} When returning a
 175     state variable from a function (probably as a part of an algebraic
 176     datatype), this always mean we're returning a substate from a
 177     subcomponent. The entire state variable should be ignored in the resulting
 178     port map. The type binder of the binder that the function call is bound
 179     to should not include the state type either.
 180
 181     \startdesc{State variables can be inserted into other variables.} When inserting
 182     a state variable into another variable (usually by constructing that new
 183     variable using its constructor), we can identify two cases:
 184
 185     \startitemize
 186       \item The state is inserted into another state variable. In this case,
 187       the inserted state is a substate, and can be safely left out of the
 188       constructed variable.
 189       \item The state is inserted into a non-state variable. This happens when
 190       building up the return value of a function, where you put state and
 191       retsult variables together in an algebraic type (usually a tuple). In
 192       this case, we should leave the state variable out as well, since we
 193       don't want it to be included as an output port.
 194     \stopitemize
 195
 196     So, in both cases, we can simply leave out the state variable from the
 197     resulting value. In the latter case, however, we should generate a state
 198     proc instead, which assigns the state variable to the input state variable
 199     at each clock tick.
 200     \stopdesc
 201
 202     \desc{State variables can appear as (part of) a function result.} When
 203     generating \small{VHDL}, we can completely ignore any part of a function result
 204     that has a state type. If the entire result is a state type, this will
 205     mean the entity will not have an output port. Otherwise, the state
 206     elements will be removed from the type of the output port.
 207
 208
 209     Now, we know how to handle each use of a state variable separately. If we
 210     look at the whole, we can conclude the following:
 211
 212     \startitemize
 213     \item A state unpack operation should not generate any \small{VHDL}. The binder
 214     to which the unpacked state is bound should still be declared, this signal
 215     will become the register and will hold the current state.
 216     \item A state pack operation should not generate any \small{VHDL}. The binder th
 217     which the packed state is bound should not be declared. The binder that is
 218     packed is the signal that will hold the new state.
 219     \item Any values of a State type should not be translated to \small{VHDL}. In
 220     particular, State elements should be removed from tuples (and other
 221     datatypes) and arguments with a state type should not generate ports.
 222     \item To make the state actually work, a simple \small{VHDL} proc should be
 223     generated. This proc updates the state at every clockcycle, by assigning
 224     the new state to the current state. This will be recognized by synthesis
 225     tools as a register specification.
 226     \stopitemize
 227
 228
 229     When applying these rules to the example program (in normal form), we will
 230     get the following result. All the parts that don't generate any value are
 231     crossed out, leaving some very boring assignments here and there.
 232
 233
 234 \starthaskell
 235   avg i --spacked-- = res
 236     where
 237       s = --case spacked of (State s) -> s--
 238       --accums = case s of (accums, \_) -> accums--
 239       count = case s of (--\_,-- count) -> count
 240       accumres = accum i --accums--
 241       --accums' = case accumres of (accums', \_) -> accums'--
 242       sum = case accumres of (--\_,-- sum) -> sum
 243       count' = count + 1
 244       o = sum / count'
 245       s' = (--accums',-- count')
 246       --spacked' = State s'--
 247       res = (--spacked',-- o)
 248 \stophaskell
 249
 250     When we would really leave out the crossed out parts, we get a slightly
 251     weird program: There is a variable \type{s} which has no value, and there
 252     is a variable \type{s'} that is never used. Together, these two will form
 253     the state proc of the function. \type{s} contains the "current" state,
 254     \type{s'} is assigned the "next" state. So, at the end of each clock
 255     cycle, \type{s'} should be assigned to \type{s}.
 256
 257     Note that the definition of \type{s'} is not removed, even though one
 258     might think it as having a state type. Since the state type has a single
 259     argument constructor \type{State}, some type that should be the resulting
 260     state should always be explicitly packed with the State constructor,
 261     allowing us to remove the packed version, but still generate \small{VHDL} for the
 262     unpacked version (of course with any substates removed).
 263
 264     As you can see, the definition of \type{s'} is still present, since it
 265     does not have a state type (The State constructor. The \type{accums'} substate has been removed,
 266     leaving us just with the state of \type{avg} itself.
 267   \section{Initial state}
 268     How to specify the initial state? Cannot be done inside a hardware
 269     function, since the initial state is its own state argument for the first
 270     call (unless you add an explicit, synchronous reset port).
 271
 272     External init state is natural for simulation.
 273
 274     External init state works for hardware generation as well.
 275
 276     Implementation issues: state splitting, linking input to output state,
 277     checking usage constraints on state variables.