Subject: Specifying a state machine: ASCII-based languages

From: Stephane Bortzmeyer <[email-masked]>
Date: Wed, 28 Jun 2006 12:55:04 +0200

There have been a lot of talk here recently about the "need" to allow
something more than US-ASCII (and some people require even more than
raw text) in the RFCs.

A common "use case" is the need to specify state machines. This is
often done by a drawing (sometimes in ASCII-art or may be in
Unicode-art in the future). I want to argue that it is not the only
way and not even the best way and to suggest that ASCII-based
languages are better.

Drawings (wether in ASCII-art, in Unicode-art, in SVG, in GIF or
whatever) are:

* impossible to analyze automatically (for instance to check if they
  are deterministic),
* not readable if the state machine is large.

Informal natural language text is not perfect either:

* impossible to analyze automatically (for instance to check if they
  are complete).

Tables are a possible solution (if the machine is finite). But most
people find them too low-level.

The best solution, IMHO, seems to be formal languages. There are
several candidates (I'm confident that the readers of this list will
suggest many others but I limited myself to languages implemented in
free software, list compiled with the help of Phil Regnauld and
Olivier Ricou):

* Graphviz (http://www.graphviz.org/). See an example for TCP state
machine at
http://www.linux.com/article.pl?sid=05/11/08/2018216. Graphviz is more
presentation-oriented. There is no way to separate the specification
of the state machine from its presentation (colors, fonts, etc). I
know no tool to analyze Graphviz files for state machine check (of
course, because Graphviz is used for much more than state machines).

If people want the nice diagrams of Graphviz, do note that many other
tools can produce Graphviz files from specifications. Should one of
these tools used in an RFC, it would be easy to generate a pretty
(non-normative) picture through Graphviz.

* State Machine Compiler, SMC (http://smc.sourceforge.net/). As its
name suggests, its main aim is to generate executable code from the
state machine description. But it can be used, it seems so, for pure
specification. A nice exemple is a telephone at
http://smc.sourceforge.net/TelephoneSrc.htm.

(The FAQ has an excellent entry "Why write state machines in text and
then compile them? Why not create a GUI to draw state machines?" which
is quite relevant here.)

* Ragel (http://www.cs.queensu.ca/home/thurston/ragel/). Quite close
from SMC.

* FSMLang (http://fsmlang.sourceforge.net/). Same concept again.

* eXtensible Abstract State Machines, xASM (http://www.xasm.org/). I
must confess that this one is less clear in my mind.

* SDL (http://www.sdl-forum.org/). It is further from our aim, I
mention it for completeness.

Therefore, as a conclusion, I would like people to notice that
specifying state machines may not always involve a picture.

Unfortunately, there is no clear winner among these applications and
some of them are not ideal for specification (Ragel is "sold" more as
a replacement for lex than as a specification tool.)

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

---

From: "Spencer Dawkins" <[email-masked]>
Date: Wed, 28 Jun 2006 07:16:10 -0500

On one minor note...

> people find them too low-level.

I have just returned from about three days of fairly intense conversations 
about one of our current BOF topics, that

- would have been a lot easier to have, if the use cases and concepts drafts 
had been organized using tables, and

- would be a lot easier to report back to the BOF community, if I could 
conveniently use tables to organize the material I want to present.

Of course, some of our specifications do contain tables, but they aren't as 
useful in our specifications as in other environments, because of things 
like a limited number of columns.

I was keeper of the tables that went into 
ftp://ftp.rfc-editor.org/in-notes/rfc2757.txt as Section 5, which I thought 
was about as good a presentation as we could do in an ID/RFC, and I remember 
that the tabular format was used extensively during early discussions, 
before we even came to IETF to do this work (who still living remembers 
"Mobile Network Computing Reference Specification"/MNCRS?)

This specification was a very early report on some of the topics that were 
presented in http://www.ietf.org/rfc/rfc3150.txt Section 3, 
http://www.ietf.org/rfc/rfc3155.txt Section 3,

http://www.ietf.org/rfc/rfc3449.txt Section 7 actually did use a tabular 
presentation, and I think it's reasonably good, given the current 
environment.

http://www.ietf.org/rfc/rfc3481.txt Section 4.10 also used a tabular 
presentation that would have been clearer if we'd had more columns to work 
with (note that whether the recommendation is for sender, receiver, or both 
is "folded" into the text comment column, but would have been clearer in its 
own column - but we had the page width issue).

(I note that several of the PILC specifications contained equations of 
approximately the complexity we've been discussing, which reminds me that 
the current toolset was usable for our needs there, however much we might 
benefit from better equation support).

... and, having looked back, I wonder if it would be worth adding a EDU Team 
tutorial on "ways we've done things in RFCs that have worked well". A fair 
amount of discussion in this and related threads has reflected (IMO) a split 
between people who have learned "what not to do" in IDs/RFCs, so don't feel 
the constraints, and people who don't have that experience, so who do feel 
the constraints of the same toolset.

If there is little/no energy or determination to do much about the current 
toolset, it might be more productive to help find usable paths than to 
criticize wandering through minefields. Entertaining as watching people 
wander through minefields might be, it does become monotonous.

Thanks,

Spencer

---

From: Henning Schulzrinne <[email-masked]>
Date: Wed, 28 Jun 2006 10:04:54 -0400

Having a more formal description of state machines is a natural next  
step from having, say, a good syntax description in ABNF.  
Unfortunately, unlike ABNF, none of these (except SDL) have a long- 
term stable reference. If we worry about PDF not being around for  
future RFC readers, I am a bit more worried about the authors of a  
SourceForge volunteer project finding other things to do.

Thus, I think the first step would have to be to define a (subset) of  
a suitable language as an IETF-stable document, presumably after a  
few people try out various basic designs.

---

From: Scott W Brim <[email-masked]>
Date: Fri, 30 Jun 2006 09:16:40 -0400

On 06/28/2006 08:16 AM, Spencer Dawkins allegedly wrote:
> I have just returned from about three days of fairly intense
> conversations about one of our current BOF topics, that
> 
> - would have been a lot easier to have, if the use cases and concepts
> drafts had been organized using tables, and
> 

http://table.sourceforge.net/

---

From: "Spencer Dawkins" <[email-masked]>
Date: Fri, 30 Jun 2006 09:55:32 -0500

Hi, Scott,

> http://table.sourceforge.net/

My real problem is fitting my table into 72 columns of courier font in a 
readable way :-(

But thanks for the pointer, of course!

Spencer