progress-2009.01.14.txt

   1 Language Design
   2 ===============
   3 A central question is, what do we want our language to look like? Deciding to
   4 use haskell would be a first step, but that still leaves a lot of
   5 possibilities. However, why would we want to use Haskell?
   6
   7   * Lots of existing support: Language specification, compilers, libraries,
   8     userbase. All of this reduces the workload to implement something.
   9   * All of Haskell is usable in simulation / testing: When not compiling to
  10     VHDL, but when doing functional tests, we can use all of Haskell's syntax,
  11     libraries, functions, etc. even when we don't support all of it in our
  12     compiler.
  13   * Haskell is probably expressive enough to be able to express a lot of
  14     different things and different approaches. By defining new (algebraic)
  15     types and operators, we can extend this even further. Finally, we could
  16     even use Template Haskell to do almost anything (The ForSyDe project uses
  17     Template Haskell extensively).
  18
  19 Typing
  20 ------
  21 What kind of types will we be using in our programs? The base type should be
  22 some kind of bit type, but there are two main options for these:
  23
  24   * Use a single bit as a type. Calculations on these types represent the
  25     calculations in a single time slice (ie, during one clock cycle). Any
  26     state in the calculation is explicit, since the input state must be a
  27     function argument and the output state part of the function's value.
  28
  29     Through the state values, these functions are closely tied to the clock
  30     domain in use (or whatever other model is used for the time domain). Ie,
  31     having different clock domains is non-trivial and will require
  32     modification to the function.
  33
  34     Composition can be done by simply connection functions together. This does
  35     require that the "state" of a function contains the states of each of the
  36     function it calls. These are extracted from its state argument and passed
  37     on to the callees, while the states returned are again inserted into the
  38     resulting state of the outer function.
  39
  40     This approach is the closest to normal functional programming and shows
  41     state very explicitly.
  42
  43   * Use a stream of bits as a type. Each value models a continuous (infinite)
  44     stream of bits. Functions have streams as arguments and value and state
  45     could probably be implicit in the calculation or could be made explicit
  46     using delay elements (this is what Lava does).
  47
  48     The primitive operations all operate on streams, which seems the
  49     fundamental difference between this and the previous approach.
  50
  51     This approach shows structure more explicitly when delay elements are
  52     used, since the registers end up exactly there.
  53
  54 It is probably possible to mix these approaches. In particular, the first
  55 approache eventually needs to do some I/O, which can be modeled as recursion
  56 over an infinite list of inputs resulting in an infinite list of outputs. This
  57 can be done at the top level always, but it is perhaps possible to move this
  58 recursion a bit downward and do composition based on stream functions instead
  59 of "single clock" functions. One problem that comes to mind is that one needs
  60 to guarantee that a function does not look into the future (ie, uses multiple
  61 input elements to generate one output element) and the state becomes a lot
  62 less explicit. This needs more thought.
  63
  64 Implementation
  65 ==============
  66 Assume we will want to translate a (subset of) haskell into something else.
  67 We will need to do parsing, typechecking, interpretation, etc. A few options
  68 for this are available:
  69
  70   * Doing everything manually, possibly using a parser generator.
  71     Lot's of work. Requires us to write down the haskell grammar, create a
  72     parser, do all kinds of funky type checking -> Too much work.
  73   * Use the Language.Haskell library and write something in haskell. This
  74     library contains a Lexer, Parser and AST, but still does not do any type
  75     checking, desugaring and simplification. Still lots of work.
  76   * Hack into an existing compiler. By writing a backend for an existing
  77     compiler, we can save most of the haskell-specific work. This requires a
  78     compiler that is modular enough to have its backend replaced by another
  79     implementation. Also, the border between backend and frontend must be
  80     suited for the work we would like to do. This approach would use the
  81     original compiler's driver for the most part
  82   * Use components from an existing compiler. By reusing selected components
  83     and creating an own driver that uses these components, we can work with
  84     the haskell source without doing all the work ourselves. This requires a
  85     compiler that is very modular, so we can decide exactly which parts we
  86     would like to use and which we don't need.
  87
  88 After some looking around it seems GHC provides a consistent and (as of
  89 version 6.10) documented API into its internals This allows us to write
  90
  91     core <- compileToCoreSimplified "adder.hs"
  92
  93 to compile the file `adder.hs` into a version in GHC's simplified CoreSyn
  94 representation. This is essentially an AST with type annotations, all
  95 syntactic sugar removed, redundant expressions simplified, etc. This seems to
  96 be a very useful form to work with. However, GHC provides other functions to
  97 access other parts of the compiler, so if we would like to access the source
  98 at another stage, or do some custom procesing in between, this is also
  99 possible (albeit a bit more complex than this).
 100
 101 Problems
 102 --------
 103 Some problems encountered or expected when trying to do some initial
 104 translator hackup:
 105
 106   * Signal naming. In the generated VHDL the signals and ports need names.
 107     These can of course be generated, but if we want to do some actual
 108     debugging, we want useful signal names. For input ports generated from
 109     function arguments, the binder name could perhaps be used, but that is not
 110     always possible when patterns are more complex.
 111
 112     For output ports, a name could be deduced when the output value is always
 113     computed in a where or let clause. However the simplification phase
 114     removes these clauses where possible, so this information is lost.
 115
 116     Perhaps some way of explicitely labeling ports could be used.
 117   * Type classes and universal qualification types are a powerful way of
 118     making functions generic, which greatly increases their reusability.
 119     However, this extra genericity makes the resulting Core representation
 120     more complex. Since the actual types used are modeled as extra function
 121     arguments, this shouldn't be too hard, but this is something that probably
 122     needs implementation right away (because a lot of builtin haskell
 123     constructs, such as tuples, use it).
 124
 125 <!-- vim: set sw=2 sts=2 ts=8: -->