State as an Emergent Phenomenon

Alan Bawden

Laboratory for Computer Science Massachusetts Institute of Technology Cambridge, Massachusetts 02139

March 12, 1993

Abstract

Systems whose components perceive state in other components are precisely those systems which depend on global topological properties of their configuration in order to function correctly.

1 Introduction

It is an interesting fact that one can build systems that support state out of almost nothing but functional components (such as streams plus nondeterministic merge, as in [Hen80]). Something about the manner in which those components are assembled causes the phenomenon of state to emerge. This suggests that state is a derived notion. Perhaps what we commonly call “state” is just the surface manifestation of some deeper phenomenon— some property of the construction of the system as a whole. In this paper I will suggest such an explanation for state.

Our primary tool in this investigation is to use a linear graph reduction system to model typical programming language run-time data structures. When modeled using this tool all systems in which state share two common characteristics: First, they are all nondeterministic. That is, they all require sets of graph reduction rules in which the outcome of a computation can depend on the order in which rules are applied. And second, they all require linear graph structure that contains cycles.

These observations motivate us to examine the mathematical properties of linear graph structure and reduction. I will present some theorems about the behavior of linear graph reduction when applied to graphs that have the same local structure but different global structure.

It will then become apparent that linear graph reduction systems that are sensitive to the global structure of the system (in a certain well-defined way) must be nondeterministic and must exhibit cycles—precisely the symptoms observed empirically in systems that experience state. This implies that what is really going on when the components of a system experience state is that the system as a whole has this kind of global sensitivity. What we normally think of as state is merely the expression of a global property of a system in the perceptions of the observers embedded in that system.

2 Linear graph reduction

This section provides a whirlwind tour of of the linear graph reduction formalism. (See [Baw86, Baw93]—a similar system is described in [Laf90].) First I will describe the static structure of a linear graph. Then I will describe how a collection of reduction rules, a

Figure 1: A Method

linear graph grammar, can be applied to a linear graph to cause it to evolve. Unfortunately space does not permit me to do more than hint at all of the techniques necessary for modeling real systems using linear graph reduction. I hope the reader will catch enough of the flavor of how such modeling is done that the connection between the theorems that follow, and real systems, will be apparent.

A linear graph is a collection of typed vertices. Each vertex has a number of labeled terminals. Each vertex type has an associated set of terminal labels—any vertex of that type always has that many terminals with those labels. Each terminal must be connected to exactly one other terminal. (In particular, there can be no unconnected terminals.)

Figure 2 shows a linear graph over the two types Copy and Cons, where type Cons has the three associated labels “car”, “cdr”, and “” (the empty string), and the type Copy has the three associated labels “target”, “a”, and “b”.

A linear graph grammar is a collection of reduction rules called methods. Each method describes how to replace one subgraph with a different subgraph. Figure 1 shows an example of a method. Both the left hand and right hand sides of a method are subgraphs with a certain number of loose ends. A method must specify how the terminals that used to be connected to terminals in the old subgraph should be reconnected to terminals in the new subgraph. In figure 1, the loose ends in each subgraph are labeled to indicate how this reconnection is to be done.

A subgraph that matches the left hand side of some method is called a redex. A methods whose left hand side consists of exactly two vertices joined by a single connection is called a binary method. (Figure 1 is a binary method.) We will never need any other kind of method.

Linear graph reduction can be used to model real computational systems by using linear graphs to represent data structures, and using methods to encode algorithms. All of the properties of the program must be encoded somehow in a collection of types and methods.

Representing data structures is generally quite straightforward. The basic idea is that objects traditionally represented using N-component record structures are instead represented using vertices of valence N + 1. The extra terminal, called a handle, is used as a place for other vertices to connect to. So, for example, where a pointer would be installed in the jth component of record structure A pointing to record structure B, a connection is made from the jth terminal of vertex A to the handle terminal of vertex B. The Cons vertex type that appears in figure 2 and figure 1 really is the way the traditional Lisp cons-cell would be represented using linear graph structure.

The simple story told in the previous paragraph has an obvious flaw: since the terminals in a linear graph must be connected to exactly one other terminal, the handle terminal of a object-representing vertex can only be connected to one referencing terminal. In real systems, where we use pointers, there can be multiple references to an object. We introduce a Copy vertex type to solve this problem. When a program requires a reference to an object to be duplicated, a trivalent Copy vertex is attached to the object’s handle

Figure 2: A Copy tree

Figure 3: Methods to ascend a Copy tree.

terminal by its “target” terminal. The other two terminals of the Copy vertex, labeled “a” and “b”, are then available to be used in place of the original handle terminal. As more and more copies of the original reference are made, more and more Copy vertices accumulate in a tree between the users and the object they wish to reference. Figure 2 shows an example of just such a tree.

In order to actually compute using linear graph reduction we need a whole toolkit of techniques for representing objects such as closures, stack frames, activation records, and more mundane things such as numbers. We also need techniques for representing the actions of procedure calling, procedure returning, and primitive operations such as arithmetic. A typical example of such a technique (and one that will be important to us later on) is the technique for the primitive operation of accessing a value from one field of a structure. Figure 3 and figure 4 depict the methods for reading the car of a Lisp cons-cell. The pair of methods in figure 3 allow a Car “message” vertex to ascend through a tree of Copy vertices. The method in figure 4 performs the actual read when the message arrives. Analogous methods are needed for all primitive operations (CDR, SET-CAR!, etc.).

3 The symptoms of state

Experience using linear graph reduction to model real systems suggests that all graph grammars that exhibit the phenomenon of state share two important characteristics: first, they are always nondeterministic grammars; second, they always construct graphs that contain cycles. In this section I shall present some intuitive arguments for why this should be so. In the next section I will show why these two characteristics constitute strong circumstantial evidence that state is a phenomenon caused by the nonlocal topological structure of linear graphs.

Figure 4: Method to read the car of a cons-cell.

Figure 5: A source of nondeterminism

Symptom: nondeterminism

Why should it be the case that nondeterministic linear graph grammars are needed in order to construct systems with state?

Methods of the kind just illustrated in figure 3 permit a messages to climb up through trees of Copy vertices. Such methods are a source of nondeterminism because in a graph such as the one in figure 5 there is a choice about which message to propagate through the Copy vertex first. The result might be either of the two graphs shown in figure 6 Depending on this choice, either the Car message (left graph), or the Set Car message (right graph) will arrive at the apex of the tree first—two completely different computational histories may then unfold. This nondeterminism is possible because Copy vertices are willing to interact with vertices connected to either their a or b terminals. Intuitively, a Copy tree is willing to “listen” to messages arriving from anywhere along its fringe.

So nondeterminism is built in to the usual linear graph reduction implementation of objects with state. Of course this does not constitute proof that any implementation of objects with state must contain nondeterminism. Still, it is hard to imagine how this nondeterminism can be eliminated. Consider what would happen if Copy vertices were only willing to interact through their a terminals (so that only the right hand method in figure 3 could be defined). In that case there would only be a single location on the fringe of a Copy tree that would be listening for the next message. This single attentive location would be determined at the time the tree was constructed. Every time a programmer made a copy of a reference (i.e., for each variable that occurred more than once in the body of a λ-expression) the programmer would have to declare which occurrence was the “a” occurrence.

Figure 6: Two possible outcomes

In effect, programmers would have to specify in advance the order in which reads and writes will take place. It would be impossible to support patterns of reads and writes that varied dynamically. It is clear that such a system would fall short of supporting what most programmers would consider state-like behavior.

Others have also observed that the need for nondeterminism seems to be a symptom of the desire for state. In [Hen80], for example, Henderson must add a nondeterministic stream merging operator before he can construct an otherwise functional description of an operating system that appears to maintain state.

Symptom: cycles

Why should it be the case that cyclic linear graphs are needed in order to construct systems with state?

Consider how an observer embedded in such a system can perceive state. There must be some experiment that the embedded observer can perform that will reveal that the part of the linear graph external to him behaves as if it had state.

Such an experiment, expressed in Scheme, might look like:

     (define (experiment x)
       (begin (set-car! x 1)
              (= (car x) 1)))

The general idea is to detect that the external system, accessed through the variable X, somehow remembers the action performed by SET-CAR!, and this can be detected by the procedure CAR. The programmer who wrote this procedure probably thought in terms of some object (probably a Cons), named by the variable X, whose state could be written and

read by SET-CAR! and CAR.

The important thing to notice about the procedure EXPERIMENT is that the variable X occurs in its body twice. The reason for this is that two references to the subsystem being tested are needed in order to complete the experiment. While one reference is passed to SET-CAR!, a second reference must be retained so that SET-CAR!’s effects can be observed. the first method that results from the translation of EXPERIMENT into a linear graph grammar appears in figure 7. The reader should not worry about the details of this method—a complete description of how this method is derived is beyond the scope of this

Figure 7: The method for calling EXPERIMENT

paper—Simply notice that two connections join the E. 401 vertex to the Set Car vertex. The first connection is through the cont terminal of the Set Car, because the E. 401 is a continuation waiting for confirmation that the call to SET-CAR! has completed. The second connection joins the tail of the Set Car to the x of the E. 401, because after that confirmation arrives, the continuation will need that second copy of the reference to the value of X to continue the experiment.

This cycle is not a spurious effect of the way the procedure was written, it it a consequence of the nature of the experiment. Any system that looks for correlations between past actions and future effects will have this structure at some point in its history.

The need for cycles in systems with state has been noticed before. Usually it is expressed as a need for some kind of equality predicate in order to have a sensible notion of side effect. In [SS78] Steele and Sussman conclude that “the meanings of ‘equality’ and ‘side effect’ simultaneously constrain each other”; in particular they note that it is impossible to discuss side effects without introducing some notion of sameness.

The programmer who wrote the EXPERIMENT procedure intended that the variable X should refer to the same object each time it occurred; he was unable to discuss side effects without using a notion of sameness. To support this notion we have to introduce cycles into the system. Cycles are thus inevitable when side effects are to be detected.

4 Locality

We need to capture the notion of locality because we can only study state as a phenomenon experienced by observers embedded in computational systems. Such observers only have access to their immediately local neighbors. To capture the notion of locality, we can define a homomorphism from one linear graph to another as a map that preserves the local structure of the graph. More precisely, a homomorphism is a map ψ: G → H from the terminals of the linear graph G to the terminals of the linear graph H such that:

• If a and b are terminals in G, and a is connected to b, then ψ(a) is connected to ψ(b).

• If a and b are terminals in G that belong to the same vertex, then ψ(a) and ψ(b) belong to the same vertex in H.

• The label of a terminal a in G is the same as the label of ψ(a) in H, and the type of a’s vertex is the same as the type of ψ(a)’s vertex.

ψ is an epimorphism if it is onto.

Figure 8 shows an example of a homomorphism. The arrows indicate how the vertices of the left hand graph are mapped to the vertices of the right hand graph.

We say that two graphs, H_{1} and H_{2} are locally indistinguishable, written H_{1} ∼ H_{2}, if there exists a graph G and two epimorphisms ψ_{1}: G → H_{1} and ψ_{2}: G → H_{2}. It can be

Figure 8: A Linear Graph Homomorphism

shown that local indistinguishability is an equivalence relation on linear graphs. As a special case of this definition note that if ψ: G → H is any epimorphism, then G ∼ H.

Now I will present three theorems (without proofs, but the proofs are not difficult) about the relationship between linear graph grammars, homomorphisms and local indistinguishability.

We write G ⇒ G′ if the linear graph G′ is the result of applying any number of methods to any number of disjoint redexes in G. We write G_{0} ⇒^{∗} G_{n} when there is a series G_{0} ⇒ G_{1} ⇒ ⋯ ⇒ G_{n}.

Theorem 1 Given ψ: G → H, and if H ⇒^{∗} H′, then there exists G′ and ψ′: G′ → H′ such that G ⇒^{∗} G′. If ψ is an epimorphism, then ψ′ can be found so that it is also an epimorphism.

The theorem 1 is true given any linear graph grammar. It is the strongest such result I have proven that does not constrain the grammar. For certain classes of grammars, and in particular for the class that contains most deterministic grammars, stronger theorems can be proven:

A linear graph grammar is preclusive if two redexes can never overlap. This means that if a redex appears in a linear graph G, and if G ⇒ G′, and if that redex was not one of the ones reduced in forming G′, then that redex still appears in G′. The appearance of a redex in a graph thus precludes the possibility that anything else will happen to those vertices before the corresponding method can be applied.

For example, any grammar that contains the two methods in figure 3 cannot be preclusive, because a graph similar to the graph shown in figure 5 can be constructed in which the Copy vertex belongs to two different redexes. The following theorem demonstrates that preclusive grammars are in fact deterministic.

Theorem 2 If a linear graph grammar is preclusive, then given linear graphs G, G_{1}, and G_{2} such that G ⇒^{∗} G_{1} and G ⇒^{∗} G_{2}, there exists G′ such that G_{1} ⇒^{∗} G′ and G_{2} ⇒^{∗} G′.

Theorem 2 shows most clearly what it is about preclusive grammars that makes them behave deterministically. It gives us a condition under which we have a Church-Rosser theorem for linear graphs. It shows that no matter what order we choose to apply the methods from a preclusive grammar, we always achieve the same result. If it is possible to apply methods until a linear graph is produced to which no further methods can be applied, then that graph is unique.

The final theorem relates local indistinguishability and preclusive grammars:

Theorem 3 If a linear graph grammar is preclusive, then given linear graphs G, H, G′, and H′ such that G ∼ H, G ⇒^{∗} G′ and H ⇒^{∗} H′, there exists linear graphs G′′ and H′′ such that G′ ⇒^{∗} G′′, H′ ⇒^{∗} H′′ and G′′ ∼ H′′. This can be summarized in the following diagram:

G ∼ H
⇓^{∗}  ⇓^{∗}
G′  H′
⇓^{∗}  ⇓^{∗}
G′′ ∼ H′′

Theorem 3 is very similar in form to theorem 2; their meanings would be identical if we replaced the “∼” in theorem 3 with “=”. Theorem 3 shows that given a preclusive grammar, not only does it not matter what order we choose to apply methods (theorem 2), it does not even matter which locally indistinguishable linear graphs we choose to apply them to. A preclusive grammar is completely insensitive to the nonlocal structure of the system.

5 Implications for programs

The theorems we have just seen have implications for what an embedded observer can learn about the system in which it is embedded.

Suppose we are given a pair of linear graphs G and H, where G ≠ H, and we are asked to produce a linear graph grammar that can somehow distinguish between the two. First, we need to be precise about what we mean by “distinguish”. We want to be able to run the grammar on G or H and then apply some test to determine if the system has learned how it was initialized. The test must be local, otherwise we could supply the empty grammar and specify that the test is simply graph equality. Thus we will include two distinguished vertex types, Was-G and Was-H, in our grammar, and specify that if a vertex of type Was-G ever appears in the graph, then it will be understood that the grammar has decided that the initial graph was G, and similarly Was-H will signal that the grammar has decided that the initial graph was H.

Now consider the case where there is an epimorphism ψ: G → H. Suppose that given some grammar we have H ⇒^{∗} H′ and that H′ contains a vertex of type Was-H, then by theorem 1 there is a graph G′ where G ⇒^{∗} G′ and an epimorphism ψ′: G′ → H′. Since ψ′ is an epimorphism, G′ must also contain a vertex of type Was-H. The grammar is thus capable of deciding that the initial graph was H, even though it was applied to G. The grammar will therefore be in error. Thus no grammar can ever correctly decide that it was initially applied to H (although it is possible that it might learn that it was applied to G).

Putting this observation in somewhat more computational terms: If, in the course of some computation, a system finds itself in configuration H, and there is an epimorphism ψ: G → H, then from that point onward there is nothing that the system can do that will allow it to discover that it had in fact been in configuration H and not in configuration G. It might discover that it had been in configuration G, and from this it could conclude that it had not been in configuration H, but it can never discover that it had been in configuration H. Everything that can happen to H is locally indistinguishable from something that can also happen to G.

Looking at this fact from yet another angle: If a system is halted in configuration H, and reconfigured to be in configuration G, where there is an epimorphism ψ: G → H, the system can perhaps “malfunction” by arriving at a configuration G′ (i.e. G ⇒^{∗} G′) where there are no configurations G′′ and H′′ such that G′ ⇒^{∗} G′′, H ⇒^{∗} H′′ and G′′ ∼ H′′.

There are two conditions under which such malfunctions are impossible:

• If the grammar is preclusive, then since G ∼ H theorem 3 guarantees us that if G ⇒^{∗} G′ we can find the requisite G′′ and H′′.

• If H contains no cycles, then any epimorphism ψ: G → H must be an isomorphism, so we can let G′′ = H′′ = G′.

Thus, replacing H with the locally indistinguishable G can cause a malfunction only if H contains cycles and the grammar is not preclusive. Surprisingly, these are almost exactly the two symptoms we previously identified as always being present in systems that exhibit state-like behavior. (I say “almost exactly” because I never precisely defined what was meant by “nondeterminism” in section 4. The content of theorem 2 was that preclusive grammars behave deterministically, but there are non-preclusive grammars that also behave deterministically, so the two concepts do not align exactly.)

We have now arrived at the crucial intersection of our intuitive observations about state-like behavior (section 3) with our theorems about locality (section 4). We have discovered that the two features that always accompany state-like behavior are just the features necessary to make the system dependent on its nonlocal structure. This leads me to propose that systems that exhibit state-like behavior are, in fact, precisely those systems which depend on their nonlocal structure in order to function correctly.

Accepting this proposed definition of what it means for a system to experience state, leaves us with the following picture of the world: Stateless systems have the property that they are insensitive to their nonlocal structure—they behave the same way in all locally indistinguishable configurations. State is experienced by the components in a system when some locally indistinguishable configurations of the system may evolve in additional unintended ways. Importantly, no test the system can perform internally can determine that it is properly configured.

This says a great deal about why programming in the presence of state is difficult. Programming with state means that there are conditions which the system depends upon, that it cannot check for itself. The system must trust that it is configured as it expects. It must trust that it evolved from known initial conditions through the application of known methods, rather than being created spontaneously in some locally indistinguishable configuration that could never have been reached naturally.

6 The parable of the robot

To make this more concrete, imagine a robot who is was interacting with his computer via a keyboard and display. Both the robot and the computer are programmed in a functional programming language. In the computer, the stream of display images is expressed as a function of the stream of keyboard events. In the robot, the stream of robot hand motions is expressed as a function of the stream of robot eye images.

Suppose we halt this system and replace it with a locally indistinguishable configuration. Specifically, replace it with two robots and two computers, where the first robot types on one computer’s keyboard, but watches the display of the other computer, while the second robot types on the other keyboard and watches the first display.

In order to remain locally indistinguishable from the original configuration, each robot and each computer must be placed in the same internal configuration as it was when the system was still singular. Each robot “believes” that he is alone, and that he is interacting with a single computer. Initially both robots continue typing away secure in this belief. They are unable to detect that they now operate in a doubled system because they both type exactly the same thing at the same time, and the computers respond identically with the appropriate output.

Suddenly a fly lands on one of the displays. The robot watching that display pauses briefly to shoo it away. The other robot then notices that his display doesn’t reflect his last few keystrokes, while the first robot notices that his display reflects keystrokes that he was only planning on making right before the fly disturbed his concentration. Upon further experimentation the robots eventually discover their true situation.

The original singular robot had no way of testing that he was part of the singular system, nevertheless he depended on this fact in order to act sensibly. He trusted that there really was a single computer that was responding to his keystrokes, and that what he saw on the display represented its reactions. He trusted that the file he typed in today, really would reappear when he called it up on the display tomorrow.

If you asked him to explain just how the rest of the system was able to behave in that way, he would explain that “the computer has state”. That is his explanation of how the situation appears to him as an embedded observer, but it isn’t a very good explanation from our point of view. It even has built into it the presupposition that there is only a single computer.

We can see that the property of the system that really matters, the property that the robot accepts and depends on to function in the system without error, is the untestable assertion that the system’s nonlocal structure is what the robot believes it to be, and not some locally indistinguishable equivalent.

References

[Baw86] Alan Bawden. Connection graphs. In Proc. Symposium on Lisp and Functional Programming, pages 258–265. ACM, August 1986.

[Baw93] Alan Bawden. Linear graph reduction: Confronting the cost of naming. TR 1360, MIT AI Lab, March 1993.

[Hen80] Peter Henderson. Is it reasonable to implement a complete programming system in a purely functional style? Technical report, The University of Newcastle upon Tyne Computing Laboratory, December 1980.

[Laf90] Yves Lafont. Interaction nets. In Proc. Symposium on Principles of Programming Languages, pages 95–108. ACM, January 1990.

[SS78] Gerald Jay Sussman and Guy L. Steele Jr. The art of the interpreter or, the modularity complex. Memo 453, MIT AI Lab, May 1978.