+++ /dev/null
-How to model hardware?
-======================
-So far, we've had some ideas about how to model hardware using a functional
-language. The general idea is that every function that models hardware has
-some input signals, some "input" state and a few output signals and "output"
-state. But how do we represent this exactly in our haskell code?
-
-The output part is probably easiest, since a function always returns a single
-value. Since it needs to return both output signals and a state, it seems
-obvious to make it always return a 2-tuple containing the state and output
-signals. So:
-
- circuit :: ? -> (State, Signals) (1)
-
-It's interesting to note that the State and Signal types here are not really
-important when simulating, so let's look at the inputs first.
-
-Again, we have both input signals and a state to pass to the function. It
-seems consistent to again do this a single tuple, so a circuit becomes:
-
- circuit :: (State, Signals) -> (State, Signals) (2)
-
-I've not given this variant a lot of thought yet, but i have the feeling this
-is not all to useful. The variant I've been using so far separates the state
-and signals into separate arguments:
-
- circuit :: Signals -> State -> (State, Signals) (4)
-
-Note that this uses a seemingly inconsistent order for the arguments, but
-that's mostly because the current implementation uses this order (and wasn't
-well thought out). The exact order is mostly relevant for partial application,
-but I'm not quite sure if that's possible or useful at all.
-
-This variant makes it easy to define a dependent type for all circuits, which
-you pass the input, state and output types as an argument:
-
- type Circuit a s b = a -> s -> (s, b) (5)
-
-A last variant would be to separate each (or perhaps only some) input signals
-into different arguments, such that each input has its own argument. For
-example, for a two input port circuit:
-
- circuit :: Signal -> Signal -> State -> (State, Signals) (6)
-
-This has the obvious advantage that it could support partial application of
-the input ports (ie, connect a few input pins to a circuit and pass the
-resulting function elsewhere). I'm not sure how that would or should work out,
-but it seems useful.
-
-However, this partial application seems only possible with input ports, which
-might limit its usefuleness. Also, this type signature makes it harder to
-define a single Circuit type that catches all circuits as with (4) and (5).
-This might make simulation more tricky, though it's probably not critical.
-
-Signals (or Ports?)
--------------------
-Now, regardless of which of the above approaches we choose, there should be
-some way to model these signals and ports. So far, a basic Bit signal type
-has been used:
-
- data Bit = High | Low | DontCare (7)
-
-For now, this is the only primitive type supported by the (Haskell-to-VHDL)
-translator, but as pointed out above the simulator doesn't really care about
-these types (as long as the input provided is of the right type). Supporting
-native Haskell types (or perhaps our own variants, *e.g.*, an Int with a fixed
-bit width) is probably needed later on as well.
-
-To allow for multiple input and output ports in a single value, tuples can be
-used. This allows for grouping multiple signals while still allowing each
-signal to have a different type.
-
-An alternative that has not been explored yet is the use of an algebraic type
-to group signals. This seems to have the direct advantage of allowing names
-for each element to be specified, but does add some overhead in type
-declarations. It's likely that a combination of tuples and algebraic types are
-best.
-
-It appears that lists might become useful to model VHDL (bit)vectors, since
-both lists and vectors have elements of the same type. This does require that
-the length of a list can be deduced at compile time.
-
-DontCare
---------
-In the above definition of the Bit datatype a DontCare element was present.
-The idea behind this element was to assign it anywhere the value of the bit
-shouldn't matter (in the alu example, this is but on the input signals that
-should be ignored). Since it is not used in any other place (*e.g.*, patterns
-usually only match Low and High, including the display functions), Haskell
-should error out as soon as a DontCare value is actually used. Due to the lazy
-nature of Haskell's evaluation, this should never happen as long as the value
-is not really used. But as soon as the value is (indirectly) needed, *i.e.*,
-contributes to the output of a circuit, Haskell errors out.
-
-Some functions ignore some inputs. For example, hwor is defined as:
-
- High `hwor` _ = High (8)
- _ `hwor` High = High
- Low `hwor` Low = Low
-
-This means that High `hwxor` DontCare will still be High (with no error), but
-that DontCare `hwand` DontCare will immediately throw an error. This seems to
-be desired behaviour, but this needs more investigation.
-
-State
------
-For state, we can mostly do the same reasoning as for signals (from the
-circuit description point of view, input state and output state is hardly any
-differen from input signals and output signals). For combining multiple
-elements of state (either because a circuit has multiple Bits of state or
-because it combines the states of each of its subcircuits), tuples can be
-used. Algebraic types might have a use here as well.
-
-Stateless circuits
-------------------
-Above we've concentrated on stateful circuits, but probably a lot of circuits
-will be stateless. This can simply be modeled by having an empty state
-(*i.e.*, () ), but that's not very elegant. However, not all of the above
-approaches are usable for supporting stateless circuits. For example, if we
-adapt (2) to be stateless:
-
- stateless_circuit :: Signals -> Signals (9)
-
-Now, considering that we allowed Signals to be a tuple of multiple signals,
-the following two circuit types are indistinguishable, since the State and
-Signal types are the same.
-
- stateless_circuit :: (Signal, Signal) -> (Signal, Signal) (10)
- stateful_circuit :: (State, Signal) -> (State, Signal)
-
-Something similar goes for (6), where leaving out the state for stateless
-circuits would make a stateless circuit with two inputs and two output
-indistinguishable from a stateful circuit with a single input and a single
-output.
-
-(4) above seems best suited for adapting for stateless circuits, since it
-always has two arguments (inputs and state). A stateless variant would always
-have a single argument.
-
-Examples
---------
-To get a feeling for things, here are some example using approach (6).
-
-Some stateless adders:
-
- -- Combinatoric stateless no-carry adder
- -- A -> B -> S
- no_carry_adder :: (Bit, Bit) -> Bit
- no_carry_adder (a, b) = a `hwxor` b
-
- -- Combinatoric stateless half adder
- -- A -> B -> (S, C)
- half_adder :: (Bit, Bit) -> (Bit, Bit)
- half_adder (a, b) =
- ( a `hwxor` b, a `hwand` b )
-
- -- Combinatoric stateless full adder
- -- (A, B, C) -> (S, C)
- full_adder :: (Bit, Bit, Bit) -> (Bit, Bit)
- full_adder (a, b, cin) = (s, c)
- where
- s = a `hwxor` b `hwxor` cin
- c = a `hwand` b `hwor` (cin `hwand` (a `hwxor` b))
-
-A simple four bit cyclic shift register, which has an input that can be used
-to toggle (xor) the first position.
-
- type ShifterState = [Bit]
- shifter :: Bit -> ShifterState -> (ShifterState, Bit)
- shifter i s =
- (s', o)
- where
- s' = (o `hwxor` i) : (init s)
- o = last s
-
-An implementation of a simple ALU (supporting only two operations: or & and on
-two one-bit inputs) combined with a register bank containing two one-bit
-registers. It also contains a list of inputs (the program), an initial state
-and some wrappers around the simulation functions (main and mainIO).
-
- main = Sim.simulate exec program initial_state
- mainIO = Sim.simulateIO exec initial_state
-
- program = [
- -- (addr, we, op)
- (High, Low, High), -- z = r1 and t (0) ; t = r1 (1)
- (Low, Low, Low), -- z = r0 or t (1); t = r0 (0)
- (Low, High, DontCare), -- r0 = z (1)
- (High, Low, High), -- z = r1 and t (0); t = r1 (1)
- (High, High, DontCare) -- r1 = z (0)
- ]
-
- initial_state = ((Low, High), (), Low, Low)
-
- -- Register bank
-
- type RegAddr = Bit
- type RegisterBankState = (Bit, Bit)
- register_bank ::
- (RegAddr, Bit, Bit) -> -- (addr, we, d)
- RegisterBankState -> -- s
- (RegisterBankState, Bit) -- (s', o)
-
- register_bank (Low, Low, _) s = -- Read r0
- (s, fst s)
-
- register_bank (High, Low, _) s = -- Read r1
- (s, snd s)
-
- register_bank (addr, High, d) s = -- Write
- (s', DontCare)
- where
- (r0, r1) = s
- r0' = if addr == Low then d else r0
- r1' = if addr == High then d else r1
- s' = (r0', r1')
-
- -- ALU
-
- type AluState = ()
- type AluOp = Bit
-
- alu :: (AluOp, Bit, Bit) -> AluState -> (AluState, Bit)
- alu (High, a, b) s = ((), a `hwand` b)
- alu (Low, a, b) s = ((), a `hwor` b)
-
- type ExecState = (RegisterBankState, AluState, Bit, Bit)
- exec :: (RegAddr, Bit, AluOp) -> ExecState -> (ExecState, ())
-
- -- Read & Exec
- exec (addr, Low, op) s =
- (s', ())
- where
- (reg_s, alu_s, t, z) = s
- (reg_s', t') = register_bank (addr, Low, DontCare) reg_s
- (alu_s', z') = alu (op, t', t) alu_s
- s' = (reg_s', alu_s', t', z')
-
- -- Write
- exec (addr, High, op) s =
- (s', ())
- where
- (reg_s, alu_s, t, z) = s
- (reg_s', _) = register_bank (addr, High, z) reg_s
- s' = (reg_s', alu_s, t, z)
projects / matthijs / master-project / report.git / blobdiff