Subject: Syntax of transitions

From: "Clive D.W. Feather" <[email-masked]>
Date: Mon, 8 Jan 2007 16:29:00 +0000

The grammar suggests four different syntaxes for transitions:

(1) state1, state2 : message1, message2 -> state3 : action1

(2) message1, message2 : state1, state2 -> state3 : action1

(3) (state1, state2 : message1, message2) -> state3 : action1

(4) message1 : state1 -> state3 : action1; state2 -> state4 : action2;

and this also suggests a fifth:

(5) state1 : message1 -> state3 : action1; message2 -> state4 : action2;

Firstly, if you want to allow states and messages in either order, I
suggest that you should have different delimiters. For example:

    state + message       + suggests "adding this message"
    message @ state       @ suggests "when at this state"

Secondly, is there any reason to forbid multiple actions? It won't make
sense for all uses, but it will for some.

Thirdly, you can then use parentheses to provide grouping, rather than
syntax (4), which is rather hard to parse (the scope of message1 ends at
the next transition with a colon before the arrow). Something like this:

    message1 @ (state1 -> state3 : action1; state2 -> state4 : action2;);
    state1 + (message1 -> state3 : action1; message2 -> state4 : action2;);

These two being equivalent to:

    message1 @ state1 -> state3 : action1;
    message1 @ state2 -> state4 : action2;
and
    state1 + message1 -> state3 : action1;
    state1 + message2 -> state4 : action2;

(Note: the semicolon before the ")" simplifies the grammar, but it would be
easy enough to make it optional.)

Common trailing actions could be put outside the parentheses:

    message1 @ (state1 -> state3 : action1; state2 -> state4;) : action2;

would be equivalent to:

    message1 @ state1 -> state3 : action1, action2;
    message1 @ state2 -> state4 : action2;

So the overall grammar for this would be:

    transition = m-transition / s-transition
    m-transition = message-list "@" body-with-s
    s-transition = state-list   "+" body-with-m
    body-with-s = simple-body-with-s / grouped-body-with-s
    body-with-m = simple-body-with-m / grouped-body-with-m
    grouped-body-with-s = "(" 1*(simple-body-with-s ";") ")" [":" action-list]
    grouped-body-with-m = "(" 1*(simple-body-with-m ";") ")" [":" action-list]
    simple-body-with-s = state-list   "->" state [":" action-list]
    simple-body-with-m = message-list "->" state [":" action-list]

(This grammar needs to have comments and white space added to bring it into
line with the base grammar.)

If people like this, I'm happy to write wording to fit it into the
document.

-- 
Clive D.W. Feather  | Work:  <[email-masked]>   | Tel:    +44 20 8495 6138
Internet Expert     | Home:  <[email-masked]>  | Fax:    +44 870 051 9937
Demon Internet      | WWW: http://www.davros.org | Mobile: +44 7973 377646
THUS plc            |                            |

_______________________________________________
Cosmogol mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cosmogol

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Tue, 9 Jan 2007 23:10:42 +0100

On Mon, Jan 08, 2007 at 04:29:00PM +0000,
 Clive D.W. Feather <[email-masked]> wrote 
 a message of 78 lines which said:

> Secondly, is there any reason to forbid multiple actions?

No, no good reasons, and protocols like SIP or SCTP really need
multiple actions.

---

From: Frank Ellermann <[email-masked]>
Date: Wed, 10 Jan 2007 23:36:01 +0100

Stephane Bortzmeyer wrote:

>> is there any reason to forbid multiple actions?

> No, no good reasons, and protocols like SIP or SCTP
> really need multiple actions.

A good reason would be KISS, you can split sequential
actions using intermediary states, and you want the
states written into lines with 69 characters.

But if the actions are simultaneously, or their order
is irrelevant it's less clear.  If some of the actions
(almost) always occur together you could get away with
named sets of states.

Maybe introducing named sets of either states, or
messsages, or actions makes sense.  With that you'd
get "state or named set of states", "message or named
set of messages", and "action or named set of actions",
and a general concept of named sets.  Is that better ?

Frank

---

From: "Clive D.W. Feather" <[email-masked]>
Date: Thu, 11 Jan 2007 14:50:57 +0000

Frank Ellermann said:
> actions using intermediary states,

You *can*, but in some cases it will obscure matters to no good end.
I'd rather have an "only one action" flag for interpreters.

> and you want the

Non-sequitor.

> (almost) always occur together you could get away with

I don't follow this either.

> and a general concept of named sets.  Is that better ?

Named sets is an interesting extension:

    SET problems = error, warning, delay ;

but it's not really relevant to the question. I want to be able to write:

    Signal1 @ IDLE -> BUSY : "Send 101", connectSubscriber ;

without having to invent a set just to contain these two actions.

---

From: Frank Ellermann <[email-masked]>
Date: Thu, 11 Jan 2007 21:00:54 +0100

Clive D.W. Feather wrote:

>> you want the states written into lines with 69 characters.

> Non-sequitor.

The RFC line length is 72 minus 3 for the left margin.  It's
difficult to squeeze formal languages into these limits, and
if you fold longer lines the result can be hard to read.

But we want folks to read and understand state machines in
RFCs - if they'd be forced to extract the source and feed it
into some presentation tool it's a lost battle because no
casual reader or reviewer will do this.

Maybe authors could write something like...

messageX1,
messageABC @    state1,
                stateC-3,
                state46 ->      state47 :       action101,
                                                actionconnect;

...if messageX1 or messageABC in one the three listed states
cause action101 and actionconnect with next state state47.

But they could as well identify the corresponding action(s)
with a single name "do101", and mention the details in a
comment of the declaration:

actions:        foo,            # do the foo thing
                bar,            # do the bar stuff
                do101;          # signal 101 and connect

The actions in a state machine can be mere identifiers, what
it really means would be anyway in prose (comment or similar).

The states, the messages, and the next states are the core of
a state machine, the "actions" only connect this abstraction
with something real in a protocol.

> I want to be able to write:

> without having to invent a set just to contain these two actions.

Okay, for readability reasons I'd want to be able to define
and use a "do101" set of actions.  If it's in some "artwork"
(69 characters) of an RFC that could be better.

So I guess we need comma-separated lists of messages, actions,
and states (excl. next states after "->").

And maybe we need named sets as shorthands for such lists.  But
above all we need KISS, not a convoluted syntax with tons of
different ways to express the same idea.  It should be intuitive,
readers must get the point without ever looking into the manual.

Frank

---

From: "Clive D.W. Feather" <[email-masked]>
Date: Fri, 12 Jan 2007 07:38:17 +0000

> if you fold longer lines the result can be hard to read.

That depends. I agree that line lengths should be taken into account.

> casual reader or reviewer will do this.

Agreed.

>                 state46 ->      state47 :       action101,

or

messageX1, messageABC @ state1, stateC-3, state46
  -> state47 : action101, actionconnect ;

>                 do101;          # signal 101 and connect

No. Firstly because there may be other places where you want to do
actionconnect but not action101. Secondly because the comment will be in
the wrong place - it will be at the declaration and not at the place where
the action actually happens. And thirdly because it clutters up the
namespace and so harms the user's understanding.

> (69 characters) of an RFC that could be better.

I'm very happy to allow you to define sets that can be used in these
contexts, provided that I'm not forced to use them.

> And maybe we need named sets as shorthands for such lists.

I think we're in agreement then: sets available, lists available, state
machine author chooses what seems best in each situation.

> But

Agreed.

At present, the proposals that involve more than one way of doing things
are:

(1) "message @ state -> state" versus "state + message -> state"

(2) Grouping: "message @ (state -> state, state -> state)" versus expanding
it out.

(3) Use of lists versus sets.

All of these, I think, offer more benefit than risk of confusion.

---

From: Frank Ellermann <[email-masked]>
Date: Sun, 21 Jan 2007 06:13:17 +0100

>   -> state47 : action101, actionconnect ;

Yes, but that's starting to be less readable if you're looking
for "what can happen in a given state", or "what's the effect
of a given message in any state".

> I'm very happy to allow you to define sets that can be used
> in these contexts, provided that I'm not forced to use them.

LOL.  My main example is a CharmapML UTF-8 "validity" state
machine, and for that purpose you might change your mind, the
"messages" there are 256 octets.

We could also try to encode the I-D tracker state machine as
an example / exercise.

 
> At present, the proposals that involve more than one way of doing
> things are:
 
> (1) "message @ state -> state" versus "state + message -> state"

In this thread I first tried to use a variant of states + messages,
but then I saw a messages @ states in one of your articles, and 
immediately decided that this is clearer.

Normally you have a directed graph with states as nodes, and some
messages on the edges connecting nodes, for that it's more natural
to use states + messages.  But of course messages @ states is
equivalent, and the "@" is unambiguous, while a "x + y" is often
(excl. floating point numbers) the same as "y + x", but not here.

Therefore I'd opt to eliminate states + messages in favour of "@".

> (2) Grouping: "message @ (state -> state, state -> state)" versus
> expanding it out.

If you pick single message @ states, not a list or set of messages,
then you could sort the expanded version by the messages.  That has
a similar effect, and it's clearer than grouping.  

Therefore I'd opt to eliminate this grouping.  There won't be many
opportunities where that's still readable in RFCs, and if it's to
some degree readable, than an expanded version is also readable.

> (3) Use of lists versus sets.

Maybe we could make lists and sets more obvious with parentheses:

Instead of   M1, M2, M3 @ Sa, Sb -> Sc : AI, AII ;
it would be  (M1, M2, M3) @ (Sa, Sb) -> Sc : (AI, AII) ; 

For named sets SoM, SoS, and SoA we could demand that they can
be only used within a list, e.g.

(M1, M2, SoM) @ (SoS) -> Sc : (AI, SoA)

In other words anything outside of parentheses must be a single
message, state, or action, it can't be a list or named set.  

Frank