Erlang/OTP Forums
Author Message

<  Erlang questions mailing list  ~  Big state machines
joelr1 at gmail.com
Posted: Fri Apr 15, 2005 9:34 am Reply with quote
Guest
Dear Erlangers,

I'm implementing my poker logic as a gen_fsm behavior. I'm finding that
my FSM is getting a bit unwieldy, though, what with all the tests I have
to write for different state transitions, etc.

I'm wondering if there's an idiomatic way of splitting big FSMs into
smaller chunks. Should I move the processing code into different modules
and leave just invocations in the FSM callback module?

I suppose this will help with reusing states in other state machines but
would like to hear how people have been tackling this problem.

Thanks, Joel

--
http://wagerlabs.com/tech



Post generated using Mail2Forum (http://m2f.sourceforge.net)
Back to top
ulf.wiger at ericsson.com
Posted: Fri Apr 15, 2005 10:38 am Reply with quote
Guest
Without having seen the code, I'd wager a guess
that you're suffering from the standard problem
of writing complex FSMs using FIFO, run-to-completion
semantics.

The problem I'm referring to occurs when the FSM
has to coordinate with different actors; the FIFO
semantics force an arbitrary merge+serialization of
otherwise unsynchronized message streams, and since
your coordinating FSM cannot choose which message
source to handle next, it has to handle all
possible message sequences.

In order to handle this, you basically have to
write your FSM as a stack machine, where you keep
track of what you were doing, and what message you
expect to arrive next. In order to survive, you
soon realise that you have to draw an event-state
matrix. For each cell in your matrix, you have to
at least ask yourself whether the history matters
(i.e. the sequence of events that got you there).
If so, your event-state matrix will contain case
statements for certain cells, where you check for
various pre-conditions. The same questions will
of course also have to be present in your code,
so the programming pattern often becomes:

handle_event(Msg, State) ->
Q = what_was_I_doing(State),
case message_is_valid(Msg, Q) of
true ->
really_handle_message(Msg, State, Q);
false ->
case is_this_an_error(Msg, Q) of
true ->
erlang:fault(...);
false ->
NewState =
case defer_or_discard(Msg, Q) of
defer ->
defer(Msg, Q, State);
discard ->
State
end
end
end.

... or something to that effect. You get the point.

Perhaps this is not at all relevant in your case.
Difficult to say without having seen the source.

The remedy? Use plain Erlang state machines with
selective receive. You will still have to think
about whether you can break up your state machines
into several smaller ones. The proof is in your
code. If it simplifies the code - do it. Otherwise,
don't.

/Uffe

-----Original Message-----
From: owner-erlang-questions@erlang.org
[mailto:owner-erlang-questions@erlang.org]On Behalf Of Joel Reymont
Sent: den 15 april 2005 10:56
To: Erlang Users' List
Subject: Big state machines


Dear Erlangers,

I'm implementing my poker logic as a gen_fsm behavior. I'm finding that
my FSM is getting a bit unwieldy, though, what with all the tests I have
to write for different state transitions, etc.

I'm wondering if there's an idiomatic way of splitting big FSMs into
smaller chunks. Should I move the processing code into different modules
and leave just invocations in the FSM callback module?

I suppose this will help with reusing states in other state machines but
would like to hear how people have been tackling this problem.

Thanks, Joel

--
http://wagerlabs.com/tech



Post generated using Mail2Forum (http://m2f.sourceforge.net)
Back to top
joelr1 at gmail.com
Posted: Fri Apr 15, 2005 11:10 am Reply with quote
Guest
> Ulf Wiger (AL/EAB) wrote:
> [...]
>The remedy? Use plain Erlang state machines with
>selective receive. You will still have to think
>about whether you can break up your state machines
>into several smaller ones. The proof is in your
>code. If it simplifies the code - do it. Otherwise,
>don't.

Let me elaborate ...

I'm writing poker game logic for the Texas Hold'em variant.

First I wait for a few seconds to let people join, leave, sit out, come
back. I selectively ignore all other actions. When getting a timeout I
check if I have enough players and transition to collecting blinds.

Here I need to ask players to post a small blind and a big blind. Players
who join in these two states need to make up by posting the big blind and
I process this in a separate state after SB and BB are collected.

So I have small_blind, big_blind and make_up_blinds for states.

Have a separate small_blind state because after picking the player whose
turn it is to post the SB I need to see if they actually post it. If they
do not then I mark them as sitting out and need to ask the following
player. If I run out of players then I cancel the game and go to wait for
players.

If the the small blind is posted then I repeat the procedure for the big
blind and so on and so forth.

I'm not sure if I'm suffering from the syndrome that you described. I
just have a lot of possible things to handle. This was far easier in Lisp
with the continuation passing style, at least far more compact Very Happy.

I'm including my Lisp implementation, nicely sequential. Note how compact
the makeup-blinds code is. With Erlang the state machine gets quite big
and I'm just trying to figure out how to modularize it.

I'm not trying to start a flame war or discuss the merits of Lisp vs.
Erlang. I picked Erlang after implementing a working poker engine in Lisp
and I'm simply trying to go back to FSM from continuations now.

Thanks for your advice, Joel

P.S.

;;; Save game continuation

(defun/cc receive (game)
(let/cc k
;; save continuation
(setf (continuation game) k)
;; TODO: start a timer here
))

(defun/cc ask-for-blind (game amount context)
(let ((posted nil)
(seat nil)
(active (car context))
(small-blind-p (= (small-blind$ game) amount)))
(while (and (not posted) (car active))
(setf seat (pop active))
;; skip people who are waiting
;; for the big blind if small blind
;; is being posted.
(unless (and (waiting-for-bb-p seat)
small-blind-p)
(setf (state seat) 'sitting-out)
(setf (current game) seat)
(send (player seat) 'blind amount)
(let* ((cmd (receive game))
(action (first cmd))
(bet (second cmd))
(inplay$ (inplay$ (player seat))))
(case action
('blind
(when (or (= bet amount)
(= bet inplay$))
(setf (state seat) (if (= bet amount)
'playing
'all-in))
(record-bet game seat bet)
(setf posted t)
(broadcast game 'notify 'blind (seat# seat) bet)))
('fold
(broadcast game 'notify 'fold (seat# seat) 0))
))))
(setf (car context) active)
(if posted seat nil)))

(defun/cc assign-blinds (game)
;; the cons bit is a hack since ask-for-blind pops the list
;; and needs pass the updated list back to us.
(let ((context (cons (copy-list (blind-active-seats game)) t))
(blind (blinds game))
(sb$ (small-blind$ game))
(bb$ (big-blind$ game))
(b nil)
(sb nil)
(bb nil))
(with-slots (small big button) blind
(if (not (or small big))
;; first hand of this game
(progn
(setf b button)
(setf sb (ask-for-blind game sb$ context))
(setf bb (ask-for-blind game bb$ context)))
(progn
;; get active players starting with the seat
;; to the left of the current small blind.
(setf (car context)
(copy-list (blind-active-seats game :start-seat small)))
(setf b small)
(if (bust-p big)
;; big blind is bust
(progn
(setf sb big)
(setf bb (ask-for-blind game bb$ context))
;; special heads-up handling
(unless (second (car context))
(setf sb (pop (car context)))))
;; otherwise
(progn
(setf sb (ask-for-blind game sb$ context))
(setf bb (ask-for-blind game bb$ context))))
)))
;; heads-up play
(when (not (car context))
(setf b sb)) ; heads-up, button = sb
(list b sb bb)
))

;;; We let people join once the blinds have passed them
;;; but they must make up for it by posting the big blind.

(defun/cc make-up-blinds (game active)
(let ((new (active-seats game))
(amount (big-blind$ game)))
(loop for seat in new
unless (member seat active) do
(send (player seat) 'blind amount)
(let* ((cmd (receive game))
(action (first cmd))
(bet (second cmd))
(inplay$ (inplay$ (player seat))))
(case action
('blind
(when (or (= bet amount)
(= bet inplay$))
(setf (state seat) (if (= bet amount)
'playing
'all-in))
(record-bet game seat bet)
(broadcast game 'notify 'blind (seat# seat) bet)))
('wait-for-bb
(setf (state seat) 'waiting-for-bb)
(broadcast game 'notify 'wait-for-bb (seat# seat) 0))
(t
;; time out received
(setf (state seat) 'sitting-out)
(broadcast game 'notify 'sit-out (seat# seat) 0))
)))))





--
http://wagerlabs.com/tech



Post generated using Mail2Forum (http://m2f.sourceforge.net)
Back to top
ulf.wiger at ericsson.com
Posted: Fri Apr 15, 2005 11:25 am Reply with quote
Guest
Well, then. You may write your code the
same way in Erlang. Your dealer process
sends messages (cards) to the players,
and receives requests or cards (if a player
plays a card, it might as well be sent to
the dealer).

Again, with selective receive, you should be
able to translate your lisp program logic into
erlang with fairly little trouble. With gen_fsm,
I'd have to think for much more than the
two minutes I spent browsing your lisp code.

Given the small amount of thinking that went
into the writing of this post, I may have
missed something.


/Uffe

-----Original Message-----
From: Joel Reymont [mailto:joelr1@gmail.com]
Sent: den 15 april 2005 12:41
To: Ulf Wiger (AL/EAB); Erlang Users' List
Subject: Re: Big state machines


> Ulf Wiger (AL/EAB) wrote:
> [...]
>The remedy? Use plain Erlang state machines with
>selective receive. You will still have to think
>about whether you can break up your state machines
>into several smaller ones. The proof is in your
>code. If it simplifies the code - do it. Otherwise,
>don't.

Let me elaborate ...

I'm writing poker game logic for the Texas Hold'em variant.

First I wait for a few seconds to let people join, leave, sit out, come
back. I selectively ignore all other actions. When getting a timeout I
check if I have enough players and transition to collecting blinds.

Here I need to ask players to post a small blind and a big blind. Players
who join in these two states need to make up by posting the big blind and
I process this in a separate state after SB and BB are collected.

So I have small_blind, big_blind and make_up_blinds for states.

Have a separate small_blind state because after picking the player whose
turn it is to post the SB I need to see if they actually post it. If they
do not then I mark them as sitting out and need to ask the following
player. If I run out of players then I cancel the game and go to wait for
players.

If the the small blind is posted then I repeat the procedure for the big
blind and so on and so forth.

I'm not sure if I'm suffering from the syndrome that you described. I
just have a lot of possible things to handle. This was far easier in Lisp
with the continuation passing style, at least far more compact Very Happy.

I'm including my Lisp implementation, nicely sequential. Note how compact
the makeup-blinds code is. With Erlang the state machine gets quite big
and I'm just trying to figure out how to modularize it.

I'm not trying to start a flame war or discuss the merits of Lisp vs.
Erlang. I picked Erlang after implementing a working poker engine in Lisp
and I'm simply trying to go back to FSM from continuations now.

Thanks for your advice, Joel

P.S.

;;; Save game continuation

(defun/cc receive (game)
(let/cc k
;; save continuation
(setf (continuation game) k)
;; TODO: start a timer here
))

(defun/cc ask-for-blind (game amount context)
(let ((posted nil)
(seat nil)
(active (car context))
(small-blind-p (= (small-blind$ game) amount)))
(while (and (not posted) (car active))
(setf seat (pop active))
;; skip people who are waiting
;; for the big blind if small blind
;; is being posted.
(unless (and (waiting-for-bb-p seat)
small-blind-p)
(setf (state seat) 'sitting-out)
(setf (current game) seat)
(send (player seat) 'blind amount)
(let* ((cmd (receive game))
(action (first cmd))
(bet (second cmd))
(inplay$ (inplay$ (player seat))))
(case action
('blind
(when (or (= bet amount)
(= bet inplay$))
(setf (state seat) (if (= bet amount)
'playing
'all-in))
(record-bet game seat bet)
(setf posted t)
(broadcast game 'notify 'blind (seat# seat) bet)))
('fold
(broadcast game 'notify 'fold (seat# seat) 0))
))))
(setf (car context) active)
(if posted seat nil)))

(defun/cc assign-blinds (game)
;; the cons bit is a hack since ask-for-blind pops the list
;; and needs pass the updated list back to us.
(let ((context (cons (copy-list (blind-active-seats game)) t))
(blind (blinds game))
(sb$ (small-blind$ game))
(bb$ (big-blind$ game))
(b nil)
(sb nil)
(bb nil))
(with-slots (small big button) blind
(if (not (or small big))
;; first hand of this game
(progn
(setf b button)
(setf sb (ask-for-blind game sb$ context))
(setf bb (ask-for-blind game bb$ context)))
(progn
;; get active players starting with the seat
;; to the left of the current small blind.
(setf (car context)
(copy-list (blind-active-seats game :start-seat small)))
(setf b small)
(if (bust-p big)
;; big blind is bust
(progn
(setf sb big)
(setf bb (ask-for-blind game bb$ context))
;; special heads-up handling
(unless (second (car context))
(setf sb (pop (car context)))))
;; otherwise
(progn
(setf sb (ask-for-blind game sb$ context))
(setf bb (ask-for-blind game bb$ context))))
)))
;; heads-up play
(when (not (car context))
(setf b sb)) ; heads-up, button = sb
(list b sb bb)
))

;;; We let people join once the blinds have passed them
;;; but they must make up for it by posting the big blind.

(defun/cc make-up-blinds (game active)
(let ((new (active-seats game))
(amount (big-blind$ game)))
(loop for seat in new
unless (member seat active) do
(send (player seat) 'blind amount)
(let* ((cmd (receive game))
(action (first cmd))
(bet (second cmd))
(inplay$ (inplay$ (player seat))))
(case action
('blind
(when (or (= bet amount)
(= bet inplay$))
(setf (state seat) (if (= bet amount)
'playing
'all-in))
(record-bet game seat bet)
(broadcast game 'notify 'blind (seat# seat) bet)))
('wait-for-bb
(setf (state seat) 'waiting-for-bb)
(broadcast game 'notify 'wait-for-bb (seat# seat) 0))
(t
;; time out received
(setf (state seat) 'sitting-out)
(broadcast game 'notify 'sit-out (seat# seat) 0))
)))))





--
http://wagerlabs.com/tech



Post generated using Mail2Forum (http://m2f.sourceforge.net)
Back to top
corrado.santoro
Posted: Fri Apr 15, 2005 1:40 pm Reply with quote
User Joined: 03 Mar 2005 Posts: 54 Location: Italy
Joel Reymont wrote:
> I'm implementing my poker logic as a gen_fsm behavior. I'm finding that
> my FSM is getting a bit unwieldy, though, what with all the tests I have
> to write for different state transitions, etc.
>
> I'm wondering if there's an idiomatic way of splitting big FSMs into
> smaller chunks. Should I move the processing code into different modules
> and leave just invocations in the FSM callback module?
The eXAT agent programming platform that I've written allows agent
behaviours to be programmed by means of hierarchical FSMs, also using
virtual inheritance.

You may take a loot at

http://www.diit.unict.it/users/csanto/exat/

The version that can be downloaded is old, but please contact me for the
new release, if you are interested.

--Corrado

--
======================================================
Eng. Corrado Santoro, Ph.D.

University of Catania - Engineering Faculty
Department of Computer Science and
Telecommunications Engineering
Viale A. Doria, 6 - 95125 CATANIA (ITALY)

Tel: +39 095 7382144 Int. (5) 8035
+39 095 7382380
+39 095 7382365
+39 095 7382364

VoIP: sip:8035@voicegw2.diit.unict.it

Fax: +39 095 7382397

EMail: csanto@diit.unict.it
Personal Home Page:
http://www.diit.unict.it/users/csanto

NUXI Home Page:
http://nuxi.iit.unict.it
======================================================


Post generated using Mail2Forum (http://m2f.sourceforge.net)
Back to top View user's profile Send private message Visit poster's website
valentin at pixie.co.za
Posted: Sat Apr 16, 2005 8:12 am Reply with quote
Guest
If you were to consider a separate FSM for each player, and game as a common
context shared amongst group of player, I would opt to implement a "table"
as a gen_server that routes messages (context of the game) between
players... I see only few states for a player's FSM. Am I missing a plot
completely?

Valentin.


----- Original Message -----
From: "Ulf Wiger (AL/EAB)" <ulf.wiger@ericsson.com>
To: "Joel Reymont" <joelr1@gmail.com>; "Erlang Users' List"
<erlang-questions@erlang.org>
Sent: Friday, April 15, 2005 12:51 PM
Subject: RE: Big state machines



Well, then. You may write your code the
same way in Erlang. Your dealer process
sends messages (cards) to the players,
and receives requests or cards (if a player
plays a card, it might as well be sent to
the dealer).

Again, with selective receive, you should be
able to translate your lisp program logic into
erlang with fairly little trouble. With gen_fsm,
I'd have to think for much more than the
two minutes I spent browsing your lisp code.

Given the small amount of thinking that went
into the writing of this post, I may have
missed something.


/Uffe

-----Original Message-----
From: Joel Reymont [mailto:joelr1@gmail.com]
Sent: den 15 april 2005 12:41
To: Ulf Wiger (AL/EAB); Erlang Users' List
Subject: Re: Big state machines


> Ulf Wiger (AL/EAB) wrote:
> [...]
>The remedy? Use plain Erlang state machines with
>selective receive. You will still have to think
>about whether you can break up your state machines
>into several smaller ones. The proof is in your
>code. If it simplifies the code - do it. Otherwise,
>don't.

Let me elaborate ...

I'm writing poker game logic for the Texas Hold'em variant.

First I wait for a few seconds to let people join, leave, sit out, come
back. I selectively ignore all other actions. When getting a timeout I
check if I have enough players and transition to collecting blinds.

Here I need to ask players to post a small blind and a big blind. Players
who join in these two states need to make up by posting the big blind and
I process this in a separate state after SB and BB are collected.

So I have small_blind, big_blind and make_up_blinds for states.

Have a separate small_blind state because after picking the player whose
turn it is to post the SB I need to see if they actually post it. If they
do not then I mark them as sitting out and need to ask the following
player. If I run out of players then I cancel the game and go to wait for
players.

If the the small blind is posted then I repeat the procedure for the big
blind and so on and so forth.

I'm not sure if I'm suffering from the syndrome that you described. I
just have a lot of possible things to handle. This was far easier in Lisp
with the continuation passing style, at least far more compact Very Happy.

I'm including my Lisp implementation, nicely sequential. Note how compact
the makeup-blinds code is. With Erlang the state machine gets quite big
and I'm just trying to figure out how to modularize it.

I'm not trying to start a flame war or discuss the merits of Lisp vs.
Erlang. I picked Erlang after implementing a working poker engine in Lisp
and I'm simply trying to go back to FSM from continuations now.

Thanks for your advice, Joel

P.S.

;;; Save game continuation

(defun/cc receive (game)
(let/cc k
;; save continuation
(setf (continuation game) k)
;; TODO: start a timer here
))

(defun/cc ask-for-blind (game amount context)
(let ((posted nil)
(seat nil)
(active (car context))
(small-blind-p (= (small-blind$ game) amount)))
(while (and (not posted) (car active))
(setf seat (pop active))
;; skip people who are waiting
;; for the big blind if small blind
;; is being posted.
(unless (and (waiting-for-bb-p seat)
small-blind-p)
(setf (state seat) 'sitting-out)
(setf (current game) seat)
(send (player seat) 'blind amount)
(let* ((cmd (receive game))
(action (first cmd))
(bet (second cmd))
(inplay$ (inplay$ (player seat))))
(case action
('blind
(when (or (= bet amount)
(= bet inplay$))
(setf (state seat) (if (= bet amount)
'playing
'all-in))
(record-bet game seat bet)
(setf posted t)
(broadcast game 'notify 'blind (seat# seat) bet)))
('fold
(broadcast game 'notify 'fold (seat# seat) 0))
))))
(setf (car context) active)
(if posted seat nil)))

(defun/cc assign-blinds (game)
;; the cons bit is a hack since ask-for-blind pops the list
;; and needs pass the updated list back to us.
(let ((context (cons (copy-list (blind-active-seats game)) t))
(blind (blinds game))
(sb$ (small-blind$ game))
(bb$ (big-blind$ game))
(b nil)
(sb nil)
(bb nil))
(with-slots (small big button) blind
(if (not (or small big))
;; first hand of this game
(progn
(setf b button)
(setf sb (ask-for-blind game sb$ context))
(setf bb (ask-for-blind game bb$ context)))
(progn
;; get active players starting with the seat
;; to the left of the current small blind.
(setf (car context)
(copy-list (blind-active-seats game :start-seat small)))
(setf b small)
(if (bust-p big)
;; big blind is bust
(progn
(setf sb big)
(setf bb (ask-for-blind game bb$ context))
;; special heads-up handling
(unless (second (car context))
(setf sb (pop (car context)))))
;; otherwise
(progn
(setf sb (ask-for-blind game sb$ context))
(setf bb (ask-for-blind game bb$ context))))
)))
;; heads-up play
(when (not (car context))
(setf b sb)) ; heads-up, button = sb
(list b sb bb)
))

;;; We let people join once the blinds have passed them
;;; but they must make up for it by posting the big blind.

(defun/cc make-up-blinds (game active)
(let ((new (active-seats game))
(amount (big-blind$ game)))
(loop for seat in new
unless (member seat active) do
(send (player seat) 'blind amount)
(let* ((cmd (receive game))
(action (first cmd))
(bet (second cmd))
(inplay$ (inplay$ (player seat))))
(case action
('blind
(when (or (= bet amount)
(= bet inplay$))
(setf (state seat) (if (= bet amount)
'playing
'all-in))
(record-bet game seat bet)
(broadcast game 'notify 'blind (seat# seat) bet)))
('wait-for-bb
(setf (state seat) 'waiting-for-bb)
(broadcast game 'notify 'wait-for-bb (seat# seat) 0))
(t
;; time out received
(setf (state seat) 'sitting-out)
(broadcast game 'notify 'sit-out (seat# seat) 0))
)))))





--
http://wagerlabs.com/tech



Post generated using Mail2Forum (http://m2f.sourceforge.net)
Back to top
joelr1 at gmail.com
Posted: Mon Apr 18, 2005 10:25 am Reply with quote
Guest
Folks,

A big thanks to all who replied. I had the insight over the weekend
that as Ulf said the code can be rewritten with selective receive. I
decided to stick with gen_fsm, though. I
Back to top
vances at motivity.ca
Posted: Mon Apr 18, 2005 3:16 pm Reply with quote
Guest
On Mon, Apr 18, 2005 at 12:47:33PM +0300, joel reymont wrote:
}
} A big thanks to all who replied. I had the insight over the weekend
} that as Ulf said the code can be rewritten with selective receive. I
} decided to stick with gen_fsm, though. I
Back to top
vances at motivity.ca
Posted: Mon Apr 18, 2005 3:21 pm Reply with quote
Guest
On Mon, Apr 18, 2005 at 03:35:07PM -0400, Vance Shipley wrote:
} ... . I've often wondered about building a new behaviour to handle
} selective receive but have yet to investigate it.


Of course having just said that I realize that this is what Ulf has
given us. The difference is that while his goal was to make things
map closer to plain erlang my concept was to make things map closer
to plain SDL.

-Vance



Post generated using Mail2Forum (http://m2f.sourceforge.net)
Back to top
ulf.wiger at ericsson.com
Posted: Mon Apr 18, 2005 8:32 pm Reply with quote
Guest
I have another version, as a matter of fact, which is much
closer to gen_fsm. It solves the dreaded complexity explosion
problem, but the programmer may still have to resort to e.g.
continuations to handle out-of-order messages (since it uses
FIFO semantics.) The idea was to find a way to hack a callback-
oriented event-handling system in order to keep complexity at
bay.

The code was written as part of an extended POTS example,
the result of which I will try to post somewhere someday.
My conclusion was that most programmers have not been
trained to consider the awful complexity that results
from botching the design of your FSM, and many teachers
of CS seem not to have considered it either, even though
they don't need to think long to realise the dangers.
Among those who have considered it, some search for
a solution that maintains the liveliness guarantees
required in hard real-time, but which are not needed
in the soft real-time programming where Erlang is used.
Most FSM frameworks are designed with hard real-time in
mind.

It's not a behaviour, but I believe that gen_fsm could
perhaps be extended to hold a "receive vector" that
modifies the normal FIFO semantics.

To start with, here's an example of it's use. A snippet
from a POTS control program, similar to the one in the
Erlang book:

offhook(?lim, #s{state = idle} = S) ->
Ref = lim_asynch:start_tone(dial),
{ok, S#s{state = {{await_tone_start,dial},
getting_first_digit}},
#recv{lim = Ref, _ = false}};


%% The semantics of the callback being:
%% - name of callback function is the signal ('offhook')
%% - return value is either {ok, NewState} or
%% {ok, NewState, ReceiveVector} - in this case,
%% receive message tagged as 'lim', where the 2nd element
%% in the message is Ref; buffer all other messages.

Here's the main event loop module:

-module(asynch_main).

-export([event_loop/2,
event_loop/3]).

%% simple event loop with FIFO semantics
event_loop(M, S) ->
receive
{From, Event} ->
dispatch(From, Event, M, S);
{From, Ref, Event} ->
dispatch(From, Event, M, S);
Other ->
io:format("event_loop received unknown msg: ~p~n", [Other]),
exit({unknown_msg, Other})
end.


event_loop(M, S, Recv) ->
%% Recv is a tuple, where each element represents a filter.
%% From is used to locate the right filter, and the value of
%% the filter in that position is interpreted as follows:
%% false : ignore (buffer) message
%% [] : consume message
%% Value : consume iff Ref == Value
receive
{From, Event} when element(From, Recv) == [] ->
dispatch(From, Event, M, S);
{From, Ref, Event} when element(From, Recv) == Ref ->
dispatch(From, Event, M, S);
{From, Ref, Event} when element(From, Recv) == [] ->
dispatch(From, Event, M, S)
end.


dispatch(From, Event, M, S) when atom(Event) ->
handle(M:Event(From, S), M);
dispatch(From, {Event, Arg}, M, S) ->
handle(M:Event(From, Arg, S), M).

handle({ok, NewState}, M) ->
event_loop(M, NewState);
handle({ok, NewState, Recv}, M) ->
event_loop(M, NewState, Recv).

Aside:
After several read-throughs, I finally grasped the fact that
there is something called "deferrable event" in UML (although
the UML tool provided by Rational -- RoseRT -- doesn't support
it.) Sadly, with UML and SDL, the default behaviour is to throw
away messages that arrive in the wrong state, and have not been
marked deferrable in that state. This makes it difficult to
maintain large programs, unless the tool in question supports
another default (everything deferrable unless otherwise specified.)

/Uffe

-----Original Message-----
From: owner-erlang-questions@erlang.org
[mailto:owner-erlang-questions@erlang.org]On Behalf Of Vance Shipley
Sent: den 18 april 2005 21:50
To: joel reymont
Cc: erlang-questions@erlang.org
Subject: Re: Big state machines


On Mon, Apr 18, 2005 at 03:35:07PM -0400, Vance Shipley wrote:
} ... . I've often wondered about building a new behaviour to handle
} selective receive but have yet to investigate it.


Of course having just said that I realize that this is what Ulf has
given us. The difference is that while his goal was to make things
map closer to plain erlang my concept was to make things map closer
to plain SDL.

-Vance



Post generated using Mail2Forum (http://m2f.sourceforge.net)
Back to top
uffe
Posted: Mon Apr 18, 2005 9:22 pm Reply with quote
User Joined: 02 Mar 2005 Posts: 365 Location: Sweden
Den 2005-04-18 22:03:59 skrev Ulf Wiger (AL/EAB) <ulf.wiger@ericsson.com>:

>
> I have another version, as a matter of fact, which is much
> closer to gen_fsm. It solves the dreaded complexity explosion
> problem, but the programmer may still have to resort to e.g.
> continuations to handle out-of-order messages (since it uses
> FIFO semantics.)

Bah! Forget that nonsense. The continuations are not needed
due to FIFO semantics, but due to the non-blocking "go-to-like"
semantics.

/Uffe


Post generated using Mail2Forum (http://m2f.sourceforge.net)
Back to top View user's profile Send private message Visit poster's website
vances at motivity.ca
Posted: Tue Apr 19, 2005 1:14 am Reply with quote
Guest
On Mon, Apr 18, 2005 at 10:03:59PM +0200, Ulf Wiger (AL/EAB) wrote:
}
} .... Sadly, with UML and SDL, the default behaviour is to throw
} away messages that arrive in the wrong state, and have not been
} marked deferrable in that state. This makes it difficult to
} maintain large programs, unless the tool in question supports
} another default (everything deferrable unless otherwise specified.)

I think it has to be this way. You are always going to get late
arrivals or other instances of messages you are not interested in.
If it weren't for these semantics you'd need to account for every
message the FSM handles in every state. You'd also run the constant
risk of overflowing the mailbox. Saving is the exceptional condition
done when you need to wait for a particular set of messages (e.g. ACK)
before proceeding.

On the other hand what I would like would require you to explicitly
throw away unwanted messages. Ideally what I would like is just a
gen_fsm which had the sematics that if an event handler didn't match
the first event in the queue it kept trying until it had tried all
messages and then kept trying for new messages. This way you would
write normal states as:

idle(offhook, StateData) ->
...
{next_state, dialtone};
idle(Event, StateData) ->
{next_state, idle}.

When you want a state which saves signals you leave out the catchall
clause.

This may be no where near the pure erlang which you crave however it
would make it easier for me to translate SDL into gen_fsm. Maybe this
isn't what I really want and I'm just too used to thinking in gen_fsm.
What I am doing is thinking in SDL though so the closer the semantic
leap is the better.

-Vance



Post generated using Mail2Forum (http://m2f.sourceforge.net)
Back to top
uffe
Posted: Tue Apr 19, 2005 5:25 am Reply with quote
User Joined: 02 Mar 2005 Posts: 365 Location: Sweden
Den 2005-04-19 07:44:24 skrev Vance Shipley <vances@motivity.ca>:

> On Mon, Apr 18, 2005 at 10:03:59PM +0200, Ulf Wiger (AL/EAB) wrote:
> }
> } .... Sadly, with UML and SDL, the default behaviour is to throw
> } away messages that arrive in the wrong state, and have not been
> } marked deferrable in that state. This makes it difficult to
> } maintain large programs, unless the tool in question supports
> } another default (everything deferrable unless otherwise specified.)
>
> I think it has to be this way. You are always going to get late
> arrivals or other instances of messages you are not interested in.
> If it weren't for these semantics you'd need to account for every
> message the FSM handles in every state. You'd also run the constant
> risk of overflowing the mailbox. Saving is the exceptional condition
> done when you need to wait for a particular set of messages (e.g. ACK)
> before proceeding.

I may read your message wrong, but the problem with the UML approach
is that you cannot easily say, for a given state: "match these
expected messages, but implicitly refer any other message". This
is the semantics needed for all transient states, since a transient
state may _never_ discard a message it doesn't recognize.

In Erlang, you don't have to worry much about transient states,
because they can be hidden behind a function call. The classic
example is gen_server:call/3. It's not too surprising that UML
specifies a special SynchronousCall method, because given the
message passing semantics of UML, it's nearly impossible to
model a generic SynchronousCall. But for all transient states
that do not fit the SynchronousCall pattern, you're in deep
trouble (granted -- I think most transient states _do_ fit the
SynchronousCall pattern.)


> On the other hand what I would like would require you to explicitly
> throw away unwanted messages. Ideally what I would like is just a
> gen_fsm which had the sematics that if an event handler didn't match
> the first event in the queue it kept trying until it had tried all
> messages and then kept trying for new messages. This way you would
> write normal states as:
>
> idle(offhook, StateData) ->
> ...
> {next_state, dialtone};
> idle(Event, StateData) ->
> {next_state, idle}.
>
> When you want a state which saves signals you leave out the catchall
> clause.

Then the dispatcher would have to trigger on function_clause as
meaning "save this message". Would it not be better to have an
explicit "defer" callback? This would essentially mimic the
semantics of RoseRT - since there is no unsend() function in
Erlang, the dispatcher would have to manage a 'defer' queue
in memory. Unless you can make it transparent, there would
also have to be a recall() function (a la RoseRT), and then
you really have a mess on your hands. It would then be better
for the dispatcher to keep a FIFO queue in memory, and always
run all messages through it. unsend() would then be equivalent
to undo() (that is, keep the old Queue variable around, and
revert to it if necessary) -- but only as long as one hasn't
pulled another message from the Erlang message queue (which
is an irreversible action).

/Uffe


Post generated using Mail2Forum (http://m2f.sourceforge.net)
Back to top View user's profile Send private message Visit poster's website
vances at motivity.ca
Posted: Tue Apr 19, 2005 9:47 am Reply with quote
Guest
On Tue, Apr 19, 2005 at 06:54:18AM +0200, Ulf Wiger wrote:
}
} I may read your message wrong, but the problem with the UML approach
} is that you cannot easily say, for a given state: "match these
} expected messages, but implicitly refer any other message". This
} is the semantics needed for all transient states, since a transient
} state may _never_ discard a message it doesn't recognize.

I don't know UML, and maybe never will as you've told us it isn't
very helpful in Erlang. :)

In SDL an unspecified signal is implicitly handled by consuming it
and transitioning back to the current state. My point was that this
default behaviour is important to have.

SDL graphical representation:
___
(_s_)
|
+--+--+
__|_ __|_
>_a_| >_b_|
_|_ _|_
(_x_) (_y_)

SDL textual representation:

state s;
input a;
nextstate x;
input b;
nextstate y;
endstate s;

Plain erlang implementation:

s(S) ->
receive
a ->
x(S);
b ->
y(S);
_ ->
s(S)
end.

SDL does provide the 'save' construct which specifies that the
referenced signal should be left in the input queue. For your
transient state you would probably want to use the asterisk save:
___
(_s_)
|
+-----+------+
__|_ __|_ __|_
>_a_| >_b_| /_*_/
_|_ _|_
(_x_) (_y_)

state s;
input a;
nextstate x;
input b;
nextstate y;
save *;
endstate s;

s(S) ->
receive
a ->
x(S);
b ->
y(S)
end.

You can also specify the signals you want to save and in the absence
of an asterisk input other signals will be consumed:
___
(_s_)
|
+-----+------+-----+
__|_ __|_ __|_ __|_
>_a_| >_b_| /_c_/ /_d_/
_|_ _|_
(_x_) (_y_)

state s;
input a;
nextstate x;
input b;
nextstate y;
save c;
save d;
endstate s;

s(S) ->
receive
a ->
x(S);
b ->
y(S);
X when X /= c, X /= d ->
s(S)
end.


} In Erlang, you don't have to worry much about transient states,
} because they can be hidden behind a function call. The classic

I sometimes need to handle a save construct in the context of external
signals (protocols) and gen_fsm doesn't provide the syntax, although
erlang does.

So the short answer I guess is that should I really need to do this
I should implement my own system process and abandon gen_fsm. It's
probably a better idea than the ugliness which results from further
bastardizing Erlang in the pursuit of retaining gen_fsm semantics.

-Vance


Post generated using Mail2Forum (http://m2f.sourceforge.net)
Back to top
Thomas Lindgren
Posted: Tue Apr 19, 2005 9:59 am Reply with quote
User Joined: 09 Mar 2005 Posts: 284
--- "Ulf Wiger (AL/EAB)" <ulf.wiger@ericsson.com>
wrote:

>
> I have another version, as a matter of fact, which
> is much
> closer to gen_fsm. It solves the dreaded complexity
> explosion
> problem, /.../

Interesting. Do you have any opinions on Harel's
statecharts? (A precursor of UML, I believe, though I
haven't studied UML very deeply.)

Best,
Thomas




__________________________________
Do you Yahoo!?
Plan great trips with Yahoo! Travel: Now over 17,000 guides!
http://travel.yahoo.com/p-travelguide


Post generated using Mail2Forum (http://m2f.sourceforge.net)
Back to top View user's profile Send private message

Display posts from previous:  

All times are GMT
View next topic
View previous topic
Page 1 of 2
Goto page 1, 2  Next
Erlang Forum - Trap Exit Forum Index  ~  Erlang questions mailing list
This forum is locked: you cannot post, reply to, or edit topics.

Jump to:  

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You cannot download files in this forum
Hosted by Erlang Solutions    |    Powered by phpBB and NoseBleed 1.14