Specifying a state machine: ASCII-based languages
Stephane Bortzmeyer <bortzmeyer@nic.fr> Wed, 28 June 2006 10:55 UTC
Received: from [127.0.0.1] (helo=stiedprmman1.va.neustar.com) by megatron.ietf.org with esmtp (Exim 4.43) id 1FvXhS-0001xz-2m; Wed, 28 Jun 2006 06:55:14 -0400
Received: from [10.91.34.44] (helo=ietf-mx.ietf.org) by megatron.ietf.org with esmtp (Exim 4.43) id 1FvXhQ-0001xu-DE for ietf@ietf.org; Wed, 28 Jun 2006 06:55:12 -0400
Received: from mx2.nic.fr ([192.134.4.11]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1FvXhM-0003TH-St for ietf@ietf.org; Wed, 28 Jun 2006 06:55:12 -0400
Received: from localhost (localhost.localdomain [127.0.0.1]) by mx2.nic.fr (Postfix) with ESMTP id 42F6126C0CB for <ietf@ietf.org>; Wed, 28 Jun 2006 12:55:08 +0200 (CEST)
Received: from relay2.nic.fr (relay2.nic.fr [192.134.4.163]) by mx2.nic.fr (Postfix) with ESMTP id CAD0426C081 for <ietf@ietf.org>; Wed, 28 Jun 2006 12:55:05 +0200 (CEST)
Received: from batilda.nic.fr (batilda.nic.fr [192.134.4.69]) by relay2.nic.fr (Postfix) with ESMTP id C874658EA40 for <ietf@ietf.org>; Wed, 28 Jun 2006 12:55:05 +0200 (CEST)
Received: by batilda.nic.fr (Postfix, from userid 1000) id 6A5CF16A9D7; Wed, 28 Jun 2006 12:55:05 +0200 (CEST)
Date: Wed, 28 Jun 2006 12:55:04 +0200
From: Stephane Bortzmeyer <bortzmeyer@nic.fr>
To: ietf@ietf.org
Message-ID: <20060628105504.GA16434@nic.fr>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
X-Operating-System: Debian GNU/Linux 3.1
X-Kernel: Linux 2.6.8-2-686 i686
Organization: NIC France
X-URL: http://www.nic.fr/
User-Agent: Mutt/1.5.9i
X-Virus-Scanned: by amavisd-new at mx2.nic.fr
X-Spam-Score: 0.0 (/)
X-Scan-Signature: 92df29fa99cf13e554b84c8374345c17
Subject: Specifying a state machine: ASCII-based languages
X-BeenThere: ietf@ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: IETF-Discussion <ietf.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/ietf>, <mailto:ietf-request@ietf.org?subject=unsubscribe>
List-Post: <mailto:ietf@ietf.org>
List-Help: <mailto:ietf-request@ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/ietf>, <mailto:ietf-request@ietf.org?subject=subscribe>
Errors-To: ietf-bounces@ietf.org
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@ietf.org https://www1.ietf.org/mailman/listinfo/ietf
- Specifying a state machine: ASCII-based languages Stephane Bortzmeyer
- Tables in specifications, and looking back (was: … Spencer Dawkins
- Re: Specifying a state machine: ASCII-based langu… Henning Schulzrinne
- Re: Tables in specifications, and looking back Scott W Brim
- Re: Tables in specifications, and looking back Spencer Dawkins
- Re: Specifying a state machine: ASCII-based langu… Stephane Bortzmeyer
- Re: Specifying a state machine: ASCII-based langu… Stewart Bryant
- Re: Specifying a state machine: ASCII-based langu… Frank Ellermann
- Re: Specifying a state machine: ASCII-based langu… Stephane Bortzmeyer
- Re: Specifying a state machine: ASCII-based langu… Stewart Bryant