views:

327

answers:

6

I am just curious if there is a programming language which has state machines (similar to boost::statechart) as primary language construct.

Analogies - c# has delegates where java uses the observer pattern and C has callbacks. Perl and python have built-in hashes while C++ and java needs a library.

Update:

This should be general programming language in the sense of C++, C#, Java, Lisp ...

I mean "mature" state machines with all bells and whistles on the level of Harel formalism or UML state diagrams or boost::statechart.

+2  A: 

I have just found one: AsmL (Abstract State Machine Language).
Here is the page with more info on it at CodePlex.

Interesting enough, it is developed by Microsoft.

Dmytrii Nagirniak
This is probably not what the OP is looking for. He was asking about FSMs not ASMs. ASMs are a completely different beast, they are a formal specification mechanism for proving theorems about programs. And, BTW, Microsoft employs several of the leading scientists in program verification, including Tony Hoare. (Which is not surprising considering that one bug in Windows could basically bring down the world economy.) So, it's not actually that surprising that this comes out of Microsoft. Also note that this is Microsoft Research, not Microsoft Corp, which is a completely different animal.
Jörg W Mittag
A: 

BSDL and VHDL are some.

wallyk
+2  A: 

There's a new W3C XML-based state machine language called SCXML, based on David Harel's StateChart formalism (which supports hierarchical and parallel state machines).

Apache Commons has a Java based implementation of SCXML:

Commons SCXML is an implementation aimed at creating and maintaining a Java SCXML engine capable of executing a state machine defined using a SCXML document, while abstracting out the environment interfaces.

Jim Ferrans
+1  A: 

In C#, iterators (with 'yield return' and 'yield break') are a language construct that directly translates to state machines. I haven't actually ever used it as such, but I actually think it could be usable in practice.

There happens to be a stackoverflow question about it here. The highest voted answer discourages it though ...

Joren
A: 

Erlang's OTP supports state machine constructs via 'gen_fsm'. It's been a couple of years since I last looked at it, so I'm a bit rusty, but you can Google for 'Erlang gen_fsm' and find loads of reference material

monch1962
+7  A: 

Ragel is a state machine language. IOW, it's not a language that also supports state machines, it's a language that only supports state machines. Which obviously means that it's not Turing-complete, but who needs that?

More precisely, Ragel is a state machine compiler, which takes a description of a state machine in a regexp-like language and generates an implementation of that state machine in C, C++, Objective-C, D, Java or Ruby. (Think yacc but for state machines instead of LALR(1) table parsers.) The primary purpose of Ragel is parsing binary protocols (such as networking protocols or also on-disk file formats), but it can just as well be used for text.

One famous example of using Ragel is the Mongrel webserver for Ruby: its HTTP kernel is written in Ragel, which makes it extremely fast and secure. The HTTP kernel is so good in fact, that it has been reused a number of times in different applications: Thin, Unicorn and Rainbows are also webservers, and in fact direct competitors to Mongrel. Ebb is a reverse HTTP proxy. RFuzz is a fuzz testing tool for web applications. Also, some security tools use it.

Ragel also allows embedding code in the host language into the state machine, thus making it Turing-complete, and able to not only recognize but also interpret protocols.

In general, every language with support for advanced user-defined control-flow via either coroutines (e.g. Lua) or continuations (e.g. Scala) or GOTO (e.g. PHP) or proper tail calls (e.g. Scheme) can be used to easily implement state machines. (Generators (Python) aka iterators (C#), which are basically "crappy coroutines" might or might not work, depending on your definition of "work".) And any language which has flexible syntax (e.g. Ruby) or supports metasyntactic abstraction (e.g. Clojure) can be used to describe state machines. (Support for non-ASCII identifiers helps, too, so that you can use actual arrows for your state machine.)

Which means that if you combine the two, and use a language that supports both tail calls and metasyntactic abstraction, you get very nice state machines, without requiring native language support. Shriram Krishnamurthi gave a now (in)famous talk titled "The Swine before Perl" at the inaugural Lightweight Languages Conference, in which he demonstrated an FSM implementation in Scheme. (Here are the slides, an audio recording and a paper explaining the code). The code itself is a 26 line (very short lines, actually) macro, that allows you to write code like this:

(define my-regex
  (automaton init
             [init : (c → more)]
             [more : (a → more)
                     (d → more)
                     (r → end)]
             [end : accept]))

This is a specification of the state machine corresponding to the regular expression c(a|d)*r. And it is not only a specification, but also a runnable program implementing that state machine.

I can call it like this:

(my-regex '(c a d a d d r))

And in this case get the result #t (which is Scheme-speak for true).

Jörg W Mittag