Communications State Machines

Article Overview
State Machines
Communications and State Machines
Creating Newton Communications State Machines
Where To Go From Here
Notes

This article discusses communications state machines and in particular, their use in programming the Newton endpoint system. It begins with a general discussion on state machines in the section titled State Machines and then goes on to talk about the use of state machines in building communications systems in the section titled Communications and State Machines. Finally the specifics of state machines built using the Newton endpoint system are discussed in the section Creating Newton Communications State Machines.

This article is meant to demonstrate the principle of Newton communications state machines rather than the details of how to construct one. Further specifics of endpoint coding can be found in the article Endpoint Details. Also useful in this regard is the Input Spec Animation which demonstrates how inputSpecs may be used to handle a variety of inputs.

A state machine (or more exactly, a finite state machine) is a machine which moves from an initial state (a state is a point where the machine has a stable set of values associated with it) to a sequence of different states until it reaches some final state. A computer running a program with a given set of inputs is a state machine which moves from the initial state just before the program begins to run to a final state after the program completes. In fact hardware designers view computers entirely as state machines where they move from one state to another based on the changing electronic impulses within the machine.

An important aspect of state machines is that from any given state there may be any number (including 0) of new states that the machine can change to. For example, if a computer is waiting for an input in the form of a switch being thrown, it may idle by remaining in the same state until that switch is thrown at which point it changes state by beginning to shut itself down. On the other hand, the same machine may go to another state if a different switch is thrown, say starting a sequence of state changes which will run a particular operating system and yet another state if a different switch is thrown. This may be viewed in the form of a table or a state diagram as shown below:

Input    Current State    Next State

Switch1    Running MacOS      Off

Switch2    Running MacOS      Running Windows OS

Switch3    Running MacOS      Running Mac OS 

The table shows how a state changes based on different input. The diagram shows the same thing schematically. These are called state tables and state diagrams respectively. Note that from the MacOS state there are three states we can transition to: Windows, Off and back to (or remain in) MacOS.

If the idea of "throwing a switch" is abstracted to mean a change in a value within a program, then we may begin to talk about a software state machine, that is an abstract state machine which exists entirely within the software running on a machine.

The usefulness of such concepts is that they allow us to more easily examine what may be a very complex set of situations in order to produce the correct response at the correct moment based on what has happened. In particular, when we are dealing with the interaction between systems, such as two computers or a computer and an input device, the state machine view of the systems makes it easier to describe and follow the possible interactions between the systems. As we will see in the next section, this is very useful when discussing communications systems.

Suppose we have a communications protocol for a bulletin board system (bbs) where the user's entries are shown in italics, the computer responses are shown in normal style and the computer actions are shown in angle brackets (<>):

Logon: userID

Password: password

Password accepted.

Command: Non-terminal commands

<Response to command>

Command: logoff

Bye!

This can be represented with the following state table and state diagram:

Input            Current State     Next State

  
Connection request  Disconnected        Connected 
  
userID              Connected           Password 
  
password            Password            Command 
  
non-terminal cmd    Command             Command 
  
logoff              Command             Disconnected

This gives us an easy way to design and review a communications interface. Since the two systems in question are the bulletin board system and the connecting terminal/computer, we can use this simple diagram as the starting point for designing a more fully realized environment. For example, we might add error handling states which deal with such things as problems connecting, bad userIDs or passwords, unknown commands, etc.

The reason that state machine designs work so well when implementing communications systems is because unlike many programs which work entirely within a computer and its sub-systems (e.g., keyboard, mouse, etc.), a communications system deals with the interface between two (or more) fully realized systems. This increases the complexity and increases the likelihood of the communicating systems getting out of step with one another. In particular this can occur because the systems are entirely asynchronous from each other.

By asynchronous we meant that events happen on each system independent of what is happening on any other system.

For example, in the bulletin board described above, if the connecting system decides that it can begin issuing commands after the password is accepted (as shown above), but the host system is looking up whether there is any mail for the connecting machine, it is possible that the host will miss a command sent from the connecting system. If a mail check is usual it must either be included as part of the password verification and response or another state should be added to the above description. In either case the state diagram helps in the design and implementation of the system.

The Newton endpoint subsystem is strongly aligned with the idea of building a communications state machine. An endpoint normally as at least the following states:



The key points here are that before an endpoint can move to a connected state it must be instantiated (become a NewtonScript object) and bound (be attached to the low-level comm tool). Similarly when an endpoint is finished transferring data and is disconnected, it reverts to a bound state and then (after unbinding) it returns to the instantiated state. Finally when the endpoint is disposed of it returns to the initial state (not running). This becomes important as if there is an error in any step of trying to connect you should return to the previous state before trying again. In other words, if you fail in the transition from the bound state to the connected state, you must not try to disconnect or you will get an error.

However, you do not have to unbind to try connecting again.

Beyond the above "must do" states you may add as many other states as you wish. In particular when handling input or other asynchronous events you will probably add a number of states which we have described simply as a single "Data Transfer" state. For example, if we were connecting the Newton to the bulletin board described above, after connecting we would add a logon state followed by a password state to finish the connection protocol. Once connected we would probably cycle from a "Send Command" state to a "Receive Response" state until we were ready to logoff.

The actual mechanics of creating such a state machine is covered in the article on Endpoint Details and in the Asynchronous Endpoint Lab as well as in the Input Spec Animation. Here we will simply discuss state transition events on the Newton in general terms.

Basically state machines operate on the basis of stimulus and response. When a stimulus such as an input reaches a state machine it responds and may change its state. In the case of the Newton communications sub-system there are three sources of stimulus: direct calls to the endpoint system, asynchronous completion callbacks from the endpoint system and callbacks caused by external input.

Direct calls to the endpoint system include all the calls made by a programmer to the endpoint routines. For example, a call to instantiate an endpoint is made by a program in order to create an endpoint object. This is usually done when it wants to begin the connection process whether because of a program is starting or because of some action taken by the user (e.g., the user routes data to a transport).

Asynchronous callbacks occur when a call to the endpoint system is made asynchronously. The callback routine is specified when the initial call is made and the callback routine is executed when the initial call completes. For example, a program may make an asynchronous call to connect to a remote device. Since this may take some time to complete and since the programmer may not want to deny the user access to other features of the program while the connect attempt is made, such calls are frequently made asynchronously. In this case the programmer specifies a method to be called when the connection attempt completes regardless of whether the attempt was successful or not.

When external input is expected a programmer must specify an inputSpec which describes what form the input is expected to take, when to notify the program of incoming data (e.g., when a particular string arrives), how big the input buffer is, and so on. When the specified input conditions occur, one of several methods will be called by the endpoint system depending on the inputSpec and the conditions which caused the endpoint system to trigger. An example of the use of an inputSpec would be the response from a bulletin board system after a command was issued. In this case the program might establish an inputSpec which will call a method when a carriage return character arrives assuming that a carriage return indicated the end of the response.

A typical sequence of state changes might look like this:

1. User taps a button requesting a connect to a bulletin board system (bbs)
2. Program makes a synchronous attempt to instantiate the endpoint
3. If instantiation succeeds, a synchronous attempt is made to bind the endpoint
4. If binding succeeds an asynchronous attempt is made to connect
5. If connection succeeds, an inputSpec is specified to look for the prompt "Login:"
6. If the login prompt is received, another inputSpec is specified looking for "Password:" and the userID is sent
7. If the password prompt is received, a command inputSpec is specified and the password is sent. Part of the command inputSpec is a check for response to a logout command.
8. As the user enters commands they are sent to the bbs and responses cause the methods specified by the command inputSpec to be called
9. When the response to a logout command is seen, the current inputSpec is canceled and an asynchronous call to disconnect the endpoint is made
10. When the disconnect attempt completes the program synchronously unbinds and destroys the endpoint object.

Note that inputSpecs are set before another message is sent.

From this example you can see how the state machine described above is built using the endpoint system. As described in the Endpoint Details article, the API for endpoints allows very complex state machines to be created which can change state based on several different possible responses or even no response within a given time period (a timeout). In building such complex systems you may find it useful to describe the states either in a table or a state diagram form before you begin to build the endpoint code.

The likeliest places to go from here include the article Endpoint Details and the InputSpec Animation which is a QuickTime movie which demonstrates several different input scenarios.

The main reference for endpoints is Chapter 4 of Newton Programmer's Guide: Communications. NPG: Communications can be found at the Newton Documentation site and is available in Acrobat and DocViewer formats.

To look at some actual code you may want to go to the Basic Modem Walkthrough Lab or simply try the endpoint folder in the DTS Sample Code (or Sample Code for Windows).

For further discussion of the state machine model for Newton communications, see the article Finite State Machines: A Model for Newton Communications in the April 1996 issue of Newton Technology Journal. This article also describes the new prototype protoFSM (FSM=finite state machine) available in the Newton Internet Enabler sample code. This issue (and others as well) is available from Apple by contacting Apple at DEVSUPPORT@apple.com. Current and back issues of NTJ are available at the Newton Documentation site.

For an example of the use of protoFSM, see the NIE sample code or look at the Other Features Lab.

Finally, the Q&As for the Newton communication sub-system give more details about what happens "below the surface" of the endpoint system. In particular see the Q&A titled: What Really Happens During Instantiate and Connect. The Q&A document is available from the Newton Documentation site.

Developer Services | Technical Information | Tools | Sample Code

Main | Page One | What's New | Apple Computer, Inc. | Find It | Contact Us | Help

Copyright Apple Computer, Inc.
Maintained online by commscourse@newton.apple.com
Updated 26-Sep-96 by dcd