-\chapter{Introduction}
+\chapter[chap:introduction]{Introduction}
+\fixme{No chapter number?}
This thesis describes the result and process of my work during my
Master's assignment. In these pages, I will try to introduce the world
of hardware descriptions, the world of functional languages and
-compilers, and present the compiler that will connect these worlds and
-sets a first step towards making hardware programming on the whole
-easier, more maintainable and generally more pleasant.
+compilers and introduce the hardware description language Cλash that will
+connect these worlds and puts a step towards making hardware programming
+on the whole easier, more maintainable and generally more pleasant.
+\section{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
+ does 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 following simple functional
+ program:\footnote[notfinalsyntax]{Note that this example is not in the final
+ Cλash syntax}
+
+\starttyping
+notword :: [Bit] -> [Bit]
+notword = map not
+\stoptyping
+
+ This is a very natural way to describe a lot of parallel not ports, that
+ perform a bitwise not on a bitvector. The architecture described would look
+ like the following:
+
+ \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
+ \useMPgraphic{AndWord}
+ \todo{Float graphic?}
+
+ Slightly more complicated is the following incremental summation of
+ values:\note[notfinalsyntax]
+
+\starttyping
+sum :: [Int] -> [Int]
+sum = sum' 0
+
+sum' :: Int -> [Int] -> [Int]
+sum' acc [] = []
+sum' acc (x:xs) = acc' : (sum' acc' xs)
+ where acc' = x + acc
+\stoptyping
+
+ Here 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.
+
+ So, 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,
+ this is the corresponding architecture:
+
+ \startMPcode
+ 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);
+ \stopMPcode
+
+ 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 0? In
+ that case, we would have described this architecture:
+
+ \startMPcode
+ 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);
+ \stopMPcode
+
+ 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:
+ \todo{Include Haskell in questions?}
+
+ % 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
+
+ \todo{Introduce Cλash?}
+
+ In addition to looking at designing a hardware description language, we
+ will also implement a prototype to test drive our 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.
+
+\section{Outline}
+
+\fxnote{This section needs updating}
In the first chapter, we will sketch the context for this research.
The current state and history of hardware description languages will be
briefly discussed, as well as the state and history of functional
programming. Since we're not the first to have merged these approaches,
a number of other functional hardware description languages are briefly
described.
+
+Chapter two describes the exploratory part of this research: How can we
+describe hardware using a functional language and how can we use functional
+concepts for hardware descriptions?
+
+Chapter three talks about the prototype that was created and which has guided
+most of the research. There is some attention for the language chosen for our
+hardware descriptions, Haskell. The possibilities and limits of this prototype
+are further explored.
+
+During the creation of the prototype, it became apparent that some structured
+way of doing program transformations was required. Doing ad-hoc interpretation
+of the hardware description proved non-scalable. These transformations and
+their application are the subject of the fourth chapter.
+
+The final chapter sketches ideas for further research, which are many. Some of
+them have seen some initial exploration and could provide a basis for future
+work in this area.
+
+% vim: set sw=2 sts=2 expandtab:
projects / matthijs / master-project / report.git / blobdiff