-*- Mode: Text; Fonts: Ct18b -*-

Chapter 13.3.4: ABSTRACT STATE MACHINES

	A state machine, or automata, is an entity that has well-defined
states and operations for changing from state to state.  Additionally,
there is some means of detecting the current state of the machine.  We may
think of abstract state machines as simple "black box" objects.  A user may
act upon the box (with procedures) or examine the attributes of the box
(via functions).  The latter are considered to be the state.  Of course,
any actions on the box may change its state.

	In terms of form, packages as abstract state machines do not export
types or (usually) objects.  In a sense, they look like abstract data types
or simple collections of program units.  However, the essential difference
is that packages used as abstract state machines have retained state
information in the package body.  For example, the TRANSCENDENTAL_FUNCTIONS
package declared earlier consisted of several subprograms, but calling one
subprogram did not affect any state.  In fact, each subprogram was quite
independent, and its outcome never could affect the other.  For state
machines, however, the operations applied do affect the state.  For
example, we may abstract a FURNACE to the user as:

	package FURNACE is
	  function  IS_RUNNING return BOOLEAN;
	  procedure SET(TEMPERATURE : in FLOAT);
	  procedure SHUT_DOWN;
	  function  TEMPERATURE_IS return FLOAT;
	  OVERTEMP  : exception;
	end FURNACE;

	The package user may only apply the four given subprograms to
either change the state of the FURNACE or determine the current
TEMPERATURE.  Clearly, the order in which these subprograms are called
makes a difference, due to the retained data.  Since no types or objects
are exported, this package defines only one object.  Furthermore, since the
package specification defines several subprograms, a complete package body
must eventually be supplied.

	Another typical example of a state machine is a lexical analyzer,
which is a machine that can recognize and classify a stream of characters. 
Such machines are necessary tools for compilers and communication systems. 
For example, as part of a compiler, we may wish to create a state machine
that can recognize identifiers or numbers.  A state transition diagram for
such a machine is shown in Figure 13-2.

	As seen in the diagram, the machine is initially in a START state. 
When the first symbol is received, it moves to a BUILD_IDENTIFIER state if
it is a LETTER, to a BUILD_NUMBER state otherwise.  The machine stays in
either state as long as a stream of LETTERs or DIGITs (for 
BUILD_IDENTIFIER) or just DIGITs (for BUILD_NUMBER) is received.  Once a
different symbol is received, the machine moves to a STOP state; at that
point, the token has been recognized.



                    Figure 13-2  State machine for LEXICAL_ANALYZER

We may define the interface to this abstract state machine as:

	package LEXICAL_ANALYZER is
	  procedure SET_START_STATE;
	  procedure RECEIVE_SYMBOL(C : in CHARACTER);
	  IDENTIFIER_ACCEPTED : exception;
	  INVALID_CHARACTER   : exception;
	  MACHINE_HALTED      : exception;
	  NUMBER_ACCEPTED     : exception;
	end LEXICAL_ANALYZER;

	Notice that we have identified the accepting conditions as
exceptions.  In this way, a user of this package may continue to send
symbols to the state machine without the overhead of explicitly checking to
see if the token has been accepted.  If desired, we could easily pass the
accepting information as a parameter through RECEIVE_SYMBOL.  We have
included an INVALID_CHARACTER exception, which is raised if the first
symbol is neither a LETTER nor a DIGIT.  We have also included the
operation SET_START_STATE so that the user may reinitialize the state
machine, plus a MACHINE_HALTED exception in case the user tries to apply an
operation to a halted machine.

     We may implement our state machine as follows:

	package body LEXICAL_ANALYZER is
	  type STATE is (START, BUILD_IDENTIFIER, BUILD_NUMBER, STOP);
	  PRESENT_STATE : STATE := START;
	  subtype ALPHA is CHARACTER range 'A'..'Z';
	  subtype DIGIT is CHARACTER range '0'..'9';
	  procedure SET_START_STATE is
	  --initialize state machine
	  begin
	    PRESENT_STATE := START;
	  end SET_START_STATE;
	  procedure RECEIVE_SYMBOL(C : in CHARACTER) is
	  --accept a symbol from the transmitter
	  begin
	    case PRESENT_STATE is
	      when START		=> if (C in ALPHA) then
					      PRESENT_STATE := BUILD_IDENTIFIER;
					   elsif (C in DIGIT) then
					      PRESENT_STATE := BUILD_NUMBER;
					   else
					      raise INVALID_CHARACTER;
					   end if;
	      when BUILD_IDENTIFIER	=> if (C in ALPHA) or (C in DIGIT) then
					      null;
					   else
					      PRESENT_STATE := STOP;
					      raise IDENTIFIER_ACCEPTED;
					   end if;
	      when BUILD_NUMBER		=> if (C in DIGIT) then
					      null;
					   else
					      PRESENT_STATE := STOP;
					      raise NUMBER_ACCEPTED;
					   end if;
					=> raise MACHINE_HALTED;
	      when STOP
	    end case;
	  end RECEIVE_SYMBOL;
	end LEXICAL_ANALYZER;

	This completes our implementation of a simple LEXICAL_ANALYZER. 
Since we defined the STATE as an enumeration type, it would be quite simple
to modify the machine to accept other tokens.

	Ada packages derive their power from their ability to encapsulate a
local entity and then enforce that abstraction.  In the next chapter, we
shall study additional packaging concepts involving generic program units.