Существует ли язык программирования со встроенным конечным автоматом?
Мне просто любопытно, есть ли язык программирования, который имеет конечные автоматы (аналогично boost::statechart) в качестве конструкции основного языка.
Аналогии - у C# есть делегаты, где java использует шаблон наблюдателя, а C имеет обратные вызовы. Perl и python имеют встроенные хэши, а C++ и java нужна библиотека.
Обновить:
Это должен быть общий язык программирования в смысле C++, C#, Java, Lisp ...
Я имею в виду "зрелые" конечные автоматы со всеми прибамбасами на уровне формализма Харела или диаграмм состояний UML или boost::statechart.
15 ответов
Рагель - государственный язык машин. Итак, это не язык, который также поддерживает конечные автоматы, это язык, который поддерживает только конечные автоматы. Что, очевидно, означает, что он не является полным по Тьюрингу, но кому это нужно?
Точнее говоря, Ragel - это компилятор конечных автоматов, который берет описание конечного автомата на языке, подобном регулярному выражению, и генерирует реализацию этого конечного автомата в C, C++, Objective-C, D, Java или Ruby. (Считать yacc но для конечных автоматов вместо парсеров таблиц LALR(1). Основная цель Ragel - анализ двоичных протоколов (таких как сетевые протоколы или форматы файлов на диске), но он также может использоваться для текста.
Одним из известных примеров использования Ragel является веб-сервер Mongrel для Ruby: его ядро HTTP написано на Ragel, что делает его чрезвычайно быстрым и безопасным. Ядро HTTP настолько хорошо, что его неоднократно использовали в различных приложениях: Thin, Unicorn и Rainbows также являются веб-серверами и фактически являются прямыми конкурентами Mongrel. Ebb - это обратный HTTP-прокси. RFuzz - это инструмент для нечеткого тестирования веб-приложений. Кроме того, некоторые инструменты безопасности используют его.
Ragel также позволяет встраивать код на языке хоста в конечный автомат, что делает его полным по Тьюрингу и способным не только распознавать, но и интерпретировать протоколы.
В общем, каждый язык с поддержкой расширенного пользовательского потока управления через сопрограммы (например, Lua) или продолжения (например, Scala) или GOTO (например, PHP) или соответствующие хвостовые вызовы (например, схема) могут быть использованы для простой реализации конечных автоматов. (Generators (Python) или итераторы (C#), которые по сути являются "дрянными сопрограммами", могут работать или не работать, в зависимости от вашего определения "работы".) И любой язык, который имеет гибкий синтаксис (например, Ruby) или поддерживает метасинтаксическую абстракцию (например, Clojure) можно использовать для описания конечных автоматов. (Поддержка не-ASCII идентификаторов также помогает, так что вы можете использовать фактические стрелки для вашего конечного автомата.)
Это означает, что если вы объедините их и используете язык, который поддерживает как хвостовые вызовы, так и метасинтаксическую абстракцию, вы получите очень хорошие конечные автоматы, не требуя поддержки родного языка. Шрирам Кришнамурти выступил с (ныне) знаменитой лекцией под названием "Свиньи перед Perl" на первой конференции по облегченным языкам, на которой он продемонстрировал реализацию FSM в Scheme. (Здесь представлены слайды, аудиозапись и документ с объяснением кода). Сам код представляет собой макрос из 26 строк (на самом деле очень короткие строки), который позволяет писать код следующим образом:
(define my-regex
(automaton init
[init : (c → more)]
[more : (a → more)
(d → more)
(r → end)]
[end : accept]))
Это спецификация конечного автомата, соответствующего регулярному выражению c(a|d)*r, И это не только спецификация, но и работающая программа, реализующая этот конечный автомат.
Я могу назвать это так:
(my-regex '(c a d a d d r))
И в этом случае получить результат #t (что означает Схема true).
Существует новый язык машин состояний на основе XML W3C под названием SCXML, основанный на формализме StateChart Дэвида Харела (который поддерживает иерархические и параллельные машины состояний).
Apache Commons имеет реализацию SCXML на основе Java:
Commons SCXML - это реализация, нацеленная на создание и поддержку механизма Java SCXML, способного выполнять конечный автомат, определенный с помощью документа SCXML, при абстрагировании интерфейсов среды.
Язык программирования Plaid представляет "Типизированное программирование, парадигму, расширяющую объектно-ориентированное программирование с помощью типов".
Вот документация: http://www.cs.cmu.edu/~aldrich/plaid/
Например:
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]
{ ... }
}
SMC - это компилятор для простого предметно-ориентированного языка, который генерирует конечные автоматы для многих популярных языков. Я использовал его для генерации поддерживаемых конечных автоматов для широкого спектра вещей, таких как сложные пользовательские интерфейсы и пользовательские сетевые протоколы.
OTP Эрланга поддерживает конечные автоматы через gen_fsm. Прошло несколько лет с тех пор, как я в последний раз смотрел на это, поэтому я немного заржавел, но вы можете найти в Google "Erlang gen_fsm" и найти множество справочных материалов
Я только что нашел один: AsmL (абстрактный государственный язык машин).
Вот страница с дополнительной информацией об этом в CodePlex.
Достаточно интересно, это разработано Microsoft.
Microsoft Research недавно выпустила язык P на GitHub. У них также есть инфраструктура PSharp, которая предоставляет библиотеку расширений C# и высокоуровневый синтаксис с компилятором для языка.
Я с нетерпением жду возможности попробовать.
Вот часть одного из их примеров для расширений C#:
internal class Server : Machine
{
MachineId Client;
[Start]
[OnEntry(nameof(InitOnEntry))]
class Init : MachineState { }
void InitOnEntry()
{
...
this.Goto(typeof(Active));
}
...
Вот часть их синтаксиса высокого уровня:
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;
}
...
Не совсем, но есть модуль конечного автомата для Python, который позволяет использовать декораторы для поддержки реализации диаграмм состояний стиля Хареля, включая контексты с несколькими состояниями, вложенные подсостояния с историей и без нее. Код выглядит примерно так, как показано ниже. Модуль находится по адресу 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()
В сентябре 2015 года был запущен проект xstate . Он реализует SCXML и стремится предоставить
JavaScript and TypeScript finite state machines and statecharts for the modern web. ссылка на документацию
Эта работа превратилась в нечто очень хорошее, см. https://microsoft.github.io/coyote.
У Шрирама Кришнамурти есть доклад и статья об использовании макросов для добавления встроенного подъязыка для автоматов в Scheme. Однако я не уверен, что какие-либо Схемы включают его макросы в качестве стандартной библиотеки.
Помимо Ragel существует технически интересный, но довольно неясный язык, называемый SL1. См. http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1095580. Он был создан Iskratel в Словении для разработки телекоммуникационных систем, в которых конечными блоками являются конечные автоматы.
В C# итераторы (с "yield return" и "yield break") являются языковой конструкцией, которая напрямую переводится в конечные автоматы. На самом деле я никогда не использовал его как таковой, но на самом деле я думаю, что он может быть использован на практике.
Здесь возникает вопрос о переполнении стека. Ответ, получивший наибольшее количество голосов, не одобряет его, хотя...
Я почти десять лет опаздываю на вечеринку, но недавно я наткнулся на неясный язык, который заимствует идеи у ФШМ под названием Юм
Я не уверен, что он все еще активно поддерживается, но вы можете по крайней мере скачать компилятор и поиграть с ним. Сложно найти информацию, но в Интернете есть несколько статей и статей, в которых показано все необходимое.
В C++ также есть фреймворк Macho (очень маленький), созданный в 2005 году Эдуардом Хити. Macho расшифровывается как «машинные объекты C++». Доступно здесь: https://github.com/yattom/macho
Очень маленький, выполняет работу для HSM, не требуя повышения.