Finites State Machine (OT?)

"Active8" <reply2group@ndbbm.net> wrote in message
news:vy7fvhinae51$.dlg@news.individual.net...
On Fri, 14 May 2004 12:54:35 GMT, Fred Bloggs wrote:
pdx wrote:
Why would a finite state machine be an appropriate method of
implementing
the control logic of a drinks vending machine?

The answer is that the desired vending machine operation can be
configured into a finite sequence of events each of which is conditioned
on a well-defined state of partial completion of operation and inputs
that assume exactly one of two values such as YES/NO, TRUE/FALSE,
GO/NOGO.

Wow! Well put. I'm glad I skipped to your post. Everyone else was
blathering on without answering the question.

I might add for future reference that the finite state machine can
be visualized with the aid of a state diagram which will aid in
defining the logic to be implemented.
Click to expand...
Anything that interacts with the outside world (including external software)
is often best described as an FSM. A drink vending machine is probably on
the degenerate end since it only has two or three states, but imagine a
ticket vending machine that requires several steps to determine the correct
ticket to print and fare to collect.

Also, drawing a state diagram is often useful (as opposed to, say, drawing
flowcharts) even if one chooses not to actually use an FSM in the
implementation. It clarifies what is acceptable input at each stage,
whereas many coders neglect handling error conditions or illegal state
transitions.

FSMs are almost indispensible when writing software that needs to handle
multiple client connections per server thread. IRC servers, for instance,
handle tens of thousands of connections with a single server thread via an
FSM, whereas common HTTP server implementations require dozens of server
threads yet still grind to a halt when the number of active clients exceeds
the size of the thread pool.

S

--
Stephen Sprunk "Stupid people surround themselves with smart
CCIE #3723 people. Smart people surround themselves with
K5SSS smart people who disagree with them." --Aaron Sorkin
 
del cecchi wrote:
"R. Steve Walz" <rstevew@armory.com> wrote in message
news:40A560A6.5C9F@armory.com...
Sander Vesik wrote:

In comp.arch R. Steve Walz <rstevew@armory.com> wrote:
Del Cecchi wrote:

"pdx" <pdx@spamtrap.com> wrote in message
news:2ghvjqF3429bU1@uni-berlin.de...
Sorry if this is off topic but I have another question to help
with the
revision for my exam (it's tomorrow).

Why would a finite state machine be an appropriate method of
implementing
the control logic of a drinks vending machine?


Another trick question. These days it isn't an appropriate way.
The
appropriate way is with an embedded microprocessor. Finite
state machines
only made sense when microprocessors were too expensive.
------------
You're not grasping that state machines are also implemented with
microprocessors these days, it's not either-or.

You should read up on Del's posting history. He grasps a rather
disconcerningly
-----------------
And so you're his doting fellatrix?


large amount of very complex things.
-------------------
So may he. So do I.
But which may still exclude the truth I mentioned on his part.

You see:
I don't HAVE to know everything to be smarter than YOU are.
Grasp set theory, over and against statistics you can't know.


Well, schematics galore. Wasn't your sister in a james bond movie?
I should have trimmed followups. comp.arch has a tradition of spoofing
folks looking for help with homework or evidencing lazyness and
cluelessness. I guess you whiz bang circuit designers over in the other
groups didn't catch on, and have nothing better to do than be volunteer
tutors.

Thanks for letting me know that one can implement state machines in
microcode. It had never occurred to me.
-------------
Click to expand...
Why do we believe you?


I shall be more careful in my followups in the future so as not to mess
your sandbox.

del cecchi
-----------------
Click to expand...
Your irrelevant off-topic posturing has you bending over the back
of the couch, asshole.

-Steve
--
-Steve Walz rstevew@armory.com ftp://ftp.armory.com/pub/user/rstevew
Electronics Site!! 1000's of Files and Dirs!! With Schematics Galore!!
http://www.armory.com/~rstevew or http://www.armory.com/~rstevew/Public
 
On Sat, 15 May 2004 05:25:09 GMT, Stephen Sprunk wrote:

"Active8" <reply2group@ndbbm.net> wrote in message
news:vy7fvhinae51$.dlg@news.individual.net...
On Fri, 14 May 2004 12:54:35 GMT, Fred Bloggs wrote:
pdx wrote:
Why would a finite state machine be an appropriate method of
implementing
the control logic of a drinks vending machine?

The answer is that the desired vending machine operation can be
configured into a finite sequence of events each of which is conditioned
on a well-defined state of partial completion of operation and inputs
that assume exactly one of two values such as YES/NO, TRUE/FALSE,
GO/NOGO.

Wow! Well put. I'm glad I skipped to your post. Everyone else was
blathering on without answering the question.

I might add for future reference that the finite state machine can
be visualized with the aid of a state diagram which will aid in
defining the logic to be implemented.

Anything that interacts with the outside world (including external software)
is often best described as an FSM. A drink vending machine is probably on
the degenerate end since it only has two or three states, but imagine a
ticket vending machine that requires several steps to determine the correct
ticket to print and fare to collect.

Also, drawing a state diagram is often useful (as opposed to, say, drawing
flowcharts) even if one chooses not to actually use an FSM in the
implementation. It clarifies what is acceptable input at each stage,
whereas many coders neglect handling error conditions or illegal state
transitions.
Click to expand...
You ain't s*@ttin'
FSMs are almost indispensible when writing software that needs to handle
multiple client connections per server thread. IRC servers, for instance,
handle tens of thousands of connections with a single server thread via an
FSM, whereas common HTTP server implementations require dozens of server
threads yet still grind to a halt when the number of active clients exceeds
the size of the thread pool.

S
Click to expand...
I'd like to see an example of how an IRC server is implemented with
a FSM. I can't quite draw a mental picture. I don't know the IRC
protocol, either.

--
Best Regards,
Mike
 
"R. Steve Walz" <rstevew@armory.com> wrote in message news:<40A5B82D.3BEA@armory.com>...
del cecchi wrote:

"R. Steve Walz" <rstevew@armory.com> wrote in message
news:40A560A6.5C9F@armory.com...
Sander Vesik wrote:

In comp.arch R. Steve Walz <rstevew@armory.com> wrote:
Del Cecchi wrote:

"pdx" <pdx@spamtrap.com> wrote in message
news:2ghvjqF3429bU1@uni-berlin.de...
Sorry if this is off topic but I have another question to help
with the
revision for my exam (it's tomorrow).

Why would a finite state machine be an appropriate method of
implementing
the control logic of a drinks vending machine?


Another trick question. These days it isn't an appropriate way.
The
appropriate way is with an embedded microprocessor. Finite
state machines
only made sense when microprocessors were too expensive.
------------
You're not grasping that state machines are also implemented with
microprocessors these days, it's not either-or.

You should read up on Del's posting history. He grasps a rather
disconcerningly
-----------------
And so you're his doting fellatrix?


large amount of very complex things.
-------------------
So may he. So do I.
But which may still exclude the truth I mentioned on his part.

You see:
I don't HAVE to know everything to be smarter than YOU are.
Grasp set theory, over and against statistics you can't know.


Well, schematics galore. Wasn't your sister in a james bond movie?
I should have trimmed followups. comp.arch has a tradition of spoofing
folks looking for help with homework or evidencing lazyness and
cluelessness. I guess you whiz bang circuit designers over in the other
groups didn't catch on, and have nothing better to do than be volunteer
tutors.

Thanks for letting me know that one can implement state machines in
microcode. It had never occurred to me.
-------------
Why do we believe you?


I shall be more careful in my followups in the future so as not to mess
your sandbox.

del cecchi
-----------------
Your irrelevant off-topic posturing has you bending over the back
of the couch, asshole.

-Steve
Click to expand...
You realize that you have made a complete fool of yourself.

Relax and read a few old c.a posts before insulting the prefects :)

regards

johnjakson_usa_com
 
On Fri, 14 May 2004 18:45:27 -0700, Terry Given <the_domes@xtra.co.nz> wrote:
IME, programmers who dont understand state machines are talentless fools,
who tend to write lousy code. Alas, they can usually draw pretty GUIs so
people keep hiring them *sigh*
Click to expand...
I once tried to debug a program that consisted of a single 3500-line
while loop that _would_ have been a state machine, if the programmer
had known what a state machine was.

--
[T]o preserve liberty, it is essential that the whole body of the people
always possess arms, and be taught alike, especially when young
- Richard Henry Lee
 
Jeffrey C. Dege wrote:

On Fri, 14 May 2004 18:45:27 -0700, Terry Given <the_domes@xtra.co.nz> wrote:

IME, programmers who dont understand state machines are talentless fools,
who tend to write lousy code. Alas, they can usually draw pretty GUIs so
people keep hiring them *sigh*


I once tried to debug a program that consisted of a single 3500-line
while loop that _would_ have been a state machine, if the programmer
had known what a state machine was.
Click to expand...
Hmmm... Wy do I get the feeling that 'tried' is the operative word here? :-(

Terje

--
- <Terje.Mathisen@hda.hydro.com>
"almost all programming can be viewed as an exercise in caching"
 
"Active8" <reply2group@ndbbm.net> wrote in message
news:5vmxhvmz3fu3.dlg@news.individual.net...
On Sat, 15 May 2004 05:25:09 GMT, Stephen Sprunk wrote:
FSMs are almost indispensible when writing software that needs to handle
multiple client connections per server thread. IRC servers, for
instance,
handle tens of thousands of connections with a single server thread via
an
FSM, whereas common HTTP server implementations require dozens of server
threads yet still grind to a halt when the number of active clients
exceeds
the size of the thread pool.

I'd like to see an example of how an IRC server is implemented with
a FSM. I can't quite draw a mental picture. I don't know the IRC
protocol, either.
Click to expand...
When a client first connects to a server, there are all sorts of things the
server must do before it allows the client to start chatting, such as
checking DNS, IDENT, and an optional username/password. Since the standard
ways to check these things are blocking and the server only has one thread,
an FSM is very useful. Here's a pseudocode example:

IDLE:
client connects
send DNS request
start timer
move to DNS_WAIT

DNS_WAIT:
if timer expires, move to DNS_ERROR, otherwise:
update client_info with DNS response
send IDENT request
start timer
move to IDENT_WAIT

IDENT_WAIT:
if timer expires, move to IDENT_ERROR, otherwise:
update client_info with IDENT response
if anonymous users allowed, move to USER_CONNECTED
else start timer and move to USER_WAIT

USER_WAIT:
if timer expires, move to USER_ERROR, otherwise:
update client_info with username
start timer
move to PASS_WAIT

PASS_WAIT:
if timer expires, move to USER_ERROR, otherwise:
if password correct, move to USER_CONNECTED
else restart timer and move to USER_WAIT

USER_CONNECTED:
if timer expires, move to INACTIVE_ERROR
if input rate exceeds threshhold, move to USER_FLOOD
if username received, update client_info, start timer, and move to PASS_WAIT
if OPER command received and valid, move to OPER_CONNECTED
parse one user-level command in input buffer
restart timer

USER_FLOOD
if input rate below threshold, move to USER_CONNECTED
else discard any input

OPER_CONNECTED
if MODE -o command received, restart timer and move to USER_CONNECTED
(operator returning to user status)
parse multiple user- or operator-level commands in input buffer


Obviously there are a number of error states referenced which I didn't give
pseudocode for, but they either terminate the connection (and move to IDLE)
or kick back an error and move to another state depending on the admin's
configuration.

S

--
Stephen Sprunk "Stupid people surround themselves with smart
CCIE #3723 people. Smart people surround themselves with
K5SSS smart people who disagree with them." --Aaron Sorkin
 
"Terry Given" <the_domes@xtra.co.nz> wrote in message
news:asopc.5574$XI4.198306@news.xtra.co.nz...
"Jeffrey C. Dege" <jdege@jdege.visi.com> wrote in message
news:slrncac317.2ta.jdege@jdege.visi.com...
I once tried to debug a program that consisted of a single 3500-line
while loop that _would_ have been a state machine, if the programmer
had known what a state machine was.

sounds terrible. I bet you couldnt convince the programmer that it was a
state machine, and therefore can be analysed as such.....
Click to expand...
First you'd have to teach the original coder what a state machine is... It
certainly wasn't covered in the Comp Sci classes I took or in any of the
dozen books I've read on programming since then; I finally learned about
FSMs when trying to decipher some RFCs on routing protocols, and I still
don't think of them at first when approaching a problem.

S

--
Stephen Sprunk "Stupid people surround themselves with smart
CCIE #3723 people. Smart people surround themselves with
K5SSS smart people who disagree with them." --Aaron Sorkin
 
"Stephen Sprunk" <stephen@sprunk.org> wrote in message
news:e19a504b702c8024df437d67c5131ba8@news.teranews.com...
First you'd have to teach the original coder what a state machine
is... It
certainly wasn't covered in the Comp Sci classes I took or in any of
the
dozen books I've read on programming since then; I finally learned
about
FSMs when trying to decipher some RFCs on routing protocols, and I
still
don't think of them at first when approaching a problem.

S

--
Stephen Sprunk "Stupid people surround themselves with smart
CCIE #3723 people. Smart people surround themselves with
K5SSS smart people who disagree with them." --Aaron Sorkin
Click to expand...
You would love the link/phy part of InfiniBand. One state machine after
another.
del
Click to expand...
 
In article <2ghvjqF3429bU1@uni-berlin.de>, "pdx" <pdx@spamtrap.com>
wrote:

Sorry if this is off topic but I have another question to help with the
revision for my exam (it's tomorrow).

Why would a finite state machine be an appropriate method of implementing
the control logic of a drinks vending machine?
Click to expand...
All computers are FSMs. A FSM diagram is a way to organize the exact
steps needed to process something. More complex diagrams have different
levels of detail; states within states. Diagrams are also good for
finding and resolving flaws/holes in the original logic.

How a diagram is translated into code is up to you. There are any
number of ways to implement it, some more suitable for a task than
others. Picking an appropriate one is part of the programming job.
 
"R. Steve Walz" <rstevew@armory.com> wrote in message
news:40A5B82D.3BEA@armory.com...
del cecchi wrote:

Thanks for letting me know that one can implement state machines in
microcode. It had never occurred to me.
-------------
Why do we believe you?
Click to expand...
Because why would he lie?

Cheers!
Rich
 
"Stephen Sprunk" <stephen@sprunk.org> wrote in message
news:54c913784ee956f775751183d92ce20d@news.teranews.com...
"Active8" <reply2group@ndbbm.net> wrote in message
I'd like to see an example of how an IRC server is implemented with
a FSM. I can't quite draw a mental picture. I don't know the IRC
protocol, either.
When a client first connects to a server, there are all sorts of things
the
server must do before it allows the client to start chatting, such as
checking DNS, IDENT, and an optional username/password. Since the
standard
ways to check these things are blocking and the server only has one
thread,
an FSM is very useful. Here's a pseudocode example:
Click to expand...
Pardon me, but what server do you have that has only one thread?

And any given thing can block its particular system call, yes, but
your main loop dispatches the functions and rather than waiting for
a particular link in the chain, it can go ahead and do something
else, and just check back whenever it wants to try thing 1 again.

Or are you saying that a FSM is indistinguishable from a flowchart?

Thanks,
Rich
 
On Sat, 15 May 2004 20:29:38 GMT, Stephen Sprunk <stephen@sprunk.org> wrote:
"Terry Given" <the_domes@xtra.co.nz> wrote in message
news:asopc.5574$XI4.198306@news.xtra.co.nz...
"Jeffrey C. Dege" <jdege@jdege.visi.com> wrote in message
news:slrncac317.2ta.jdege@jdege.visi.com...
I once tried to debug a program that consisted of a single 3500-line
while loop that _would_ have been a state machine, if the programmer
had known what a state machine was.

sounds terrible. I bet you couldnt convince the programmer that it was a
state machine, and therefore can be analysed as such.....

First you'd have to teach the original coder what a state machine is... It
certainly wasn't covered in the Comp Sci classes I took or in any of the
dozen books I've read on programming since then; I finally learned about
FSMs when trying to decipher some RFCs on routing protocols, and I still
don't think of them at first when approaching a problem.
Click to expand...
I don't see how you could possibly teach a compiler class without
either covering, or requiring as prerequisite, finite automata and
state machines.

And I don't see how a degree in Comp Sci could not include classes in
compiler technology and context-free grammars.

--
Be not afraid of any man
Who walks beneath the skies,
For be he tall or be he strong,
I will equalize.
- Samuel Colt
 
"john jakson" <johnjakson@yahoo.com> wrote in message
news:adb3971c.0405150303.3ba09f3d@posting.google.com...
"R. Steve Walz" <rstevew@armory.com> wrote in message
news:<40A5B82D.3BEA@armory.com>...
-----------------
Your irrelevant off-topic posturing has you bending over the back
of the couch, asshole.

-Steve

You realize that you have made a complete fool of yourself.
Click to expand...
No, john jakson, unfortunately, Walz never seems to realize anything at all.

Good Luck!
Rich
 
In article <2ghvjqF3429bU1@uni-berlin.de>, pdx <pdx@spamtrap.com> wrote:
Sorry if this is off topic but I have another question to help with the
revision for my exam (it's tomorrow).

Why would a finite state machine be an appropriate method of implementing
the control logic of a drinks vending machine?
Click to expand...
Because a finite state machine is far easier for humans to debug and/or
verify than are infinite state machines.

Compare and contrast the frequency and size of OS patches for a typical
vending machine compared with Windows XP for some hints as to the asymtotic
behavior.


IMHO. YMMV.
--
Ron Nicholson rhn AT nicholson DOT com http://www.nicholson.com/rhn/
#include <canonical.disclaimer> // only my own opinions, etc.
 
In article <40a3edb0$0$170$c3e8da3@news.astraweb.com>,
Frank Bemelman <f.bemelmanx@planet.invalid.nl> wrote:
"Richard Henry" <rphenry@home.com> schreef in bericht
news:yqRoc.29065$fE.19074@fed1read02...

"Del Cecchi" <cecchinospam@us.ibm.com> wrote in message
news:2gi5u4F359r3U1@uni-berlin.de...
"pdx" <pdx@spamtrap.com> wrote in message
news:2ghvjqF3429bU1@uni-berlin.de...
Why would a finite state machine be an appropriate method of
implementing
the control logic of a drinks vending machine?

Another trick question. These days it isn't an appropriate way. The
appropriate way is with an embedded microprocessor. Finite state
machines
only made sense when microprocessors were too expensive.

I always implemented finite state machines in software on microprocessors.

A microprocessor *is* a finite state machine, no matter what software
you load it with.
Click to expand...
None of the above. A microprocessor running software is actually a
collection of probablisticly behaved quantum particles which have been
abstracted into several levels of machines, given sufficiently bounded
operating conditions (below the melting point of Si, for instance).
Several of these abstraction levels are assumed to behave like finite state
machines: registers and memory elements, the CPU pipeline, CPU ISA,
microcode, library routines, OS, byte-code or script interpreters,
and application code.

Perhaps at Planck dimensions something finite is happening.


IMHO. YMMV.
--
Ron Nicholson rhn AT nicholson DOT com http://www.nicholson.com/rhn/
#include <canonical.disclaimer> // only my own opinions, etc.
 
"Terry Given" <the_domes@xtra.co.nz> wrote in message
news:FSZoc.5006$XI4.180423@news.xtra.co.nz...
"pdx" <pdx@spamtrap.com> wrote in message
news:2ghvjqF3429bU1@uni-berlin.de...
Sorry if this is off topic but I have another question to help with the
revision for my exam (it's tomorrow).

Why would a finite state machine be an appropriate method of
implementing
the control logic of a drinks vending machine?



The answer to your question is simple - because it can be made to work.

IME, programmers who dont understand state machines are talentless fools,
who tend to write lousy code. Alas, they can usually draw pretty GUIs so
people keep hiring them *sigh*

Terry
Click to expand...
OK, Fred's explanation is better than mine. terse is bad?

Terry
 
john jakson wrote:
"R. Steve Walz" <rstevew@armory.com> wrote in message news:<40A5B82D.3BEA@armory.com>...
del cecchi wrote:

"R. Steve Walz" <rstevew@armory.com> wrote in message
news:40A560A6.5C9F@armory.com...
Sander Vesik wrote:

In comp.arch R. Steve Walz <rstevew@armory.com> wrote:
Del Cecchi wrote:

"pdx" <pdx@spamtrap.com> wrote in message
news:2ghvjqF3429bU1@uni-berlin.de...
Sorry if this is off topic but I have another question to help
with the
revision for my exam (it's tomorrow).

Why would a finite state machine be an appropriate method of
implementing
the control logic of a drinks vending machine?


Another trick question. These days it isn't an appropriate way.
The
appropriate way is with an embedded microprocessor. Finite
state machines
only made sense when microprocessors were too expensive.
------------
You're not grasping that state machines are also implemented with
microprocessors these days, it's not either-or.

You should read up on Del's posting history. He grasps a rather
disconcerningly
-----------------
And so you're his doting fellatrix?


large amount of very complex things.
-------------------
So may he. So do I.
But which may still exclude the truth I mentioned on his part.

You see:
I don't HAVE to know everything to be smarter than YOU are.
Grasp set theory, over and against statistics you can't know.


Well, schematics galore. Wasn't your sister in a james bond movie?
I should have trimmed followups. comp.arch has a tradition of spoofing
folks looking for help with homework or evidencing lazyness and
cluelessness. I guess you whiz bang circuit designers over in the other
groups didn't catch on, and have nothing better to do than be volunteer
tutors.

Thanks for letting me know that one can implement state machines in
microcode. It had never occurred to me.
-------------
Why do we believe you?


I shall be more careful in my followups in the future so as not to mess
your sandbox.

del cecchi
-----------------
Your irrelevant off-topic posturing has you bending over the back
of the couch, asshole.

-Steve

You realize that you have made a complete fool of yourself.
------------------------
Click to expand...
That's merely your disingenuous lie.


Relax and read a few old c.a posts before insulting the prefects :)
------------------------
Click to expand...
I AM among the prefects, you insipid little shit-mind!

(here since 1992)

-Steve
--
-Steve Walz rstevew@armory.com ftp://ftp.armory.com/pub/user/rstevew
Electronics Site!! 1000's of Files and Dirs!! With Schematics Galore!!
http://www.armory.com/~rstevew or http://www.armory.com/~rstevew/Public
 
Rich Grise wrote:
"john jakson" <johnjakson@yahoo.com> wrote in message
news:adb3971c.0405150303.3ba09f3d@posting.google.com...
"R. Steve Walz" <rstevew@armory.com> wrote in message
news:<40A5B82D.3BEA@armory.com>...
-----------------
Your irrelevant off-topic posturing has you bending over the back
of the couch, asshole.

-Steve

You realize that you have made a complete fool of yourself.

No, john jakson, unfortunately, Walz never seems to realize anything at all.
-------------------------
Click to expand...
The knee-kerker Rich should know, eh?

-Steve
--
-Steve Walz rstevew@armory.com ftp://ftp.armory.com/pub/user/rstevew
Electronics Site!! 1000's of Files and Dirs!! With Schematics Galore!!
http://www.armory.com/~rstevew or http://www.armory.com/~rstevew/Public
 
Rich Grise wrote:
"R. Steve Walz" <rstevew@armory.com> wrote in message
news:40A5B82D.3BEA@armory.com...
del cecchi wrote:

Thanks for letting me know that one can implement state machines in
microcode. It had never occurred to me.
-------------
Why do we believe you?

Because why would he lie?

Cheers!
Rich
-----------------
Click to expand...
Look, Rich, if you don't even GET the humor, don't try to re-tell
the joke, it embarrases us for you.

Joke explained (WHY do I bother?):
Since he knew and pretended he hadn't, saying "Why do we believe
you" is an amusing backhanded cut.

Then you trying to stick up for his honesty shows your ignorance,
because he was intentionally lying to be smug. Your notion that
*I* actually thought that he didn't know was simply your error
in the level of subtletly you perceieved in the convertsation.

-Steve
--
-Steve Walz rstevew@armory.com ftp://ftp.armory.com/pub/user/rstevew
Electronics Site!! 1000's of Files and Dirs!! With Schematics Galore!!
http://www.armory.com/~rstevew or http://www.armory.com/~rstevew/Public
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top