Chapters/Prototype.tex

   1 \chapter{Prototype}
   2   An important step in this research is the creation of a prototype compiler.
   3   Having this prototype allows us to apply the ideas from the previous chapter
   4   to actual hardware descriptions and evaluate their usefulness. Having a
   5   prototype also helps to find new techniques and test possible
   6   interpretations.
   7
   8   Obviously the prototype was not created after all research
   9   ideas were formed, but its implementation has been interleaved with the
  10   research itself. Also, the prototype described here is the final version, it
  11   has gone through a number of design iterations which we will not completely
  12   describe here.
  13
  14   \section{Choice of language}
  15     When implementing this prototype, the first question to ask is: What
  16     (functional) language will we use to describe our hardware? (Note that
  17     this does not concern the \emph{implementation language} of the compiler,
  18     just the language \emph{translated by} the compiler).
  19
  20     On the highest level, we have two choices:
  21
  22     \startitemize
  23       \item Create a new functional language from scratch. This has the
  24       advantage of having a language that contains exactly those elements that
  25       are convenient for describing hardware and can contain special
  26       constructs that might.
  27       \item Use an existing language and create a new backend for it. This has
  28       the advantage that existing tools can be reused, which will speed up
  29       development.
  30     \stopitemize
  31
  32     Considering that we required a prototype which should be working quickly,
  33     and that implementing parsers, semantic checkers and especially
  34     typcheckers isn't exactly the core of this research (but it is lots and
  35     lots of work!), using an existing language is the obvious choice. This
  36     also has the advantage that a large set of language features is available
  37     to experiment with and it is easy to find which features apply well and
  38     which don't. A possible second prototype could use a custom language with
  39     just the useful features (and possibly extra features that are specific to
  40     the domain of hardware description as well).
  41
  42     The second choice is to pick one of the many existing languages. As
  43     mentioned before, this language is Haskell.  This choice has not been the
  44     result of a thorough comparison of languages, for the simple reason that
  45     the requirements on the language were completely unclear at the start of
  46     this language. The fact that Haskell is a language with a broad spectrum
  47     of features, that it is commonly used in research projects and that the
  48     primary compiler, GHC, provides a high level API to its internals, made
  49     Haskell an obvious choice.
  50
  51     TODO: Was Haskell really a good choice? Perhaps say this somewhere else?
  52
  53   \section{Prototype design}
  54     As stated above, we will use the Glasgow Haskell Compiler (\small{GHC}) to
  55     implement our prototype compiler. To understand the design of the
  56     compiler, we will first dive into the \small{GHC} compiler a bit. It's
  57     compilation consists of the following steps (slightly simplified):
  58
  59     \startdesc{Frontend}
  60       This step takes the Haskell source files and parses them into an
  61       abstract syntax tree (\small{AST}). This \small{AST} can express the
  62       complete Haskell language and is thus a very complex one (in contrast
  63       with the Core \small{AST}, later on). All identifiers in this
  64       \small{AST} are resolved by the renamer and all types are checked by the
  65       typechecker.
  66     \stopdesc
  67     \startdesc{Desugaring}
  68       This steps takes the full \small{AST} and translates it to the
  69       \emph{Core} language. Core is a very small functional language with lazy
  70       semantics, that can still express everything Haskell can express. Its
  71       simpleness makes Core very suitable for further simplification and
  72       translation. Core is the language we will be working on as well.
  73     \stopdesc
  74     \startdesc{Simplification}
  75       Through a number of simplification steps (such as inlining, common
  76       subexpression elimination, etc.) the Core program is simplified to make
  77       it faster or easier to process further.
  78     \stopdesc
  79     \startdesc{Backend}
  80       This step takes the simplified Core program and generates an actual
  81       runnable program for it. This is a big and complicated step we will not
  82       discuss it any further, since it is not required for our prototype.
  83     \stopdesc
  84
  85         Core - description of the language (appendix?)
  86         Stages (-> Core, Normalization, -> VHDL)
  87         Implementation issues
  88
  89         Haskell language coverage / constraints
  90                 Recursion
  91                 Builtin types
  92                 Custom types (Sum types, product types)
  93                 Function types / higher order expressions
  94