+\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
+ 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):
+
+ \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
+ 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
+
+ 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].
+
+
projects / matthijs / master-project / report.git / blobdiff