+ \note{This section should also mention hierarchy, top level functions and
+ subcircuits}
+
+ \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 or
+ pattern matching.
+
+ 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 multiplex (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 True = False
+ inv 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{CaseInv}}
+
+ 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}
+ We've seen the two most basic functional concepts translated to hardware:
+ Function application and choice. Before we look further into less obvious
+ concepts like higher order expressions and polymorphism, we will have a
+ look at the types of the values we use in our descriptions.
+
+ When working with values in our descriptions, we'll also need to provide
+ some way to translate the values used to hardware equivalents. In
+ particular, this means having to come up with a hardware equivalent for
+ every \emph{type} used in our program.
+
+ 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.), we will start out by defining a number of \quote{builtin}
+ types ourselves. These types are builtin 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 we sketch here.
+
+ \todo{Introduce Haskell type syntax (type constructors, type application,
+ :: operator?)}
+
+ \subsection{Builtin types}
+ The language currently supports the following builtin 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 builtin 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 Register = 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 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
+ \fxnote{There should be a reference to Christiaan's work here.}
+
+ \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. This
+ explicitly excludes more advanced type creation from \GHC extensions
+ such as type families, existential typing, \small{GADT}s, etc.
+
+ The first of these actually introduces a new type, for which we provide
+ the \VHDL translation below. The latter two only define new names for
+ existing types (where synonyms are completely interchangeable and
+ renamings need explicit conversion). Therefore, these don't need any
+ particular \VHDL translation, a synonym or renamed type will just use
+ the same representation as the equivalent type.
+
+ 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 builtin tuple types are just algebraic product
+ types (and are thus supported in exactly the same way).
+
+ The "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 no fields (unit
+ types) and just one field (which are technically not a product).
+ \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 we'll leave it out.
+
+ 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. However, we can be
+ sure that the two \hs{Word}s in the \hs{Sum} type will never be valid
+ at the same time, so this is a waste of space.
+
+ Obviously, we could do some duplication detection here to reuse a
+ particular field for another constructor, but this would only
+ partially solve the problem. If I would, for example, have an array of
+ 8 bits and a 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 we would use the naive approach for sum types we described above, we
+ would create a record where the first field is an enumeration to
+ distinguish \hs{Empty} from \hs{Cons}. Furthermore, we would add two
+ more fields: One with the (\VHDL equivalent of) type \hs{t} (assuming we
+ actually know what type this is 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 we were trying to translate
+ in the first place.
+
+ Our \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, we can say we can never properly translate recursive types:
+ 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 determine an upper bound on its size).
+