Is a generic finite state machine engine reasonable?

Is a generic finite state machine engine reasonable?

[Loren Schall]

I originally asked this question in comp.programming, but I think I'm
really looking for a more specific solution.

>Hello Netters, a colleague of mine brought me an interesting question
>and I knew that you would have some useful input.
>
>We're involved with a large realtime application that includes several
>pieces which could reasonably be implemented as finite state machines.
>Is it possible and reasonable to implement a "generic" finite state
>engine?  Please reply via e-mail and I'll summarize and re-post.  If
>you think this is an inapropriate place for this discussion, tell me
>where the right place is.
>
>I'm envisioning a (static) initialization step where the specific
>machine is defined (inputs, transitions, and outputs) and an
>invocation process taking an input and producing an output (the
>actual state transition being internal and invisible).
>
>The main objective we're looking for is ease of maintenance.  We
>believe that it would be easier to maintain several state machine
>descriptions and one implementation, than several different state
>machine implementations.
>
>Does anyone know of any appropiate references or examples (Ada, C,
>or C++ would be must useful).
>
>Thanks, in advance, for any help you can offer.

I'm not very familiar will OOP.  Isn't there some way to implement this
in Ada (instanciate and call)?  This would become part of an existing
project that is moving from Pascal to Ada.

comp.programming replies:

#Look into LEX. 
#I am sure you will be able to write a good utility using LEX to serve
#all your needs involving finite state machines.

I hadn't really thought about lex/flex.  I was hoping to avoid a two step
process.  Most of the programmers that would be using this are unfamiliar
with Unix (and its ideas).

*You may infer a general code-mapping algorithm that compiles DFA's
*directly into code, instead of into an abstract DFA implemented on top
*of the code layer, from the pesudo-code example below.
  [example deleted]

=In this years conference on Compiler Construction a paper by L.O.
=Larsen describes how one can generate an efficient specific finite
=state machine from a generic one by partially evaluating the generic
=machine with respect to a definition. The paper is in Springer-Verlag
=LNCS 641.

(I haven't checked out this paper, yet.)  I was kind'a thinking of
using "an abstract DFA implemented on top of the code".  Is this the
wrong approach?  Let me expand on my original idea.  What I'm really
looking for is an easy way to implement The Specification.  Several
place in our System Specification, state tables or state diagrams are
used to describe the expected response(s).  It would be most
convenient if these could be (almost) directly translated to code.

Am I making any sense?  Is this kind of thing possible or do I have to
look at making a translator (state machine description -> Ada)?  It is
a requirement that we use Ada, so nothing but Ada code can be concidered
the *offical* source.

I eagerly await any suggesting you might have to offer.

Loren
schall@swtech.cfsat.honeywell.com (Loren Schall)

Re: Is a generic finite state machine engine reasonable?

[John Goodsen]

Bob Martin has a very nice, clean design of a
generic finite state machine.  He has written
a parser which will parse textual state tables
and generate the corresponding C++ classes.
I'm sure this could just as easily be done in and
for Ada.  Bob used lex and yacc for the parsing.
AFLEX and AYACC would work equally well for the
Ada version.  

It's his Object Oriented design of the FSM that is
of most interest, however.  Once you've designed it,
parsing and spitting the code is the trivial part.

If you're interested in a copy, email me directly.
I'm sure Bob will let me distribute to the Ada world,
but I'll check for sure.  If I get too many requests,
then I'll just make it available on anonymous ftp or
post it...

--
John Goodsen                           PCIS Programme
Software Process & Environments        Ada Joint Program Office       
EVB Software Engineering               goodsenj@ajpo.sei.cmu.edu
jgg@evb.com