+ Here, there is only a single alternative (but no \lam{DEFAULT}
+ alternative, since the single alternative is already exhaustive). When
+ it's body is evaluated, the arguments to the tuple constructor \lam{(,)}
+ (\eg, the elements of the tuple) are bound to \lam{a} and \lam{b}.
+ \stopdesc
+
+ \startdesc{Cast expression}
+ \startlambda
+ body :: targettype
+ \stoplambda
+ A cast expression allows you to change the type of an expression to an
+ equivalent type. Note that this is not meant to do any actual work, like
+ conversion of data from one format to another, or force a complete type
+ change. Instead, it is meant to change between different representations
+ of the same type, \eg switch between types that are provably equal (but
+ look different).
+
+ In our hardware descriptions, we typically see casts to change between a
+ Haskell newtype and its contained type, since those are effectively
+ different representations of the same type.
+
+ More complex are types that are proven to be equal by the typechecker,
+ but look different at first glance. To ensure that, once the typechecker
+ has proven equality, this information sticks around, explicit casts are
+ added. In our notation we only write the target type, but in reality a
+ cast expressions carries around a \emph{coercion}, which can be seen as a
+ proof of equality. TODO: Example
+
+ The value of a cast is the value of its body, unchanged. The type of this
+ value is equal to the target type, not the type of its body.
+
+ Note that this syntax is also used sometimes to indicate that a particular
+ expression has a particular type, even when no cast expression is
+ involved. This is then purely informational, since the only elements that
+ are explicitely typed in the Core language are the binder references and
+ cast expressions, the types of all other elements are determined at
+ runtime.
+ \stopdesc
+
+ \startdesc{Note}
+
+ The Core language in \small{GHC} allows adding \emph{notes}, which serve
+ as hints to the inliner or add custom (string) annotations to a core
+ expression. These shouldn't be generated normally, so these are not
+ handled in any way in the prototype.
+ \stopdesc
+
+ \startdesc{Type}
+ \startlambda
+ @type
+ \stoplambda
+ It is possibly to use a Core type as a Core expression. This is done to
+ allow for type abstractions and applications to be handled as normal
+ lambda abstractions and applications above. This means that a type
+ expression in Core can only ever occur in the argument position of an
+ application, and only if the type of the function that is applied to
+ expects a type as the first argument. This happens for all polymorphic
+ functions, for example, the \lam{fst} function:
+
+ \startlambda
+ fst :: \forall a. \forall b. (a, b) -> a
+ fst = λtup.case tup of (,) a b -> a
+
+ fstint :: (Int, Int) -> Int
+ fstint = λa.λb.fst @Int @Int a b
+ \stoplambda
+
+ The type of \lam{fst} has two universally quantified type variables. When
+ \lam{fst} is applied in \lam{fstint}, it is first applied to two types.
+ (which are substitued for \lam{a} and \lam{b} in the type of \lam{fst}, so
+ the type of \lam{fst} actual type of arguments and result can be found:
+ \lam{fst @Int @Int :: (Int, Int) -> Int}).
+ \stopdesc
+
+ TODO: Core type system
+
+ \section[sec:prototype:statetype]{State annotations in Haskell}
+ Ideal: Type synonyms, since there is no additional code overhead for
+ packing and unpacking. Downside: there is no explicit conversion in Core
+ either, so type synonyms tend to get lost in expressions (they can be
+ preserved in binders, but this makes implementation harder, since that
+ statefulness of a value must be manually tracked).
+
+ Less ideal: Newtype. Requires explicit packing and unpacking of function
+ arguments. If you don't unpack substates, there is no overhead for
+ (un)packing substates. This will result in many nested State constructors
+ in a nested state type. \eg:
+
+ \starttyping
+ State (State Bit, State (State Word, Bit), Word)
+ \stoptyping
+
+ Alternative: Provide different newtypes for input and output state. This
+ makes the code even more explicit, and typechecking can find even more
+ errors. However, this requires defining two type synomyms for each
+ stateful function instead of just one. \eg:
+
+ \starttyping
+ type AccumStateIn = StateIn Bit
+ type AccumStateOut = StateOut Bit
+ \stoptyping
+
+ This also increases the possibility of having different input and output
+ states. Checking for identical input and output state types is also
+ harder, since each element in the state must be unpacked and compared
+ separately.
+
+ Alternative: Provide a type for the entire result type of a stateful
+ function, not just the state part. \eg:
+
+ \starttyping
+ newtype Result state result = Result (state, result)
+ \stoptyping
+
+ This makes it easy to say "Any stateful function must return a
+ \type{Result} type, without having to sort out result from state. However,
+ this either requires a second type for input state (similar to
+ \type{StateIn} / \type{StateOut} above), or requires the compiler to
+ select the right argument for input state by looking at types (which works
+ for complex states, but when that state has the same type as an argument,
+ things get ambiguous) or by selecting a fixed (\eg, the last) argument,
+ which might be limiting.
+
+ \subsubsection{Example}
+ As an example of the used approach, a simple averaging circuit, that lets
+ the accumulation of the inputs be done by a subcomponent.
+
+ \starttyping
+ newtype State s = State s
+
+ type AccumState = State Bit
+ accum :: Word -> AccumState -> (AccumState, Word)
+ accum i (State s) = (State (s + i), s + i)
+
+ type AvgState = (AccumState, Word)
+ avg :: Word -> AvgState -> (AvgState, Word)
+ avg i (State s) = (State s', o)
+ where
+ (accums, count) = s
+ -- Pass our input through the accumulator, which outputs a sum
+ (accums', sum) = accum i accums
+ -- Increment the count (which will be our new state)
+ count' = count + 1
+ -- Compute the average
+ o = sum / count'
+ s' = (accums', count')
+ \stoptyping
+
+ And the normalized, core-like versions:
+
+ \starttyping
+ accum i spacked = res
+ where
+ s = case spacked of (State s) -> s
+ s' = s + i
+ spacked' = State s'
+ o = s + i
+ res = (spacked', o)
+
+ avg i spacked = res
+ where
+ s = case spacked of (State s) -> s
+ accums = case s of (accums, \_) -> accums
+ count = case s of (\_, count) -> count
+ accumres = accum i accums
+ accums' = case accumres of (accums', \_) -> accums'
+ sum = case accumres of (\_, sum) -> sum
+ count' = count + 1
+ o = sum / count'
+ s' = (accums', count')
+ spacked' = State s'
+ res = (spacked', o)
+ \stoptyping
+
+
+
+ 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:
+
+ \startitemize
+ \item The state is inserted into another state variable. In this case,
+ the inserted state is a substate, and can be safely left out of the
+ constructed variable.
+ \item The state is inserted into a non-state variable. This happens when
+ building up the return value of a function, where you put state and
+ retsult variables together in an algebraic type (usually a tuple). In
+ this case, we should leave the state variable out as well, since we
+ don't want it to be included as an output port.
+ \stopitemize
+
+ So, in both cases, we can simply leave out the state variable from the
+ resulting value. In the latter case, however, we should generate a state
+ proc instead, which assigns the state variable to the input state variable
+ at each clock tick.
+ \stopdesc
+
+ \desc{State variables can appear as (part of) a function result.} When
+ generating \small{VHDL}, we can completely ignore any part of a function result
+ that has a state type. If the entire result is a state type, this will
+ mean the entity will not have an output port. Otherwise, the state
+ elements will be removed from the type of the output port.
+
+
+ Now, we know how to handle each use of a state variable separately. If we
+ look at the whole, we can conclude the following:
+
+ \startitemize
+ \item A state unpack operation should not generate any \small{VHDL}. The binder
+ to which the unpacked state is bound should still be declared, this signal
+ will become the register and will hold the current state.
+ \item A state pack operation should not generate any \small{VHDL}. The binder th
+ which the packed state is bound should not be declared. The binder that is
+ packed is the signal that will hold the new state.
+ \item Any values of a State type should not be translated to \small{VHDL}. In
+ particular, State elements should be removed from tuples (and other
+ datatypes) and arguments with a state type should not generate ports.
+ \item To make the state actually work, a simple \small{VHDL} proc should be
+ generated. This proc updates the state at every clockcycle, by assigning
+ the new state to the current state. This will be recognized by synthesis
+ tools as a register specification.
+ \stopitemize
+
+
+ When applying these rules to the example program (in normal form), we will
+ get the following result. All the parts that don't generate any value are
+ crossed out, leaving some very boring assignments here and there.
+
projects / matthijs / master-project / report.git / blobdiff