Python state machine programming learning notes

Now I am reading MIT 6.01's course materials on state machine programming.

MIT OCW Scholar Introduction to Electrical Engineering and Computer Science I  6.01— Spring 2011— April 25, 2011 

Chapter 4  State Machines

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-01sc-introduction-to-electrical-engineering-and-computer-science-i-spring-2011/unit-1-software-engineering/state-machines/MIT6_01SCS11_chap04.pdf

State machines are a method of modeling systems whose output depends on the entire history of their inputs, and not just on the most recent input. Compared to purely functional systems, in which the output is purely determined by the input, state machines have a performance that is determined by its history. State machines can be used to model a wide variety of systems, including:

• user interfaces, with typed input, mouse clicks, etc.;

• conversations, in which, for example, the meaning of a word “it” depends on the history of
things that have been said;

• the state of a spacecraft, including which valves are open and closed, the levels of fuel and 
oxygen, etc.; and

• the sequential patterns in DNA and what they mean.

State machine models can either be continuous time or discrete time. In continuous time models, we typically assume continuous spaces for the range of values of inputs and outputs, and use differential equations to describe the system’s dynamics. This is an interesting and important ap­proach, but it is hard to use it to describe the desired behavior of our robots, for example. The loop of reading sensors, computing, and generating an output is inherently discrete and too slow to be well-modeled as a continuous-time process. 

Also, our control policies are often highly non­linear and discontinuous. So, in this class, we will concentrate on discrete-time models, meaning models whose inputs and outputs are determined at specific increments of time, and which are synchronized to those specific time samples.

Furthermore, in this chapter, we will make no as­sumptions about the form of the dependence of the output on the time-history of inputs; it can be an arbitrary function.

Generally speaking, we can think of the job of an embedded system as performing a transduction from a stream (infinite sequence) of input values to a stream of output values. In order to specify the behavior of a system whose output depends on the history of its inputs mathematically, you could think of trying to specify a mapping from i 1,...,i t (sequences of previous inputs) to ot (current output), but that could become very complicated to specify or execute as the history gets longer.

In the state-machine approach, we try to find some set of states of the system, which capture the essential properties of the history of the inputs and are used to determine the current output of the system as well as its next state.

It is an interesting and sometimes difficult modeling problem to find a good state-machine model with the right set of states; in this chapter we will explore how the ideas of PCAP can aid us in designing useful models. 

One thing that is particularly interesting and important about state machine models is how many ways we can use them. In this class, we will use them in three fairly different ways:

1.  Synthetically: State machines can specify a “program” for a robot or other system embedded
in the world, with inputs being sensor readings and outputs being control commands.

2.  Analytically: State machines can describe the behavior of the combination of a control system and the environment it is controlling; the input is generally a simple command to the entire system, and the output is some simple measure of the state of the system. The goal here is to analyze global properties of the coupled system, like whether it will converge to a steady state, or will oscillate, or will diverge.

3.  Predictively: State machines can describe the way the environment works, for example, where I will end up if I drive down some road from some intersection. In this case, the inputs are control commands and the outputs are states of the external world. Such a model can be used to plan trajectories through the space of the external world to reach desirable states, by considering different courses of action and using the model to predict their results.

We will develop a single formalism, and an encoding of that formalism in Python classes, that will serve all three of these purposes.

Our strategy for building very complex state machines will be, abstractly, the same strategy we use to build any kind of complex machine. We will define a set of primitive machines (in this case, an infinite class of primitive machines) and then a collection of combinators that allow us to put primitive machines together to make more complex machines, which can themselves be abstracted and combined to make more complex machines.

...

4.1.2 State machines in Python

Now, it is time to make computational implementations of state machine models. In this section we will build up some basic Python infrastructure to make it straightforward to define primitive machines; in later sections we will see how to combine primitive machines into more complex structures.

We will use Python’s object-oriented facilities to make this convenient. We have an abstract class, SM, which will be the superclass for all of the particular state machine classes we define. It does not make sense to make an instance of SM, because it does not actually specify the behavior of the machine; it just provides some utility methods. To specify a new type of state machine, you define a new class that has SM as a superclass.

In any subclass of SM, it is crucial to define an attribute startState, which specifies the initial state of the machine, and a method getNextValues which takes the state at time t and the input at time t as input, and returns the state at time t + 1 and the output at time t. This is a choice that we have made as designers of our state machine model; we will rely on these two pieces of information in our underlying infrastructure for simulating state machines, as we will see shortly.

Here, for example, is the Python code for an accumulator state machine, which implements the definition given in section 4.1.1.4.

class Accumulator(SM):
startState = 0

def getNextValues(self, state, inp):
return (state + inp, state + inp)

It is important to note that getNextValues does not change the state of the machine, in other words, it does not mutate a state variable. Its job is to be a pure function: to answer the question of what the next state and output would be if the current state were state and the current input were inp. We will use the getNextValues methods of state machines later in the class to make plans by considering alternative courses of action, so they must not have any side effects. As we noted, this is our choice as designers of the state machine infrastructure We could have chosen to implement things differently, however this choice will prove to be very useful. Thus, in all our state machines, the function getNextValues will capture the transition from input and state to output and state, without mutating any stored state values.

To run a state machine, we make an instance of the appropriate state-machine class, call its start method (a built in method we will see shortly) to set the state to the starting state, and then ask it to take steps; each step consists of generating an output value (which is printed) and updating the state to the next state, based on the input. The abstract superclass SM defines the start and step methods. These methods are in charge of actually initializing and then changing the state of the machine as it is being executed. They do this by calling the getNextValues method for the class to which this instance belongs. The start method takes no arguments (but, even so, we have to put parentheses after it, indicating that we want to call the method, not to do something 29 Throughout this code, we use inp, instead of input, which would be clearer. The reason is that the name input is used by Python as a function. Although it is legal to re-use it as the name of an argument to a procedure, doing so is a source of bugs that are hard to find (if, for instance, you misspell the name input in the argument list, your references to input later in the procedure will be legal, but will return the built-in function.)

...

.END