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.
12 \section{Explicit state specification}
13 Note about semantic correctness of top level state.
15 Note about automatic ``down-pushing'' of state.
17 Note about explicit state specification as the best solution.
21 Note about conditions on state variables and checking them.
23 \section{Explicit state implementation}
24 Recording state variables at the type level.
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).
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:
38 State (State Bit, State (State Word, Bit), Word)
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:
46 type AccumStateIn = StateIn Bit
47 type AccumStateOut = StateOut Bit
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
54 Alternative: Provide a type for the entire result type of a stateful
55 function, not just the state part. \eg:
58 newtype Result state result = Result (state, result)
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.
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.
75 newtype State s = State s
77 type AccumState = State Bit
78 accum :: Word -> AccumState -> (AccumState, Word)
79 accum i (State s) = (State (s + i), s + i)
81 type AvgState = (AccumState, Word)
82 avg :: Word -> AvgState -> (AvgState, Word)
83 avg i (State s) = (State s', o)
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)
90 -- Compute the average
92 s' = (accums', count')
95 And the normalized, core-like versions:
100 s = case spacked of (State s) -> s
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
116 s' = (accums', count')
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 VHDL for this component can be generated entirely within the called
127 function. So,we can completely leave out substates from any function.
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 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).
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 VHDL generation.
141 Here, we are translating from Core to VHDL, and we can simply not generate
142 VHDL for substates, effectively removing the substate components
145 There are a few important points when ignore substates.
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.
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 VHDL procedure within the function.
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.
161 \desc{State variables can appear as an argument.} When generating VHDL, we
162 completely ignore the argument and generate no input port for it.
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 VHDL for any extraction operation that has a state variable as a result.
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
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.
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:
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.
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
202 \desc{State variables can appear as (part of) a function result.} When
203 generating 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.
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:
213 \item A state unpack operation should not generate any 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 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 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 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.
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.
235 avg i --spacked-- = res
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
245 s' = (--accums',-- count')
246 --spacked' = State s'--
247 res = (--spacked',-- o)
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}.
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 VHDL for the
262 unpacked version (of course with any substates removed).
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).
272 External init state is natural for simulation.
274 External init state works for hardware generation as well.
276 Implementation issues: state splitting, linking input to output state,
277 checking usage constraints on state variables.