* Hierarchical States Machines
@ 2004-04-28 18:48 Fabien
2004-04-28 19:39 ` Marius Amado Alves
` (2 more replies)
0 siblings, 3 replies; 12+ messages in thread
From: Fabien @ 2004-04-28 18:48 UTC (permalink / raw)
Hi everyone !!!
Pretty new to ADA dev., i am currently trying to implement a
hierarchical state machine for my application. So far, i must confess
that i do not really get on well with it. I am thus looking for some
people who might have tried to do it and who could give me some useful
tips .
Fabien
pS : I don't look for a ready-to-use solution, just some help !!!!!
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Hierarchical States Machines
2004-04-28 18:48 Hierarchical States Machines Fabien
@ 2004-04-28 19:39 ` Marius Amado Alves
2004-04-28 19:57 ` Robert I. Eachus
2004-04-29 3:58 ` Steve
2 siblings, 0 replies; 12+ messages in thread
From: Marius Amado Alves @ 2004-04-28 19:39 UTC (permalink / raw)
To: comp.lang.ada
> Pretty new to ADA dev.,
Welcome! You can now start writing "Ada" not "ADA" as your first rite of
passage :-)
> i am currently trying to implement a
> hierarchical state machine for my application....
I write state machines a lot in Ada. For example package XML_Automaton, which
I've just put for your viewing pleasure at the following secret URLs:
http://www.liacc.up.pt/~maa/mneson/xml_automaton.ads
http://www.liacc.up.pt/~maa/mneson/xml_automaton.adb
http://www.liacc.up.pt/~maa/mneson/xml2mntext.adb
The last unit is an real life example application of the package.
(Soon I'll update the Mneson site with *all* the cool latest developments. As
you might guess from above, XML import/export is one of them.)
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Hierarchical States Machines
2004-04-28 18:48 Hierarchical States Machines Fabien
2004-04-28 19:39 ` Marius Amado Alves
@ 2004-04-28 19:57 ` Robert I. Eachus
2004-04-29 3:00 ` Randy Brukardt
2004-04-29 12:10 ` Wojtek Narczynski
2004-04-29 3:58 ` Steve
2 siblings, 2 replies; 12+ messages in thread
From: Robert I. Eachus @ 2004-04-28 19:57 UTC (permalink / raw)
Fabien wrote:
> Pretty new to ADA dev., i am currently trying to implement a
> hierarchical state machine for my application. So far, i must confess
> that i do not really get on well with it. I am thus looking for some
> people who might have tried to do it and who could give me some useful
> tips .
>
> Fabien
>
> pS : I don't look for a ready-to-use solution, just some help !!!!!
Unlike any other type of software, goto is your friend.
The reason that goto is normally deprecated is that it results in
spaghetti code. However, if you are implementing a state machine, you
need to reflect the structure of the actual state diagram, which may
look like spaghetti.
Also if you are implementing a table driven state machine, the best way
to do it is to build a driver that is its own state machine. (Sort of
like using a universal Turing machine to read a description of a Turing
machine and emulate it.) Again, the use of gotos will allow you to
write a driver so that its structure corresponds to the algorithm you
are implementing.
Incidentally, as far as I know, or for that matter most Ada experts
know, this is the only area in Ada where you should use gotos. But goto
has been kept in the language primarily because it is _necessary_ to
create maintainable finite state machines, push-down automata, and the like.
--
Robert I. Eachus
"The terrorist enemy holds no territory, defends no population, is
unconstrained by rules of warfare, and respects no law of morality. Such
an enemy cannot be deterred, contained, appeased or negotiated with. It
can only be destroyed--and that, ladies and gentlemen, is the business
at hand." -- Dick Cheney
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Hierarchical States Machines
2004-04-28 19:57 ` Robert I. Eachus
@ 2004-04-29 3:00 ` Randy Brukardt
2004-04-29 7:25 ` Martin Krischik
2004-04-29 12:10 ` Wojtek Narczynski
1 sibling, 1 reply; 12+ messages in thread
From: Randy Brukardt @ 2004-04-29 3:00 UTC (permalink / raw)
"Robert I. Eachus" <rieachus@comcast.net> wrote in message
news:jrOdnQYzWKMxkQ3dRVn-hQ@comcast.com...
> Incidentally, as far as I know, or for that matter most Ada experts
> know, this is the only area in Ada where you should use gotos. But goto
> has been kept in the language primarily because it is _necessary_ to
> create maintainable finite state machines, push-down automata, and the
like.
Ah, baloney. :-)
I use gotos whenever they prevent duplicating work that otherwise would have
to be done. It's silly to have two copies of code to do something just to
avoid a goto (or to make such code into a subprogram with no purpose other
than to avoid a goto).
A common case is to emulate the missing "continue" that Ada doesn't have. It
usually shows up in some deeply nested code:
loop
<bunch of conditions>
<Do some processing>
if <unusual condition> then
<Handle unusual case>
goto Continue;
end if;
<bunch of else conditions>
end if;
<normal processing>;
<<continue>> null;
end loop;
You can avoid the goto by making a hash out of the code, but why bother?
Gotos are efficient, not particularly unstructured in Ada (most of the bad
cases are illegal) - compiler optimizers are unlikely to be able to get rid
of batches of boolean flags and turn them into the branches that really were
intended in the first place.
Randy.
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Hierarchical States Machines
2004-04-28 18:48 Hierarchical States Machines Fabien
2004-04-28 19:39 ` Marius Amado Alves
2004-04-28 19:57 ` Robert I. Eachus
@ 2004-04-29 3:58 ` Steve
2004-04-29 5:14 ` Robert I. Eachus
2004-04-29 15:41 ` Marius Amado Alves
2 siblings, 2 replies; 12+ messages in thread
From: Steve @ 2004-04-29 3:58 UTC (permalink / raw)
I don't have anything against using goto's for state machines... but...
I usually set up an enumeration for each state:
type my_states is ( start_state, initializing, etc, end_state );
And then use a loop with an enclosed case statement:
state := start_state;
loop
case state is
when start_state =>
...
state := initializing;
when initializing =>
when etc =>
when end_state =>
end case;
end loop;
In my opinion it makes things easier to follow since the entry
to a new state always happens from the same place.
Steve
(The Duck)
"Fabien" <fab_lio@yahoo.fr> wrote in message
news:fed2d60.0404281048.41d6c549@posting.google.com...
> Hi everyone !!!
>
> Pretty new to ADA dev., i am currently trying to implement a
> hierarchical state machine for my application. So far, i must confess
> that i do not really get on well with it. I am thus looking for some
> people who might have tried to do it and who could give me some useful
> tips .
>
> Fabien
>
> pS : I don't look for a ready-to-use solution, just some help !!!!!
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Hierarchical States Machines
2004-04-29 3:58 ` Steve
@ 2004-04-29 5:14 ` Robert I. Eachus
2004-04-29 6:36 ` tmoran
2004-04-29 15:41 ` Marius Amado Alves
1 sibling, 1 reply; 12+ messages in thread
From: Robert I. Eachus @ 2004-04-29 5:14 UTC (permalink / raw)
Steve wrote:
> I don't have anything against using goto's for state machines... but...
>
> I usually set up an enumeration for each state...
>
> In my opinion it makes things easier to follow since the entry
> to a new state always happens from the same place.
Exactly. My point is that this:
loop
case State is
when...
end case;
-- post processing
end loop;
...is the real underlying structure, and you should use gotos when
needed to preserve it. Randy mentioned one such case continue. (His
code looked exactly like a FSM to me, even if he wants to call it
something else.) Other typical patterns you run into are where you need
multiple exits from the loop, or you need to return to the beginning
while skipping the post-processing. For example in the Ada parser
driver I wrote for state machines created by LALR1 on Multics, there
were some "merged" state entries where several states action tables were
almost identical. So LALR1 generated table entries that said
essentially: if the next token is X do Y, otherwise go to the state
table for state Z. You could distort the engine all out of shape to
implement this, or put in a goto to just before the loop.
Someone who had been taught the "gotos are evil" religion reorganized
the code with a couple of added state variables to demonstrate the goto
wasn't necessary. His code was only twenty lines longer than my code,
and ran 40% slower. (Register pressure from those state variables push
things that should have been in registers onto the stack.) Although he
talked about looking at the generated code to see why it was so much
slower, I think he realized that his version was the spaghetti.
--
Robert I. Eachus
"The terrorist enemy holds no territory, defends no population, is
unconstrained by rules of warfare, and respects no law of morality. Such
an enemy cannot be deterred, contained, appeased or negotiated with. It
can only be destroyed--and that, ladies and gentlemen, is the business
at hand." -- Dick Cheney
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Hierarchical States Machines
2004-04-29 5:14 ` Robert I. Eachus
@ 2004-04-29 6:36 ` tmoran
2004-04-29 16:36 ` Robert I. Eachus
0 siblings, 1 reply; 12+ messages in thread
From: tmoran @ 2004-04-29 6:36 UTC (permalink / raw)
>and ran 40% slower. (Register pressure from those state variables push
Do you mean the parser state transitions ran 40% slower, or the whole
compiler, including IO, lexer, symbol tables, code generation, etc
was slowed by 40%?
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Hierarchical States Machines
2004-04-29 3:00 ` Randy Brukardt
@ 2004-04-29 7:25 ` Martin Krischik
2004-04-29 20:37 ` Randy Brukardt
0 siblings, 1 reply; 12+ messages in thread
From: Martin Krischik @ 2004-04-29 7:25 UTC (permalink / raw)
Randy Brukardt wrote:
> loop
> <bunch of conditions>
> <Do some processing>
> if <unusual condition> then
> <Handle unusual case>
> goto Continue;
> end if;
> <bunch of else conditions>
> end if;
> <normal processing>;
> <<continue>> null;
> end loop;
Is there any deepter reason why you did not use:
loop
<<continue>>
<bunch of conditions>
<Do some processing>
if <unusual condition> then
<Handle unusual case>
goto Continue;
end if;
<bunch of else conditions>
end if;
<normal processing>;
end loop;
i.E. A style guide or a RM I am not aware of?
With Regards
Martin
--
mailto://krischik@users.sourceforge.net
http://www.ada.krischik.com
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Hierarchical States Machines
2004-04-28 19:57 ` Robert I. Eachus
2004-04-29 3:00 ` Randy Brukardt
@ 2004-04-29 12:10 ` Wojtek Narczynski
1 sibling, 0 replies; 12+ messages in thread
From: Wojtek Narczynski @ 2004-04-29 12:10 UTC (permalink / raw)
Hello,
> But goto has been kept in the language primarily because it is _necessary_ to
> create maintainable finite state machines, push-down automata, and the like.
In the absence of "last call optimisation".
Regards,
Wojtek
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Hierarchical States Machines
2004-04-29 3:58 ` Steve
2004-04-29 5:14 ` Robert I. Eachus
@ 2004-04-29 15:41 ` Marius Amado Alves
1 sibling, 0 replies; 12+ messages in thread
From: Marius Amado Alves @ 2004-04-29 15:41 UTC (permalink / raw)
To: comp.lang.ada
On Thursday 29 April 2004 04:58, Steve wrote:
> I don't have anything against using goto's for state machines... but...
>
> I usually set up an enumeration for each state:
>
> type my_states is ( start_state, initializing, etc, end_state );...
That's how I usually do it too.
See
http://www.liacc.up.pt/~maa/files/Ada_Automaton/
for an Ada tokenizer written this way. Programs Ada_Automaton_Test and
Ada_Counter are example applications of the package. Ada_Counter counts the
significant semicolons in a unit.
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Hierarchical States Machines
2004-04-29 6:36 ` tmoran
@ 2004-04-29 16:36 ` Robert I. Eachus
0 siblings, 0 replies; 12+ messages in thread
From: Robert I. Eachus @ 2004-04-29 16:36 UTC (permalink / raw)
tmoran@acm.org wrote:
>>and ran 40% slower. (Register pressure from those state variables push
>
> Do you mean the parser state transitions ran 40% slower, or the whole
> compiler, including IO, lexer, symbol tables, code generation, etc
> was slowed by 40%?
Sorry, the first pass of the compiler, which included the scanner
(lexer) and created the symbol table and AST. The second pass did the
semantic analysis and 'decorated' the parse tree, and did all the
code-generator independent optimizations.
As I remember it, the running times were roughly 1-3-3. So it would
have been 1.4-3-3, for a 5 to 6% overall slowdown.
Even so it was pretty huge, and it shocked me. By the point this
occurred we had done a lot of optimization of the LALR1 engine and
structure so that (mostly for error correcting reasons) successive
reduce operations on the parse stack were deferred, then all called at
once after two successful succeeding shifts, or a successful shift and
(pending) reduce.
That sounds complicated, and it was. But it made for wonderful syntax
error correction without increasing the parse table size. (Well we had
about a half dozen added states to allow "panic mode" if none of the
single or double token fixes worked.)
We were initially worried about the changes for the error correction
support slowing down performance, but since it grouped the actions that
resulted in subroutine calls, it actually sped things up significantly
by eliminating register spills. When we looked at the generated code to
try and explain that 40% number, adding the two flags for the non-goto
solution increased the number of active variables from 6 to 8 in the key
loops--and we had six available registers once you eliminated the stack
pointer and program counter. Worse the access pattern basically rotated
through the variables. We thought about fixing that for both the Ada
and Multics PL/1 compilers, but a little bit of monitoring indicated
that this code was about the only thing around that hit this 'misfeature'.
The wonderful thing about being in a compiler group, and using Multics,
was that we could slip in performance counters like this on the
production machine, and see whether or not we should actually fix
anything. Technically our group supported the DPS-6 line not DPS-8M,
but we were in Billerica, MA, Multics development was at CISL in
Cambridge, MA, and GCOS-3/8 support was in Phoenix, AZ. So I could
submit a performance counter proposal like that to CISL, and we and they
would put it into the "development" version of the compiler within a few
days.
My favorite story about doing that was that we had a debate about using
static links or a display to manage up-level references in the Ada/SIL
compiler. We had a ferocious call-graph analyzer that merged stack
frames whenever possible, and of course, all variables in library
packages (and in the main program if it was not called recursively) were
handled directly. So we put in a trigger that added the static pointers
if necessary, and sent e-mail to a list of compiler people. Almost two
years later, I finally got one of those messages--for an ACVC test.
We decided we would take that code out and use a dynamic stack walk if
it was really necessary. I don't think that change ever happened--it
was of course, very low priority.
--
Robert I. Eachus
"The terrorist enemy holds no territory, defends no population, is
unconstrained by rules of warfare, and respects no law of morality. Such
an enemy cannot be deterred, contained, appeased or negotiated with. It
can only be destroyed--and that, ladies and gentlemen, is the business
at hand." -- Dick Cheney
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Hierarchical States Machines
2004-04-29 7:25 ` Martin Krischik
@ 2004-04-29 20:37 ` Randy Brukardt
0 siblings, 0 replies; 12+ messages in thread
From: Randy Brukardt @ 2004-04-29 20:37 UTC (permalink / raw)
"Martin Krischik" <krischik@users.sourceforge.net> wrote in message
news:1649831.NvcpCQcTn1@linux1.krischik.com...
...
> Is there any deepter reason why you did not use:
>
> loop
> <<continue>>
> <bunch of conditions>
> <Do some processing>
> if <unusual condition> then
> <Handle unusual case>
> goto Continue;
> end if;
> <bunch of else conditions>
> end if;
> <normal processing>;
> end loop;
>
> i.E. A style guide or a RM I am not aware of?
I usually want the loop head to be re-executed, so that if it gets modified
during maintenance (to a for-loop or a while-loop), it won't be necessary to
restructure the code. Besides, in most of these cases, the loop actually is
a while-loop, walking a list or other data structure.
Randy.
^ permalink raw reply [flat|nested] 12+ messages in thread
end of thread, other threads:[~2004-04-29 20:37 UTC | newest]
Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2004-04-28 18:48 Hierarchical States Machines Fabien
2004-04-28 19:39 ` Marius Amado Alves
2004-04-28 19:57 ` Robert I. Eachus
2004-04-29 3:00 ` Randy Brukardt
2004-04-29 7:25 ` Martin Krischik
2004-04-29 20:37 ` Randy Brukardt
2004-04-29 12:10 ` Wojtek Narczynski
2004-04-29 3:58 ` Steve
2004-04-29 5:14 ` Robert I. Eachus
2004-04-29 6:36 ` tmoran
2004-04-29 16:36 ` Robert I. Eachus
2004-04-29 15:41 ` Marius Amado Alves
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox