Running a Program

An AND program runs over a series of time-steps. At each time-step, we do the following:

Read the values from source registers (lower-case).
Evaluate each expression using these values.
Write each result (either 0 or 1) to the target register (upper-case).
Move to the next time-step.

The target registers update only after all expressions have been evaluated. This ensures that every expression sees the same values before any register changes.

Input, Memory, and Output

Figure 1 shows the program from the previous section, running for 6 time-steps.

t	Input	Mem.	Output	Expressions
Running a Program

0	AB	CD	E	(bd)+(cd) ↦ C a+d ↦ D c ↦ E
1	AB	CD	E	(bd)+(cd) ↦ C a+d ↦ D c ↦ E
2	AB	CD	E	(bd)+(cd) ↦ C a+d ↦ D c ↦ E
3	AB	CD	E	(bd)+(cd) ↦ C a+d ↦ D c ↦ E
4	AB	CD	E	(bd)+(cd) ↦ C a+d ↦ D c ↦ E
5	AB	CD	E	(bd)+(cd) ↦ C a+d ↦ D c ↦ E

Figure 1: Running an AND program. Registers and expressions that are active are highlighted. An expression that is active generates sets the register in the next time-step.

The three columns on the left show the program state. This program uses registers A to E, grouped into three types:

Input registers can be read by expressions, but not written to.
Memory registers can be both read from and written to.
Output registers can be written to, but not read from.

In this run, we provide input by setting register A at time-step 0 and register B at time-step 2.

The “program activation” column on the right shows the compact DNF expressions that make up the program. When an expression evaluates to 1, its target register gets set in the next time-step. For example, at time-step 0, A is present as input. This activates the second expression (a+d ↦ D), setting register D at time-step 1.

What happens with different input? Above, we set A at time-step 0 and B at time-step 2. If we reverse this order—presenting B first, then A—the program generates a different output. Figure 2 shows the two runs side-by-side.

t	A then B			B then A
Same Program, Different Input

t	Input	Mem.	Output	Input	Mem.	Output
0	AB	CD	E	AB	CD	E
1	AB	CD	E	AB	CD	E
2	AB	CD	E	AB	CD	E
3	AB	CD	E	AB	CD	E
4	AB	CD	E	AB	CD	E
5	AB	CD	E	AB	CD	E

Figure 2: Comparing two runs of of the same program with different input. The program settles into a different stable state depending on the order of the inputs.

The program’s behaviour depends on the order of the inputs (see Figure 2). When A arrives before B, the output register E stays on. Reverse the order, and E stays off.

AND is a reactive programming language

An AND program reads input and produces output at every time-step. This may seem like a trivial point, but its importance is often overlooked. Most people think of a program as something that receives input, works through a predefined set of steps, and finishes by delivering output.

Harel and Pnueli (1985) draw a useful distinction here, contrasting reactive programs with transformative ones.

Our proposed distinction is between what we call tranformational and reactive systems. A transformational system accepts inputs, performs transformations on them and produces outputs […] Reactive systems, on the other hand, are repeatedly prompted by the outside world and their role is to continuously respond to external inputs. (Harel and Pnueli 1985, p479)

Traditional thinking about programs assumes they are transformational. The behaviour of a transformational program reduces to a function from inputs to outputs, and the central theoretical questions concern computability and termination (famously, the Halting Problem).

Reactive programs differ fundamentally. They do not compute a final result; they respond continuously to an environment over time, often running indefinitely. Their behaviour is not a function but a set of possible event histories: ongoing sequences of inputs, outputs, and internal state transitions. The central question shifts from what does the program compute? to what patterns of behaviour can it produce and sustain?

Many criticisms of genetic programs rest on the assumption that programs are transformative (Calcott 2020). AND sidesteps these criticisms: it is a reactive language from the ground up.

In Calcott (2020) I refer to transformative programs as “batch programs” and reactive programs “interactive programs”.

References

Calcott, Brett. 2020. “A Roomful of Robovacs: How to Think About Genetic Programs.” In Philosophical Perspectives on the Engineering Approach in Biology: Living Machines?, edited by Sune Holm and Maria Serban. Routledge. https://doi.org/10.4324/9781351212243.

Harel, D., and A. Pnueli. 1985. “On the Development of Reactive Systems.” In Logics and Models of Concurrent Systems, edited by Krzysztof R. Apt. Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-82453-1_17.