Day 4, Part 2

The next part of the talk was given by Alexey Radul, a graduate student of Gerry's. Alexey described propagator networks. The idea is quite simple: you create a network that is built out of two kinds of parts. One kind of part is a stateless computational node. Computation nodes can have arbitrary inputs and outputs, but the outputs are a pure function of the inputs. (This doesn't mean that the guts of the node can't have state, just that any such state cannot be observed from examination of the outputs.) The second kind of part is a stateful value cell. Cells do no computation at all, but they save the results of the computational nodes. You compute things by creating a network that is specialized to the problem you are trying to solve.

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:

1. Make it impossible. Require that the computation network is strictly tree-like. This is boring.
2. 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.
3. Ignore it. Discard the new value.
4. Allow it. Discard the old value. Continue propagating the new value to any computation nodes connected to the cell.
5. Do something else (call a function) involving both the old and new value.

Option 5 subsumes options 2, 2a, 3 and 4, if you choose function apropriately, but it offers a couple of more interesting alternatives. First, perhaps the values you are computing have potential errors. You may have obtained them from some physical process. Instead of using a best-estimate for each computation, you may decide to use interval arithmetic. If a cell is recomputed and the new interval overlaps the old, then you can perhaps compute a tighter interval.

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 amb and backtracking.