progress-2009.02.04.txt

   1 What is a function?
   2 ===================
   3 In general, a function is something providing a mapping from a number of input
   4 arguments to a number of results. Each of these arguments and results can be
   5 normal values, but also again functions.
   6
   7 Function application is evaluating the mapping for a given set of input
   8 operands.
   9
  10 Looking at this from a hardware modeling perspective, we get different
  11 results. Then, a function is essentially a template for a circuit, with each
  12 of the arguments and results representing input and output ports. Optionally,
  13 some of the arguments and results (always matched pairs) can become part of
  14 the state, meaning that they generate a register that connects to the argument
  15 and result concerned.
  16
  17 Function application, then, is embedding the function's circuit template into
  18 the callers circuit template, connecting any arguments and results to the
  19 circuit's ports. This embedding will completely decouple the applied function
  20 from the original function: The circuit may look alike, but different
  21 applications have no connection or shared components in the final hardware.
  22
  23 This is an important property, since it allows the caller complete freedom in
  24 inlining, simplifying and changing any functions it applies. Or more
  25 specifically, a caller can clone a function and modify the clone freely
  26 (since it is the only caller of it). Since every application is unrelated to
  27 all others, cloning a function has no extra cost whatsoever (unlike function
  28 duplication in software, where the code size greatly increases).
  29
  30 The above view works only for functions accepting and returning primitive
  31 values, *i.e.*, that can be represented as (possibly multiple) VHDL signals
  32 directly. In particular, functions cannot be used as arguments or returned
  33 from functions.
  34
  35 High order functions and partial evaluation
  36 ===========================================
  37 Before wondering how we implement high order functions and partial evaluation,
  38 let's see where we would like to use them.
  39
  40 Modifying function signature
  41 ----------------------------
  42 A simple application of high order functions is modifying a function's
  43 signature. An example of this is the (un)curry function. In hardware, a
  44 stateless function could be used to make a stateless function conform to the
  45 standard signature and make it synthesisable / simulatable:
  46
  47     stateless :: (a -> b) -> (a -> () -> ((), b))
  48     stateless f i s = (s, f i)
  49
  50 This would be used to make some function foo statefull as follows:
  51
  52     stateful_foo = stateless foo
  53
  54 Another example would be to swap the order of inputs:
  55
  56     swap_in :: ((a, b) -> o) -> ((b, a) -> o)
  57     swap_in f (b, a) = f (a, b)
  58
  59 Both of these examples take a function as argument, but return plain values
  60 (though swap_in could return a high order function when the function passed in
  61 has multiple arguments).
  62
  63 Reusing common code
  64 -------------------
  65 When modeling an ALU, we could imagine generalizing the ALU operations and
  66 making the control code independent of the actual operation.
  67
  68 The following alu models a circuit with three input: A one bit opcode and two
  69 inputs. The opcode selects between two operations, bitwis and and bitwise or.
  70
  71     and_or_alu :: (Bit, Bit, Bit) -> BIt
  72     and_or_alu (o, a, b) =
  73       if o == Low
  74         then hwand a b
  75         else hwor a b
  76
  77 Now, we might want to generalize this to be independent of the actual
  78 operations peformed:
  79
  80     type operation = Bit -> Bit -> Bit
  81     alu :: operation -> operation -> (Bit, Bit, Bit) -> Bit
  82
  83     alu op1 op2 (o, a, b) =
  84       if o == Low
  85         then op1 a b
  86         else op2 a b
  87
  88 Now, we can write the above specific alu as:
  89
  90     and_or_alu = alu and or
  91
  92 Parameterized circuits
  93 ----------------------
  94 This is probably a variant on the above, but using literal parameters instead
  95 of functions as parameters.
  96
  97 Finding a good example of this seems hard, since a lot of parameterized
  98 circuits are implicitly parameterized using the length of lists in their
  99 input, output or state.
 100
 101 A possible example could be a program counter, that is a incrementing
 102 register. The amount by which to increment the register depends on the
 103 instruction word size, which you might want to make generic.
 104
 105     pc :: Int -> Word32 -> (Word32, Word32)
 106     pc n s =
 107       (s', o)
 108       where
 109         s' = s + n
 110         o  = s
 111
 112 Since this example is only useful when using some kind of integers instead of
 113 just Bits, this assumes Word32 can actually be used.
 114
 115 Partial application
 116 -------------------
 117 Say we have some encryption circuit, that encrypts a stream by xor'ing it with
 118 some key stream.
 119
 120     crypt :: (s -> (s, Bit)) -> Bit -> s -> (s, Bit)
 121     crypt f i s =
 122       (s', o)
 123       where
 124         (s', key) = f s
 125         o = hwxor i key
 126
 127 Now, we have some function taking in some source of entropy (modeled as a
 128 signal of type Foo) and uses that to generate a (pseudo) random keystream. The
 129 implementation of this function is not so important. Also, the type KeyState
 130 represents the state of mkKey, but what it is exactly doesn't really matter.
 131
 132     mkKey :: Foo -> KeyState -> (KeyState, Bit)
 133
 134 Now, I can create a full crypt system as follows. This function has a Foo and
 135 Bit input signals and a Bit output signal.
 136
 137     crypt_full :: Foo -> Bit -> KeyState -> (KeyState, Bit)
 138     crypt_full foo i s
 139       crypt keygen i s
 140       where
 141         keygen = mkKey foo
 142
 143 Now, this example isn't particularly good, since it would be just as easy to
 144 simply make crypt take a Bit as input instead of a function generating bits
 145 (This is probably also how you would synthesize something like this). Perhaps
 146 more useful examples could be found, where passing a function makes notation
 147 a lot easier than passing the function's (remaining) inputs and outputs
 148 around.
 149
 150 Preconnecting ports
 151 -------------------
 152 Sometimes it is useful to connect some ports of multiple similar pieces
 153 of hardware to the same signal. For example, the following builds a
 154 multibit multiplexer by mapping a bunch of single bit ones together.
 155 Since all multiplexers use the same select input, we pass it to mplex_1
 156 and then pass the result to map. This makes the code clearer than
 157 replicating the select input (length abs) times and using zipWith
 158 instead of map.
 159
 160                 mplex_1 :: Bit -> (Bit, Bit) -> Bit
 161                 mplex_1 enable select (a, b) =
 162                         if select == Low then a else b
 163
 164                 mplex :: Bit -> [(Bit, Bit)] -> [Bit]
 165                 mplex select abs =
 166                         map (mplex_1 select) abs
 167
 168 State ambiguity
 169 ===============
 170 Previously, we've concluded that choosing to translate an argument or result
 171 to either a state variable or port would be possible by requiring a specific
 172 type signature on the top level function and hierarchically looking which
 173 variables are thus also state variables.
 174
 175 In practice, this appears harder than we thought. We can observe that a state
 176 variable should resolve to a register, but where exactly is undefined. In
 177 particular, we could simply translate all arguments and results to ports, and
 178 on the highest level instantiate registers for all state variables.
 179 Functionally, this is completely correct, but this is probably not what we
 180 want in most cases. Each function that has state will probably want to have
 181 that state represented inside it's architecture, rather than to have two ports
 182 which should be connected to a register externally.
 183
 184 This means we need to "push" the registers down the hierarchy to get them
 185 where they "belong". Somewhere down the line, however, a state variable will
 186 eventually be used in some way, often by passing it to another function
 187 (*i.e.*, connecting the output of the register to some other circuit). The
 188 place where this happens is also the place where you want the register to end
 189 up.
 190
 191 In a lot of cases, this place is also as far as you can push the register down
 192 (when you pass the current register value to some function a, but bind the new
 193 register value to the result of some function b, you can't push further down
 194 since both a and b use the register). The tricky part is now when you pass a
 195 state value to some function a and that same function a produces the new value
 196 of the state value. Is the state value now really a state of the function a,
 197 or did the programmer just mean to connect a register to function a
 198 externally?
 199
 200 Note that this assumes some clever implementation for finding out if the state
 201 can be pushed down, which takes things into account like "is the current state
 202 only used once", "is the new state directly produced by the application that
 203 also uses the state", "which state value in the arguments belongs to which
 204 value in the function result". Actually implementing this will probably need
 205 some extra thought, initially having all the state at the top level is
 206 probably fine.
 207
 208 It's probable that this case will not occur that often, and some extra
 209 heuristics might help to guess the right thing more often. Adding some "force
 210 state here" primitive will probably possible as well for final disambiguation.
 211 Still, it would nicer to really solve this problem somehow.