1 \chapter[chap:introduction]{Introduction}
2 This thesis describes the result and process of my work during my
3 Master's assignment. In these pages, I will try to introduce the world
4 of hardware descriptions, the world of functional languages and
5 compilers, and present the compiler that will connect these worlds and
6 sets a first step towards making hardware programming on the whole
7 easier, more maintainable and generally more pleasant.
9 \section{Research goals}
10   This research started out with the notion that a functional program is very
11   easy to interpret as a hardware description. A functional program typically
12   does no assumptions about evaluation order and does not have any side
13   effects. This fits hardware nicely, since the evaluation order is simply
14   everything in parallel.
16   As a motivating example, consider the following simple functional program:
18 \starttyping
19 andword :: [Bit] -> [Bit]
20 andword = map not
21 \stoptyping
23   This is a very natural way to describe a lot of parallel and ports, that
24   perform a bitwise and on a bitvector. The architecture described would look
25   like the following:
27   \startMPcode
28     % Create objects
29     save a, inp, out;
30     newCircle.inp(btex $\overrightarrow{input}$ etex) "framed(false)";
31     num := 4;
32     for i=1 upto num:
33       newCircle.a[i](btex not etex);
34     endfor
35     newCircle.out(btex $\overrightarrow{output}$ etex) "framed(false)";
37     % Center the input and output ports vertically, and put them left and right
38     % resp.
39     inp.c = (xpart(a1.c) - 2cm, ypart((a.c + a[num].c)/2));
40     out.c = (xpart(a1.c) + 2cm, ypart((a.c + a[num].c)/2));
42     % Space the operations vertically, with some extra space between the middle
43     % two
44     a2.c-a1.c=(0cm, 1.5cm);
45     a3.c-a2.c=(0cm, 2.5cm);
46     a4.c-a3.c=(0cm, 1.5cm);
47     a1.c=origin;
49     % Draw objects and lines
50     drawObj(inp);
51     for i=1 upto num:
52       ncline(inp)(a[i]);
53       drawObj(a[i]);
54       ncline(a[i])(out);
55     endfor
56     drawObj(out);
57     % Draw a dotted line between the middle operations
58     ncline(a2)(a3) "linestyle(dashed withdots)", "arrows(-)";
59   \stopMPcode
61   Slightly more complicated is the following incremental summation of values:
63 \starttyping
64 sum :: [Int] -> [Int]
65 sum = sum' 0
67 sum' :: [Int] -> Int -> [Int]
68 sum' [] acc = []
69 sum' (x:xs) acc = acc' : (sum' xs acc')
70   where acc' = x + acc
71 \stoptyping
73   Here we see a recursive function \hs{sum'} that recurses over a list and
74   takes an accumulator argument that stores the sum so far. On each step of
75   the recusion, another number from the input vector is added to the
76   accumulator and each intermediate step returns its result.
78   So, this is a nice description of a bunch of sequential adders that produce
79   the incremental sums of a vector of numbers. For an input list of length 4,
80   this is the corresponding architecture:
82   \startMPcode
83     save inp, a, zero, out;
84     % Create objects
85     newCircle.inp(btex $\overrightarrow{input}$ etex) "framed(false)";
86     newCircle.zero(btex $0$ etex) "framed(false)";
87     num := 4;
88     for i=1 upto num:
89       newCircle.a[i](btex + etex);
90     endfor
91     newCircle.out(btex $output$ etex) "framed(false)";
93     % Center the input and output ports vertically, and put them left and right
94     % resp.
96     % Space the operations vertically, with some extra space between the middle
97     % two
98     a1.c-inp.c=(2cm, 0cm);
99     a2.c-a1.c=(1.5cm, 0cm);
100     a3.c-a2.c=(1.5cm, 0cm);
101     a4.c-a3.c=(1.5cm, 0cm);
102     out.c-a4.c=(2cm, 0cm);
103     a1.c = origin;
104     % Put the zero above the input
105     zero.c-inp.c=(0cm, 1cm);
107     nccurve(zero)(a1) "angleA(0)", "angleB(-40)";
108     % Draw objects and lines
109     drawObj(inp, zero);
110     %ncarc(inp)(a0);
111     for i=1 upto num:
112       if (i <> num):
113         nccurve(a[i])(out) "posA(e)", "angleB(" & decimal((num - i)*-20) & ")", "angleA(60)";
114       fi
115       nccurve(inp)(a[i]) "angleA(" & decimal(i*-15) & ")", "angleB(40)";
116       if (i <> 1):
117         ncline(a[i-1])(a[i]);
118       fi
120       drawObj(a[i]);
121     endfor
122     ncline(a1)(a2);
123     ncline(a3)(a4);
124     ncline(a4)(out);
125     drawObj(out);
126   \stopMPcode
128   Or... is this the description of a single accumulating adder, that will add
129   one element of each input each clock cycle? In that case, we would have
130   described this architecture:
132   \startMPcode
133     save reg, inp, a, out;
134     newReg.reg("") "dx(4mm)", "dy(6mm)", "reflect(true)";
135     newCircle.inp(btex $input$ etex) "framed(false)";
136     newCircle.a(btex + etex);
137     newCircle.out(btex $output$ etex) "framed(false)";
139     % Put inp, a and out in one horizontal line, with reg above a
140     reg.c-a.c=(0cm, 2cm);
141     a.c-inp.c=(3cm, 0cm);
142     out.c-a.c=(3cm, 0cm);
143     a.c = origin;
145     % Draw objects and lines
146     drawObj(reg);
147     drawObj(inp);
148     drawObj(a);
149     drawObj(out);
151     ncline(inp)(a);
152     % a.e to reg.d
153     nccurve(a)(reg) "posA(e)", "angleA(0)", "angleB(180)", "posB(d)";
154     % reg.out to a
155     nccurve(reg)(a) "posA(out)", "angleA(180)", "angleB(-30)";
156     ncline(a)(out);
157   \stopMPcode
159   The distinction in possible interpretations we see here, is an important
160   distinction in this research. In the first figure, the recursion in the code
161   is taken as recursion in space and each recursion step results in a
162   different piece of hardware, all of which are active simultaneously. In the
163   second figuer, the recursion in the code is taken as recursion in time and
164   each recursion step is executed sequentially, \emph{on the same piece of
165   hardware}.
167   In this research we explore how to apply these two interpretations two
168   hardware descriptions. Additionally, we explore how other functional
169   programming concepts can be applied to hardware descriptions to give use an
170   efficient way to describe hardware.
172   This leads us to the following research question:
174   % Slightly bigger font, some extra spacing.
175   \setupquotation[style=tfb,spacebefore=5mm]
176   \startquotation
177     How can we describe the structural properties of a hardware design, using
178     a functional language?
179   \stopquotation
180   \setupquotation[style=normal,spacebefore=]
182   We can further split this into subquestions from a hardware perspective:
183   \startitemize
184     \item How can we describe a stateful design?
185     \item How can we describe (hierarchical) structure in a design?
186   \stopitemize
188   functional perspective:
189   \startitemize
190     \item How to interpret recursion in descriptions?
191     \item How to interpret polymorphism?
192     \item How to interpret higher order in descriptions?
193   \stopitemize
195 \section{Outline}
197 In the first chapter, we will sketch the context for this research.
198 The current state and history of hardware description languages will be
199 briefly discussed, as well as the state and history of functional
200 programming. Since we're not the first to have merged these approaches,
201 a number of other functional hardware description languages are briefly
202 described.
204 Chapter two describes the exploratory part of this research: How can we
205 describe hardware using a functional language and how can we use functional
206 concepts for hardware descriptions?
208 Chapter three talks about the prototype that was created and which has guided
209 most of the research. There is some attention for the language chosen for our
210 hardware descriptions, Haskell. The possibilities and limits of this prototype
211 are further explored.
213 During the creation of the prototype, it became apparent that some structured
214 way of doing program transformations was required. Doing ad-hoc interpretation
215 of the hardware description proved non-scalable. These transformations and
216 their application are the subject of the fourth chapter.
218 The final chapter sketches ideas for further research, which are many. Some of
219 have seen some initial exploration and could provide a basis for future work
220 in this area.