+++ /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