Big state machines

[Ulf Wiger (AL/EAB)]

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@REDACTED
[mailto:owner-erlang-questions@REDACTED]On Behalf Of Vance Shipley
Sent: den 18 april 2005 21:50
To: joel reymont
Cc: erlang-questions@REDACTED
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