+ TODO: Define top level function and subfunctions/circuits.
+
+ \section{Choice}
+ Since 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 case expressions, if expressions or
+ pattern matching (all of which can be reduced to case expressions).
+
+ 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. (TODO: Are
+ there other mechanisms of choice in hardware?)
+
+ However, to be able to describe our hardware in a more convenient way, we
+ also need to translate Haskell's choice mechanisms. The easiest of these
+ are of course case expressions (and if expressions, which can be very
+ directly translated to case expressions). A case expression can in turn
+ simply be translated to a conditional assignment, where the conditions use
+ equality comparisons against the constructors in the case expressions.
+
+ In \in{example}[ex:CaseInv] a simple case statement is shown,
+ scrutinizing a boolean value. 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 case statements. Optimizations such as these are left for the
+ \VHDL synthesizer, which handles them very well.
+
+ \startbuffer[CaseInv]
+ inv :: Bool -> Bool
+ inv in = case in 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
+
+ Slightly more complex (but very powerful) forms of choice are pattern
+ matches. 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.}
+ {\typebufferhs{CaseInv}}
+
+ The architecture described in \in{example}[ex:PatternInv] is of course the
+ same one as the one in \in{example}[ex:CaseInv]. The general interpration
+ of pattern matching is also similar to that of case expressions: Generate
+ hardware for each of the clause (like each of the clauses of a 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}
+ Apart from giving structure to our hardware, 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.
+
+ \subsection{Builtin types}
+ \startdesc{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)
+ \stopdesc
+ \startdesc{Bool}
+ This is a builtin Haskell type, but is translated exactly like the
+ Bit type. 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{SizedWord, SizedInt}
+ These are types to represent integers. \hs{SizedWord} is unsigned,
+ while \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, \hs{D32} is the \emph{type level representation} of the number
+ 32. TODO: Introduce dependent types somewhere.
+
+ These types are translated to the \small{VHDL} \type{unsigned} and
+ \type{signed} respectively.
+ \stopdesc
+ \startdesc{RangedWord}
+ This is another type to describe integers, but unlike the previous
+ two it has no specific width, 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.
+
+ This type is translated to the \type{unsigned} \small{VHDL} type.
+ \stopdesc
+ \startdesc{TFVec}
+ This is a vector type, with a fixed length. It has two type
+ parameters: Its length and the type of the elements contained in it.
+
+ A fixed size vector is translated to a \small{VHDL} array type.
+
+ The \hs{TF} in its name is a reference to the implementation used in
+ the prototype, which uses \emph{type families}.
+ \stopdesc
+
+ TODO: Reference Christiaan / describe dependent typing
+ \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
+ expclitely 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. This is essentially a way to pack a few values
+ together in a record-like structure. In fact, the builtin tuple types
+ are just 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 cartesic
+ 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}
+ 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 its
+ translation is not so obvious as before. The can easily be emulated,
+ 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 fields of
+ the \hs{Sum} type are valid, 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 a = Empty | Cons a (List a)
+ \stophaskell
+
+ Where \hs{Empty} is usually written as \hs{[]} and \hs{Cons} as \hs{:}.
+ This immediately shows the problem with recursive types: What hardware
+ type to allocate here? There is no way to statically determine how long
+ the list will be
+
+ In general, we can say we can never properly translated 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.
+
projects / matthijs / master-project / report.git / blobdiff