Restructure some of the normalization chapter.
[matthijs/master-project/report.git] / Chapters / HardwareDescription.tex
1 \chapter[chap:description]{Hardware description}
2   This chapter will provide an overview of the hardware description language
3   that was created and the issues that have arisen in the process. It will
4   focus on the issues of the language, not the implementation. The prototype
5   implementation will be discussed in \in{chapter}[chap:prototype].
6
7   \todo{Shortshort introduction to Cλash (Bit, Word, and, not, etc.)}
8
9   When translating Haskell to hardware, we need to make choices about what kind
10   of hardware to generate for which Haskell constructs. When faced with
11   choices, we've tried to stick with the most obvious choice wherever
12   possible. In a lot of cases, when you look at a hardware description it is
13   comletely clear what hardware is described. We want our translator to
14   generate exactly that hardware whenever possible, to minimize the amount of
15   surprise for people working with it.
16    
17   In this chapter we try to describe how we interpret a Haskell program from a
18   hardware perspective. We provide a description of each Haskell language
19   element that needs translation, to provide a clear picture of what is
20   supported and how.
21
22   \section[sec:description:application]{Function application}
23   \todo{Sidenote: Inputs vs arguments}
24   The basic syntactic element of a functional program are functions and
25   function application. These have a single obvious \small{VHDL} translation: Each
26   function becomes a hardware component, where each argument is an input port
27   and the result value is the (single) output port. This output port can have
28   a complex type (such as a tuple), so having just a single output port does
29   not pose a limitation.
30
31   Each function application in turn becomes component instantiation. Here, the
32   result of each argument expression is assigned to a signal, which is mapped
33   to the corresponding input port. The output port of the function is also
34   mapped to a signal, which is used as the result of the application.
35
36   \in{Example}[ex:And3] shows a simple program using only function
37   application and the corresponding architecture.
38
39 \startbuffer[And3]
40 -- | A simple function that returns 
41 --   conjunction of three bits
42 and3 :: Bit -> Bit -> Bit -> Bit
43 and3 a b c = and (and a b) c
44 \stopbuffer
45
46 \todo{Mirror this image vertically}
47   \startuseMPgraphic{And3}
48     save a, b, c, anda, andb, out;
49
50     % I/O ports
51     newCircle.a(btex $a$ etex) "framed(false)";
52     newCircle.b(btex $b$ etex) "framed(false)";
53     newCircle.c(btex $c$ etex) "framed(false)";
54     newCircle.out(btex $out$ etex) "framed(false)";
55
56     % Components
57     newCircle.anda(btex $and$ etex);
58     newCircle.andb(btex $and$ etex);
59
60     a.c    = origin;
61     b.c    = a.c + (0cm, 1cm);
62     c.c    = b.c + (0cm, 1cm);
63     anda.c = midpoint(a.c, b.c) + (2cm, 0cm);
64     andb.c = midpoint(b.c, c.c) + (4cm, 0cm);
65
66     out.c   = andb.c + (2cm, 0cm);
67
68     % Draw objects and lines
69     drawObj(a, b, c, anda, andb, out);
70
71     ncarc(a)(anda) "arcangle(-10)";
72     ncarc(b)(anda);
73     ncarc(anda)(andb);
74     ncarc(c)(andb);
75     ncline(andb)(out);
76   \stopuseMPgraphic
77
78   \placeexample[here][ex:And3]{Simple three input and gate.}
79     \startcombination[2*1]
80       {\typebufferhs{And3}}{Haskell description using function applications.}
81       {\boxedgraphic{And3}}{The architecture described by the Haskell description.}
82     \stopcombination
83
84   \note{This section should also mention hierarchy, top level functions and
85   subcircuits}
86
87   \section{Choice}
88     Although describing components and connections allows us to describe a lot of
89     hardware designs already, there is an obvious thing missing: Choice. We
90     need some way to be able to choose between values based on another value.
91     In Haskell, choice is achieved by \hs{case} expressions, \hs{if} expressions or
92     pattern matching.
93
94     An obvious way to add choice to our language without having to recognize
95     any of Haskell's syntax, would be to add a primivite \quote{\hs{if}}
96     function. This function would take three arguments: The condition, the
97     value to return when the condition is true and the value to return when
98     the condition is false.
99
100     This \hs{if} function would then essentially describe a multiplexer and
101     allows us to describe any architecture that uses multiplexers. \fxnote{Are
102     there other mechanisms of choice in hardware?}
103
104     However, to be able to describe our hardware in a more convenient way, we
105     also want to translate Haskell's choice mechanisms. The easiest of these
106     are of course case expressions (and \hs{if} expressions, which can be very
107     directly translated to \hs{case} expressions). A \hs{case} expression can in turn
108     simply be translated to a conditional assignment, where the conditions use
109     equality comparisons against the constructors in the \hs{case} expressions.
110
111     \todo{Assignment vs multiplexers}
112
113     In \in{example}[ex:CaseInv] a simple \hs{case} expression is shown,
114     scrutinizing a boolean value. The corresponding architecture has a
115     comparator to determine which of the constructors is on the \hs{in}
116     input. There is a multiplexer to select the output signal. The two options
117     for the output signals are just constants, but these could have been more
118     complex expressions (in which case also both of them would be working in
119     parallel, regardless of which output would be chosen eventually).
120     
121     If we would translate a Boolean to a bit value, we could of course remove
122     the comparator and directly feed 'in' into the multiplex (or even use an
123     inverter instead of a multiplexer).  However, we will try to make a
124     general translation, which works for all possible \hs{case} expressions.
125     Optimizations such as these are left for the \VHDL synthesizer, which
126     handles them very well.
127
128     \todo{Be more explicit about >2 alternatives}
129
130     \startbuffer[CaseInv]
131     inv :: Bool -> Bool
132     inv True  = False
133     inv False = True
134     \stopbuffer
135
136     \startuseMPgraphic{CaseInv}
137       save in, truecmp, falseout, trueout, out, cmp, mux;
138
139       % I/O ports
140       newCircle.in(btex $in$ etex) "framed(false)";
141       newCircle.out(btex $out$ etex) "framed(false)";
142       % Constants
143       newBox.truecmp(btex $True$ etex) "framed(false)";
144       newBox.trueout(btex $True$ etex) "framed(false)";
145       newBox.falseout(btex $False$ etex) "framed(false)";
146
147       % Components
148       newCircle.cmp(btex $==$ etex);
149       newMux.mux;
150
151       in.c       = origin;
152       cmp.c      = in.c + (3cm, 0cm);
153       truecmp.c  = cmp.c + (-1cm, 1cm);
154       mux.sel    = cmp.e + (1cm, -1cm);
155       falseout.c = mux.inpa - (2cm, 0cm);
156       trueout.c  = mux.inpb - (2cm, 0cm);
157       out.c      = mux.out + (2cm, 0cm);
158
159       % Draw objects and lines
160       drawObj(in, out, truecmp, trueout, falseout, cmp, mux);
161
162       ncline(in)(cmp);
163       ncarc(truecmp)(cmp);
164       nccurve(cmp.e)(mux.sel) "angleA(0)", "angleB(-90)";
165       ncline(falseout)(mux) "posB(inpa)";
166       ncline(trueout)(mux) "posB(inpb)";
167       ncline(mux)(out) "posA(out)";
168     \stopuseMPgraphic
169
170     \placeexample[here][ex:CaseInv]{Simple inverter.}
171       \startcombination[2*1]
172         {\typebufferhs{CaseInv}}{Haskell description using a Case expression.}
173         {\boxedgraphic{CaseInv}}{The architecture described by the Haskell description.}
174       \stopcombination
175
176     A slightly more complex (but very powerful) form of choice is pattern
177     matching. A function can be defined in multiple clauses, where each clause
178     specifies a pattern. When the arguments match the pattern, the
179     corresponding clause will be used.
180
181     \startbuffer[PatternInv]
182     inv :: Bool -> Bool
183     inv True = False
184     inv False = True
185     \stopbuffer
186
187     \placeexample[here][ex:PatternInv]{Simple inverter using pattern matching.
188     Describes the same architecture as \in{example}[ex:CaseInv].}
189         {\typebufferhs{CaseInv}}
190
191     The architecture described by \in{example}[ex:PatternInv] is of course the
192     same one as the one in \in{example}[ex:CaseInv]. The general interpretation
193     of pattern matching is also similar to that of \hs{case} expressions: Generate
194     hardware for each of the clauses (like each of the clauses of a \hs{case}
195     expression) and connect them to the function output through (a number of
196     nested) multiplexers. These multiplexers are driven by comparators and
197     other logic, that check each pattern in turn.
198
199   \section{Types}
200     We've seen the two most basic functional concepts translated to hardware:
201     Function application and choice. Before we look further into less obvious
202     concepts like higher order expressions and polymorphism, we will have a
203     look at the types of the values we use in our descriptions.
204
205     When working with values in our descriptions, we'll also need to provide
206     some way to translate the values used to hardware equivalents. In
207     particular, this means having to come up with a hardware equivalent for
208     every \emph{type} used in our program.
209
210     Since most functional languages have a lot of standard types that are
211     hard to translate (integers without a fixed size, lists without a static
212     length, etc.), we will start out by defining a number of \quote{builtin}
213     types ourselves. These types are builtin in the sense that our compiler
214     will have a fixed VHDL type for these. User defined types, on the other
215     hand, will have their hardware type derived directly from their Haskell
216     declaration automatically, according to the rules we sketch here.
217
218     \todo{Introduce Haskell type syntax (type constructors, type application,
219     :: operator?)}
220
221     \subsection{Builtin types}
222       The language currently supports the following builtin types. Of these,
223       only the \hs{Bool} type is supported by Haskell out of the box (the
224       others are defined by the Cλash package, so they are user-defined types
225       from Haskell's point of view).
226
227       \startdesc{\hs{Bit}}
228         This is the most basic type available. It is mapped directly onto
229         the \type{std_logic} \small{VHDL} type. Mapping this to the
230         \type{bit} type might make more sense (since the Haskell version
231         only has two values), but using \type{std_logic} is more standard
232         (and allowed for some experimentation with don't care values)
233
234         \todo{Sidenote bit vs stdlogic}
235       \stopdesc
236       \startdesc{\hs{Bool}}
237         This is the only builtin Haskell type supported and is translated
238         exactly like the Bit type (where a value of \hs{True} corresponds to a
239         value of \hs{High}). Supporting the Bool type is particularly
240         useful to support \hs{if ... then ... else ...} expressions, which
241         always have a \hs{Bool} value for the condition.
242
243         A \hs{Bool} is translated to a \type{std_logic}, just like \hs{Bit}.
244       \stopdesc
245       \startdesc{\hs{SizedWord}, \hs{SizedInt}}
246         These are types to represent integers. A \hs{SizedWord} is unsigned,
247         while a \hs{SizedInt} is signed. These types are parameterized by a
248         length type, so you can define an unsigned word of 32 bits wide as
249         follows:
250         
251         \starthaskell
252           type Word32 = SizedWord D32
253         \stophaskell
254
255         Here, a type synonym \hs{Word32} is defined that is equal to the
256         \hs{SizedWord} type constructor applied to the type \hs{D32}. \hs{D32}
257         is the \emph{type level representation} of the decimal number 32,
258         making the \hs{Word32} type a 32-bit unsigned word.
259
260         These types are translated to the \small{VHDL} \type{unsigned} and
261         \type{signed} respectively.
262         \todo{Sidenote on dependent typing?}
263       \stopdesc
264       \startdesc{\hs{Vector}}
265         This is a vector type, that can contain elements of any other type and
266         has a fixed length. It has two type parameters: Its
267         length and the type of the elements contained in it. By putting the
268         length parameter in the type, the length of a vector can be determined
269         at compile time, instead of only at runtime for conventional lists.
270
271         The \hs{Vector} type constructor takes two type arguments: The length
272         of the vector and the type of the elements contained in it. The state
273         type of an 8 element register bank would then for example be:
274
275         \starthaskell
276         type RegisterState = Vector D8 Word32
277         \stophaskell
278
279         Here, a type synonym \hs{RegisterState} is defined that is equal to
280         the \hs{Vector} type constructor applied to the types \hs{D8} (The type
281         level representation of the decimal number 8) and \hs{Word32} (The 32
282         bit word type as defined above). In other words, the
283         \hs{RegisterState} type is a vector of 8 32-bit words.
284
285         A fixed size vector is translated to a \small{VHDL} array type.
286       \stopdesc
287       \startdesc{\hs{RangedWord}}
288         This is another type to describe integers, but unlike the previous
289         two it has no specific bitwidth, but an upper bound. This means that
290         its range is not limited to powers of two, but can be any number.
291         A \hs{RangedWord} only has an upper bound, its lower bound is
292         implicitly zero. There is a lot of added implementation complexity
293         when adding a lower bound and having just an upper bound was enough
294         for the primary purpose of this type: Typesafely indexing vectors.
295
296         To define an index for the 8 element vector above, we would do:
297
298         \starthaskell
299         type Register = RangedWord D7
300         \stophaskell
301
302         Here, a type synonym \hs{RegisterIndex} is defined that is equal to
303         the \hs{RangedWord} type constructor applied to the type \hs{D7}. In
304         other words, this defines an unsigned word with values from 0 to 7
305         (inclusive). This word can be be used to index the 8 element vector
306         \hs{RegisterState} above.
307
308         This type is translated to the \type{unsigned} \small{VHDL} type.
309       \stopdesc
310       \fxnote{There should be a reference to Christiaan's work here.}
311
312     \subsection{User-defined types}
313       There are three ways to define new types in Haskell: Algebraic
314       datatypes with the \hs{data} keyword, type synonyms with the \hs{type}
315       keyword and type renamings with the \hs{newtype} keyword. This
316       explicitly excludes more advanced type creation from \GHC extensions
317       such as type families, existential typing, \small{GADT}s, etc.
318
319       The first of these actually introduces a new type, for which we provide
320       the \VHDL translation below. The latter two only define new names for
321       existing types (where synonyms are completely interchangeable and
322       renamings need explicit conversion). Therefore, these don't need any
323       particular \VHDL translation, a synonym or renamed type will just use
324       the same representation as the equivalent type.
325
326       For algebraic types, we can make the following distinction:
327
328       \startdesc{Product types}
329         A product type is an algebraic datatype with a single constructor with
330         two or more fields, denoted in practice like (a,b), (a,b,c), etc. This
331         is essentially a way to pack a few values together in a record-like
332         structure. In fact, the builtin tuple types are just algebraic product
333         types (and are thus supported in exactly the same way).
334
335         The "product" in its name refers to the collection of values belonging
336         to this type. The collection for a product type is the cartesian
337         product of the collections for the types of its fields.
338
339         These types are translated to \VHDL, record types, with one field for
340         every field in the constructor. This translation applies to all single
341         constructor algebraic datatypes, including those with no fields (unit
342         types) and just one field (which are technically not a product).
343       \stopdesc
344       \startdesc{Enumerated types}
345         An enumerated type is an algebraic datatype with multiple constructors, but
346         none of them have fields. This is essentially a way to get an
347         enum-like type containing alternatives.
348
349         Note that Haskell's \hs{Bool} type is also defined as an
350         enumeration type, but we have a fixed translation for that.
351         
352         These types are translated to \VHDL enumerations, with one value for
353         each constructor. This allows references to these constructors to be
354         translated to the corresponding enumeration value.
355       \stopdesc
356       \startdesc{Sum types}
357         A sum type is an algebraic datatype with multiple constructors, where
358         the constructors have one or more fields. Technically, a type with
359         more than one field per constructor is a sum of products type, but
360         for our purposes this distinction does not really make a difference,
361         so we'll leave it out.
362
363         Sum types are currently not supported by the prototype, since there is
364         no obvious \VHDL alternative. They can easily be emulated, however, as
365         we will see from an example:
366
367         \starthaskell
368         data Sum = A Bit Word | B Word 
369         \stophaskell
370
371         An obvious way to translate this would be to create an enumeration to
372         distinguish the constructors and then create a big record that
373         contains all the fields of all the constructors. This is the same
374         translation that would result from the following enumeration and
375         product type (using a tuple for clarity):
376
377         \starthaskell
378         data SumC = A | B
379         type Sum = (SumC, Bit, Word, Word)
380         \stophaskell
381
382         Here, the \hs{SumC} type effectively signals which of the latter three
383         fields of the \hs{Sum} type are valid (the first two if \hs{A}, the
384         last one if \hs{B}), all the other ones have no useful value.
385
386         An obvious problem with this naive approach is the space usage: The
387         example above generates a fairly big \VHDL type. However, we can be
388         sure that the two \hs{Word}s in the \hs{Sum} type will never be valid
389         at the same time, so this is a waste of space.
390
391         Obviously, we could do some duplication detection here to reuse a
392         particular field for another constructor, but this would only
393         partially solve the problem. If I would, for example, have an array of
394         8 bits and a 8 bit unsiged word, these are different types and could
395         not be shared. However, in the final hardware, both of these types
396         would simply be 8 bit connections, so we have a 100\% size increase by
397         not sharing these.
398       \stopdesc
399
400       Another interesting case is that of recursive types. In Haskell, an
401       algebraic datatype can be recursive: Any of its field types can be (or
402       contain) the type being defined. The most well-known recursive type is
403       probably the list type, which is defined is:
404       
405       \starthaskell
406       data List t = Empty | Cons t (List t)
407       \stophaskell
408
409       Note that \hs{Empty} is usually written as \hs{[]} and \hs{Cons} as
410       \hs{:}, but this would make the definition harder to read.  This
411       immediately shows the problem with recursive types: What hardware type
412       to allocate here? 
413       
414       If we would use the naive approach for sum types we described above, we
415       would create a record where the first field is an enumeration to
416       distinguish \hs{Empty} from \hs{Cons}. Furthermore, we would add two
417       more fields: One with the (\VHDL equivalent of) type \hs{t} (assuming we
418       actually know what type this is at compile time, this should not be a
419       problem) and a second one with type \hs{List t}.  The latter one is of
420       course a problem: This is exactly the type we were trying to translate
421       in the first place. 
422       
423       Our \VHDL type will thus become infinitely deep. In other words, there
424       is no way to statically determine how long (deep) the list will be
425       (it could even be infinite).
426       
427       In general, we can say we can never properly translate recursive types:
428       All recursive types have a potentially infinite value (even though in
429       practice they will have a bounded value, there is no way for the
430       compiler to determine an upper bound on its size).
431
432   \subsection{Partial application}
433   Now we've seen how to to translate application, choice and types, we will
434   get to a more complex concept: Partial applications. A \emph{partial
435   application} is any application whose (return) type is (again) a function
436   type.
437
438   From this, we can see that the translation rules for full application do not
439   apply to a partial application. \in{Example}[ex:Quadruple] shows an example
440   use of partial application and the corresponding architecture.
441
442 \startbuffer[Quadruple]
443 -- | Multiply the input word by four.
444 quadruple :: Word -> Word
445 quadruple n = mul (mul n)
446   where
447     mul = (*) 2
448 \stopbuffer
449
450   \startuseMPgraphic{Quadruple}
451     save in, two, mula, mulb, out;
452
453     % I/O ports
454     newCircle.in(btex $n$ etex) "framed(false)";
455     newCircle.two(btex $2$ etex) "framed(false)";
456     newCircle.out(btex $out$ etex) "framed(false)";
457
458     % Components
459     newCircle.mula(btex $\times$ etex);
460     newCircle.mulb(btex $\times$ etex);
461
462     two.c    = origin;
463     in.c     = two.c + (0cm, 1cm);
464     mula.c  = in.c + (2cm, 0cm);
465     mulb.c  = mula.c + (2cm, 0cm);
466     out.c   = mulb.c + (2cm, 0cm);
467
468     % Draw objects and lines
469     drawObj(in, two, mula, mulb, out);
470
471     nccurve(two)(mula) "angleA(0)", "angleB(45)";
472     nccurve(two)(mulb) "angleA(0)", "angleB(45)";
473     ncline(in)(mula);
474     ncline(mula)(mulb);
475     ncline(mulb)(out);
476   \stopuseMPgraphic
477
478   \placeexample[here][ex:Quadruple]{Simple three port and.}
479     \startcombination[2*1]
480       {\typebufferhs{Quadruple}}{Haskell description using function applications.}
481       {\boxedgraphic{Quadruple}}{The architecture described by the Haskell description.}
482     \stopcombination
483
484   Here, the definition of mul is a partial function application: It applies
485   the function \hs{(*) :: Word -> Word -> Word} to the value \hs{2 :: Word},
486   resulting in the expression \hs{(*) 2 :: Word -> Word}. Since this resulting
487   expression is again a function, we can't generate hardware for it directly.
488   This is because the hardware to generate for \hs{mul} depends completely on
489   where and how it is used. In this example, it is even used twice.
490
491   However, it is clear that the above hardware description actually describes
492   valid hardware. In general, we can see that any partial applied function
493   must eventually become completely applied, at which point we can generate
494   hardware for it using the rules for function application given in
495   \in{section}[sec:description:application]. It might mean that a partial
496   application is passed around quite a bit (even beyond function boundaries),
497   but eventually, the partial application will become completely applied.
498   \todo{Provide a step-by-step example of how this works}
499
500   \section{Costless specialization}
501     Each (complete) function application in our description generates a
502     component instantiation, or a specific piece of hardware in the final
503     design. It is interesting to note that each application of a function
504     generates a \emph{separate} piece of hardware. In the final design, none
505     of the hardware is shared between applications, even when the applied
506     function is the same (of course, if a particular value, such as the result
507     of a function application, is used twice, it is not calculated twice).
508
509     This is distinctly different from normal program compilation: Two separate
510     calls to the same function share the same machine code. Having more
511     machine code has implications for speed (due to less efficient caching)
512     and memory usage. For normal compilation, it is therefore important to
513     keep the amount of functions limited and maximize the code sharing.
514
515     When generating hardware, this is hardly an issue. Having more \quote{code
516     sharing} does reduce the amount of \small{VHDL} output (Since different
517     component instantiations still share the same component), but after
518     synthesis, the amount of hardware generated is not affected.
519
520     In particular, if we would duplicate all functions so that there is a
521     separate function for every application in the program (\eg, each function
522     is then only applied exactly once), there would be no increase in hardware
523     size whatsoever.
524     
525     Because of this, a common optimization technique called
526     \emph{specialization} can be applied to hardware generation without any
527     performance or area cost (unlike for software). 
528    
529    \fxnote{Perhaps these next three sections are a bit too
530    implementation-oriented?}
531
532     \subsection{Specialization}
533       \defref{specialization}
534       Given some function that has a \emph{domain} $D$ (\eg, the set of all
535       possible arguments that could be applied), we create a specialized
536       function with exactly the same behaviour, but with a domain $D' \subset
537       D$. This subset can be chosen in all sorts of ways. Any subset is valid
538       for the general definition of specialization, but in practice only some
539       of them provide useful optimization opportunities.
540
541       Common subsets include limiting a polymorphic argument to a single type
542       (\ie, removing polymorphism) or limiting an argument to just a single
543       value (\ie, cross-function constant propagation, effectively removing
544       the argument). 
545       
546       Since we limit the argument domain of the specialized function, its
547       definition can often be optimized further (since now more types or even
548       values of arguments are already known). By replacing any application of
549       the function that falls within the reduced domain by an application of
550       the specialized version, the code gets faster (but the code also gets
551       bigger, since we now have two versions instead of one). If we apply
552       this technique often enough, we can often replace all applications of a
553       function by specialized versions, allowing the original function to be
554       removed (in some cases, this can even give a net reduction of the code
555       compared to the non-specialized version).
556
557       Specialization is useful for our hardware descriptions for functions
558       that contain arguments that cannot be translated to hardware directly
559       (polymorphic or higher order arguments, for example). If we can create
560       specialized functions that remove the argument, or make it translatable,
561       we can use specialization to make the original, untranslatable, function
562       obsolete.
563
564   \section{Higher order values}
565     What holds for partial application, can be easily generalized to any
566     higher order expression. This includes partial applications, plain
567     variables (e.g., a binder referring to a top level function), lambda
568     expressions and more complex expressions with a function type (a \hs{case}
569     expression returning lambda's, for example).
570
571     Each of these values cannot be directly represented in hardware (just like
572     partial applications). Also, to make them representable, they need to be
573     applied: function variables and partial applications will then eventually
574     become complete applications, applied lambda expressions disappear by
575     applying β-reduction, etc.
576
577     So any higher order value will be \quote{pushed down} towards its
578     application just like partial applications. Whenever a function boundary
579     needs to be crossed, the called function can be specialized.
580     
581     \fxnote{This section needs improvement and an example}
582
583   \section{Polymorphism}
584     In Haskell, values can be \emph{polymorphic}: They can have multiple types. For
585     example, the function \hs{fst :: (a, b) -> a} is an example of a
586     polymorphic function: It works for tuples with any two element types. Haskell
587     typeclasses allow a function to work on a specific set of types, but the
588     general idea is the same. The opposite of this is a \emph{monomorphic}
589     value, which has a single, fixed, type.
590
591 %    A type class is a collection of types for which some operations are
592 %    defined. It is thus possible for a value to be polymorphic while having
593 %    any number of \emph{class constraints}: The value is not defined for
594 %    every type, but only for types in the type class. An example of this is
595 %    the \hs{even :: (Integral a) => a -> Bool} function, which can map any
596 %    value of a type that is member of the \hs{Integral} type class 
597
598     When generating hardware, polymorphism can't be easily translated. How
599     many wires will you lay down for a value that could have any type? When
600     type classes are involved, what hardware components will you lay down for
601     a class method (whose behaviour depends on the type of its arguments)?
602     Note that the language currently does not allow user-defined typeclasses,
603     but does support partly some of the builtin typeclasses (like \hs{Num}).
604
605     Fortunately, we can again use the principle of specialization: Since every
606     function application generates a separate piece of hardware, we can know
607     the types of all arguments exactly. Provided that we don't use existential
608     typing, all of the polymorphic types in a function must depend on the
609     types of the arguments (In other words, the only way to introduce a type
610     variable is in a lambda abstraction).
611
612     If a function is monomorphic, all values inside it are monomorphic as
613     well, so any function that is applied within the function can only be
614     applied to monomorphic values. The applied functions can then be
615     specialized to work just for these specific types, removing the
616     polymorphism from the applied functions as well.
617
618     Our top level function must not have a polymorphic type (otherwise we
619     wouldn't know the hardware interface to our top level function).
620
621     By induction, this means that all functions that are (indirectly) called
622     by our top level function (meaning all functions that are translated in
623     the final hardware) become monomorphic.
624
625   \section{State}
626     A very important concept in hardware designs is \emph{state}. In a
627     stateless (or, \emph{combinatoric}) design, every output is  directly and solely dependent on the
628     inputs. In a stateful design, the outputs can depend on the history of
629     inputs, or the \emph{state}. State is usually stored in \emph{registers},
630     which retain their value during a clockcycle, and are typically updated at
631     the start of every clockcycle. Since the updating of the state is tightly
632     coupled (synchronized) to the clock signal, these state updates are often
633     called \emph{synchronous} behaviour.
634
635     \todo{Sidenote? Registers can contain any (complex) type}
636   
637     To make our hardware description language useful to describe more than
638     simple combinatoric designs, we'll need to be able to describe state in
639     some way.
640
641     \subsection{Approaches to state}
642       In Haskell, functions are always pure (except when using unsafe
643       functions with the \hs{IO} monad, which is not supported by Cλash). This
644       means that the output of a function solely depends on its inputs. If you
645       evaluate a given function with given inputs, it will always provide the
646       same output.
647
648       \todo{Define pure}
649
650       This is a perfect match for a combinatoric circuit, where the output
651       also soley depends on the inputs. However, when state is involved, this
652       no longer holds. Since we're in charge of our own language (or at least
653       let's pretend we aren't using Haskell and we are), we could remove this
654       purity constraint and allow a function to return different values
655       depending on the cycle in which it is evaluated (or rather, the current
656       state). However, this means that all kinds of interesting properties of
657       our functional language get lost, and all kinds of transformations and
658       optimizations might no longer be meaning preserving.
659
660       Provided that we want to keep the function pure, the current state has
661       to be present in the function's arguments in some way. There seem to be
662       two obvious ways to do this: Adding the current state as an argument, or
663       including the full history of each argument.
664
665       \subsubsection{Stream arguments and results}
666         Including the entire history of each input (\eg, the value of that
667         input for each previous clockcycle) is an obvious way to make outputs
668         depend on all previous input. This is easily done by making every
669         input a list instead of a single value, containing all previous values
670         as well as the current value.
671
672         An obvious downside of this solution is that on each cycle, all the
673         previous cycles must be resimulated to obtain the current state. To do
674         this, it might be needed to have a recursive helper function as well,
675         wich might be hard to be properly analyzed by the compiler.
676
677         A slight variation on this approach is one taken by some of the other
678         functional \small{HDL}s in the field: \todo{References to Lava,
679         ForSyDe, ...} Make functions operate on complete streams. This means
680         that a function is no longer called on every cycle, but just once. It
681         takes stream as inputs instead of values, where each stream contains
682         all the values for every clockcycle since system start. This is easily
683         modeled using an (infinite) list, with one element for each clock
684         cycle. Since the function is only evaluated once, its output must also
685         be a stream. Note that, since we are working with infinite lists and
686         still want to be able to simulate the system cycle-by-cycle, this
687         relies heavily on the lazy semantics of Haskell.
688
689         Since our inputs and outputs are streams, all other (intermediate)
690         values must be streams. All of our primitive operators (\eg, addition,
691         substraction, bitwise operations, etc.) must operate on streams as
692         well (note that changing a single-element operation to a stream
693         operation can done with \hs{map}, \hs{zipwith}, etc.).
694
695         Note that the concept of \emph{state} is no more than having some way
696         to communicate a value from one cycle to the next. By introducing a
697         \hs{delay} function, we can do exactly that: Delay (each value in) a
698         stream so that we can "look into" the past. This \hs{delay} function
699         simply outputs a stream where each value is the same as the input
700         value, but shifted one cycle. This causes a \quote{gap} at the
701         beginning of the stream: What is the value of the delay output in the
702         first cycle? For this, the \hs{delay} function has a second input
703         (which is a value, not a stream!).
704
705         \in{Example}[ex:DelayAcc] shows a simple accumulator expressed in this
706         style.
707
708 \startbuffer[DelayAcc]
709 acc :: Stream Word -> Stream Word
710 acc in = out
711   where
712     out = (delay out 0) + in
713 \stopbuffer
714
715 \startuseMPgraphic{DelayAcc}
716   save in, out, add, reg;
717
718   % I/O ports
719   newCircle.in(btex $in$ etex) "framed(false)";
720   newCircle.out(btex $out$ etex) "framed(false)";
721
722   % Components
723   newReg.reg("") "dx(4mm)", "dy(6mm)", "reflect(true)";
724   newCircle.add(btex + etex);
725   
726   in.c    = origin;
727   add.c   = in.c + (2cm, 0cm);
728   out.c   = add.c + (2cm, 0cm);
729   reg.c   = add.c + (0cm, 2cm);
730
731   % Draw objects and lines
732   drawObj(in, out, add, reg);
733
734   nccurve(add)(reg) "angleA(0)", "angleB(180)", "posB(d)";
735   nccurve(reg)(add) "angleA(180)", "angleB(-45)", "posA(out)";
736   ncline(in)(add);
737   ncline(add)(out);
738 \stopuseMPgraphic
739
740
741         \placeexample[here][ex:DelayAcc]{Simple accumulator architecture.}
742           \startcombination[2*1]
743             {\typebufferhs{DelayAcc}}{Haskell description using streams.}
744             {\boxedgraphic{DelayAcc}}{The architecture described by the Haskell description.}
745           \stopcombination
746
747
748         This notation can be confusing (especially due to the loop in the
749         definition of out), but is essentially easy to interpret. There is a
750         single call to delay, resulting in a circuit with a single register,
751         whose input is connected to \hs{out} (which is the output of the
752         adder), and it's output is the expression \hs{delay out 0} (which is
753         connected to one of the adder inputs).
754
755         This notation has a number of downsides, amongst which are limited
756         readability and ambiguity in the interpretation. \note{Reference
757         Christiaan, who has done further investigation}
758         
759       \subsubsection{Explicit state arguments and results}
760         A more explicit way to model state, is to simply add an extra argument
761         containing the current state value. This allows an output to depend on
762         both the inputs as well as the current state while keeping the
763         function pure (letting the result depend only on the arguments), since
764         the current state is now an argument.
765
766         In Haskell, this would look like
767         \in{example}[ex:ExplicitAcc]\footnote[notfinalsyntax]{Note that this example is not in the final
768   Cλash syntax}. \todo{Referencing notfinalsyntax from Introduction.tex doesn't
769   work}
770
771 \startbuffer[ExplicitAcc]
772 -- input -> current state -> (new state, output)
773 acc :: Word -> Word -> (Word, Word)
774 acc in s = (s', out)
775   where
776     out = s + in
777     s'  = out
778 \stopbuffer
779
780         \placeexample[here][ex:ExplicitAcc]{Simple accumulator architecture.}
781           \startcombination[2*1]
782             {\typebufferhs{ExplicitAcc}}{Haskell description using explicit state arguments.}
783             % Picture is identical to the one we had just now.
784             {\boxedgraphic{DelayAcc}}{The architecture described by the Haskell description.}
785           \stopcombination
786
787         This approach makes a function's state very explicit, which state
788         variables are used by a function can be completely determined from its
789         type signature (as opposed to the stream approach, where a function
790         looks the same from the outside, regardless of what state variables it
791         uses (or whether it's stateful at all).
792
793         This approach is the one chosen for Cλash and will be examined more
794         closely below.
795
796     \subsection{Explicit state specification}
797       We've seen the concept of explicit state in a simple example below, but
798       what are the implications of this approach?
799
800       \subsubsection{Substates}
801         Since a function's state is reflected directly in its type signature,
802         if a function calls other stateful functions (\eg, has subcircuits), it
803         has to somehow know the current state for these called functions. The
804         only way to do this, is to put these \emph{substates} inside the
805         caller's state. This means that a function's state is the sum of the
806         states of all functions it calls, and its own state.
807
808         This also means that the type of a function (at least the "state"
809         part) is dependent on its own implementation and of the functions it
810         calls.
811
812         This is the major downside of this approach: The separation between
813         interface and implementation is limited. However, since Cλash is not
814         very suitable for separate compilation (see
815         \in{section}[sec:prototype:separate]) this is not a big problem in
816         practice.
817
818         Additionally, when using a type synonym for the state type
819         of each function, we can still provide explicit type signatures
820         while keeping the state specification for a function near its
821         definition only.
822         \todo{Example}
823     
824       \subsubsection{Which arguments and results are stateful?}
825         \fxnote{This section should get some examples}
826         We need some way to know which arguments should become input ports and
827         which argument(s?) should become the current state (\eg, be bound to
828         the register outputs). This does not hold just for the top
829         level function, but also for any subfunction. Or could we perhaps
830         deduce the statefulness of subfunctions by analyzing the flow of data
831         in the calling functions?
832
833         To explore this matter, the following observeration is interesting: We
834         get completely correct behaviour when we put all state registers in
835         the top level entity (or even outside of it). All of the state
836         arguments and results on subfunctions are treated as normal input and
837         output ports. Effectively, a stateful function results in a stateless
838         hardware component that has one of its input ports connected to the
839         output of a register and one of its output ports connected to the
840         input of the same register.
841
842         \todo{Example}
843
844         Of course, even though the hardware described like this has the
845         correct behaviour, unless the layout tool does smart optimizations,
846         there will be a lot of extra wire in the design (since registers will
847         not be close to the component that uses them). Also, when working with
848         the generated \small{VHDL} code, there will be a lot of extra ports
849         just to pass on state values, which can get quite confusing.
850
851         To fix this, we can simply \quote{push} the registers down into the
852         subcircuits. When we see a register that is connected directly to a
853         subcircuit, we remove the corresponding input and output port and put
854         the register inside the subcircuit instead. This is slightly less
855         trivial when looking at the Haskell code instead of the resulting
856         circuit, but the idea is still the same.
857
858         \todo{Example}
859
860         However, when applying this technique, we might push registers down
861         too far. When you intend to store a result of a stateless subfunction
862         in the caller's state and pass the current value of that state
863         variable to that same function, the register might get pushed down too
864         far. It is impossible to distinguish this case from similar code where
865         the called function is in fact stateful. From this we can conclude
866         that we have to either:
867
868         \todo{Example of wrong downpushing}
869
870         \startitemize
871         \item accept that the generated hardware might not be exactly what we
872         intended, in some specific cases. In most cases, the hardware will be
873         what we intended.
874         \item explicitely annotate state arguments and results in the input
875         description.
876         \stopitemize
877
878         The first option causes (non-obvious) exceptions in the language
879         intepretation. Also, automatically determining where registers should
880         end up is easier to implement correctly with explicit annotations, so
881         for these reasons we will look at how this annotations could work.
882
883         \todo{Sidenote: One or more state arguments?}
884
885     \subsection{Explicit state annotation}
886       To make our stateful descriptions unambigious and easier to translate,
887       we need some way for the developer to describe which arguments and
888       results are intended to become stateful.
889     
890       Roughly, we have two ways to achieve this:
891       \startitemize[KR]
892         \item Use some kind of annotation method or syntactic construction in
893         the language to indicate exactly which argument and (part of the)
894         result is stateful. This means that the annotation lives
895         \quote{outside} of the function, it is completely invisible when
896         looking at the function body.
897         \item Use some kind of annotation on the type level, \ie give stateful
898         arguments and stateful (parts of) results a different type. This has the
899         potential to make this annotation visible inside the function as well,
900         such that when looking at a value inside the function body you can
901         tell if it's stateful by looking at its type. This could possibly make
902         the translation process a lot easier, since less analysis of the
903         program flow might be required.
904       \stopitemize
905
906       From these approaches, the type level \quote{annotations} have been
907       implemented in Cλash. \in{Section}[sec:prototype:statetype] expands on
908       the possible ways this could have been implemented.
909
910   \todo{Note about conditions on state variables and checking them}
911
912   \section[sec:recursion]{Recursion}
913   An import concept in functional languages is recursion. In it's most basic
914   form, recursion is a definition that is defined in terms of itself. A
915   recursive function is thus a function that uses itself in its body. This
916   usually requires multiple evaluations of this function, with changing
917   arguments, until eventually an evaluation of the function no longer requires
918   itself.
919
920   Recursion in a hardware description is a bit of a funny thing. Usually,
921   recursion is associated with a lot of nondeterminism, stack overflows, but
922   also flexibility and expressive power.
923
924   Given the notion that each function application will translate to a
925   component instantiation, we are presented with a problem. A recursive
926   function would translate to a component that contains itself. Or, more
927   precisely, that contains an instance of itself. This instance would again
928   contain an instance of itself, and again, into infinity. This is obviously a
929   problem for generating hardware.
930
931   This is expected for functions that describe infinite recursion. In that
932   case, we can't generate hardware that shows correct behaviour in a single
933   cycle (at best, we could generate hardware that needs an infinite number of
934   cycles to complete).
935   
936   However, most recursive hardware descriptions will describe finite
937   recursion. This is because the recursive call is done conditionally. There
938   is usually a \hs{case} expression where at least one alternative does not contain
939   the recursive call, which we call the "base case". If, for each call to the
940   recursive function, we would be able to detect at compile time which
941   alternative applies, we would be able to remove the \hs{case} expression and
942   leave only the base case when it applies. This will ensure that expanding
943   the recursive functions will terminate after a bounded number of expansions.
944
945   This does imply the extra requirement that the base case is detectable at
946   compile time. In particular, this means that the decision between the base
947   case and the recursive case must not depend on runtime data.
948
949   \subsection{List recursion}
950   The most common deciding factor in recursion is the length of a list that is
951   passed in as an argument. Since we represent lists as vectors that encode
952   the length in the vector type, it seems easy to determine the base case. We
953   can simply look at the argument type for this. However, it turns out that
954   this is rather non-trivial to write down in Haskell already, not even
955   looking at translation. As an example, we would like to write down something
956   like this:
957  
958   \starthaskell
959     sum :: Vector n Word -> Word
960     sum xs = case null xs of
961       True -> 0
962       False -> head xs + sum (tail xs)
963   \stophaskell
964
965   However, the Haskell typechecker will now use the following reasoning (element
966   type of the vector is left out). Below, we write conditions on type
967   variables before the \hs{=>} operator. This is not completely valid Haskell
968   syntax, but serves to illustrate the typechecker reasoning. Also note that a
969   vector can never have a negative length, so \hs{Vector n} implicitly means
970   \hs{(n >= 0) => Vector n}.
971
972   \todo{This typechecker disregards the type signature}
973   \startitemize
974   \item tail has the type \hs{(n > 0) => Vector n -> Vector (n - 1)}
975   \item This means that xs must have the type \hs{(n > 0) => Vector n}
976   \item This means that sum must have the type \hs{(n > 0) => Vector n -> a}
977   \item sum is called with the result of tail as an argument, which has the
978   type \hs{Vector n} (since \hs{(n > 0) => Vector (n - 1)} is the same as \hs{(n >= 0)
979   => Vector n}, which is the same as just \hs{Vector n}).
980   \item This means that sum must have the type \hs{Vector n -> a}
981   \item This is a contradiction between the type deduced from the body of sum
982   (the input vector must be non-empty) and the use of sum (the input vector
983   could have any length).
984   \stopitemize
985
986   As you can see, using a simple \hs{case} expression  at value level causes
987   the type checker to always typecheck both alternatives, which can't be done!
988   This is a fundamental problem, that would seem perfectly suited for a type
989   class.  Considering that we need to switch between to implementations of the
990   sum function, based on the type of the argument, this sounds like the
991   perfect problem to solve with a type class. However, this approach has its
992   own problems (not the least of them that you need to define a new typeclass
993   for every recursive function you want to define).
994
995   Another approach tried involved using GADTs to be able to do pattern
996   matching on empty / non empty lists. While this worked partially, it also
997   created problems with more complex expressions.
998
999   \note{This should reference Christiaan}
1000
1001   Evaluating all possible (and non-possible) ways to add recursion to our
1002   descriptions, it seems better to leave out list recursion alltogether. This
1003   allows us to focus on other interesting areas instead. By including
1004   (builtin) support for a number of higher order functions like map and fold,
1005   we can still express most of the things we would use list recursion for.
1006   
1007   \todo{Expand on this decision a bit}
1008  
1009   \subsection{General recursion}
1010   Of course there are other forms of recursion, that do not depend on the
1011   length (and thus type) of a list. For example, simple recursion using a
1012   counter could be expressed, but only translated to hardware for a fixed
1013   number of iterations. Also, this would require extensive support for compile
1014   time simplification (constant propagation) and compile time evaluation
1015   (evaluation of constant comparisons), to ensure non-termination. Even then, it
1016   is hard to really guarantee termination, since the user (or GHC desugarer)
1017   might use some obscure notation that results in a corner case of the
1018   simplifier that is not caught and thus non-termination.
1019
1020   Due to these complications and limited time available, we leave other forms
1021   of recursion as future work as well.
1022
1023 % vim: set sw=2 sts=2 expandtab: