+ \section{Choice}
+ Although describing components and connections allows us to describe a lot of
+ hardware designs already, there is an obvious thing missing: Choice. We
+ need some way to be able to choose between values based on another value.
+ In Haskell, choice is achieved by \hs{case} expressions, \hs{if}
+ expressions, pattern matching and guards.
+
+ An obvious way to add choice to our language without having to recognize
+ any of Haskell's syntax, would be to add a primivite \quote{\hs{if}}
+ function. This function would take three arguments: The condition, the
+ value to return when the condition is true and the value to return when
+ the condition is false.
+
+ This \hs{if} function would then essentially describe a multiplexer and
+ allows us to describe any architecture that uses multiplexers. \fxnote{Are
+ there other mechanisms of choice in hardware?}
+
+ However, to be able to describe our hardware in a more convenient way, we
+ also want to translate Haskell's choice mechanisms. The easiest of these
+ are of course case expressions (and \hs{if} expressions, which can be very
+ directly translated to \hs{case} expressions). A \hs{case} expression can in turn
+ simply be translated to a conditional assignment, where the conditions use
+ equality comparisons against the constructors in the \hs{case} expressions.
+
+ \todo{Assignment vs multiplexers}
+
+ In \in{example}[ex:CaseInv] a simple \hs{case} expression is shown,
+ scrutinizing a boolean value. The corresponding architecture has a
+ comparator to determine which of the constructors is on the \hs{in}
+ input. There is a multiplexer to select the output signal. The two options
+ for the output signals are just constants, but these could have been more
+ complex expressions (in which case also both of them would be working in
+ parallel, regardless of which output would be chosen eventually).
+
+ If we would translate a Boolean to a bit value, we could of course remove
+ the comparator and directly feed 'in' into the multiplexer (or even use an
+ inverter instead of a multiplexer). However, we will try to make a
+ general translation, which works for all possible \hs{case} expressions.
+ Optimizations such as these are left for the \VHDL\ synthesizer, which
+ handles them very well.
+
+ \todo{Be more explicit about >2 alternatives}
+
+ \startbuffer[CaseInv]
+ inv :: Bool -> Bool
+ inv x = case x of
+ True -> False
+ False -> True
+ \stopbuffer
+
+ \startuseMPgraphic{CaseInv}
+ save in, truecmp, falseout, trueout, out, cmp, mux;
+
+ % I/O ports
+ newCircle.in(btex $in$ etex) "framed(false)";
+ newCircle.out(btex $out$ etex) "framed(false)";
+ % Constants
+ newBox.truecmp(btex $True$ etex) "framed(false)";
+ newBox.trueout(btex $True$ etex) "framed(false)";
+ newBox.falseout(btex $False$ etex) "framed(false)";
+
+ % Components
+ newCircle.cmp(btex $==$ etex);
+ newMux.mux;
+
+ in.c = origin;
+ cmp.c = in.c + (3cm, 0cm);
+ truecmp.c = cmp.c + (-1cm, 1cm);
+ mux.sel = cmp.e + (1cm, -1cm);
+ falseout.c = mux.inpa - (2cm, 0cm);
+ trueout.c = mux.inpb - (2cm, 0cm);
+ out.c = mux.out + (2cm, 0cm);
+
+ % Draw objects and lines
+ drawObj(in, out, truecmp, trueout, falseout, cmp, mux);
+
+ ncline(in)(cmp);
+ ncarc(truecmp)(cmp);
+ nccurve(cmp.e)(mux.sel) "angleA(0)", "angleB(-90)";
+ ncline(falseout)(mux) "posB(inpa)";
+ ncline(trueout)(mux) "posB(inpb)";
+ ncline(mux)(out) "posA(out)";
+ \stopuseMPgraphic
+
+ \placeexample[here][ex:CaseInv]{Simple inverter.}
+ \startcombination[2*1]
+ {\typebufferhs{CaseInv}}{Haskell description using a Case expression.}
+ {\boxedgraphic{CaseInv}}{The architecture described by the Haskell description.}
+ \stopcombination
+
+ A slightly more complex (but very powerful) form of choice is pattern
+ matching. A function can be defined in multiple clauses, where each clause
+ specifies a pattern. When the arguments match the pattern, the
+ corresponding clause will be used.
+
+ \startbuffer[PatternInv]
+ inv :: Bool -> Bool
+ inv True = False
+ inv False = True
+ \stopbuffer
+
+ \placeexample[here][ex:PatternInv]{Simple inverter using pattern matching.
+ Describes the same architecture as \in{example}[ex:CaseInv].}
+ {\typebufferhs{PatternInv}}
+
+ The architecture described by \in{example}[ex:PatternInv] is of course the
+ same one as the one in \in{example}[ex:CaseInv]. The general interpretation
+ of pattern matching is also similar to that of \hs{case} expressions: Generate
+ hardware for each of the clauses (like each of the clauses of a \hs{case}
+ expression) and connect them to the function output through (a number of
+ nested) multiplexers. These multiplexers are driven by comparators and
+ other logic, that check each pattern in turn.
+
+ \section{Types}
+ Translation of two most basic functional concepts has been
+ discussed: Function application and choice. Before looking further
+ into less obvious concepts like higher-order expressions and
+ polymorphism, the possible types that can be used in hardware
+ descriptions will be discussed.
+
+ Some way is needed to translate every values used to its hardware
+ equivalents. In particular, this means a hardware equivalent for
+ every \emph{type} used in a hardware description is needed
+
+ Since most functional languages have a lot of standard types that
+ are hard to translate (integers without a fixed size, lists without
+ a static length, etc.), a number of \quote{built-in} types will be
+ defined first. These types are built-in in the sense that our
+ compiler will have a fixed VHDL type for these. User defined types,
+ on the other hand, will have their hardware type derived directly
+ from their Haskell declaration automatically, according to the rules
+ sketched here.
+
+ \todo{Introduce Haskell type syntax (type constructors, type application,
+ :: operator?)}
+
+ \subsection{Built-in types}
+ The language currently supports the following built-in types. Of these,
+ only the \hs{Bool} type is supported by Haskell out of the box (the
+ others are defined by the Cλash package, so they are user-defined types
+ from Haskell's point of view).
+
+ \startdesc{\hs{Bit}}
+ This is the most basic type available. It is mapped directly onto
+ the \type{std_logic} \small{VHDL} type. Mapping this to the
+ \type{bit} type might make more sense (since the Haskell version
+ only has two values), but using \type{std_logic} is more standard
+ (and allowed for some experimentation with don't care values)
+
+ \todo{Sidenote bit vs stdlogic}
+ \stopdesc
+ \startdesc{\hs{Bool}}
+ This is the only built-in Haskell type supported and is translated
+ exactly like the Bit type (where a value of \hs{True} corresponds to a
+ value of \hs{High}). Supporting the Bool type is particularly
+ useful to support \hs{if ... then ... else ...} expressions, which
+ always have a \hs{Bool} value for the condition.
+
+ A \hs{Bool} is translated to a \type{std_logic}, just like \hs{Bit}.
+ \stopdesc
+ \startdesc{\hs{SizedWord}, \hs{SizedInt}}
+ These are types to represent integers. A \hs{SizedWord} is unsigned,
+ while a \hs{SizedInt} is signed. These types are parameterized by a
+ length type, so you can define an unsigned word of 32 bits wide as
+ follows:
+
+ \starthaskell
+ type Word32 = SizedWord D32
+ \stophaskell
+
+ Here, a type synonym \hs{Word32} is defined that is equal to the
+ \hs{SizedWord} type constructor applied to the type \hs{D32}. \hs{D32}
+ is the \emph{type level representation} of the decimal number 32,
+ making the \hs{Word32} type a 32-bit unsigned word.
+
+ These types are translated to the \small{VHDL} \type{unsigned} and
+ \type{signed} respectively.
+ \todo{Sidenote on dependent typing?}
+ \stopdesc
+ \startdesc{\hs{Vector}}
+ This is a vector type, that can contain elements of any other type and
+ has a fixed length. It has two type parameters: Its
+ length and the type of the elements contained in it. By putting the
+ length parameter in the type, the length of a vector can be determined
+ at compile time, instead of only at runtime for conventional lists.
+
+ The \hs{Vector} type constructor takes two type arguments: The length
+ of the vector and the type of the elements contained in it. The state
+ type of an 8 element register bank would then for example be:
+
+ \starthaskell
+ type RegisterState = Vector D8 Word32
+ \stophaskell
+
+ Here, a type synonym \hs{RegisterState} is defined that is equal to
+ the \hs{Vector} type constructor applied to the types \hs{D8} (The type
+ level representation of the decimal number 8) and \hs{Word32} (The 32
+ bit word type as defined above). In other words, the
+ \hs{RegisterState} type is a vector of 8 32-bit words.
+
+ A fixed size vector is translated to a \small{VHDL} array type.
+ \stopdesc
+ \startdesc{\hs{RangedWord}}
+ This is another type to describe integers, but unlike the previous
+ two it has no specific bitwidth, but an upper bound. This means that
+ its range is not limited to powers of two, but can be any number.
+ A \hs{RangedWord} only has an upper bound, its lower bound is
+ implicitly zero. There is a lot of added implementation complexity
+ when adding a lower bound and having just an upper bound was enough
+ for the primary purpose of this type: Typesafely indexing vectors.
+
+ To define an index for the 8 element vector above, we would do:
+
+ \starthaskell
+ type RegisterIndex = RangedWord D7
+ \stophaskell
+
+ Here, a type synonym \hs{RegisterIndex} is defined that is equal to
+ the \hs{RangedWord} type constructor applied to the type \hs{D7}. In
+ other words, this defines an unsigned word with values from
+ {\definedfont[Serif*normalnum]0 to 7} (inclusive). This word can be be used to index the
+ 8 element vector \hs{RegisterState} above.
+
+ This type is translated to the \type{unsigned} \small{VHDL} type.
+ \stopdesc
+
+ The integer and vector built-in types are discussed in more detail
+ in \cite[baaij09].
+
+ \subsection{User-defined types}
+ There are three ways to define new types in Haskell: Algebraic
+ datatypes with the \hs{data} keyword, type synonyms with the \hs{type}
+ keyword and type renamings with the \hs{newtype} keyword. \GHC\
+ offers a few more advanced ways to introduce types (type families,
+ existential typing, \small{GADT}s, etc.) which are not standard
+ Haskell. These will be left outside the scope of this research.
+
+ Only an algebraic datatype declaration actually introduces a
+ completely new type, for which we provide the \VHDL\ translation
+ below. Type synonyms and renamings only define new names for
+ existing types (where synonyms are completely interchangeable and
+ renamings need explicit conversion). Therefore, these do not need
+ any particular \VHDL\ translation, a synonym or renamed type will
+ just use the same representation as the original type. The
+ distinction between a renaming and a synonym does no longer matter
+ in hardware and can be disregarded in the generated \VHDL.
+
+ For algebraic types, we can make the following distinction:
+
+ \startdesc{Product types}
+ A product type is an algebraic datatype with a single constructor with
+ two or more fields, denoted in practice like (a,b), (a,b,c), etc. This
+ is essentially a way to pack a few values together in a record-like
+ structure. In fact, the built-in tuple types are just algebraic product
+ types (and are thus supported in exactly the same way).
+
+ The \quote{product} in its name refers to the collection of values belonging
+ to this type. The collection for a product type is the Cartesian
+ product of the collections for the types of its fields.
+
+ These types are translated to \VHDL\ record types, with one field for
+ every field in the constructor. This translation applies to all single
+ constructor algebraic datatypes, including those with just one
+ field (which are technically not a product, but generate a VHDL
+ record for implementation simplicity).
+ \stopdesc
+ \startdesc{Enumerated types}
+ \defref{enumerated types}
+ An enumerated type is an algebraic datatype with multiple constructors, but
+ none of them have fields. This is essentially a way to get an
+ enum-like type containing alternatives.
+
+ Note that Haskell's \hs{Bool} type is also defined as an
+ enumeration type, but we have a fixed translation for that.
+
+ These types are translated to \VHDL\ enumerations, with one value for
+ each constructor. This allows references to these constructors to be
+ translated to the corresponding enumeration value.
+ \stopdesc
+ \startdesc{Sum types}
+ A sum type is an algebraic datatype with multiple constructors, where
+ the constructors have one or more fields. Technically, a type with
+ more than one field per constructor is a sum of products type, but
+ for our purposes this distinction does not really make a
+ difference, so this distinction is note made.
+
+ The \quote{sum} in its name refers again to the collection of values
+ belonging to this type. The collection for a sum type is the
+ union of the the collections for each of the constructors.
+
+ Sum types are currently not supported by the prototype, since there is
+ no obvious \VHDL\ alternative. They can easily be emulated, however, as
+ we will see from an example:
+
+ \starthaskell
+ data Sum = A Bit Word | B Word
+ \stophaskell
+
+ An obvious way to translate this would be to create an enumeration to
+ distinguish the constructors and then create a big record that
+ contains all the fields of all the constructors. This is the same
+ translation that would result from the following enumeration and
+ product type (using a tuple for clarity):
+
+ \starthaskell
+ data SumC = A | B
+ type Sum = (SumC, Bit, Word, Word)
+ \stophaskell
+
+ Here, the \hs{SumC} type effectively signals which of the latter three
+ fields of the \hs{Sum} type are valid (the first two if \hs{A}, the
+ last one if \hs{B}), all the other ones have no useful value.
+
+ An obvious problem with this naive approach is the space usage: The
+ example above generates a fairly big \VHDL\ type. Since we can be
+ sure that the two \hs{Word}s in the \hs{Sum} type will never be valid
+ at the same time, this is a waste of space.
+
+ Obviously, duplication detection could be used to reuse a
+ particular field for another constructor, but this would only
+ partially solve the problem. If two fields would be, for
+ example, an array of 8 bits and an 8 bit unsiged word, these are
+ different types and could not be shared. However, in the final
+ hardware, both of these types would simply be 8 bit connections,
+ so we have a 100\% size increase by not sharing these.
+ \stopdesc
+
+ Another interesting case is that of recursive types. In Haskell, an
+ algebraic datatype can be recursive: Any of its field types can be (or
+ contain) the type being defined. The most well-known recursive type is
+ probably the list type, which is defined is:
+
+ \starthaskell
+ data List t = Empty | Cons t (List t)
+ \stophaskell
+
+ Note that \hs{Empty} is usually written as \hs{[]} and \hs{Cons} as
+ \hs{:}, but this would make the definition harder to read. This
+ immediately shows the problem with recursive types: What hardware type
+ to allocate here?
+
+ If the naive approach for sum types described above would be used,
+ a record would be created where the first field is an enumeration
+ to distinguish \hs{Empty} from \hs{Cons}. Furthermore, two more
+ fields would be added: One with the (\VHDL\ equivalent of) type
+ \hs{t} (assuming this type is actually known at compile time, this
+ should not be a problem) and a second one with type \hs{List t}.
+ The latter one is of course a problem: This is exactly the type
+ that was to be translated in the first place.
+
+ The resulting \VHDL\ type will thus become infinitely deep. In
+ other words, there is no way to statically determine how long
+ (deep) the list will be (it could even be infinite).
+
+ In general, recursive types can never be properly translated: All
+ recursive types have a potentially infinite value (even though in
+ practice they will have a bounded value, there is no way for the
+ compiler to automatically determine an upper bound on its size).