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

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

Точнее, 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) или правильные хвостовые вызовы (например, Схема) можно использовать для простого реализации конечных автоматов. (Генераторы (Python), также известные как итераторы (C #), которые в основном представляют собой «дрянные сопрограммы», могут работать или не работать, в зависимости от вашего определения «работа».) И любой язык, имеющий гибкий синтаксис (например, Ruby) или поддерживающий метасинтаксическую абстракцию ( например, Clojure) можно использовать для описания конечных автоматов. (Поддержка идентификаторов, отличных от ASCII, тоже помогает, так что вы можете использовать фактические стрелки для своего конечного автомата.)

Это означает, что если вы объедините два и используете язык, поддерживающий ] оба хвостовых вызовов и метасинтаксическая абстракция, вы получите очень хорошие конечные автоматы, без поддержки родного языка. Шрирам Кришнамурти выступил с известной ныне речью под названием " в котором он продемонстрировал реализацию конечного автомата на схеме. (Вот слайды , аудиозапись и документ, объясняющий код ). Сам код представляет собой макрос из 26 строк (на самом деле, очень коротких строк), который позволяет писать такой код:

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

Это спецификация конечного автомата, соответствующего регулярному выражению c (a | d) * г . И это не только спецификация, но и исполняемая программа , реализующая этот конечный автомат.

Я могу назвать это так:

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

И в этом случае получить результат #t (что на языке схемы верно ).

в котором он продемонстрировал реализацию конечного автомата на схеме. (Вот слайды , аудиозапись и документ, объясняющий код ). Сам код представляет собой макрос из 26 строк (на самом деле, очень коротких строк), который позволяет писать такой код:

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

Это спецификация конечного автомата, соответствующего регулярному выражению c (a | d) * г . И это не только спецификация, но и исполняемая программа , реализующая этот конечный автомат.

Я могу назвать это так:

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

И в этом случае получить результат #t (что на языке схемы верно ).

Сам код представляет собой макрос из 26 строк (на самом деле очень коротких строк), который позволяет вам писать такой код:

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

Это спецификация конечного автомата, соответствующего регулярному выражению c (a | d) * г . И это не только спецификация, но и исполняемая программа , реализующая этот конечный автомат.

Я могу назвать это так:

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

И в этом случае получить результат #t (что на языке схемы верно ).

Сам код представляет собой макрос из 26 строк (на самом деле, очень коротких строк), который позволяет писать такой код:

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

Это спецификация конечного автомата, соответствующего регулярному выражению c (a | d) * г . И это не только спецификация, но и исполняемая программа , реализующая этот конечный автомат.

Я могу назвать это так:

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

И в этом случае получить результат #t (что на языке схемы верно ).