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?
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
13 circuit :: ? -> (State, Signals) (1)
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.
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:
21 circuit :: (State, Signals) -> (State, Signals) (2)
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:
27 circuit :: Signals -> State -> (State, Signals) (4)
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.
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:
37 type Circuit a s b = a -> s -> (s, b) (5)
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:
43 circuit :: Signal -> Signal -> State -> (State, Signals) (6)
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,
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.
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
61 data Bit = High | Low | DontCare (7)
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.
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.
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
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.
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.
95 Some functions ignore some inputs. For example, hwor is defined as:
97 High `hwor` _ = High (8)
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.
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.
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:
122 stateless_circuit :: Signals -> Signals (9)
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.
128 stateless_circuit :: (Signal, Signal) -> (Signal, Signal) (10)
129 stateful_circuit :: (State, Signal) -> (State, Signal)
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
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.
142 To get a feeling for things, here are some example using approach (6).
144 Some stateless adders:
146 -- Combinatoric stateless no-carry adder
148 no_carry_adder :: (Bit, Bit) -> Bit
149 no_carry_adder (a, b) = a `hwxor` b
151 -- Combinatoric stateless half adder
153 half_adder :: (Bit, Bit) -> (Bit, Bit)
155 ( a `hwxor` b, a `hwand` b )
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)
162 s = a `hwxor` b `hwxor` cin
163 c = a `hwand` b `hwor` (cin `hwand` (a `hwxor` b))
165 A simple four bit cyclic shift register, which has an input that can be used
166 to toggle (xor) the first position.
168 type ShifterState = [Bit]
169 shifter :: Bit -> ShifterState -> (ShifterState, Bit)
173 s' = (o `hwxor` i) : (init s)
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).
181 main = Sim.simulate exec program initial_state
182 mainIO = Sim.simulateIO exec initial_state
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)
193 initial_state = ((Low, High), (), Low, Low)
198 type RegisterBankState = (Bit, Bit)
200 (RegAddr, Bit, Bit) -> -- (addr, we, d)
201 RegisterBankState -> -- s
202 (RegisterBankState, Bit) -- (s', o)
204 register_bank (Low, Low, _) s = -- Read r0
207 register_bank (High, Low, _) s = -- Read r1
210 register_bank (addr, High, d) s = -- Write
214 r0' = if addr == Low then d else r0
215 r1' = if addr == High then d else r1
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)
227 type ExecState = (RegisterBankState, AluState, Bit, Bit)
228 exec :: (RegAddr, Bit, AluOp) -> ExecState -> (ExecState, ())
231 exec (addr, Low, op) s =
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')
240 exec (addr, High, op) s =
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)