Path: archiver1.google.com!news2.google.com!news.maxwell.syr.edu!wn11feed!worldnet.att.net!attbi_feed3!attbi_feed4!attbi.com!attbi_s51.POSTED!not-for-mail
From: Dave Roberts <ld...@re-move.droberts.com>
Subject: Re: State machine representation
Newsgroups: comp.lang.lisp
References: <Sn1Tb.154045$5V2.806622@attbi_s53> <87hdybc8q0.fsf@g.mccaughan.ntlworld.com> <4YaTb.74925$ef.19287@twister01.bloor.is.net.cable.rogers.com>
Lines: 97
User-Agent: KNode/0.7.2
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7Bit
Message-ID: <VGbTb.160358$nt4.729455@attbi_s51>
NNTP-Posting-Host: 24.6.199.184
X-Complaints-To: abuse@comcast.net
X-Trace: attbi_s51 1075660597 24.6.199.184 (Sun, 01 Feb 2004 18:36:37 GMT)
NNTP-Posting-Date: Sun, 01 Feb 2004 18:36:37 GMT
Organization: Comcast Online
Date: Sun, 01 Feb 2004 18:36:37 GMT

Paul Tarvydas wrote:

> In any language, if you want to use state machines as a *serious*
> programming construct, you need to consider:
> 
> a) entry code - code that is executed when a state is entered
> 
> b) exit code - code that is executed when you leave a state
> 
> c) transition code - code that is executed when a particular
> state-to-state transition is taken
> 
> d) hierarchical states - (a la Harel Statecharts) state machines nested
> inside of parent states, where transitions into and out of the parent
> state are "inherited" by the nested states - for example an "error" or
> "reset" transition out of a parent state causes all nested machines to
> execute their exit code, deepest first.
> 
> The protocol for performing a "step" of a state machine, triggered by an
> incoming reactive event is:
> 
> 1) exit current state
> 
> 2) determine which particular transition is to be taken, then execute its
> transition code
> 
> 3) enter next state.
> 
> (Suitably augmented by considerations for hierarchical states).

Right. My plan was to play around with some simple protocol state machines
and then develop a more general macro "language" that implements more fully
general state machines. I figured this would be a good exercise to learn
both the basics of CL and then make my way into non-trivial macros.

> None of the suggestions, thus far, have addressed these issues.  For
> example "go" is insufficient for performing a transition (since it must
> perform the
> above protocol).  Symbols / case #'s are insufficient because a sate
> transition has a least 3 parts.

Depends on how complex your state machines are. If you have a hardware
background, you understand the difference between Mealy and Moore state
machines. Moore state machines associates actions to the entry of states
themselves, while Mealy assigns them to the transitions between states.
Moore state machines are more simply and work well for small problems, but
can lead to state explosion if the machine logic is really complex. The
things you describe above are all nice generalizations of Mealy machines
and further increase flexibility and reduce state explosion. They're nice,
but they aren't *required* to make state machines work.

> If I wanted debug-ability, I would implement state machines using
> defstructs or clos objects along with a state-walking engine (which would
> have state-single-stepping built into it).

Right. That was one of the things I was looking at.

> If I wanted performance, I would implement a state compiler using lisp
> macros (e.g. define defmachine and defstate macros) that unroll the
> control flow within a machine into the hoary combination of case's, go's
> and name-manglings necessary to efficiently encode the above logic.

That was step 2 of my plan. ;-)

> In a language other than lisp, the state compiler would generally be
> "outside of" the language, i.e. a separate compiler program which emits
> source code in the target language and then is compiled again by the
> target-language compiler.
> 
> This demonstrates one of the features of CL - due to a combination of its
> regular syntax and its macros, CL has a compiler-compiler (think "Antlr"
> or
> "YACC") built into the language.  [And, just to over-do the analogy, lisp
> comes pre-LEX'ed - "symbols" are "tokens".  "LEX" is built into CL via the
> reader.]

Yes, exactly. That's one of the reasons for the exercise from my side. I
want to understand this machinery and flexibility in greater detail. I have
done the reading, now I want to flex my mental muscles.

> Great physicists solve a problem by inventing a notation to describe the
> problem, first.  Good lispers do the same.

Yes, exactly. That's precisely what I want to do. I have written state
machines in lots of different languages over the years. In some, the amount
of baggage you need to write to get a maintainable system is large, and the
more maintainable the system is, the slower it typically operates. My goal
is to learn about how I could implement the system in low-level constructs,
then develop a macro language on top of those ideas that allows simple,
maintainable expression, but transformation down to the efficient
representations.

Anyway, this is just a self-imposed exercise for myself to get me to work
through the details. Thanks for the discussion. Your input is spot on.

-- Dave