Is there a programming language with built-in state machine construct?
https://stackoverflow.com/questions/9011523
-
19-04-2021 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
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.
Solution
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).
OTHER TIPS
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.
SMC is a compiler for a simple domain specific language that will generate state machines for many popular languages. I have used it to generate maintainable state machines for a wide variety of things such as complex user interfaces and custom network protocols.
The Plaid Programming Language introduce "Typestate-Oriented Programming, a paradigm that extends object-oriented programming with typestates."
Here is the doc: http://www.cs.cmu.edu/~aldrich/plaid/
E.g:
state File {
public final String filename;
}
state OpenFile extends File {
private CFilePtr filePtr;
public int read() { ... }
public void close() [OpenFile>>ClosedFile]
{ ... }
}
state ClosedFile extends File {
public void open() [ClosedFile>>OpenFile]
{ ... }
}
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.
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
Not quite, but there is a state machine module for Python that lets you use decorators to support implementing Harel style statecharts, including contexts with multiple states, nesting substates with and without history. The code winds up looking something like below. Module is at http://wiki.python.org/moin/State%20Machine%20via%20Decorators
#!/bin/env/python
"""
This example now works. The state pattern module
allows defining states which are their their own context for
implementing substates. Substate Medium (class Medium) shows this here.
"""
"""
Example with 5 buttons. Two ,'up','down' cause state to rotate among the
several states. The other three, bx,by,bz, invoke state dependent behavior.
Switching into a state causes the labels of the three buttons bx,by,bz to
change. Pressing one of the buttons causes associated text to appear in
corresponding static text box. An 'onEnter' method changes the text.
"""
import wx
import DecoratorStateMachine as dsm
class MyFrame(wx.Frame, dsm.ContextBase):
xtable = dsm.TransitionTable('pstate')
def __init__(self):
MyFrame.xtable.initialize(self)
wx.Frame.__init__(self, None, -1, "My Frame", size=(470,220))
family = wx.SWISS
style = wx.NORMAL
weight = wx.BOLD
font = wx.Font(11,family,style,weight, False, "Verdana")
self.SetFont(font)
panel = wx.Panel(self, -1)
b = wx.Button(panel, -1, "Up", pos=(50,20), size=(80,35))
self.Bind(wx.EVT_BUTTON, self.OnUp, b)
b.SetDefault()
b = wx.Button(panel, -1, "Down", pos=(50,60), size=(80,35))
self.Bind(wx.EVT_BUTTON, self.OnDown, b)
self.bx = wx.Button(panel, -1, "xxx", pos=(50,100), size=(110,35))
self.Bind(wx.EVT_BUTTON, self.OnBA, self.bx)
self.tx = wx.StaticText(panel, -1, "", pos=(50,140), size=(110,35))
self.by = wx.Button(panel, -1, "yyy", pos=(180,100), size=(110,35))
self.Bind(wx.EVT_BUTTON, self.OnBB, self.by)
self.ty = wx.StaticText(panel, -1, "", pos=(180,140), size=(110,35))
self.bz = wx.Button(panel, -1, "zzz", pos=(310,100), size=(110,35))
self.Bind(wx.EVT_BUTTON, self.OnBC, self.bz )
self.tz = wx.StaticText(panel, -1, "", pos=(310,140), size=(110,35))
@dsm.transition(xtable)
def OnUp(self, event):
pass
@dsm.transition(xtable)
def OnDown(self, event):
pass
@dsm.event(xtable)
def OnBA(self, event):
pass
@dsm.event(xtable)
def OnBB(self, event):
pass
@dsm.event(xtable)
def OnBC(self, event):
self.tz.SetLabel("Bossy")
class Off(MyFrame):
"This is state Off "
def onEnter(self):
self.bx.SetLabel("Chase")
self.by.SetLabel("Onry")
self.bz.SetLabel("Cow")
def OnBA(self, event):
self.tx.SetLabel("Chase the")
def OnBB(self, event):
self.ty.SetLabel("Onry")
class Low(MyFrame):
"This is state Low "
items = ["Walk", "Green", "Llama"]
def onEnter(self):
self.bx.SetLabel(self.items[0])
self.by.SetLabel(self.items[1])
self.bz.SetLabel(self.items[2])
def OnBA(self, event):
self.tx.SetLabel("Walk the ")
def OnBB(self, event):
self.ty.SetLabel(self.items[1])
def OnBC(self, event):
self.tz.SetLabel(self.items[2])
class Medium(MyFrame):
"This is state Medium "
ytable = dsm.TransitionTable('qstate')
def onEnter(self):
if not hasattr(self, 'qstate'): #unconditionally initialize for no history
self.ytable.initialize(self)
self.doEnter()
@dsm.event(ytable)
def doEnter(): pass
@dsm.transitionevent(ytable)
def OnBA(self, event):
pass
@dsm.transitionevent(ytable)
def OnBB(self, event):
pass
@dsm.transitionevent(ytable)
def OnBC(self, event):
pass
class High(Low):
"This is state High "
items = ["Pet","Tame", "Dog"]
def OnBA(self, event):
self.tx.SetLabel("Pet his")
class MedBlue(Medium):
"""State med blu"""
items = ["Med BLue","Checkered", "Tractor"]
def onEnter(self):
self.bx.SetLabel(self.items[0])
self.by.SetLabel(self.items[1])
self.bz.SetLabel(self.items[2])
def doEnter(self):
self.onEnter()
def OnBA(self, event):
self.tx.SetLabel("Med Blue")
def OnBB(self, event):
self.ty.SetLabel("Chekered")
def OnBC(self, event):
self.tz.SetLabel("Tractor")
class MedRed(Medium):
"""State med red"""
items = ["Med Red","Striped", "Combine"]
def onEnter(self):
self.bx.SetLabel(self.items[0])
self.by.SetLabel(self.items[1])
self.bz.SetLabel(self.items[2])
def doEnter(self):
self.onEnter()
def OnBA(self, event):
self.tx.SetLabel("Med Red")
def OnBB(self, event):
self.ty.SetLabel("Striped")
def OnBC(self, event):
self.tz.SetLabel("Combine")
MyFrame.xtable.nextStates(Low, (Medium,Off))
MyFrame.xtable.nextStates(Medium, (High,Low))
MyFrame.xtable.nextStates(High, (Off,Medium))
MyFrame.xtable.nextStates(Off, (Low,High))
MyFrame.xtable.initialstate = Off
Medium.ytable.nextStates(MedBlue, (MedBlue, MedRed, MedRed))
Medium.ytable.nextStates(MedRed, (MedBlue, MedBlue, MedRed))
Medium.ytable.initialstate = MedBlue
if __name__=='__main__':
app = wx.PySimpleApp()
frame = MyFrame()
frame.Show(True)
app.MainLoop()
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 ...
Apart from Ragel there is a technically interesting,but quite obscure language called SL1. See http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1095580. It was created by Iskratel in Slovenia in order to develop telecom systems where state machines are the basic blocks.
Shriram Krishnamurthi has a talk and a paper about using macros to add an embedded sublanguage for automata to Scheme. I'm not sure if any Schemes include his macros as a standard library, though.
Microsoft Research recently released the P language on GitHub. They also have the PSharp framework which provides a C# extension library and a high-level syntax with compiler for the language.
I am looking forward to trying it out.
Here is a portion from one of their examples for the C# extensions:
internal class Server : Machine
{
MachineId Client;
[Start]
[OnEntry(nameof(InitOnEntry))]
class Init : MachineState { }
void InitOnEntry()
{
...
this.Goto(typeof(Active));
}
...
Here is a portion of their high-level syntax:
using System;
namespace TheStateMachine
{
internal machine Client
{
private machine Server;
private start state Init
{
entry
{
this.Server = (trigger as Config).target;
jump(Playing);
}
}
private state Playing
{
entry
{
//execute logic
}
on AnotherEvent goto AnotherState;
on SomeEvent do ProcessSomeLogic;
}
...
I'm almost a decade late to the party but I recently stumbled upon an obscure language which borrows ideas from FSMs called Hume
I'm not sure if it's still actively maintained, but you can at least download the compiler and play around with it. Information is hard to come by, but there's a few papers and articles online that show the essentials.
This work has evolved further into something very nice, see https://microsoft.github.io/coyote.
