X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Freport.git;a=blobdiff_plain;f=Chapters%2FIntroduction.tex;h=18950802c16f31fd2f6f33036e7076218389c436;hp=7458e2f850ade083fae0d0cab4f20f27ff0cd8dd;hb=f2d45a8c05c4fff4eb9574e8514b213fbfc8fb84;hpb=ebd7336493f39d3da5a05477c9da04199ad2079e

diff --git a/Chapters/Introduction.tex b/Chapters/Introduction.tex
index 7458e2f..1895080 100644
--- a/Chapters/Introduction.tex
+++ b/Chapters/Introduction.tex
@@ -1,31 +1,40 @@
-\chapter{Introduction}
+\chapter[chap:introduction]{Introduction}
 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
+Master's assignment. In these pages, I will 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 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
-  does no assumptions about evaluation order and does not have any side
-  effects. This fits hardware nicely, since the evaluation order is simply
-  everything in parallel.
-
-  As a motivating example, consider the following simple functional program:
+  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.
 
-\starttyping
-andword :: [Bit] -> [Bit]
-andword = map not
-\stoptyping
+  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.
 
-  This is a very natural way to describe a lot of parallel and ports, that
-  perform a bitwise and on a bitvector. The architecture described would look
-  like the following:
+  \startbuffer[AndWord]
+    notword :: [Bit] -> [Bit]
+    notword = map not
+  \stopbuffer
 
-  \startMPcode
+  \startuseMPgraphic{AndWord}
     % Create objects
+    save a, inp, out;
     newCircle.inp(btex $\overrightarrow{input}$ etex) "framed(false)";
     num := 4;
     for i=1 upto num:
@@ -55,35 +64,36 @@ andword = map not
     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
 
-    % Clear everything
-    clearObj a;
-    clearObj inp;
-    clearObj out;
-  \stopMPcode
-
-  Slightly more complicated is the following incremental summation of values:
-
-\starttyping
-sum :: [Int] -> [Int]
-sum = sum' 0
-
-sum' :: [Int] -> Int -> [Int]
-sum' [] acc = []
-sum' (x:xs) acc = acc' : (sum' xs acc')
-  where acc' = x + acc
-\stoptyping
+  Slightly more complicated is the incremental summation of
+  values shown in \in{example}[ex:RecursiveSum]\note[notfinalsyntax].
 
-  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
+  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.
 
-  So, this is a nice description of a bunch of sequential adders that produce
+  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:
+  the corresponding architecture is show in the example.
 
-  \startMPcode
+  \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)";
@@ -92,7 +102,7 @@ sum' (x:xs) acc = acc' : (sum' xs acc')
     for i=1 upto num:
       newCircle.a[i](btex + etex);
     endfor 
-    newCircle.out(btex $output$ etex) "framed(false)";
+    newCircle.out(btex $\overrightarrow{output}$ etex) "framed(false)";
 
     % Center the input and output ports vertically, and put them left and right
     % resp.
@@ -127,20 +137,28 @@ sum' (x:xs) acc = acc' : (sum' xs acc')
     ncline(a3)(a4);
     ncline(a4)(out);
     drawObj(out);
-  \stopMPcode
+  \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? In that case, we would have
-  described this architecture:
+  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]
 
-  \startMPcode
+  \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)";
    
-    % Punt inp, a and out in one horizontal line, with reg above a
+    % 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);
@@ -158,17 +176,20 @@ sum' (x:xs) acc = acc' : (sum' xs acc')
     % reg.out to a
     nccurve(reg)(a) "posA(out)", "angleA(180)", "angleB(-30)";
     ncline(a)(out);
-  \stopMPcode
+  \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 figuer, the recursion in the code is taken as recursion in time and
+  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 two
+  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.
@@ -181,6 +202,7 @@ sum' (x:xs) acc = acc' : (sum' xs acc')
     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
@@ -188,23 +210,51 @@ sum' (x:xs) acc = acc' : (sum' xs acc')
     \item How can we describe (hierarchical) structure in a design?
   \stopitemize
   
-  functional perspective:
+  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 in descriptions?
+    \item How to interpret higher-order descriptions?
   \stopitemize
 
-\section{Outline}
+  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}
 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,
+programming. Since we are 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
+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?
 
@@ -218,6 +268,10 @@ 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
-have seen some initial exploration and could provide a basis for future work
-in this area.
+The next 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.
+
+Finally, we present our conclusions.
+
+% vim: set sw=2 sts=2 expandtab: