Fix some more header stuff.
[matthijs/master-project/report.git] / 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.