Computation networks like this are not a new idea. The first spreadsheet programs developed in the late 60s and early 70s are computation networks. (Spreadsheets have a lot of structure that is an artifact of the original paper model. For example, the physical layout of rows and columns of cells is very strongly built in to the computation model.) Despite their age, propagation networks are still a model that is worth exploring. Gerry and Alexey described some interesting ideas.
First, Gerry and Alexey have narrowed their exploration to unidirectional propagation. Each computation node only knows how to compute the output from the input. This is different from a constraint network where a computation node may be able to ‘run backwards’ and deduce an input value given the output. Constraints are trivially added by simply making a new propagator that runs from the output back to the input. That is, the computation nodes are unidirectional, but the network topology can have circular connections and can therefore mimic bi-directional propagation.
The ability to create arbitrary connections is the reason we want to use a propagator network, but you are immediately faced with the key problem of such a network: what do you do if you compute a value, but the receiving cell already has a value? There are a few potential solutions to this problem:
- Make it impossible. Require that the computation network is strictly tree-like. This is boring.
- Make it illegal. Raise an error if the network ever attempts
to modify a value cell that already has a value.
- Make it illegal unless it is benign. Raise an error if the network ever attempts to *change* a value in a cell. Attempts to re-write the existing value are ignored. This raises the question of what might be considered equivalent. At one end of the spectrum, the new value might be required to EQ to the existing one to be considered benign. At the other end, maybe they both match the same pattern.
- Ignore it. Discard the new value.
- Allow it. Discard the old value. Continue propagating the new value to any computation nodes connected to the cell.
- Do something else (call a function) involving both the old and new value.
This leads to this interesting idea: Rather than put values in the cells, we'll accumulate information about the values and put that in the cells. What sort of information? As the computation propagates through the network, we can tag each value and note where it came from and what computations were done to compute it. A value will come with a provenance that we can examine. Now suppose we find that we are about to assign a value to a cell that already has a value. We can look at the two provenances and see if there is reason to believe one more than the other. Or if the values agree, we can combine the provenances to show that the value is supported by multiple methods of computation.
Or perhaps you are a Bayesian and want each cell to represent a belief (probability distribution) about a value. Then the value we assign to the cell would be a distribution that has been updated by a new piece of evidence. Again, we could use the provenance idea to determine what evidence was important in determining a value.
Gerry and Alexey have a paper coming out soon called The Art of the Propagator. It goes much further than I did here and is much clearer, so I suggest reading it as soon as it appears.
Ok, keep that idea in the back of your mind while we revisit the problem of