ietf
[Top] [All Lists]

Specifying a state machine: ASCII-based languages

2006-06-28 03:55:49
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
Ietf(_at_)ietf(_dot_)org
https://www1.ietf.org/mailman/listinfo/ietf

<Prev in Thread] Current Thread [Next in Thread>