X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Freport.git;a=blobdiff_plain;f=progress-2009.02.04.txt;fp=progress-2009.02.04.txt;h=0b475d12660f3c4a6bc955689748cd0fdd4bfb44;hp=0000000000000000000000000000000000000000;hb=84d984a32326eefa22249bd377e452aed14671df;hpb=612e72177321ead79248a8dcf49b783f8153d967 diff --git a/progress-2009.02.04.txt b/progress-2009.02.04.txt new file mode 100644 index 0000000..0b475d1 --- /dev/null +++ b/progress-2009.02.04.txt @@ -0,0 +1,211 @@ +What is a function? +=================== +In general, a function is something providing a mapping from a number of input +arguments to a number of results. Each of these arguments and results can be +normal values, but also again functions. + +Function application is evaluating the mapping for a given set of input +operands. + +Looking at this from a hardware modeling perspective, we get different +results. Then, a function is essentially a template for a circuit, with each +of the arguments and results representing input and output ports. Optionally, +some of the arguments and results (always matched pairs) can become part of +the state, meaning that they generate a register that connects to the argument +and result concerned. + +Function application, then, is embedding the function's circuit template into +the callers circuit template, connecting any arguments and results to the +circuit's ports. This embedding will completely decouple the applied function +from the original function: The circuit may look alike, but different +applications have no connection or shared components in the final hardware. + +This is an important property, since it allows the caller complete freedom in +inlining, simplifying and changing any functions it applies. Or more +specifically, a caller can clone a function and modify the clone freely +(since it is the only caller of it). Since every application is unrelated to +all others, cloning a function has no extra cost whatsoever (unlike function +duplication in software, where the code size greatly increases). + +The above view works only for functions accepting and returning primitive +values, *i.e.*, that can be represented as (possibly multiple) VHDL signals +directly. In particular, functions cannot be used as arguments or returned +from functions. + +High order functions and partial evaluation +=========================================== +Before wondering how we implement high order functions and partial evaluation, +let's see where we would like to use them. + +Modifying function signature +---------------------------- +A simple application of high order functions is modifying a function's +signature. An example of this is the (un)curry function. In hardware, a +stateless function could be used to make a stateless function conform to the +standard signature and make it synthesisable / simulatable: + + stateless :: (a -> b) -> (a -> () -> ((), b)) + stateless f i s = (s, f i) + +This would be used to make some function foo statefull as follows: + + stateful_foo = stateless foo + +Another example would be to swap the order of inputs: + + swap_in :: ((a, b) -> o) -> ((b, a) -> o) + swap_in f (b, a) = f (a, b) + +Both of these examples take a function as argument, but return plain values +(though swap_in could return a high order function when the function passed in +has multiple arguments). + +Reusing common code +------------------- +When modeling an ALU, we could imagine generalizing the ALU operations and +making the control code independent of the actual operation. + +The following alu models a circuit with three input: A one bit opcode and two +inputs. The opcode selects between two operations, bitwis and and bitwise or. + + and_or_alu :: (Bit, Bit, Bit) -> BIt + and_or_alu (o, a, b) = + if o == Low + then hwand a b + else hwor a b + +Now, we might want to generalize this to be independent of the actual +operations peformed: + + type operation = Bit -> Bit -> Bit + alu :: operation -> operation -> (Bit, Bit, Bit) -> Bit + + alu op1 op2 (o, a, b) = + if o == Low + then op1 a b + else op2 a b + +Now, we can write the above specific alu as: + + and_or_alu = alu and or + +Parameterized circuits +---------------------- +This is probably a variant on the above, but using literal parameters instead +of functions as parameters. + +Finding a good example of this seems hard, since a lot of parameterized +circuits are implicitly parameterized using the length of lists in their +input, output or state. + +A possible example could be a program counter, that is a incrementing +register. The amount by which to increment the register depends on the +instruction word size, which you might want to make generic. + + pc :: Int -> Word32 -> (Word32, Word32) + pc n s = + (s', o) + where + s' = s + n + o = s + +Since this example is only useful when using some kind of integers instead of +just Bits, this assumes Word32 can actually be used. + +Partial application +------------------- +Say we have some encryption circuit, that encrypts a stream by xor'ing it with +some key stream. + + crypt :: (s -> (s, Bit)) -> Bit -> s -> (s, Bit) + crypt f i s = + (s', o) + where + (s', key) = f s + o = hwxor i key + +Now, we have some function taking in some source of entropy (modeled as a +signal of type Foo) and uses that to generate a (pseudo) random keystream. The +implementation of this function is not so important. Also, the type KeyState +represents the state of mkKey, but what it is exactly doesn't really matter. + + mkKey :: Foo -> KeyState -> (KeyState, Bit) + +Now, I can create a full crypt system as follows. This function has a Foo and +Bit input signals and a Bit output signal. + + crypt_full :: Foo -> Bit -> KeyState -> (KeyState, Bit) + crypt_full foo i s + crypt keygen i s + where + keygen = mkKey foo + +Now, this example isn't particularly good, since it would be just as easy to +simply make crypt take a Bit as input instead of a function generating bits +(This is probably also how you would synthesize something like this). Perhaps +more useful examples could be found, where passing a function makes notation +a lot easier than passing the function's (remaining) inputs and outputs +around. + +Preconnecting ports +------------------- +Sometimes it is useful to connect some ports of multiple similar pieces +of hardware to the same signal. For example, the following builds a +multibit multiplexer by mapping a bunch of single bit ones together. +Since all multiplexers use the same select input, we pass it to mplex_1 +and then pass the result to map. This makes the code clearer than +replicating the select input (length abs) times and using zipWith +instead of map. + + mplex_1 :: Bit -> (Bit, Bit) -> Bit + mplex_1 enable select (a, b) = + if select == Low then a else b + + mplex :: Bit -> [(Bit, Bit)] -> [Bit] + mplex select abs = + map (mplex_1 select) abs + +State ambiguity +=============== +Previously, we've concluded that choosing to translate an argument or result +to either a state variable or port would be possible by requiring a specific +type signature on the top level function and hierarchically looking which +variables are thus also state variables. + +In practice, this appears harder than we thought. We can observe that a state +variable should resolve to a register, but where exactly is undefined. In +particular, we could simply translate all arguments and results to ports, and +on the highest level instantiate registers for all state variables. +Functionally, this is completely correct, but this is probably not what we +want in most cases. Each function that has state will probably want to have +that state represented inside it's architecture, rather than to have two ports +which should be connected to a register externally. + +This means we need to "push" the registers down the hierarchy to get them +where they "belong". Somewhere down the line, however, a state variable will +eventually be used in some way, often by passing it to another function +(*i.e.*, connecting the output of the register to some other circuit). The +place where this happens is also the place where you want the register to end +up. + +In a lot of cases, this place is also as far as you can push the register down +(when you pass the current register value to some function a, but bind the new +register value to the result of some function b, you can't push further down +since both a and b use the register). The tricky part is now when you pass a +state value to some function a and that same function a produces the new value +of the state value. Is the state value now really a state of the function a, +or did the programmer just mean to connect a register to function a +externally? + +Note that this assumes some clever implementation for finding out if the state +can be pushed down, which takes things into account like "is the current state +only used once", "is the new state directly produced by the application that +also uses the state", "which state value in the arguments belongs to which +value in the function result". Actually implementing this will probably need +some extra thought, initially having all the state at the top level is +probably fine. + +It's probable that this case will not occur that often, and some extra +heuristics might help to guess the right thing more often. Adding some "force +state here" primitive will probably possible as well for final disambiguation. +Still, it would nicer to really solve this problem somehow.