Подтвердить что ты не робот

Есть ли язык программирования со встроенной конструкцией конечного автомата?

Мне просто интересно, есть ли язык программирования, который в качестве основной языковой конструкции имеет состояние машины (аналогично boost:: statechart).

Аналогии - С# имеет делегатов, где java использует шаблон наблюдателя, а C имеет обратные вызовы. Perl и python имеют встроенные хэши, а С++ и java - библиотека.

Update:

Это должен быть общий язык программирования в смысле С++, С#, Java, Lisp...

Я имею в виду "зрелые" государственные машины со всеми звонками и свистами на уровне формализма Хареля или диаграмм состояний UML или boost:: statechart.

4b9b3361

ОТВЕТЫ

Ответ 1

Ragel - это язык конечного автомата. IOW, это не язык, который также поддерживает государственные машины, это язык, который поддерживает только государственные машины. Это, очевидно, означает, что это не Тьюринг-полный, но кому это нужно?

Точнее, Ragel является компилятором конечных машин, который описывает описание конечного автомата в языке, подобном регулярному выражению, и генерирует реализацию этого конечного автомата в C, С++, Objective-C, D, Java или Ruby. (Think yacc, но для машин с государственными машинами вместо парсеров таблиц LALR (1).) Основная цель Ragel - анализировать бинарные протоколы (например, сетевые протоколы или форматы файлов на диске), но его можно так же использовать для текста.

Один известный пример использования Ragel - веб-сервер Mongrel для Ruby: его ядро ​​HTTP написано в Ragel, что делает его чрезвычайно быстрым и безопасным. Ядро HTTP настолько хорошо на самом деле, что оно многократно использовалось в разных приложениях: Thin, Unicorn и Rainbows также являются веб-серверами и фактически являются непосредственными конкурентами Mongrel. Ebb - это обратный HTTP-прокси. RFuzz - это инструмент тестирования fuzz для веб-приложений. Кроме того, некоторые средства безопасности используют его.

Ragel также позволяет внедрять код на языке хоста в конечный автомат, что делает его завершением Turing и способным не только распознавать, но и интерпретировать протоколы.

В общем, каждый язык с поддержкой расширенного пользовательского потока управления через сопрограммы (например, Lua) или продолжения (например, Scala) или GOTO (например, PHP) или правильные хвостовые вызовы (например, схема) может чтобы легко использовать государственные машины. (Генераторы (Python) aka iterators (С#), которые в основном являются "crappy coroutines", могут работать или не работать, в зависимости от вашего определения "работа".) И любой язык, который имеет гибкий синтаксис (например, Ruby) или поддерживает метасинтаксическую абстракцию (например, например, Clojure), может использоваться для описания состояний машин. (Поддержка не-ASCII-идентификаторов также помогает, так что вы можете использовать фактические стрелки для вашего конечного автомата.)

Это означает, что если вы объедините эти два языка и используете язык, который поддерживает как хвостовые вызовы, так и метасинтетические абстракции, вы получаете очень хорошие государственные машины, не требуя поддержки на родном языке. Шрирам Кришнамурти (Shriram Krishnamurthi) дал сегодня (в) знаменитый доклад под названием "The Swine before Perl" на первой конференции по легким языкам, на которой он продемонстрировал реализацию FSM на Схеме. (Ниже приведены слайды, запись и документ, объясняющий код). Сам код представляет собой макрос 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 (который является Scheme-speak для true).

Ответ 2

Там появился новый язык машинного языка W3C на основе XML, называемый SCXML, основанный на Дэвиде Хареле StateChart формализм (который поддерживает иерархические и параллельные государственные машины).

Apache Commons имеет Java-реализацию SCXML:

Commons SCXML - это реализация, направленная на создание и поддержку ядра Java SCXML, способного выполнять конечный автомат, определенный с использованием документа SCXML, при абстрагировании интерфейсов среды.

Ответ 3

SMC - это компилятор для простого языка, специфичного для домена, который будет генерировать государственные машины для многих популярных языков. Я использовал его для создания поддерживаемых состояний машин для самых разных вещей, таких как сложные пользовательские интерфейсы и пользовательские сетевые протоколы.

Ответ 4

Erlang OTP поддерживает конструкции конечных автоматов через 'gen_fsm'. Прошло пару лет с тех пор, как я в последний раз смотрел на него, поэтому я немного ржавый, но вы можете использовать Google для "Erlang gen_fsm" и находить множество эталонных материалов.

Ответ 5

Не совсем, но для Python существует модуль конечных автоматов, который позволяет использовать декораторы для поддержки реализации графиков состояния стиля Harel, включая контексты с несколькими состояниями, вложенные подтесты с историей и без нее. Код заканчивается, смотря что-то вроде ниже. Модуль находится в 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()

Ответ 6

Язык программирования Plaid представляет собой "Typestate-Oriented Programming", парадигму, которая расширяет объектно-ориентированное программирование с помощью типов ".

Вот документ: 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]
        { ... }
}

Ответ 8

В С# итераторы (с 'yield return' и 'yield break') являются языковой конструкцией, которая непосредственно переводится в конечные машины. Я на самом деле никогда не использовал его как таковой, но на самом деле считаю, что его можно использовать на практике.

В этом случае возникает вопрос об использовании stackoverflow здесь. Самый высокий голосовой ответ обескураживает его, хотя...

Ответ 9

Помимо Ragel есть технически интересный, но довольно неясный язык под названием SL1. См. http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1095580. Он был создан компанией Iskratel в Словении для развития телекоммуникационных систем, где основными машинами являются государственные машины.

Ответ 11

Недавно Microsoft Research выпустила P язык GitHub. Они также имеют структуру PSharp, которая предоставляет библиотеку расширений С# и синтаксис высокого уровня с компилятором для языка.

Я с нетерпением жду, чтобы попробовать.

Вот часть из одного из примеров для расширений С#:

internal class Server : Machine
{
    MachineId Client;

    [Start]
    [OnEntry(nameof(InitOnEntry))]
    class Init : MachineState { }

    void InitOnEntry()
    {
        ...
        this.Goto(typeof(Active));
    }

    ...

Вот часть их синтаксиса высокого уровня:

  с использованием System;

пространство имен TheStateMachine
{ внутренний клиент машины {   частный сервер;   частное начальное состояние Init   {     запись     {       this.Server = (trigger as Config).target;       прыгать (Игра);     }   }
   частное государство   {     запись     {       // выполнять логику     }     на AnotherEvent перейти AnotherState;     на SomeEvent сделать ProcessSomeLogic;   }
...
Код>