Add initial sketch for conclusions.
[matthijs/master-project/report.git] / 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: -->