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