Reorder and complete the list of transformations.
[matthijs/master-project/report.git] / progress-2009.01.28.txt
1 How to model hardware?
2 ======================
3 So far, we've had some ideas about how to model hardware using a functional
4 language. The general idea is that every function that models hardware has
5 some input signals, some "input" state and a few output signals and "output"
6 state. But how do we represent this exactly in our haskell code?
7
8 The output part is probably easiest, since a function always returns a single
9 value. Since it needs to return both output signals and a state, it seems
10 obvious to make it always return a 2-tuple containing the state and output
11 signals. So:
12     
13     circuit :: ? -> (State, Signals)                                    (1)
14
15 It's interesting to note that the State and Signal types here are not really
16 important when simulating, so let's look at the inputs first.
17
18 Again, we have both input signals and a state to pass to the function. It
19 seems consistent to again do this a single tuple, so a circuit becomes:
20
21     circuit :: (State, Signals) -> (State, Signals)                     (2)
22
23 I've not given this variant a lot of thought yet, but i have the feeling this
24 is not all to useful. The variant I've been using so far separates the state
25 and signals into separate arguments:
26
27     circuit :: Signals -> State -> (State, Signals)                     (4)
28
29 Note that this uses a seemingly inconsistent order for the arguments, but
30 that's mostly because the current implementation uses this order (and wasn't
31 well thought out). The exact order is mostly relevant for partial application,
32 but I'm not quite sure if that's possible or useful at all.
33
34 This variant makes it easy to define a dependent type for all circuits, which
35 you pass the input, state and output types as an argument:
36
37     type Circuit a s b = a -> s -> (s, b)                               (5)
38
39 A last variant would be to separate each (or perhaps only some) input signals
40 into different arguments, such that each input has its own argument. For
41 example, for a two input port circuit:
42
43     circuit :: Signal -> Signal -> State -> (State, Signals)            (6)
44
45 This has the obvious advantage that it could support partial application of
46 the input ports (ie, connect a few input pins to a circuit and pass the
47 resulting function elsewhere). I'm not sure how that would or should work out,
48 but it seems useful.
49
50 However, this partial application seems only possible with input ports, which
51 might limit its usefuleness. Also, this type signature makes it harder to
52 define a single Circuit type that catches all circuits as with (4) and (5).
53 This might make simulation more tricky, though it's probably not critical.
54
55 Signals (or Ports?)
56 -------------------
57 Now, regardless of which of the above approaches we choose, there should be
58 some way to model these signals and ports. So far, a basic Bit signal type
59 has been used:
60
61     data Bit = High | Low | DontCare                                    (7)
62
63 For now, this is the only primitive type supported by the (Haskell-to-VHDL)
64 translator, but as pointed out above the simulator doesn't really care about
65 these types (as long as the input provided is of the right type). Supporting
66 native Haskell types (or perhaps our own variants, *e.g.*, an Int with a fixed
67 bit width) is probably needed later on as well.
68
69 To allow for multiple input and output ports in a single value, tuples can be
70 used. This allows for grouping multiple signals while still allowing each
71 signal to have a different type.
72
73 An alternative that has not been explored yet is the use of an algebraic type
74 to group signals. This seems to have the direct advantage of allowing names
75 for each element to be specified, but does add some overhead in type
76 declarations. It's likely that a combination of tuples and algebraic types are
77 best.
78
79 It appears that lists might become useful to model VHDL (bit)vectors, since
80 both lists and vectors have elements of the same type. This does require that
81 the length of a list can be deduced at compile time.
82
83 DontCare
84 --------
85 In the above definition of the Bit datatype a DontCare element was present.
86 The idea behind this element was to assign it anywhere the value of the bit
87 shouldn't matter (in the alu example, this is but on the input signals that
88 should be ignored). Since it is not used in any other place (*e.g.*, patterns
89 usually only match Low and High, including the display functions), Haskell
90 should error out as soon as a DontCare value is actually used. Due to the lazy
91 nature of Haskell's evaluation, this should never happen as long as the value
92 is not really used. But as soon as the value is (indirectly) needed, *i.e.*,
93 contributes to the output of a circuit, Haskell errors out.
94
95 Some functions ignore some inputs. For example, hwor is defined as:
96
97     High `hwor` _  = High                                               (8)
98     _ `hwor` High  = High
99     Low `hwor` Low = Low
100
101 This means that High `hwxor` DontCare will still be High (with no error), but
102 that DontCare `hwand` DontCare will immediately throw an error. This seems to
103 be desired behaviour, but this needs more investigation. 
104
105 State
106 -----
107 For state, we can mostly do the same reasoning as for signals (from the
108 circuit description point of view, input state and output state is hardly any
109 differen from input signals and output signals). For combining multiple
110 elements of state (either because a circuit has multiple Bits of state or
111 because it combines the states of each of its subcircuits), tuples can be
112 used. Algebraic types might have a use here as well.
113
114 Stateless circuits
115 ------------------
116 Above we've concentrated on stateful circuits, but probably a lot of circuits
117 will be stateless. This can simply be modeled by having an empty state
118 (*i.e.*, () ), but that's not very elegant. However, not all of the above
119 approaches are usable for supporting stateless circuits. For example, if we
120 adapt (2) to be stateless:
121
122     stateless_circuit :: Signals -> Signals                             (9)
123
124 Now, considering that we allowed Signals to be a tuple of multiple signals,
125 the following two circuit types are indistinguishable, since the State and
126 Signal types are the same.
127
128     stateless_circuit :: (Signal, Signal) -> (Signal, Signal)           (10)
129     stateful_circuit :: (State, Signal) -> (State, Signal)
130
131 Something similar goes for (6), where leaving out the state for stateless
132 circuits would make a stateless circuit with two inputs and two output
133 indistinguishable from a stateful circuit with a single input and a single
134 output.
135
136 (4) above seems best suited for adapting for stateless circuits, since it
137 always has two arguments (inputs and state). A stateless variant would always
138 have a single argument.
139
140 Examples
141 --------
142 To get a feeling for things, here are some example using approach (6).
143
144 Some stateless adders:
145
146     -- Combinatoric stateless no-carry adder
147     -- A -> B -> S
148     no_carry_adder :: (Bit, Bit) -> Bit
149     no_carry_adder (a, b) = a `hwxor` b
150
151     -- Combinatoric stateless half adder
152     -- A -> B -> (S, C)
153     half_adder :: (Bit, Bit) -> (Bit, Bit)
154     half_adder (a, b) = 
155       ( a `hwxor` b, a `hwand` b )
156
157     -- Combinatoric stateless full adder
158     -- (A, B, C) -> (S, C)
159     full_adder :: (Bit, Bit, Bit) -> (Bit, Bit)
160     full_adder (a, b, cin) = (s, c)
161       where
162         s = a `hwxor` b `hwxor` cin
163         c = a `hwand` b `hwor` (cin `hwand` (a `hwxor` b))
164
165 A simple four bit cyclic shift register, which has an input that can be used
166 to toggle (xor) the first position.
167
168     type ShifterState = [Bit]
169     shifter :: Bit -> ShifterState -> (ShifterState, Bit)
170     shifter i s =
171       (s', o)
172       where
173         s' = (o `hwxor` i) : (init s)
174         o  = last s
175
176 An implementation of a simple ALU (supporting only two operations: or & and on
177 two one-bit inputs) combined with a register bank containing two one-bit
178 registers. It also contains a list of inputs (the program), an initial state
179 and some wrappers around the simulation functions (main and mainIO).
180
181     main = Sim.simulate exec program initial_state
182     mainIO = Sim.simulateIO exec initial_state
183
184     program = [
185                 -- (addr, we, op)
186                 (High, Low, High), -- z = r1 and t (0) ; t = r1 (1)
187                 (Low, Low, Low), -- z = r0 or t (1); t = r0 (0)
188                 (Low, High, DontCare), -- r0 = z (1)
189                 (High, Low, High), -- z = r1 and t (0); t = r1 (1)
190                 (High, High, DontCare) -- r1 = z (0)
191               ]
192
193     initial_state = ((Low, High), (), Low, Low)
194
195     -- Register bank
196
197     type RegAddr = Bit
198     type RegisterBankState = (Bit, Bit)
199     register_bank :: 
200       (RegAddr, Bit, Bit) -> -- (addr, we, d)
201       RegisterBankState -> -- s
202       (RegisterBankState, Bit) -- (s', o)
203
204     register_bank (Low, Low, _) s = -- Read r0
205       (s, fst s)
206
207     register_bank (High, Low, _) s = -- Read r1
208       (s, snd s)
209
210     register_bank (addr, High, d) s = -- Write
211       (s', DontCare)
212       where
213         (r0, r1) = s
214         r0' = if addr == Low then d else r0
215         r1' = if addr == High then d else r1
216         s' = (r0', r1')
217
218     -- ALU
219
220     type AluState = ()
221     type AluOp = Bit
222
223     alu :: (AluOp, Bit, Bit) -> AluState -> (AluState, Bit)
224     alu (High, a, b) s = ((), a `hwand` b)
225     alu (Low, a, b) s = ((), a `hwor` b)
226
227     type ExecState = (RegisterBankState, AluState, Bit, Bit)
228     exec :: (RegAddr, Bit, AluOp) -> ExecState -> (ExecState, ())
229
230     -- Read & Exec
231     exec (addr, Low, op) s =
232       (s', ())
233       where
234         (reg_s, alu_s, t, z) = s
235         (reg_s', t') = register_bank (addr, Low, DontCare) reg_s
236         (alu_s', z') = alu (op, t', t) alu_s
237         s' = (reg_s', alu_s', t', z')
238
239     -- Write
240     exec (addr, High, op) s =
241       (s', ())
242       where
243         (reg_s, alu_s, t, z) = s
244         (reg_s', _) = register_bank (addr, High, z) reg_s
245         s' = (reg_s', alu_s, t, z)