\chapter[chap:introduction]{Introduction}
This thesis describes the result and process of my work during my
Master's assignment. In these pages, I will introduce the world
of hardware descriptions, the world of functional languages and
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.

% 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[here][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 show 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
  0\todo{normal 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).
    \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,
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 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:
