From dadae33d89b183cb9aab04b4a82dab53c4cf2ce4 Mon Sep 17 00:00:00 2001
From: Matthijs Kooijman <matthijs@stdin.nl>
Date: Wed, 23 Sep 2009 15:40:58 +0200
Subject: [PATCH 01/16] Define a custom "Register" MetaObj object.

---
 Utils/Metapost.tex | 78 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 78 insertions(+)

diff --git a/Utils/Metapost.tex b/Utils/Metapost.tex
index cac69dd..6d00ae4 100644
--- a/Utils/Metapost.tex
+++ b/Utils/Metapost.tex
@@ -16,4 +16,82 @@ setCurveDefaultOption("linewidth",.75mm);
 % included in the bounding box for line cutoff.
 setCurveDefaultOption("nodesep",curve_linewidth_default);
 
+
+% Define a register.
+% |v| is either a picture, a string or an object given by its number which
+% will be contained inside the register. Supports the same options as Box,
+% plus:
+%   reflect    Reflect the register vertically, so input is right and output
+%              is left. (default: false)
+%   labels     Show labels for the input and output ports. (default: false)
+vardef newReg@#(expr v) text options=
+  ExecuteOptions(@#)(options);
+  assignObj(@#,"Reg");
+  StandardInterface;
+  
+  % We contain a box (that contains the passed object in turn)
+  SubObject(box,obj(newobjstring_));
+  newBox.obj(@#box)(v) options;
+ 
+  % Some points for ports
+  ObjPoint ck,d,out;
+
+  ObjCode StandardEquations,
+    % Align our bounding box with the enclosed box
+    "obj(@#box).c = @#c",
+    "obj(@#box).se = @#se",
+    "obj(@#box).nw = @#nw",
+    % Put the clock, data and output ports at the right spots
+    if OptionValue@#("reflect"):
+      "xpart @#out = xpart @#w",
+      "xpart @#d = xpart @#ck = xpart @#e",
+    else:
+      "xpart @#out = xpart @#e",
+      "xpart @#d = xpart @#ck = xpart @#w",
+    fi
+    "ypart @#d = ypart @#out = ypart (@#sw * .25 + @#nw * .75)",
+    "ypart @#ck = ypart (@#sw * .75 + @#nw * .25)";
+
+  StandardTies;
+enddef;
+
+% Draw a register
+def drawReg(suffix reg)=
+  save clkwh, refl;
+  % Draw the box
+  drawObj(obj(reg.box));
+
+  % Fill refl with 1 or -1, to invert coordinates when reflected.
+  if OptionValue.reg("reflect"):
+    refl = -1;
+  else:
+    refl = 1;
+  fi;
+
+  % Calculate (half of) the height and width of the triangle
+  clkwh = ypart((reg.n - reg.s)) * .1;
+  % Draw the "clock" triangle
+  draw ((0, clkwh) -- (refl * clkwh, 0) -- (0, -clkwh)) shifted reg.ck;
+
+  % Draw input and output labels
+  if OptionValue.reg("labels"):
+    if OptionValue.reg("reflect"):
+      label.lft(\sometxt{D}, reg.d);
+      label.rt(\sometxt{O}, reg.out);
+    else:
+      label.rt(\sometxt{D}, reg.d);
+      label.lft(\sometxt{O}, reg.out);
+    fi;
+  fi
+enddef;
+
+% Bounding path for a register
+def BpathReg(suffix n)=BpathObj(obj(n.box)) enddef;
+
+% Define options
+define_global_boolean_option("reflect");
+define_global_boolean_option("labels");
+setObjectDefaultOption("Reg")("reflect")(false);
+setObjectDefaultOption("Reg")("labels")(false);
+
 \stopMPinclusions
-- 
2.30.2


From 04787b97e28a61c0e96ae9c3670c47c6bb1c881e Mon Sep 17 00:00:00 2001
From: Matthijs Kooijman <matthijs@stdin.nl>
Date: Wed, 23 Sep 2009 15:41:14 +0200
Subject: [PATCH 02/16] Add a hack to make \overrightarrow work in MetaPost.

---
 Utils/Metapost.tex | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/Utils/Metapost.tex b/Utils/Metapost.tex
index 6d00ae4..7caa6e0 100644
--- a/Utils/Metapost.tex
+++ b/Utils/Metapost.tex
@@ -95,3 +95,9 @@ setObjectDefaultOption("Reg")("reflect")(false);
 setObjectDefaultOption("Reg")("labels")(false);
 
 \stopMPinclusions
+
+% Make \overrightarrow "unexpanded", to make it work within metapost.
+% http://www.ntg.nl/pipermail/ntg-context/2009/043620.html. Will be fixed in
+% context.
+\let\normaloverrightarrow\overrightarrow                                                                                                                     
+\unexpanded\def\overrightarrow{\normaloverrightarrow} 
-- 
2.30.2


From 06f9b8afcdca6cc6cd82af650666c9d1faf27b98 Mon Sep 17 00:00:00 2001
From: Matthijs Kooijman <matthijs@stdin.nl>
Date: Thu, 24 Sep 2009 16:15:33 +0200
Subject: [PATCH 03/16] Update outline.

---
 Outline | 50 ++++++++++++++++++++++++++------------------------
 1 file changed, 26 insertions(+), 24 deletions(-)

diff --git a/Outline b/Outline
index 73246f9..0825321 100644
--- a/Outline
+++ b/Outline
@@ -1,13 +1,32 @@
-Implementation issues
+Context
+  Other FHDLs (short, Christiaan has details)
+
+  Advantages of clash / why clash?
+
+  VHDL / Verilog / EDIF etc. Why VHDL?
 
-State
+
+Haskell as hardware
+        Simple function -> component interpretation (Model: Structure)
+        Model: State
+          Explicit vs implicit passing of state (e.g, delay)
+          Explicit vs implicit marking
+        Interpret: Polymorphism
+        Interpret: Higher order
+	Need: Dependent types
+	Impossible things: Infinite recursion, higher order expressions
 
 Prototype
+        Choice of Haskell
+        Core - description of the language (appendix?)
 	Stages (-> Core, Normalization, -> VHDL)
+        Implementation issues
 
-Core
-
-VHDL vs EDIF generation
+        Haskell language coverage / constraints
+                Recursion
+                Builtin types
+                Custom types (Sum types, product types)
+                Function types / higher order expressions
 
 Normalization
 	Normal form
@@ -16,26 +35,9 @@ Normalization
 	Termination
 	Casts
 
-Context
-
-Other FHDLs
-
-VHDL / Verilog / EDIF etc.
-
-Advantages of clash / why clash?
-
-Haskell as hardware
-	Dependent types
-	Impossible things: Infinite recursion, higher order expressions
-
-Haskell language coverage / constraints
-	Recursion
-	Builtin types
-	Custom types (Sum types, product types)
-	Function types / higher order expressions
-
 Future work
 	Boilerplate reduction (State distribution & pipelining)
 	Recursion
-	Multiple time domains
+	Multiple time domains (Events)
 	Multiple cycle descriptions
+        Higher order state
-- 
2.30.2


From ebd7336493f39d3da5a05477c9da04199ad2079e Mon Sep 17 00:00:00 2001
From: Matthijs Kooijman <matthijs@stdin.nl>
Date: Thu, 24 Sep 2009 16:16:05 +0200
Subject: [PATCH 04/16] Add a section on research goals and an outline.

---
 Chapters/Introduction.tex | 209 ++++++++++++++++++++++++++++++++++++++
 1 file changed, 209 insertions(+)

diff --git a/Chapters/Introduction.tex b/Chapters/Introduction.tex
index ebbd931..7458e2f 100644
--- a/Chapters/Introduction.tex
+++ b/Chapters/Introduction.tex
@@ -6,9 +6,218 @@ 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.
 
+\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 is simply
+  everything in parallel.
+
+  As a motivating example, consider the following simple functional program:
+
+\starttyping
+andword :: [Bit] -> [Bit]
+andword = map not
+\stoptyping
+
+  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:
+
+  \startMPcode
+    % Create objects
+    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(-)";
+
+    % 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
+
+  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 bunch 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 $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? 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)";
+   
+    % Punt 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 figuer, 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
+  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
+
+  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
+  
+  functional perspective:
+  \startitemize
+    \item How to interpret recursion in descriptions?
+    \item How to interpret polymorphism?
+    \item How to interpret higher order in descriptions?
+  \stopitemize
+
+\section{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 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.
-- 
2.30.2


From d957c07d7ba3f6b2bccc6aafb1c8012882556c6e Mon Sep 17 00:00:00 2001
From: Matthijs Kooijman <matthijs@stdin.nl>
Date: Mon, 28 Sep 2009 19:00:26 +0200
Subject: [PATCH 05/16] Add outline for Prototype chapter.

---
 Chapters/Prototype.tex | 12 ++++++++++++
 Report.tex             |  1 +
 2 files changed, 13 insertions(+)
 create mode 100644 Chapters/Prototype.tex

diff --git a/Chapters/Prototype.tex b/Chapters/Prototype.tex
new file mode 100644
index 0000000..1db9c6d
--- /dev/null
+++ b/Chapters/Prototype.tex
@@ -0,0 +1,12 @@
+\chapter{Prototype}
+        Choice of Haskell
+        Core - description of the language (appendix?)
+	Stages (-> Core, Normalization, -> VHDL)
+        Implementation issues
+
+        Haskell language coverage / constraints
+                Recursion
+                Builtin types
+                Custom types (Sum types, product types)
+                Function types / higher order expressions
+
diff --git a/Report.tex b/Report.tex
index 40b94b6..c00b633 100644
--- a/Report.tex
+++ b/Report.tex
@@ -20,6 +20,7 @@ Matthijs Kooijman
 \completecontent
 \input Chapters/Introduction
 \input Chapters/HardwareDescription
+\input Chapters/Prototype
 \input Chapters/Normalization
 \input Chapters/State
 \stoptext
-- 
2.30.2


From 1c16f3b33548a1b08064263c63ab8b7f7e9f06ed Mon Sep 17 00:00:00 2001
From: Matthijs Kooijman <matthijs@stdin.nl>
Date: Mon, 28 Sep 2009 20:37:10 +0200
Subject: [PATCH 06/16] Add "New language" to the outline.

---
 Outline | 1 +
 1 file changed, 1 insertion(+)

diff --git a/Outline b/Outline
index 0825321..38383b8 100644
--- a/Outline
+++ b/Outline
@@ -41,3 +41,4 @@ Future work
 	Multiple time domains (Events)
 	Multiple cycle descriptions
         Higher order state
+        New language
-- 
2.30.2


From d13b2459ebafe1cdeef354cc4e4f28ca9d7c3a83 Mon Sep 17 00:00:00 2001
From: Matthijs Kooijman <matthijs@stdin.nl>
Date: Mon, 28 Sep 2009 20:37:34 +0200
Subject: [PATCH 07/16] Make a start with the prototype chapter.

---
 Chapters/Prototype.tex | 84 +++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 83 insertions(+), 1 deletion(-)

diff --git a/Chapters/Prototype.tex b/Chapters/Prototype.tex
index 1db9c6d..64fbbe7 100644
--- a/Chapters/Prototype.tex
+++ b/Chapters/Prototype.tex
@@ -1,5 +1,87 @@
 \chapter{Prototype}
-        Choice of Haskell
+  An important step in this research is the creation of a prototype compiler.
+  Having this prototype allows us to apply the ideas from the previous chapter
+  to actual hardware descriptions and evaluate their usefulness. Having a
+  prototype also helps to find new techniques and test possible
+  interpretations.
+
+  Obviously the prototype was not created after all research
+  ideas were formed, but its implementation has been interleaved with the
+  research itself. Also, the prototype described here is the final version, it
+  has gone through a number of design iterations which we will not completely
+  describe here.
+
+  \section{Choice of language}
+    When implementing this prototype, the first question to ask is: What
+    (functional) language will we use to describe our hardware? (Note that
+    this does not concern the \emph{implementation language} of the compiler,
+    just the language \emph{translated by} the compiler).
+
+    On the highest level, we have two choices:
+
+    \startitemize
+      \item Create a new functional language from scratch. This has the
+      advantage of having a language that contains exactly those elements that
+      are convenient for describing hardware and can contain special
+      constructs that might.
+      \item Use an existing language and create a new backend for it. This has
+      the advantage that existing tools can be reused, which will speed up
+      development.
+    \stopitemize
+
+    Considering that we required a prototype which should be working quickly,
+    and that implementing parsers, semantic checkers and especially
+    typcheckers isn't exactly the core of this research (but it is lots and
+    lots of work!), using an existing language is the obvious choice. This
+    also has the advantage that a large set of language features is available
+    to experiment with and it is easy to find which features apply well and
+    which don't. A possible second prototype could use a custom language with
+    just the useful features (and possibly extra features that are specific to
+    the domain of hardware description as well).
+
+    The second choice is to pick one of the many existing languages. As
+    mentioned before, this language is Haskell.  This choice has not been the
+    result of a thorough comparison of languages, for the simple reason that
+    the requirements on the language were completely unclear at the start of
+    this language. The fact that Haskell is a language with a broad spectrum
+    of features, that it is commonly used in research projects and that the
+    primary compiler, GHC, provides a high level API to its internals, made
+    Haskell an obvious choice.
+
+    TODO: Was Haskell really a good choice? Perhaps say this somewhere else?
+
+  \section{Prototype design}
+    As stated above, we will use the Glasgow Haskell Compiler (\small{GHC}) to
+    implement our prototype compiler. To understand the design of the
+    compiler, we will first dive into the \small{GHC} compiler a bit. It's
+    compilation consists of the following steps (slightly simplified):
+
+    \startdesc{Frontend}
+      This step takes the Haskell source files and parses them into an
+      abstract syntax tree (\small{AST}). This \small{AST} can express the
+      complete Haskell language and is thus a very complex one (in contrast
+      with the Core \small{AST}, later on). All identifiers in this
+      \small{AST} are resolved by the renamer and all types are checked by the
+      typechecker.
+    \stopdesc
+    \startdesc{Desugaring}
+      This steps takes the full \small{AST} and translates it to the
+      \emph{Core} language. Core is a very small functional language with lazy
+      semantics, that can still express everything Haskell can express. Its
+      simpleness makes Core very suitable for further simplification and
+      translation. Core is the language we will be working on as well.
+    \stopdesc
+    \startdesc{Simplification}
+      Through a number of simplification steps (such as inlining, common
+      subexpression elimination, etc.) the Core program is simplified to make
+      it faster or easier to process further.
+    \stopdesc
+    \startdesc{Backend}
+      This step takes the simplified Core program and generates an actual
+      runnable program for it. This is a big and complicated step we will not
+      discuss it any further, since it is not required for our prototype.
+    \stopdesc
+
         Core - description of the language (appendix?)
 	Stages (-> Core, Normalization, -> VHDL)
         Implementation issues
-- 
2.30.2


From b585bb305e914b8ad88da1876c8daef66e9bbb95 Mon Sep 17 00:00:00 2001
From: Matthijs Kooijman <matthijs@stdin.nl>
Date: Tue, 29 Sep 2009 14:04:32 +0200
Subject: [PATCH 08/16] Use save instead of clearObj in a MP drawing.

---
 Chapters/Introduction.tex | 6 +-----
 1 file changed, 1 insertion(+), 5 deletions(-)

diff --git a/Chapters/Introduction.tex b/Chapters/Introduction.tex
index 7458e2f..69fb7e4 100644
--- a/Chapters/Introduction.tex
+++ b/Chapters/Introduction.tex
@@ -26,6 +26,7 @@ andword = map not
 
   \startMPcode
     % Create objects
+    save a, inp, out;
     newCircle.inp(btex $\overrightarrow{input}$ etex) "framed(false)";
     num := 4;
     for i=1 upto num:
@@ -55,11 +56,6 @@ andword = map not
     drawObj(out);
     % Draw a dotted line between the middle operations
     ncline(a2)(a3) "linestyle(dashed withdots)", "arrows(-)";
-
-    % Clear everything
-    clearObj a;
-    clearObj inp;
-    clearObj out;
   \stopMPcode
 
   Slightly more complicated is the following incremental summation of values:
-- 
2.30.2


From fc1688977fdd8ee18e027876b8d86b0c38e25540 Mon Sep 17 00:00:00 2001
From: Matthijs Kooijman <matthijs@stdin.nl>
Date: Tue, 29 Sep 2009 16:22:50 +0200
Subject: [PATCH 09/16] Further expand the Prototype chapter.

---
 Chapters/Prototype.tex | 118 ++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 117 insertions(+), 1 deletion(-)

diff --git a/Chapters/Prototype.tex b/Chapters/Prototype.tex
index 64fbbe7..945e920 100644
--- a/Chapters/Prototype.tex
+++ b/Chapters/Prototype.tex
@@ -56,6 +56,39 @@
     compiler, we will first dive into the \small{GHC} compiler a bit. It's
     compilation consists of the following steps (slightly simplified):
 
+    \startuseMPgraphic{ghc-pipeline}
+      % Create objects
+      save inp, front, desugar, simpl, back, out;
+      newEmptyBox.inp(0,0);
+      newBox.front(btex Parser etex);
+      newBox.desugar(btex Desugarer etex);
+      newBox.simpl(btex Simplifier etex);
+      newBox.back(btex Backend etex);
+      newEmptyBox.out(0,0);
+
+      % Space the boxes evenly
+      inp.c - front.c = front.c - desugar.c = desugar.c - simpl.c 
+        = simpl.c - back.c = back.c - out.c = (0, 1.5cm);
+      out.c = origin;
+
+      % Draw lines between the boxes. We make these lines "deferred" and give
+      % them a name, so we can use ObjLabel to draw a label beside them.
+      ncline.inp(inp)(front) "name(haskell)";
+      ncline.front(front)(desugar) "name(ast)";
+      ncline.desugar(desugar)(simpl) "name(core)";
+      ncline.simpl(simpl)(back) "name(simplcore)";
+      ncline.back(back)(out) "name(native)";
+      ObjLabel.inp(btex Haskell source etex) "labpathname(haskell)", "labdir(rt)";
+      ObjLabel.front(btex Haskell AST etex) "labpathname(ast)", "labdir(rt)";
+      ObjLabel.desugar(btex Core etex) "labpathname(core)", "labdir(rt)";
+      ObjLabel.simpl(btex Simplified core etex) "labpathname(simplcore)", "labdir(rt)";
+      ObjLabel.back(btex Native code etex) "labpathname(native)", "labdir(rt)";
+
+      % Draw the objects (and deferred labels)
+      drawObj (inp, front, desugar, simpl, back, out);
+    \stopuseMPgraphic
+    \placefigure[right]{GHC compiler pipeline}{\useMPgraphic{ghc-pipeline}}
+
     \startdesc{Frontend}
       This step takes the Haskell source files and parses them into an
       abstract syntax tree (\small{AST}). This \small{AST} can express the
@@ -82,9 +115,92 @@
       discuss it any further, since it is not required for our prototype.
     \stopdesc
 
+    In this process, there a number of places where we can start our work.
+    Assuming that we don't want to deal with (or modify) parsing, typechecking
+    and other frontend business and that native code isn't really a useful
+    format anymore, we are left with the choice between the full Haskell
+    \small{AST}, or the smaller (simplified) core representation.
+
+    The advantage of taking the full \small{AST} is that the exact structure
+    of the source program is preserved. We can see exactly what the hardware
+    descriiption looks like and which syntax constructs were used. However,
+    the full \small{AST} is a very complicated datastructure. If we are to
+    handle everything it offers, we will quickly get a big compiler.
+
+    Using the core representation gives us a much more compact datastructure
+    (a core expression only uses 9 constructors). Note that this does not mean
+    that the core representation itself is smaller, on the contrary. Since the
+    core language has less constructs, a lot of things will take a larger
+    expression to express.
+
+    However, the fact that the core language is so much smaller, means it is a
+    lot easier to analyze and translate it into something else. For the same
+    reason, \small{GHC} runs its simplifications and optimizations on the core
+    representation as well.
+
+    However, we will use the normal core representation, not the simplified
+    core. Reasons for this are detailed below.
+    
+    The final prototype roughly consists of three steps:
+    
+    \startuseMPgraphic{ghc-pipeline}
+      % Create objects
+      save inp, front, norm, vhdl, out;
+      newEmptyBox.inp(0,0);
+      newBox.front(btex \small{GHC} frontend + desugarer etex);
+      newBox.norm(btex Normalization etex);
+      newBox.vhdl(btex VHDL generation etex);
+      newEmptyBox.out(0,0);
+
+      % Space the boxes evenly
+      inp.c - front.c = front.c - norm.c = norm.c - vhdl.c 
+        = vhdl.c - out.c = (0, 1.5cm);
+      out.c = origin;
+
+      % Draw lines between the boxes. We make these lines "deferred" and give
+      % them a name, so we can use ObjLabel to draw a label beside them.
+      ncline.inp(inp)(front) "name(haskell)";
+      ncline.front(front)(norm) "name(core)";
+      ncline.norm(norm)(vhdl) "name(normal)";
+      ncline.vhdl(vhdl)(out) "name(vhdl)";
+      ObjLabel.inp(btex Haskell source etex) "labpathname(haskell)", "labdir(rt)";
+      ObjLabel.front(btex Core etex) "labpathname(core)", "labdir(rt)";
+      ObjLabel.norm(btex Normalized core etex) "labpathname(normal)", "labdir(rt)";
+      ObjLabel.vhdl(btex VHDL description etex) "labpathname(vhdl)", "labdir(rt)";
+
+      % Draw the objects (and deferred labels)
+      drawObj (inp, front, norm, vhdl, out);
+    \stopuseMPgraphic
+    \placefigure[right]{GHC compiler pipeline}{\useMPgraphic{ghc-pipeline}}
+
+    \startdesc{Frontend}
+      This is exactly the frontend and desugarer from the \small{GHC}
+      pipeline, that translates Haskell sources to a core representation.
+    \stopdesc
+    \startdesc{Normalization}
+      This is a step that transforms the core representation into a normal
+      form. This normal form is still expressed in the core language, but has
+      to adhere to an extra set of constraints. This normal form is less
+      expressive than the full core language (e.g., it can have limited higher
+      order expressions, has a specific structure, etc.), but is also very
+      close to directly describing hardware.
+    \stopdesc
+    \startdesc{VHDL generation}
+      The last step takes the normal formed core representation and generates
+      VHDL for it. Since the normal form has a specific, hardware-like
+      structure, this final step is very straightforward.
+    \stopdesc
+    
+    The most interesting step in this process is the normalization step. That
+    is where more complicated functional constructs, which have no direct
+    hardware interpretation, are removed and translated into hardware
+    constructs. This step is described in a lot of detail at
+    \in{chapter}[chap:normalization].
+    
+
         Core - description of the language (appendix?)
-	Stages (-> Core, Normalization, -> VHDL)
         Implementation issues
+        Simplified core?
 
         Haskell language coverage / constraints
                 Recursion
-- 
2.30.2


From 6b779650796b6ef5c72ea261238f8576b049d925 Mon Sep 17 00:00:00 2001
From: Matthijs Kooijman <matthijs@stdin.nl>
Date: Tue, 29 Sep 2009 16:50:39 +0200
Subject: [PATCH 10/16] Add labels to all chapters.

---
 Chapters/Future.tex              | 2 +-
 Chapters/HardwareDescription.tex | 2 +-
 Chapters/Introduction.tex        | 2 +-
 Chapters/Normalization.tex       | 2 +-
 Chapters/Prototype.tex           | 2 +-
 Chapters/State.tex               | 2 +-
 6 files changed, 6 insertions(+), 6 deletions(-)

diff --git a/Chapters/Future.tex b/Chapters/Future.tex
index 10a883a..420771f 100644
--- a/Chapters/Future.tex
+++ b/Chapters/Future.tex
@@ -1,4 +1,4 @@
-\chapter{Future work}
+\chapter[chap:future]{Future work}
 \section{Improved notation for hierarchical state}
 The hierarchic state model requires quite some boilerplate code for unpacking
 and distributing the input state and collecting and repacking the output
diff --git a/Chapters/HardwareDescription.tex b/Chapters/HardwareDescription.tex
index a0cc1c5..c900596 100644
--- a/Chapters/HardwareDescription.tex
+++ b/Chapters/HardwareDescription.tex
@@ -1,4 +1,4 @@
-\chapter{Hardware description}
+\chapter[chap:description]{Hardware description}
   This chapter will provide an overview of the hardware description language
   that was created and the issues that have arisen in the process. It will
   focus on the issues of the language, not the implementation.
diff --git a/Chapters/Introduction.tex b/Chapters/Introduction.tex
index 69fb7e4..8ffba57 100644
--- a/Chapters/Introduction.tex
+++ b/Chapters/Introduction.tex
@@ -1,4 +1,4 @@
-\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
 of hardware descriptions, the world of functional languages and
diff --git a/Chapters/Normalization.tex b/Chapters/Normalization.tex
index 68d48d4..c1c6268 100644
--- a/Chapters/Normalization.tex
+++ b/Chapters/Normalization.tex
@@ -1,4 +1,4 @@
-\chapter{Normalization}
+\chapter[chap:normalization]{Normalization}
 
 % A helper to print a single example in the half the page width. The example
 % text should be in a buffer whose name is given in an argument.
diff --git a/Chapters/Prototype.tex b/Chapters/Prototype.tex
index 945e920..9e6893a 100644
--- a/Chapters/Prototype.tex
+++ b/Chapters/Prototype.tex
@@ -1,4 +1,4 @@
-\chapter{Prototype}
+\chapter[chap:prototype]{Prototype}
   An important step in this research is the creation of a prototype compiler.
   Having this prototype allows us to apply the ideas from the previous chapter
   to actual hardware descriptions and evaluate their usefulness. Having a
diff --git a/Chapters/State.tex b/Chapters/State.tex
index 0160e55..2cffa21 100644
--- a/Chapters/State.tex
+++ b/Chapters/State.tex
@@ -1,4 +1,4 @@
-\chapter{State}
+\chapter[chap:state]{State}
   \section{Introduction}
     Provide some examples
 
-- 
2.30.2


From 24186af91e8401f45b11b2ba45bc9e9daedc2b55 Mon Sep 17 00:00:00 2001
From: Matthijs Kooijman <matthijs@stdin.nl>
Date: Tue, 29 Sep 2009 17:42:50 +0200
Subject: [PATCH 11/16] Add pretty boxes around various typing environments.

---
 Utils/Lambda.tex | 27 ++++++++++++++++++++++++---
 1 file changed, 24 insertions(+), 3 deletions(-)

diff --git a/Utils/Lambda.tex b/Utils/Lambda.tex
index 4642245..ad11419 100644
--- a/Utils/Lambda.tex
+++ b/Utils/Lambda.tex
@@ -3,21 +3,42 @@
 % transformations.
 %
 
+\startuniqueMPgraphic{box}
+path a, b;
+% Create a rectangle of the full size
+a := unitsquare xyscaled(\overlaywidth,\overlayheight);
+% Randomize it a bit
+b := a randomized 10pt ;
+% And draw it
+drawoptions (withpen pencircle scaled .75mm withcolor black) ;
+draw b; 
+\stopuniqueMPgraphic
+
+\defineoverlay[box][\uniqueMPgraphic{box}]
+
+% Define \{start,stop}boxed with a nice metapost box around it.
+\defineframedtext[boxed][background=box,frame=off]
+% A boxed variant with the width forced to page width. This is used in
+% \startrans, since the content somehow doesn't scale the box around it
+% properly.
+\defineframedtext[wideboxed][background=box,frame=off,width=\textwidth]
+
 % Install the lambda calculus pretty-printer, as defined in pret-lam.lua.
 \installprettytype [LAM] [LAM]
 % Define \startlambda \stoplambda
-\definetyping[lambda][option=LAM,style=sans]
+\definetyping[lambda][option=LAM,style=sans,before=\startboxed,after=\stopboxed]
+
 % Define \lam{} (since \lambda is taken)
 \definetype[lam][option=LAM,style=sans]
 
 % Install the transformation pretty-printer, as defined in pret-trans.lua.
 \installprettytype [TRANS] [TRANS]
 % Define \starttrans \stoptrans
-\definetyping[trans][option=TRANS,style=normal,before=]
+\definetyping[trans][option=TRANS,style=normal,before=\startwideboxed,after=\stopwideboxed]
 
 % Install the haskell pretty-printer, as defined in pret-haskell.lua.
 \installprettytype [HASKELL] [HASKELL]
 % Define \starthaskell \stophaskell
-\definetyping[haskell][option=HASKELL,before=,after=]
+\definetyping[haskell][option=HASKELL,before=\startboxed,after=\stopboxed]
 % Define \hs
 \definetype[hs][option=HASKELL,style=mono]
-- 
2.30.2


From 4f0ad92ab36aa4f87bc4a16cb5f7733bbef41428 Mon Sep 17 00:00:00 2001
From: Matthijs Kooijman <matthijs@stdin.nl>
Date: Tue, 29 Sep 2009 17:43:18 +0200
Subject: [PATCH 12/16] Tweak the sizes of the frames in transformations a bit.

Because we added an extra frame before, with its own offset, the frames
used to put the transformation and conditions next to each other became a
bit too big.
---
 Utils/Lambda.tex | 2 +-
 pret-trans.lua   | 6 +++---
 2 files changed, 4 insertions(+), 4 deletions(-)

diff --git a/Utils/Lambda.tex b/Utils/Lambda.tex
index ad11419..70c583d 100644
--- a/Utils/Lambda.tex
+++ b/Utils/Lambda.tex
@@ -21,7 +21,7 @@ draw b;
 % A boxed variant with the width forced to page width. This is used in
 % \startrans, since the content somehow doesn't scale the box around it
 % properly.
-\defineframedtext[wideboxed][background=box,frame=off,width=\textwidth]
+\defineframedtext[wideboxed][background=box,frame=off,width=\textwidth,offset=.02\textwidth]
 
 % Install the lambda calculus pretty-printer, as defined in pret-lam.lua.
 \installprettytype [LAM] [LAM]
diff --git a/pret-trans.lua b/pret-trans.lua
index a96002f..1d2eb95 100644
--- a/pret-trans.lua
+++ b/pret-trans.lua
@@ -13,15 +13,15 @@ local vis = buffers.newvisualizer("trans")
 
 local commands = {}
 -- A command to create a horizontal rule.
-commands.rule = "\\blackrule[height=0.5pt,depth=0pt,width=.45\\textwidth]"
+commands.rule = "\\blackrule[height=0.5pt,depth=0pt,width=.40\\textwidth]"
 -- Pretty printer to use for the stuff before and after the line
 commands.before_pret = "lam"
 commands.after_pret = "lam"
 -- Frame commands to use for the left (before + line + after) and right
 -- (conditions) parts. Should include an opening {, which will be closed
 -- automatically.
-commands.leftframe = "\\framed[offset=0mm,location=middle,strut=no,align=right,frame=off,width=.5\\textwidth]{\\sans"
-commands.rightframe = "\\framed[offset=0mm,location=middle,strut=no,align=right,frame=off,width=.5\\textwidth]{"
+commands.leftframe = "\\framed[offset=0mm,location=middle,strut=no,align=right,frame=off,width=.48\\textwidth]{\\sans"
+commands.rightframe = "\\framed[offset=0mm,location=middle,strut=no,align=right,frame=off,width=.48\\textwidth]{"
 
 -- A table to keep the lines in this buffer, so we can process them all at
 -- once at the end.
-- 
2.30.2


From af417b97de0fc5fe1257481e94a9532c205c6ce4 Mon Sep 17 00:00:00 2001
From: Matthijs Kooijman <matthijs@stdin.nl>
Date: Tue, 29 Sep 2009 18:02:00 +0200
Subject: [PATCH 13/16] Put a fancy box around transformation examples as well.

---
 Chapters/Normalization.tex | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/Chapters/Normalization.tex b/Chapters/Normalization.tex
index c1c6268..efd59ff 100644
--- a/Chapters/Normalization.tex
+++ b/Chapters/Normalization.tex
@@ -7,7 +7,7 @@
 % will end up on a single line. The strut=no option prevents a bunch of empty
 % space at the start of the frame.
 \define[1]\example{
-  \framed[offset=1mm,align=right,strut=no]{
+  \framed[offset=1mm,align=right,strut=no,background=box,frame=off]{
     \setuptyping[option=LAM,style=sans,before=,after=]
     \typebuffer[#1]
     \setuptyping[option=none,style=\tttf]
-- 
2.30.2


From 3fb953c21f9258fea8b4a0df8f80e2dc2e40acb6 Mon Sep 17 00:00:00 2001
From: Matthijs Kooijman <matthijs@stdin.nl>
Date: Tue, 29 Sep 2009 18:06:54 +0200
Subject: [PATCH 14/16] Make the box randomization scale with the box size.

Previously, small boxes would sometimes be warped to much, causing content
to fall out.
---
 Utils/Lambda.tex | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/Utils/Lambda.tex b/Utils/Lambda.tex
index 70c583d..2426178 100644
--- a/Utils/Lambda.tex
+++ b/Utils/Lambda.tex
@@ -8,7 +8,7 @@ path a, b;
 % Create a rectangle of the full size
 a := unitsquare xyscaled(\overlaywidth,\overlayheight);
 % Randomize it a bit
-b := a randomized 10pt ;
+b := a randomized (\overlaywidth / 25) ;
 % And draw it
 drawoptions (withpen pencircle scaled .75mm withcolor black) ;
 draw b; 
-- 
2.30.2


From d4ef2f4768796c2f317ba8a3808900a5b30d87b5 Mon Sep 17 00:00:00 2001
From: Matthijs Kooijman <matthijs@stdin.nl>
Date: Wed, 30 Sep 2009 11:39:55 +0200
Subject: [PATCH 15/16] Add TODO about globbed spaces after \eg and \ie.

---
 Utils/Shortcuts.tex | 1 +
 1 file changed, 1 insertion(+)

diff --git a/Utils/Shortcuts.tex b/Utils/Shortcuts.tex
index ecf4fed..75bff27 100644
--- a/Utils/Shortcuts.tex
+++ b/Utils/Shortcuts.tex
@@ -4,5 +4,6 @@
 
 
 % A shortcut for italicized e.g. and i.e.
+% TODO: Prevent this macro from globbing the following space
 \define[0]\eg{{\em e.g.}}
 \define[0]\ie{{\em i.e.}}
-- 
2.30.2


From 2e1c7f4982d5e485feff87b9dae7a34fb7c0e7bf Mon Sep 17 00:00:00 2001
From: Matthijs Kooijman <matthijs@stdin.nl>
Date: Wed, 30 Sep 2009 13:56:09 +0200
Subject: [PATCH 16/16] Add \HLine command that draws a horizontal line.

This line is drawn using metapost, to make it look more consistent with
the other boxes etc.
---
 Utils/Lambda.tex | 19 +++++++++++++++++++
 1 file changed, 19 insertions(+)

diff --git a/Utils/Lambda.tex b/Utils/Lambda.tex
index 2426178..24230d8 100644
--- a/Utils/Lambda.tex
+++ b/Utils/Lambda.tex
@@ -3,6 +3,25 @@
 % transformations.
 %
 
+\startuniqueMPgraphic{HLine}
+path a, b;
+% Create a rectangle of the full size
+a := origin -- (\MPvar{width}, 0mm);
+% Randomize it a bit
+%b := a randomized (\overlaywidth / 25) ;
+% And draw it
+drawoptions (withpen pencircle scaled .75mm withcolor black) ;
+draw a; 
+\stopuniqueMPgraphic
+
+% Draw a line with the given options. Accepts only the 'width' option. Be
+% careful that these are metapost options, so use \the\textwidth instead of
+% textwidth, and a metapost expression for arithmethic (e.g. 0.5 *
+% \the\textwidth instead of 0.5\textwidth).
+\def\HLine[#1]%
+  {\setupMPvariables[HLine][#1]%
+  \uniqueMPgraphic{HLine}}
+
 \startuniqueMPgraphic{box}
 path a, b;
 % Create a rectangle of the full size
-- 
2.30.2