Move the State chapter into the Hardware Description chapter.
authorMatthijs Kooijman <matthijs@stdin.nl>
Tue, 20 Oct 2009 09:35:46 +0000 (11:35 +0200)
committerMatthijs Kooijman <matthijs@stdin.nl>
Tue, 20 Oct 2009 13:40:00 +0000 (15:40 +0200)
Chapters/HardwareDescription.tex
Chapters/State.tex [deleted file]
Report.tex

index 5113689..0266490 100644 (file)
   function boundaries), but eventually, the partial application will become
   completely applied.
 
+  \section{State}
+    \subsection{Introduction}
+      Provide some examples
+
+
+    \subsection{Approaches to state}
+      Explain impact of state (or rather, temporal behaviour) on function signature.
+      \subsubsection{Stream arguments and results}
+      \subsubsection{Explicit state arguments and results}
+        Nested state for called functions.
+
+    \subsection{Explicit state specification}
+      Note about semantic correctness of top level state.
+
+      Note about automatic ``down-pushing'' of state.
+
+      Note about explicit state specification as the best solution.
+
+      Note about substates
+
+      Note about conditions on state variables and checking them.
+
+    \subsection{Explicit state implementation}
+      Recording state variables at the type level.
+
+      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.
+      
+    
+  \starthaskell
+    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)
+  \stophaskell
+          
+      When we would really leave out the crossed out parts, we get a slightly
+      weird program: There is a variable \type{s} which has no value, and there
+      is a variable \type{s'} that is never used. Together, these two will form
+      the state proc of the function. \type{s} contains the "current" state,
+      \type{s'} is assigned the "next" state. So, at the end of each clock
+      cycle, \type{s'} should be assigned to \type{s}.
+
+      Note that the definition of \type{s'} is not removed, even though one
+      might think it as having a state type. Since the state type has a single
+      argument constructor \type{State}, some type that should be the resulting
+      state should always be explicitly packed with the State constructor,
+      allowing us to remove the packed version, but still generate \small{VHDL} for the
+      unpacked version (of course with any substates removed).
+      
+      As you can see, the definition of \type{s'} is still present, since it
+      does not have a state type (The State constructor. The \type{accums'} substate has been removed,
+      leaving us just with the state of \type{avg} itself.
+    \subsection{Initial state}
+      How to specify the initial state? Cannot be done inside a hardware
+      function, since the initial state is its own state argument for the first
+      call (unless you add an explicit, synchronous reset port).
+
+      External init state is natural for simulation.
+
+      External init state works for hardware generation as well.
+
+      Implementation issues: state splitting, linking input to output state,
+      checking usage constraints on state variables.
   \section{Recursion}
   An import concept in functional languages is recursion. In it's most basic
   form, recursion is a function that is defined in terms of itself. This
diff --git a/Chapters/State.tex b/Chapters/State.tex
deleted file mode 100644 (file)
index f8f268a..0000000
+++ /dev/null
@@ -1,277 +0,0 @@
-\chapter[chap:state]{State}
-  \section{Introduction}
-    Provide some examples
-
-
-  \section{Approaches to state}
-    Explain impact of state (or rather, temporal behaviour) on function signature.
-    \subsection{Stream arguments and results}
-    \subsection{Explicit state arguments and results}
-      Nested state for called functions.
-
-  \section{Explicit state specification}
-    Note about semantic correctness of top level state.
-
-    Note about automatic ``down-pushing'' of state.
-
-    Note about explicit state specification as the best solution.
-
-    Note about substates
-
-    Note about conditions on state variables and checking them.
-
-  \section{Explicit state implementation}
-    Recording state variables at the type level.
-
-    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.
-
-    \subsection{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.
-    
-  
-\starthaskell
-  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)
-\stophaskell
-        
-    When we would really leave out the crossed out parts, we get a slightly
-    weird program: There is a variable \type{s} which has no value, and there
-    is a variable \type{s'} that is never used. Together, these two will form
-    the state proc of the function. \type{s} contains the "current" state,
-    \type{s'} is assigned the "next" state. So, at the end of each clock
-    cycle, \type{s'} should be assigned to \type{s}.
-
-    Note that the definition of \type{s'} is not removed, even though one
-    might think it as having a state type. Since the state type has a single
-    argument constructor \type{State}, some type that should be the resulting
-    state should always be explicitly packed with the State constructor,
-    allowing us to remove the packed version, but still generate \small{VHDL} for the
-    unpacked version (of course with any substates removed).
-    
-    As you can see, the definition of \type{s'} is still present, since it
-    does not have a state type (The State constructor. The \type{accums'} substate has been removed,
-    leaving us just with the state of \type{avg} itself.
-  \section{Initial state}
-    How to specify the initial state? Cannot be done inside a hardware
-    function, since the initial state is its own state argument for the first
-    call (unless you add an explicit, synchronous reset port).
-
-    External init state is natural for simulation.
-
-    External init state works for hardware generation as well.
-
-    Implementation issues: state splitting, linking input to output state,
-    checking usage constraints on state variables.
index bbcc14e..69817cb 100644 (file)
@@ -26,5 +26,4 @@ Matthijs Kooijman
 \input Chapters/HardwareDescription
 \input Chapters/Prototype
 \input Chapters/Normalization
-\input Chapters/State
 \stoptext