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.