12.1 Introduction

A dynamic system is one that changes state over time. In some cases these changes are prompted by external inputs. In some cases, the changes occur in response to purely internal events (such as the ticks of a clock). In some cases, the behavior results from a combination of such stimuli.

In this chapter, we look at the use of operation definitions in specifying the behavior of such systems. In the next section, we look at an example of a reactive system, i.e. one that responds to external inputs. We then look at an example of a closed dynamic system, i.e. one that operates without external input. After that, we look at an example of mixed initiative system, i.e. one that is driven by a combination of internal and external stimuli. Finally, we look at the issues involved in handling simultaneous inputs.

12.2 Reactive Systems

The simplest form of reactive system is one whose behavior is driven entirely by external inputs. Prior to an input, the system is quiescent, i.e. nothing is changing; on observing an input, the system changes state in accordance with the input; and, afterward, the system becomes quiescent once again (until the next input is observed).

As an example, consider a system with three buttons and three lights. At each point in time, some of the lights are on and some are off. If the user pushes the first button, the system toggles the first light. If the user pushes the second button, the system interchanges the states of the first light and the second light. If the user pushes the third button, the system interchanges the states of the second and third lights.

In order to formalize the behavior of this system, we give names to the components of state. We use the Boolean predicate p to mean that the first light is on; q means that the second light is on; and r means that the third light is on. Next, we give names to the three possible events. We use the Boolean predicate a to designate the first button being pushed; b refers to the second button being pushed; and c refers to the third button being pushed.

Given this vocabulary, we represent the state of our system as a dataset consisting of some subset of p, q, and r factoids, and we represent the occurrence of an event as one of our three actions, i.e. a, b, or c.

With this new terminology, we can describe the desired behavior of our system with the operation definitions shown below. If the user pushes the a button and p is true, the system makes p false. If the user pushes a and p is false, the system makes p true. If the user pushes b, the system interchanges p and q. And, if the user pushes c, the system interchanges q and r. (Note that, if action b is performed and p and q are the same, nothing changes. Similarly, if action c is performed and q and r are the same, nothing changes. Consequently, we do not need rules for those cases.)

Note that, if the system starts in a state in which all three conditions are false, it can achieve a state in which they are true by executing the action sequence a, b, c, a, b, and a. Can you think of a different sequence of actions that would do the trick? How many sequences are there that produce the desired state?

12.3 Closed Systems

A closed dynamic system is one that operates without external input. Its behavior results from internal stimuli only, such as the ticks of a clock.

As an example, imagine a variation of the Buttons and Lights World described in the preceding section. In this case, there are no buttons and so no external input. Instead, the system cycles through states, starting in a state where all of the lights are off, cycling through states in a particular order until all lights are on, resetting, and then repeating ad infinitum.

In specifying the behavior of this system, we use the same vocabulary as in the preceding section except that in place of the the actions a, b, and c, we have a single internal action tick representing the tick of the clock.

With this terminology, we can describe the desired behavior of our system with the operation definition shown below. When the clock ticks, the system changes state in accordance with the state current at that time. When all of the lights are off, the first light is turned on. When the first light is on and only the first light is on, the first light is extinguished and the second light is turned on. And so forth.

Note that this sequence of states is the same as the sequence that would result by executing the sequence of actions mentioned at the end of the preceding section, viz. a, b, c, a, b, and a.

If we wanted, we could also formalize this behavior using the actions defined in the preceding sections (except that the actions would be internal actions, not external stimuli).

As before, we would have the definitions of the actions, but to these we would add a reset operation to turn off all of the lights. See below.

Given these definitions, we could rewrite the specification above as shown below. The rules have the same conditions; but, instead of enumerating changes to base relations, the rules in this case specify which internal action is performed in which state.

This style of specification is sometimes called a universal plan. For each state, it specifies an action to be performed in that state.

12.4 Mixed Initiative

A mixed initiative system is one whose behavior is determined by either external or internal inputs. Interestingly, in a mixed initiative system, a single external input can lead to a single state change or a sequence of changes.

As an example, consider a variation of the closed Buttons and Lights World described in the preceding section. In this version, in place of the buttons described in Section 12.2, we have two different buttons. If the user pushes the first button, the system begins behaving as described in the preceding section. If the user presses the second button, the system pauses its operation. If the user presses the first button again, the system picks up where it left off.

As before, we use p, q, and r to describe the state of the three lights. To these, we add a single 0-ary predicate running to capture the state of the process. We use the symbols play and stop, to refer to the two external inputs. Finally, as before, we use the symbol tick to refer to a tick of the internal clock.

The operation rules below specify the desired behavior of our system. The definitions of play and stop, ad there are the usual rules defining tick, the only difference being the dependence on running.

Given these rules, the system will exhibit the desired behavior. When the user presses the play button, the state is updated to include the factoid running. The upshot is that, as the system's internal clock ticks, it proceeds through its cycle of states. When the user presses stop button, running is removed, and the system will do nothing on subsequent clock ticks unless the play button is pushed once again.

12.5 Simultaneous Actions

In the preceding sections, we looked at the problem of handling one input at a time. In some applications, we must deal with the possibility of multiple simultaneous inputs. For example, a robot might be commanded to move and extend its arm at the same time, or a computer user might press two keys at the same time.

In some cases, the effects of such events are independent of each other. In such cases, it is possible to handle such events independently, in effect treating the events as though they happened independently.

The a operation and the c operation in the original version of the Buttons and Lights World illustrate this. The behaviors associated with these inputs are independent of each other. Pressing the a button toggles p and has nothing to do with q and r. Pressing the c button interchanges q and r and has nothing to do with p. The upshot is that these inputs can be processed independently and simultaneously in accordance with the rules defining their individual behaviors.

Unfortunately, treating simultaneous inputs independently does not always work. In some cases, simultaneous actions can interact in ways that lead to results that are different from the results of independent execution.

As an example, consider a state in which the first and second lights in the Buttons and Lights World are both on, and imagine that the user simultaneously presses both the first and second buttons, i.e. he performs actions a and b at the same time. In this situation, the definition of the a action mandates that p should become false, and the definition of the b action mandates that p should become true. So what happens?

The problem in this case is that our operation definitions, as written, assume that only one action occurs at a time. In order to deal with the possible interactions, we need to describe the effects of simultaneous inputs.

One way to do this is to invent terminology for talking about compound actions and then write operation definitions for such combinations.

If the number of possible actions is small, it is common practice to use chords to specify different combinations of inputs. For example, in the Buttons and Lights World, we could use a ternary constructor press and specify Booleans as arguments. If the first argument is true, this means that button a is pressed. If the second argument is true, this means that button b is pressed. If the third argument is true, this means that button c is pressed. By specifying different combinations of Boolean, we can characterize various combinations of actions.

If the number of possible actions is large, representing compound actions as chords is impractical. In such cases, it is common practice to represent compound actions as action lists. For example, in the Buttons and Lights World, we would invent represent the combination of actions a and c with the list [a,c], and we might specify the execution of this compound action by writing an expression like execute([a,c]).

Once we have a representation for compound actions, we can write operation definitions using this representation. For example, the rules shown below specify one possible behavior for a Buttons and Lights World system that allows up to two simultaneous actions. If the user presses both a and b at the same time, then a has its usual effect on p and b has its usual effect on q. If the user presses both a and c at the same time, then these actions have their usual effects (as defined in Section 12.2). If the user presses both b and c at the same time, then b has its usual effect on q and c has its usual effect on r.

Note that, if all actions in an application are independent of each other, specifying the behavior of compound actions is very simple. Suppose, for example, we had a system with a selection of individual actions execute(a), execute(b), and so forth; and suppose that these actions were all independent. Then we could define the behavior of a system in response to an arbitrary subset of these actions with the rule shown below (together with the rules defining the individual actions).

Formalizing the behavior of simultaneous inputs can be tedious. However, using operation definitions for compound actions, it is at least possible to formalize this behavior correctly in situations where independent treatment would be inadequate.

Exercises