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.