State machine in ruby

Ruby
21

On Mon, 11 Sep 2006, Paul L. wrote:

John C. wrote:

First off I would just like to note a small mathematical congruence…

Every state machine can be replaced by a Thread. ie. Instead of a tangly
state machine, you have a thread sucking on an event queue.

Let me add my 2c. Every program is a state machine. The difference between
an ordinary program and what we might call a “state machine” is one of
explicit expression.

Correct.

Also, the use of threads make the state of the state machine harder to
determine. By using threads, the thread scheduler’s quirks, and every other
thread being run, becomes part of the behavior of a particular thread’s
state machine. One might go so far as to say that threads that show any
interaction at all prevent a state machine from being deterministic.

Yes and no.

If you only ever communicate event’s with between thread’s via a
SizedQueue’s of
length 1, you have the same “interlocking cog” determinancy as an
unthreaded state machine only model.

The difference is you may …

  • Program each Thread/state machine in a “simple forward manner” same
    as any program
  • You can, in appropriate cases, get substantial performance gains by
    increasing
    the Queue sizes.

Djikstra’s “Goto Consider Harmful” is even more applicable to state
machines where every transition is a “goto”!

Where there is more than one state machine, your main program becomes a
poorly designed inefficient home grown scheduler.

The fact is state machines suffer the same defects as Threads, ie. races
and deadlocks, it’s just the “interlocking gears” nature tends to make
them trigger or not trigger the defects the same way on every run.
(However, change the program and that is not true.)

John C. Phone : (64)(3) 358 6639
Tait Electronics Fax : (64)(3) 359 4632
PO Box 1645 Christchurch Email : [email protected]
New Zealand

“We have more to fear from
The Bungling of the Incompetent
Than from the Machinations of the Wicked.” (source unknown)

22

On 9/11/06, John C. [email protected] wrote:

If you only ever communicate event’s with between thread’s via a SizedQueue’s of
length 1, you have the same “interlocking cog” determinancy as an
unthreaded state machine only model.

Been there, done that. It’s a well-studied (and often very effective)
programming model to pipe different functional “stacks” inside a
process together with intra-process event queues. Unfortunately it
still leaves you with performance problems unless you really keep the
number of threads down. Such programs tend to scale only moderately
well, in my experience (which is extensive). Especially in the case of
Ruby (which has significant problems handling large per-process
working sets), I think it’s more potentially interesting to build
large systems by piping processes (not threads) together with
queues.

Where there is more than one state machine, your main program becomes a
poorly designed inefficient home grown scheduler.

Maybe your main program does :-). There is a technique and a body of
experience to this kind of programming, just as there is with threads.
Threads are superficially more attractive to most programmers, perhaps
for the reason you give (that you can program each thread in a “simple
forward manner”). This “simplicity” is often deceptive. At the end of
the day, I think we should be able to agree that high-performance
concurrent programming is just hard to do well, regardless of the
chosen technique.