--- /dev/null
+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.
projects / matthijs / master-project / report.git / blobdiff