+This assignment has been performed in close cooperation with Christiaan
+Baaij, whose Master's thesis \cite[baaij09]\ has been completed at the
+same time as this thesis. Where this thesis focuses on the
+interpretation of the Haskell language and the compilation process,
+\cite[baaij09]\ has a more thorough study of the field, explores more
+advanced types and provides a case study.
+
+% Use \subject to hide this section from the toc
+\subject{Research goals}
+ This research started out with the notion that a functional program is very
+ easy to interpret as a hardware description. A functional program typically
+ makes no assumptions about evaluation order and does not have any side
+ effects. This fits hardware nicely, since the evaluation order for hardware
+ is simply everything in parallel.
+
+ As a motivating example, consider the simple functional program shown in
+ \in{example}[ex:AndWord]\footnote[notfinalsyntax]{This example is not in the final
+ Cλash syntax}. This is a very natural way to describe a lot of parallel not
+ ports, that perform a bitwise not on a bitvector. The example also shows an
+ image of the architecture described.
+
+ \startbuffer[AndWord]
+ notword :: [Bit] -> [Bit]
+ notword = map not
+ \stopbuffer
+
+ \startuseMPgraphic{AndWord}
+ % Create objects
+ save a, inp, out;
+ newCircle.inp(btex $\overrightarrow{input}$ etex) "framed(false)";
+ num := 4;
+ for i=1 upto num:
+ newCircle.a[i](btex not etex);
+ endfor
+ newCircle.out(btex $\overrightarrow{output}$ etex) "framed(false)";
+
+ % Center the input and output ports vertically, and put them left and right
+ % resp.
+ inp.c = (xpart(a1.c) - 2cm, ypart((a[1].c + a[num].c)/2));
+ out.c = (xpart(a1.c) + 2cm, ypart((a[1].c + a[num].c)/2));
+
+ % Space the operations vertically, with some extra space between the middle
+ % two
+ a2.c-a1.c=(0cm, 1.5cm);
+ a3.c-a2.c=(0cm, 2.5cm);
+ a4.c-a3.c=(0cm, 1.5cm);
+ a1.c=origin;
+
+ % Draw objects and lines
+ drawObj(inp);
+ for i=1 upto num:
+ ncline(inp)(a[i]);
+ drawObj(a[i]);
+ ncline(a[i])(out);
+ endfor
+ drawObj(out);
+ % Draw a dotted line between the middle operations
+ ncline(a2)(a3) "linestyle(dashed withdots)", "arrows(-)";
+ \stopuseMPgraphic
+ \placeexample[][ex:AndWord]{Simple architecture that inverts a vector of bits.}
+ \startcombination[2*1]
+ {\typebufferlam{AndWord}}{Haskell description of the architecture.}
+ {\boxedgraphic{AndWord}}{The architecture described by the Haskell description.}
+ \stopcombination
+
+ Slightly more complicated is the incremental summation of
+ values shown in \in{example}[ex:RecursiveSum]\note[notfinalsyntax].
+
+ In this example we see a recursive function \hs{sum'} that recurses over a
+ list and takes an accumulator argument that stores the sum so far. On each
+ step of the recusion, another number from the input vector is added to the
+ accumulator and each intermediate step returns its result.
+
+ This is a nice description of a series of sequential adders that produce
+ the incremental sums of a vector of numbers. For an input list of length 4,
+ the corresponding architecture is show in the example.
+
+ \startbuffer[RecursiveSum]
+ sum :: [Int] -> [Int]
+ sum = sum' 0
+
+ sum' :: Int -> [Int] -> [Int]
+ sum' acc [] = []
+ sum' acc (x:xs) = acc' : (sum' acc' xs)
+ where acc' = x + acc
+ \stopbuffer
+
+ \startuseMPgraphic{RecursiveSum}
+ save inp, a, zero, out;
+ % Create objects
+ newCircle.inp(btex $\overrightarrow{input}$ etex) "framed(false)";
+ newCircle.zero(btex $0$ etex) "framed(false)";
+ num := 4;
+ for i=1 upto num:
+ newCircle.a[i](btex + etex);
+ endfor
+ newCircle.out(btex $\overrightarrow{output}$ etex) "framed(false)";
+
+ % Center the input and output ports vertically, and put them left and right
+ % resp.
+
+ % Space the operations vertically, with some extra space between the middle
+ % two
+ a1.c-inp.c=(2cm, 0cm);
+ a2.c-a1.c=(1.5cm, 0cm);
+ a3.c-a2.c=(1.5cm, 0cm);
+ a4.c-a3.c=(1.5cm, 0cm);
+ out.c-a4.c=(2cm, 0cm);
+ a1.c = origin;
+ % Put the zero above the input
+ zero.c-inp.c=(0cm, 1cm);
+
+ nccurve(zero)(a1) "angleA(0)", "angleB(-40)";
+ % Draw objects and lines
+ drawObj(inp, zero);
+ %ncarc(inp)(a0);
+ for i=1 upto num:
+ if (i <> num):
+ nccurve(a[i])(out) "posA(e)", "angleB(" & decimal((num - i)*-20) & ")", "angleA(60)";
+ fi
+ nccurve(inp)(a[i]) "angleA(" & decimal(i*-15) & ")", "angleB(40)";
+ if (i <> 1):
+ ncline(a[i-1])(a[i]);
+ fi
+
+ drawObj(a[i]);
+ endfor
+ ncline(a1)(a2);
+ ncline(a3)(a4);
+ ncline(a4)(out);
+ drawObj(out);
+ \stopuseMPgraphic
+
+ \placeexample[here][ex:RecursiveSum]{A recursive description that sums values.}
+ \startcombination[2*1]
+ {\typebufferlam{RecursiveSum}}{Haskell description of the architecture.}
+ {\boxedgraphic{RecursiveSum}}{The architecture described by the Haskell description.}
+ \stopcombination
+
+
+ Or... is this the description of a single accumulating adder, that will add
+ one element of each input each clock cycle and has a reset value of
+ {\definedfont[Serif*normalnum]0}? In
+ that case, we would have described the architecture show in \in{example}[ex:RecursiveSumAlt]
+
+ \startuseMPgraphic{RecursiveSumAlt}
+ save reg, inp, a, out;
+ newReg.reg("") "dx(4mm)", "dy(6mm)", "reflect(true)";
+ newCircle.inp(btex $input$ etex) "framed(false)";
+ newCircle.a(btex + etex);
+ newCircle.out(btex $output$ etex) "framed(false)";
+
+ % Put inp, a and out in one horizontal line, with reg above a
+ reg.c-a.c=(0cm, 2cm);
+ a.c-inp.c=(3cm, 0cm);
+ out.c-a.c=(3cm, 0cm);
+ a.c = origin;
+
+ % Draw objects and lines
+ drawObj(reg);
+ drawObj(inp);
+ drawObj(a);
+ drawObj(out);
+
+ ncline(inp)(a);
+ % a.e to reg.d
+ nccurve(a)(reg) "posA(e)", "angleA(0)", "angleB(180)", "posB(d)";
+ % reg.out to a
+ nccurve(reg)(a) "posA(out)", "angleA(180)", "angleB(-30)";
+ ncline(a)(out);
+ \stopuseMPgraphic
+
+ \placeexample[here][ex:RecursiveSumAlt]{An alternative interpretation of the description in \in{example}[ex:RecursiveSum]}
+ {\boxedgraphic{RecursiveSumAlt}}
+
+ The distinction in possible interpretations we see here, is an important
+ distinction in this research. In the first figure, the recursion in the code
+ is taken as recursion in space and each recursion step results in a
+ different piece of hardware, all of which are active simultaneously. In the
+ second figure, the recursion in the code is taken as recursion in time and
+ each recursion step is executed sequentially, \emph{on the same piece of
+ hardware}.
+
+ In this research we explore how to apply these two interpretations to
+ hardware descriptions. Additionally, we explore how other functional
+ programming concepts can be applied to hardware descriptions to give use an
+ efficient way to describe hardware.
+
+ This leads us to the following research question:
+
+ % Slightly bigger font, some extra spacing.
+ \setupquotation[style=tfb,spacebefore=5mm]
+ \startquotation
+ How can we describe the structural properties of a hardware design, using
+ a functional language?
+ \stopquotation
+ \setupquotation[style=normal,spacebefore=]
+
+ We can further split this into subquestions from a hardware perspective:
+ \startitemize
+ \item How can we describe a stateful design?
+ \item How can we describe (hierarchical) structure in a design?
+ \stopitemize
+
+ And subquestions from a functional perspective:
+ \startitemize
+ \item How to interpret recursion in descriptions?
+ \item How to interpret polymorphism?
+ \item How to interpret higher-order descriptions?
+ \stopitemize
+
+ In addition to looking at designing a hardware description language, we
+ will also implement a prototype to test ideas. This prototype will
+ translate hardware descriptions written in the Haskell functional language
+ to simple (netlist-like) hardware descriptions in the \VHDL\ language. The
+ reasons for choosing these languages are detailed in section
+ \in{}[sec:prototype:input] and \in{}[sec:prototype:output] respectively.
+
+ \placeintermezzo{}{
+ \startframedtext[width=8cm,background=box,frame=no]
+ \startalignment[center]
+ {\tfa The name Cλash}
+ \stopalignment
+ \blank[medium]
+ The name Cλash more-or-less expands to CAES language for hardware
+ descriptions, where CAES refers to the research chair where this
+ project was undertaken (Computer Architectures for Embedded
+ Systems). The lambda in the name is of course a reference to the
+ lambda abstraction, which is an essential element of most functional
+ languages (and is also prominent in the Haskell logo).
+
+ Cλash is pronounced like \quote{Clash}.
+ \stopframedtext
+ }
+
+ The result of this research will thus be a prototype compiler and a language
+ that it can compile, to which we will refer to as the Cλash system and Cλash
+ language for short, or simply Cλash.
+
+% Use \subject to hide this section from the toc
+\subject{Outline}