Propagator networks very briefly
Published by Arun Isaac on
In other languages: தமிழ்
Tags: software, propagator networks
Propagator networks are a novel way to express computation that allow us to escape the expression-orientedness of traditional programming languages. Propagator networks are a network consisting of two kinds of components—cells and propagators. Cells are like variables, and contain values. Propagators are pure stateless functions taking one or more values as inputs and outputting a value 1. Cells are only connected to propagators, and never to other cells. Likewise, propagators are only connected to cells, and never to other propagators. All connections are directed—either from cells to the inputs of propagators, or from the outputs of propagators to cells. Many propagators may output to the same cell. Whenever the value of a cell connected to the inputs of a propagator change, that propagator is activated, its function is computed and the returned value is accumulated (more on accumulation later, but for now, you may think of the value as just being written to the cell) in the cell connected to the output of the propagator.
For example, here is a simple propagator network that adds two numbers—/a/ and b/—and writes the /sum to a cell. Also shown is a propagator network in action.
Figure 1: A simple propagator network that adds two numbers to produce the sum
Figure 2: A propagator network is shown in action. When a value is written into the top-most cell, the connected propagator is activated and writes its output to its output cell. Then, two subsequent propagators are activated and write their outputs to their respective output cell.
Figure 3: Many propagators outputting to the same cell is allowed.
Constraint propagator
Now, propagators can also express an undirected constraint between cells. For example, the propagator network shown below expresses the constraint or equation a + b = sum. This means that this propagator network is not only capable of calculating sum from a and b, but also a from b and sum, and b from a and sum. However, this is not special behaviour. Under the hood, it is simply implemented using three separate regular directed propagators that express each one of the three computations.
Figure 4: A constraint propagator is really several directed propagator paths wired in parallel.
Figure 5: The internals of a constraint propagator are shown. In each one of the frames, one of the directed propagator paths are highlit.
Accumulation of values in cells
Now, let's rewind back to what I said earlier in the introduction about cells accumulating values, and not merely being passive containers into which values are written. This is a very important feature of a propagator network. A propagator network never ever deletes information. Information in a propagator network is strictly increasing. Let me demonstrate this accumulation of values with an example. In the propagator network shown below, there are two propagators connected to the same cell. Each propagator is outputting a partial vector—a vector with some values missing. The cell merges these partial vectors into a more complete vector. Since cells strictly accumulate information, the timing of these writes does not matter. The specific accumulation logic used by each cell depends on the application and the kind of value stored in that cell. You can imagine other kinds of accumulation logic for merging dictionaries, intervals of real numbers, etc. Merging contradicting values is not allowed.
Figure 6: Each one of the propagators are outputting a vector with some values missing. These vectors are combined together in the cell to produce a more complete vector with values from both the vectors.
Substrate independence
You may have noticed that I have been very abstract in all my descriptions in this article. I have not mentioned any implementation details. Nor have I provided any pseudocode. This is deliberate. Propagator networks can be implemented on a wide variety of computational substrates. The entire network can be on a single machine. Or, the propagators and cells can be on different machines and communicating over a computer network. Cell state can be shared through memory, the filesystem or over the network. The possibilities are endlessly varied, with each design choice having different implications for performance, practical utility, etc. But, focussing on these aspects is a mistake. It detracts attention from the expressive power of propagator network, which is really what this is all about. In this regard, it is more akin to a constraint solving logic programming system.
Footnotes:
or more than one value, but let's not worry about that
All content is licensed under a