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.
+
\subsection{Partial application}
It should be obvious that we cannot generate hardware signals for all
expressions we can express in Haskell. The most obvious criterium for this
function boundaries), but eventually, the partial application will become
completely applied.
+ \section{Costless specialization}
+ Each (complete) function application in our description generates a
+ component instantiation, or a specific piece of hardware in the final
+ design. It is interesting to note that each application of a function
+ generates a \emph{separate} piece of hardware. In the final design, none
+ of the hardware is shared between applications, even when the applied
+ function is the same.
+
+ This is distinctly different from normal program compilation: Two separate
+ calls to the same function share the same machine code. Having more
+ machine code has implications for speed (due to less efficient caching)
+ and memory usage. For normal compilation, it is therefore important to
+ keep the amount of functions limited and maximize the code sharing.
+
+ When generating hardware, this is hardly an issue. Having more \quote{code
+ sharing} does reduce the amount of \small{VHDL} output (Since different
+ component instantiations still share the same component), but after
+ synthesis, the amount of hardware generated is not affected.
+
+ In particular, if we would duplicate all functions so that there is a
+ duplicate for every application in the program (\eg, each function is then
+ only applied exactly once), there would be no increase in hardware size
+ whatsoever.
+
+ TODO: Perhaps these next two sections are a bit too
+ implementation-oriented?
+
+ \subsection{Specialization}
+ Because of this, a common optimization technique called
+ \emph{specialization} is as good as free for hardware generation. Given
+ some function that has a \emph{domain} of $D$ (\eg, the set of all
+ possible arguments that could be applied), we create a specialized
+ function with exactly the same behaviour, but with an domain of $D'
+ \subset D$. This subset can be derived in all sort of ways, but commonly
+ this is done by limiting a polymorphic argument to a single type (\eg,
+ removing polymorphism) or by limiting an argument to just a single value
+ (\eg, cross-function constant propagation, effectively removing the
+ argument).
+
+ Since we limit the argument domain of the specialized function, its
+ definition can often be optimized further (since now more types or even
+ values of arguments are already know). By replacing any application of
+ the function that falls within the reduced domain by an application of
+ the specialized version, the code gets faster (but the code also gets
+ bigger, since we now have two versions instead of one!). If we apply
+ this technique often enough, we can often replace all applications of a
+ function by specialized versions, allowing the original function to be
+ removed (in some cases, this can even give a net reduction of the code
+ compared to the non-specialized version).
+
+ Specialization is useful for our hardware descriptions for functions
+ that contain arguments that cannot be translated to hardware directly
+ (polymorphic or higher order arguments, for example). If we can create
+ specialized functions that remove the argument, or make it translatable,
+ we can use specialization to make the original, untranslatable, function
+ obsolete.
+
+ \section{Higher order values}
+ What holds for partial application, can be easily generalized to any
+ higher order expression. This includes partial applications, plain
+ variables (e.g., a binder referring to a top level function), lambda
+ expressions and more complex expressions with a function type (a case
+ expression returning lambda's, for example).
+
+ Each of these values cannot be directly represented in hardware (just like
+ partial applications). Also, to make them representable, they need to be
+ applied: function variables and partial applications will then eventually
+ become complete applications, applied lambda expressions disappear by
+ applying β-reduction, etc.
+
+ So any higher order value will be \quote{pushed down} towards its
+ application just like partial applications. Whenever a function boundary
+ needs to be crossed, the called function can be specialized.
+
+ TODO: This is section should be improved
+
+ \section{Polymorphism}
+ In Haskell, values can be polymorphic: They can have multiple types. For
+ example, the function \hs{fst :: (a, b) -> a} is an example of a
+ polymorphic function: It works for tuples with any element types. Haskell
+ typeclasses allow a function to work on a specific set of types, but the
+ general idea is the same.
+
+% A type class is a collection of types for which some operations are
+% defined. It is thus possible for a value to be polymorphic while having
+% any number of \emph{class constraints}: The value is not defined for
+% every type, but only for types in the type class. An example of this is
+% the \hs{even :: (Integral a) => a -> Bool} function, which can map any
+% value of a type that is member of the \hs{Integral} type class
+
+ When generating hardware, polymorphism can't be easily translated. How
+ many wire will you lay down for a value that could have any type? When
+ type classes are involved, what hardware components will you lay down for
+ a class method (whose behaviour depends on the type of its arguments)?
+
+ Fortunately, we can again use the principle of specialization: Since every
+ function application generates separate pieces of hardware, we can know
+ the types of all arguments exactly. Provided that we don't use existential
+ typing, all of the polymorphic types in a function must depend on the
+ types of the arguments (In other words, the only way to introduce a type
+ variable is in a lambda abstraction). Our top level function must not have
+ a polymorphic type (otherwise we wouldn't know the hardware interface to
+ our top level function).
+
+ If a function is monomorphic, all values inside it are monomorphic as
+ well, so any function that is applied within the function can only be
+ applied to monomorphic values. The applied functions can then be
+ specialized to work just for these specific types, removing the
+ polymorphism from the applied functions as well.
+
+ By induction, this means that all functions that are (indirectly) called
+ by our top level function (meaning all functions that are translated in
+ the final hardware) become monomorphic.
+
\section{State}
A very important concept in hardware designs is \emph{state}. In a
stateless (or, \emph{combinatoric}) design, every output is a directly and solely dependent on the
implemented in Cλash. \in{Section}[sec:prototype:statetype] expands on
the possible ways this could have been implemented.
+ TODO: Say something about dependent types and fixed size vectors
+
\section[sec:recursion]{Recursion}
An import concept in functional languages is recursion. In it's most basic
form, recursion is a function that is defined in terms of itself. This
projects / matthijs / master-project / report.git / blobdiff