Informal discussion:
The physical world is highly parallel, with many things happening side by side. A realistic model of computation is dataflow, which can be conceptualized as a kind of motion. Much like how particles move around in physical systems, bits of information move around in computers. This motivates our development of a theory of information flows.
But what exactly are these bits of information? Consider even and odd; then both are bit-valued functions that produce ones and zeros. But even and odd produce the same bits of information. They represent the information in two different ways. If $n$ is even then we know it is not odd, and if its not even then we know it is odd. The same applies the other way around.
To represent the same bit of information as evenness or oddness, we can use a partition. Both the even and odd functions are representations of the abstract notion of parity, which can be defined as a partition with two elements. An abstract bit of information is then a partition of a set into two different classes. It does not matter rather you get the parity from even, odd, 2 * mod(n,2), or any other representation. An abstract bit of information may be realized in many different forms.
A piece of information, in general, is just a collection of bits of information. We can call these partitions, but the important point is that they refer to a place within the information of a larger structure. A piece of information is larger than another one if it has more bits than it. Partitions abstract functions so that every function can now be treated as a representation of a piece of information.
We now know how to think abstractly about places within an information system, but we still need to understand how information moves around. Let $f: A \to B$ be a function; then we can describe a flow relation on $f$ by a pair (P,Q) which proclaims that the function moves the information in the place $P$ to the place $Q$. We now have a fundamental notion of information flows.
As an example, return back to our notion of parity. If we take a function like $x+1$ then we see that $x+1$ maps the parity information in its input to the parity information in its output. So (parity, parity) is a datflow relation on $x+1$. If we take an even number and add one to it, then we get an odd number and if we take an odd number and add one to it we get an even number. So $x+1$ flips parity bits around.
On the other hand, $x^2$ leaves the parity bit as it is: the square of an even number is even, and the square of an odd number is odd. Two other examples are $2x$, which always produces a number of even parity, and $2x+1$, which always produces one that is odd. Other functions like $\Omega$ might not map parities back to parities at all. These functions might take different numbers of the same parity and map them to numbers of different parities.
It would be nice if we could take a place in an input structure, like the parity of a number, and then find out exactly what place in the output it flows into. By doing this, we will depart from the traditional view of set theory which is that functions values in sets and instead make them take values in partitions.
In fact, we can do this if we take the notion of a partition image $f(P)$. This produces the set of information we know from $f$ when it is given the information in $P$. So the partition image directly codifies how a function moves information from places to places, and it lets you compute how a function moves bits from one location back to another. The dual concept is the partition inverse image $f^{-1}(Q)$, which is the collection of all bits of information that map into $Q$.
Partition images are the basis of our new way of programming with dataflow relations. A whole new parallel universe of functions that take operate on partitions is created alongside those that take values in sets. This is a new paradigm of computing in information systems which we call functional dataflow.
We provide a system of support for smart functions: special data types of functions that know things about their own data flow characteristics. These are combined with special partition data types, so that smart functions can have computable partition images. They can take a place in a system and return the place it maps to. This makes information flows accessible to the user.
As a basic example, consider a transposition permutation on pairs. Then this function swaps the order in an ordered pair $f(x,y) = (y,x)$. We might make this into a smart function that records its own flow information so that it records that the information in the first index is moved to the second index, and the information in the second is moved to the first. This flow information might be made computable using partition images, so that if you $f$ what it maps the first index to it will return the second index.
If bits of information are the simplest units of storage, then this suggests that bit-flow relations $(P,Q)$ between bits of information $P$ and $Q$ are the simplest forms of dataflow. We already saw an example of a bit flow relation with the (parity, parity) relations in arithmetic functions. These bit-flow relations are the atomic building blocks for all other dataflow relations.
Information flows can now be seen to form an ordering by scale. There can be large events with millions of bits moving around to ones with only one or two. By the same token, an event in a physical system might have anything from the motion of an astronomical body on the higher end to the motions of subatomic particles on the smallest scales. In both cases, we have an intuitive notion of scale. We now have a way of capturing information flows from the smallest scales to the largest.
For technical experts:
For aficionados of functors, categories, adjunctions, toposes, lattices, lenses, theorems and proofs: the topos structure theory of computing
No comments:
Post a Comment