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)