Add section about don't care values.
authorMatthijs Kooijman <matthijs@stdin.nl>
Wed, 11 Nov 2009 21:14:51 +0000 (22:14 +0100)
committerMatthijs Kooijman <matthijs@stdin.nl>
Wed, 11 Nov 2009 21:14:51 +0000 (22:14 +0100)
Chapters/Future.tex

index f59e034..9495922 100644 (file)
@@ -537,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.
+
+\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.