Add / update TODOs.
[matthijs/master-project/report.git] / Chapters / Future.tex
index 38904be..d83f600 100644 (file)
 \section{Improved notation for hierarchical state}
 The hierarchic state model requires quite some boilerplate code for unpacking
 and distributing the input state and collecting and repacking the output
 \section{Improved notation for hierarchical state}
 The hierarchic state model requires quite some boilerplate code for unpacking
 and distributing the input state and collecting and repacking the output
-state. There is really only one way in which this state handling can be done,
-so it would make sense to hide this boilerplate. This would incur no
-flexibility cost at all, since there are no other ways that would work.
+state.
+
+\in{Example}[ex:NestedState] shows a simple composition of two stateful
+functions, \hs{funca} and \hs{funcb}. The state annotation using the
+\hs{State} newtype has been left out, for clarity and because the proposed
+approach below cannot handle that (yet).
+
+\startbuffer[NestedState]
+  type FooState = ( AState, BState )
+  foo :: Word -> FooState -> (FooState, Word)
+  foo in s = (s', outb)
+    where
+      (sa, sb) = s
+      (sa', outa) = funca in sa
+      (sb', outb) = funcb outa sb
+      s' = (sa', sb')
+\stopbuffer
+\placeexample[here][ex:NestedState]{Simple function composing two stateful
+                                    functions.}{\typebufferhs{NestedState}}
+
+Since state handling always follows strict rules, there is really no other way
+in which this state handling can be done (you can of course move some things
+around from the where clause to the pattern or vice versa, but it would still
+be effectively the same thing). This means it makes extra sense to hide this
+boilerplate away. This would incur no flexibility cost at all, since there are
+no other ways that would work.
+
+One particular notation in Haskell that seemed promising, whas he \hs{do}
+notation. This is meant to simplify Monad notation by hiding away some
+details. It allows one to write a list of expressions, which are composited
+using the monadic \emph{bind} operator, written in Haskell as \hs{>>}. For
+example, the snippet:
 
 
-Options: Misuse the do notation in Haskell, create some abstraction in
-Haskell or add new syntax.
+\starthaskell
+do
+  somefunc a
+  otherfunc b
+\stophaskell
+
+will be desugared into:
+
+\starthaskell
+(somefunc a b) >> (otherfunc b c)
+\stophaskell
+
+There is also the \hs{>>=} operator, which allows for passing variables from
+one expression to the next. If we could use this notation to compose a
+stateful computation from a number of other stateful functions, this could
+move all the boilerplate code into the \hs{>>} operator. Perhaps the compiler
+should be taught to always inline the \hs{>>} operator, but after that there
+should be no further changes required to the compiler.
+
+This is highlights an important aspect of using a functional language for our
+descriptions: We can use the language itself to provide abstractions of common
+patterns, making our code smaller.
+
+\subsection{Outside the Monad}
+However, simply using the monad notation is not as easy as it sounds. The main
+problem is that the Monad type class poses a number of limitations on the
+bind operator \hs{>>}. Most importantly, it has the following type signature:
+
+\starthaskell
+(>>) :: (Monad m) => m a -> m b -> m b
+\stophaskell
+
+This means that any expression in our composition must use the same Monad
+instance as its type, only the "return" value can be different between
+expressions. 
+
+Ideally, we would like the \hs{>>} operator to have a type like the following
+\starthaskell
+type Stateful s r = s -> (s, r)
+(>>) :: Stateful s1 r1 -> Stateful s2 r2 -> Stateful (s1, s2) r2
+\stophaskell
+
+What we see here, is that when we compose two stateful functions (whose inputs
+have already been applied, leaving just the state argument to be applied), the
+result is again a stateful function whose state is composed of the two
+\emph{substates}. The return value is simply the return value of the second
+function, discarding the first (to preserve that one, the \hs{>>=} operator
+can be used).
+
+There is a trick we can apply to change the signature of the \hs{>>} operator.
+\small{GHC} does not require the bind operators to be part of the \hs{Monad}
+type class, as long as it can use them to translate the do notation. This
+means we can define our own \hs{>>} and \hs{>>=} operators, outside of the
+\hs{Monad} typeclass. This does conflict with the existing methods of the
+\hs{Monad} typeclass, so we should prevent \small{GHC} from loading those (and
+all of the Prelude) by passing \type{-XNoImplicitPrelude} to \type{ghc}. This
+is slightly inconvenient, but since we hardly using anything from the prelude,
+this is not a big problem. We might even be able to replace some of the
+Prelude with hardware-translateable versions by doing this.
+
+We can now define the following binding operators. For completeness, we also
+supply the return function, which is not called by \small{GHC} implicitely,
+but can be called explicitely by a hardware description.
+
+\starthaskell
+(>>) :: Stateful s1 r1 -> Stateful s2 r2 -> Stateful (s1, s2) r2
+f1 >> f2 = f1 >>= \_ -> f2
+
+(>>=) :: Stateful s1 r1 -> (r1 -> Stateful s2 r2) -> Stateful (s1, s2) r2
+f1 >>= f2 = \(s1, s2) -> let (s1', r1) = f1 s1
+                             (s2', r2) = f2 r1 s2
+                         in ((s1', s2'), r2)
+               
+return :: r -> Stateful () r
+return r = \s -> (s, r)
+\stophaskell
+
+As you can see, this closely resembles the boilerplate of unpacking state,
+passing it to two functions and repacking the new state. With these
+definitions, we could have writting \in{example}[ex:NestedState] a lot
+shorter, see \in{example}[ex:DoState]. In this example the type signature of
+foo is the same (though it is now written using the \hs{Stateful} type
+synonym, it is still completel equivalent to the original: \hs{foo :: Word ->
+FooState -> (FooState, Word)}.
+
+Note that the \hs{FooState} type has changed (so indirectly the type of
+\hs{foo} as well). Since the state composition by the \hs{>>} works on two
+stateful functions at a time, the final state consists of nested two-tuples.
+The final \hs{()} in the state originates from the fact that the \hs{return}
+function has no real state, but is part of the composition. We could have left
+out the return statement (and the \hs{outb <-} part) to make \hs{foo}'s return
+value equal to \hs{funcb}'s, but this approach makes it clearer what is
+happening.
+
+\startbuffer[DoState]
+  type FooState = ( AState, (BState, ()) )
+  foo :: Word -> Stateful FooState Word
+  foo in = do
+      outa <- funca in sa
+      outb <- funcb outa sb
+      return outb
+\stopbuffer
+\placeexample[here][ex:DoState]{Simple function composing two stateful
+                                functions, using do notation.}
+                               {\typebufferhs{DoState}}
+
+An important implication of this approach is that the order of writing
+function applications affects the state type. Fortunately, this problem can be
+localized by consistently using type synonyms for state types, which should
+prevent changes in other function's source when a function changes.
+
+A less obvous implications of this approach is that the scope of variables
+produced by each of these expressions (using the \hs{<-} syntax) is limited to
+the expressions that come after it. This prevents values from flowing between
+two functions (components) in two directions. For most Monad instances, this
+is a requirement, but here it could have been different.
+
+\subsection{Alternative syntax}
+Because of the above issues, misusing Haskell's do notation is probably not
+the best solution here. However, it does show that using fairly simple
+abstractions, we could hide a lot of the boilerplate code. Extending
+\small{GHC} with some new syntax sugar similar to the do notation might be a
+feasible.
 
 \section[sec:future:pipelining]{Improved notation or abstraction for pipelining}
 Since pipelining is a very common optimization for hardware systems, it should
 
 \section[sec:future:pipelining]{Improved notation or abstraction for pipelining}
 Since pipelining is a very common optimization for hardware systems, it should
@@ -15,15 +165,57 @@ be easy to specify a pipelined system. Since it involves quite some registers
 into an otherwise regular combinatoric system, we might look for some way to
 abstract away some of the boilerplate for pipelining.
 
 into an otherwise regular combinatoric system, we might look for some way to
 abstract away some of the boilerplate for pipelining.
 
-Example of naive pipelined code
+Something similar to the state boilerplate removal above might be appropriate:
+Abstract away some of the boilerplate code using combinators, then hide away
+the combinators in special syntax. The combinators will be slightly different,
+since there is a (typing) distinction between a pipeline stage and a pipeline
+consisting of multiple stages. Also, it seems necessary to treat either the
+first or the last pipeline stage differently, to prevent an off-by-one error
+in the amount of registers (which is similar to the extra \hs{()} state type
+in \in{example}[ex:DoState], which is harmless there, but would be a problem
+if it introduced an extra, useless, pipeline stage).
+
+This problem is slightly more complex than the problem we've seen before. One
+significant difference is that each variable that crosses a stage boundary
+needs a registers. However, when a variable crosses multiple stage boundaries,
+it must be stored for a longer period and should receive multiple registers.
+Since we can't find out from the combinator code where the result of the
+combined values is used (at least not without using Template Haskell to
+inspect the \small{AST}), there seems to be no easy way to find how much
+registers are needed.
+
+There seem to be two obvious ways of handling this problem:
 
 
-Using monadic do does not fit the typing
+\startitemize
+  \item Limit the scoping of each variable produced by a stage to the next
+  stage only. This means that any variables that are to be used in subsequent
+  stages should be passed on explicitely, which should allocate the required
+  number of registers.
+
+  This produces cumbersome code, where there is still a lot of explicitness
+  (though this could be hidden in syntax sugar).
+  \item Scope each variable over every subsequent pipeline stage and allocate
+  the maximum amount of registers that \emph{could} be needed. This means we
+  will allocate registers that are never used, but those could be optimized
+  away later. This does mean we need some way to introduce a variable number
+  of variables (depending on the total number of stages), assign the output of
+  a different register to each (\eg., a different part of the state) and scope
+  a different one of them over each the subsequent stages.
+
+  This also means that when adding a stage to an existing pipeline will change
+  the state type of each of the subsequent pipeline stages, and the state type
+  ofthe added stage depends on the number of subsequent stages.
+
+  Properly describing this will probably also require quite explicit syntax,
+  meaning this is not feasible without some special syntax.
+\stopitemize
 
 
-Using custom combinators would work
+Some other interesting issues include pipeline stages which are already
+stateful, mixing pipelined with normal computation, etc.
 
 \section{Recursion}
 The main problems of recursion have been described in
 
 \section{Recursion}
 The main problems of recursion have been described in
-\at{section}[sec:recursion]. In the current implementation, recursion is
+\in{section}[sec:recursion]. In the current implementation, recursion is
 therefore not possible, instead we rely on a number of implicit list-recursive
 builtin functions.
 
 therefore not possible, instead we rely on a number of implicit list-recursive
 builtin functions.
 
@@ -49,7 +241,7 @@ transformations to prevent infinite expansion. The main challenge here is how
 to make this set complete, or at least define the constraints on possible
 recursion which guarantee it will work.
 
 to make this set complete, or at least define the constraints on possible
 recursion which guarantee it will work.
 
-TODO: Loop unrolling
+TODO: Reference Christian for loop unrolling
 \stopitemize
 
 \section{Multiple clock domains and asynchronicity}
 \stopitemize
 
 \section{Multiple clock domains and asynchronicity}
@@ -213,7 +405,7 @@ take multiple cycles. Some examples include:
   \item A large combinatoric expressions that would introduce a very long
   combinatoric path and thus limit clock frequency. Such an expression could
   be broken up into multiple stages, which effectively results in a pipelined
   \item A large combinatoric expressions that would introduce a very long
   combinatoric path and thus limit clock frequency. Such an expression could
   be broken up into multiple stages, which effectively results in a pipelined
-  system (see also \at{section}[sec:future:pipelining]) with a known delay.
+  system (see also \in{section}[sec:future:pipelining]) with a known delay.
   There should probably be some way for the developer to specify the cycle
   division of the expression, since automatically deciding on such a division
   is too complex and contains too many tradeoffs, at least initially.
   There should probably be some way for the developer to specify the cycle
   division of the expression, since automatically deciding on such a division
   is too complex and contains too many tradeoffs, at least initially.
@@ -345,3 +537,77 @@ It is not unlikely that the most flexible way
 forward would be to define a completely new language with exactly the needed
 features. This is of course an enormous effort, which should not be taken
 lightly.
 forward would be to define a completely new language with exactly the needed
 features. This is of course an enormous effort, which should not be taken
 lightly.
+
+\section{Don't care values}
+  A powerful value in \VHDL is the \emph{don't care} value, given as
+  \type{'-'}. This value tells the compiler that you don't really care about
+  which value is assigned to a signal, allowing the compiler to make some
+  optimizations. Since hardware choice in hardware is often implemented using
+  a collection of logic gates instead of multiplexers only, synthesizers can
+  often reduce the amount of hardware needed by smartly choosing values for
+  these don't care cases.
+
+  There is not really anything comparable with don't care values in normal
+  programming languages. The closest thing is an undefined or uninitialized
+  value, though those are usually associated with error conditions.
+
+  It would be useful if Cλash also has some way to specify don't care values.
+  When looking at the Haskell typing system, there are really two ways to do
+  this:
+
+  \startitemize
+    \item Add a special don't care value to every datatype. This includes the
+    obvious \hs{Bit} type, but will also need to include every user defined
+    type. An exception can be made for vectors and product types, since those
+    can simply use the don't care values of the types they contain.
+
+    This would also require some kind of \quote{Dont careable} type class
+    that allows each type to specify what its don't care value is. The
+    compiler must then recognize this constant and replace it with don't care
+    values in the final \VHDL code.
+
+    This is of course a very intrusive solution. Every type must become member
+    of this typeclass, and there is now some member in every type that is a
+    special don't care value. Guaranteeing the obvious don't care semantics
+    also becomes harder, since every pattern match or case statement must now
+    also take care of the don't care value (this might actually be an
+    advantage, since it forces designers to specify how to handle don't care
+    for different operations).
+
+    \item Use the special \hs{undefined}, or \emph{bottom} value present in
+    Haskell. This is a type that is member of all types automatically, without
+    any explicit declarations.
+
+    Any expression that requires evaluation of an undefined value
+    automatically becomes undefined itself (or rather, there is some exception
+    mechanism). Since Haskell is lazy, this means that whenever it tries to
+    evaluate undefined, it is apparently required for determining the output
+    of the system. This property is useful, since typically a don't care
+    output is used when some output is not valid and should not be read. If
+    it is in fact not read, it should never be evaluated and simulation should
+    be fine.
+
+    In practice, this works less ideal. In particular, pattern matching is not
+    always smart enough to deal with undefined. Consider the following
+    definition of an \hs{and} operator:
+
+    \starthaskell
+    or :: Bit -> Bit -> Bit
+    and Low _ = Low
+    and _ Low = Low
+    and High High = High
+    \stophaskell
+
+    When using the \hs{and} operation on an undefined (don't care) and a Low
+    value should always return a Low value. Its value does not depend on the
+    value chosen for the don't care value. However, though when applying the
+    above and function to \hs{Low} and \hs{undefined} results in exactly that
+    behviour, the result is \hs{undefined} when the arguments are swapped.
+    This is because the first pattern forces the first argument to be
+    evaluated. If it is \hs{undefined}, evaluation is halted and an exception
+    is show, which is not what is intended.
+  \stopitemize
+
+  These options should be explored further to see if they provide feasible
+  methods for describing don't care conditions. Possibly there are completely
+  other methods which work better.