-defuntionalization}, first described by J.C. Reynolds and seems to apply well
-to this situation. One note here is that Reynolds' approach puts all the
-higher order values in a single datatype. For a typed language, we will at
-least have to have a single datatype for each function type, since we can't
-mix them. It would be even better to split these datatypes a bit further, so
-that such a datatype will never hold a constructor that is never used for a
-particular state variable. This separation is probably a non-trivial problem,
-though.
-
-TODO: Reference "Definitional interpreters for higher-order programming
-languages":
-http://portal.acm.org/citation.cfm?id=805852\&dl=GUIDE\&coll=GUIDE\&CFID=58835435\&CFTOKEN=81856623
-
-\section{New language}
-During the development of the prototype, it has become clear that Haskell is
-not the perfect language for this work. There are two main problems:
-\startitemize
-\item Haskell is not expressive enough. Haskell is still quite new in the area
-of dependent typing, something we use extensively. Also, Haskell has some
-special syntax to write monadic composition and arrow composition, which is
-well suited to normal Haskell programs. However, for our hardware
-descriptions, we could use some similar, but other, syntactic sugar (as we
-have seen above).
-\item Haskell is too expressive. There are some things that Haskell can
-express, but we can never properly translate. There are certain types (both
-primitive types and certain type constructions like recursive types) we can
-never translate, as well as certain forms of recursion.
-\stopitemize
-
-It might be good to reevaluate the choice of language for Cλash, perhaps there
-are other languages which are better suited to describe hardware, now that
-we've learned a lot about it.
-
-Perhaps Haskell (or some other language) can be extended by using a
-preprocessor. There has been some (point of proof) work on a the Strathclyde
-Haskell Enhancement (\small{SHE}) preprocessor for type-level programming,
-perhaps we can extend that, or create something similar for hardware-specific
-notation.
-
-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.
+defuntionalization}, first described by J.C. Reynolds \cite[reynolds98]\ and
+seems to apply well to this situation. One note here is that Reynolds'
+approach puts all the higher-order values in a single datatype. For a typed
+language, we will at least have to have a single datatype for each function
+type, since we cannot mix them. It would be even better to split these
+datatypes a bit further, so that such a datatype will never hold a constructor
+that is never used for a particular state variable. This separation is
+probably a non-trivial problem, though.
+
+\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 do not really care about
+ which value is assigned to a signal, allowing the compiler to make some
+ optimizations. Since 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{Don't 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 type class, 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 expressions 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
+ and :: 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.
+
+% vim: set sw=2 sts=2 expandtab: