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=0000000000000000000000000000000000000000;hp=0b475d12660f3c4a6bc955689748cd0fdd4bfb44;hb=0dfecb0be783911fd804436c22bbbf8c79711cc3;hpb=a552dc2d5a6d27f397543585caa90352fee37db0 diff --git a/progress-2009.02.04.txt b/progress-2009.02.04.txt deleted file mode 100644 index 0b475d1..0000000 --- a/progress-2009.02.04.txt +++ /dev/null @@ -1,211 +0,0 @@ -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.