С помощью генератора машин состояний Guile-SMC сделал разбор формата Portable Network Graphics (PNG): https://github.com/artyom-poptsov/guile-png

Guile-PNG позволяет читать изображения в формате PNG и разбирать их на части (чанки, "chunks"). Для некоторых чанков я уже написал разбор на осмысленные поля, остальные содержат в себе просто двоичные данные — которые тем не менее можно разобрать на что-то вменяемое, если посмотреть в стандарт PNG.

Интересно было попробовать, насколько хорошо Guile-SMC подходит для решения подобных сложных задач с разбором двоичного формата. Пришлось дорабатывать Guile-SMC по ходу дела.

Из основных новшеств Guile-SMC:
- Добавил возможность задавать входные и выходные действия для каждого состояния.
- Добавил возможность задавать источники событий как для ДКА в целом, так и для каждого отдельного состояния.

На данный момент архитектура системы получилось достаточно гибкая. Можно разбить большой ДКА на несколько более простых, построенных иерархическим способом — подобные ДКА называются по понятным причинам иерархическими (Hierarchical State Machines, HSM). HSM позволяет разбить крупную задачу на несколько более мелких, таким образом, снизив сложность решения в целом, что очень важно для практического применения автоматного программирования.

Конечной целью Guile-SMC я вижу упрощение написания различных парсеров и в целом программ, придерживающихся автоматного стиля. При этом, смысл не только в кодогенерации на основе формального описания, но и формальная проверка получившихся ДКА, а также (возможно) оптимизация — но это уже более сложная задача. На данный момент Guile-SMC например способен проверять ДКА на тупиковые и недостижимые состояния.

В целом, очень интересная фундаментальная задача.

#projects #guile #fsm

В коммитах на master в Guile-SMC добавил standalone-режим для компилятора машин состояний, теперь все необходимые модули копируются в отдельный каталог.

$ tree
.
├── context.scm
├── fsm.puml
├── main.scm
└── README.org

0 directories, 5 files

Далее выполняем компиляцию в standalone-режиме:

$ cat fsm.puml | /usr/bin/smc compile -L . -U "((context))" -m "(custom-fsm)" \
    -t guile-standalone --debug > custom-fsm.scm

Содержимое каталога теперь выглядит так:

$ tree
.
├── context.scm
├── custom-fsm
│   ├── context.scm
│   └── smc
│       ├── context
│       │   ├── char-context.scm
│       │   └── context.scm
│       ├── core
│       │   ├── common.scm
│       │   ├── log.scm
│       │   ├── stack.scm
│       │   ├── state.scm
│       │   └── transition.scm
│       └── fsm.scm
├── custom-fsm.scm
├── fsm.puml
├── main.scm
└── README.org

4 directories, 14 files

Обратите внимание, что появился каталог с именем модуля, в котором указано расположить целевой ДКА — "custom-fsm". В этот каталог были скопированы модули Guile-SMC, необходимые для работы целевого ДКА, плюс зависимости из списка дополнительных модулей (-U "((context))").

При копировании в модулях происходит замена зависимостей так, чтобы они все указывали на скопированные модули. Например, было:

$ head -4 context.scm
(define-module (context)
  #:use-module (oop goops)
  #:use-module (ice-9 textual-ports)
  #:use-module (smc context char-context)

Стало:

$ head -4 custom-fsm/context.scm
(define-module (custom-fsm context)
  #:use-module (oop goops)
  #:use-module (ice-9 textual-ports)
  #:use-module (custom-fsm smc context char-context)

Такой автомат можно запускать без наличия Guile-SMC в системе.

#guile #smc #dev #lisp #fsm

Пример профилирования ДКА в Guile-INI 0.3.0 через Guile-SMC профилировщик.

Тестовая программа:

$ cat test.scm 
#!/usr/bin/guile-3.0 \
-L modules -e main -s
!#

(use-modules (ice-9 pretty-print)
             (oop goops)
             (logging logger)
             (smc core log)
             (ini))

(define (main args)
  (log-clear-handlers!)
  (log-add-handler! (make <port-log/us>
                      #:port (open-output-file "ini.log")))
  (let ((data (ini->scm (current-input-port) #:debug-mode? #t)))
    (pretty-print data)
    (scm->ini data)))

Запуск парсера с выводом лога в файл:

$ cat /etc/php/7.4/apache2/php.ini | ./test.scm

Лог:

$ wc ini.log 
  3528  21168 280750 ini.log
$ head ini.log 
2022-01-07 17:06:27.338353 (DEBUG): [*] -> [read]
2022-01-07 17:06:27.339380 (DEBUG): [read] -> [read_section_title]
2022-01-07 17:06:27.339982 (DEBUG): [read_section_title] -> [read_section_content]
2022-01-07 17:06:27.340274 (DEBUG): [read_section_content] -> [read_comment]
2022-01-07 17:06:27.340710 (DEBUG): [read_comment] -> [read_section_content]
2022-01-07 17:06:27.340888 (DEBUG): [read_section_content] -> [read_comment]
2022-01-07 17:06:27.341363 (DEBUG): [read_comment] -> [read_section_content]
2022-01-07 17:06:27.341504 (DEBUG): [read_section_content] -> [read_comment]
2022-01-07 17:06:27.341728 (DEBUG): [read_comment] -> [read_section_content]
2022-01-07 17:06:27.341860 (DEBUG): [read_section_content] -> [read_comment]

Собственно профилирование:

$ smc profile ini.log
Total transitions: 3528
Total time:        630510 us
Stats:
  read_comment: 416994 us (66.1360 %)
  read_section_content: 153088 us (24.2800 %)
  read_section_property_value: 17230 us (2.7327 %)
  read_section_property_key: 16376 us (2.5973 %)
  trim_section_property_key: 14990 us (2.3774 %)
  trim_section_property_value: 6673 us (1.0583 %)
  read_section_title: 4132 us (.6553 %)
  read: 1027 us (.1629 %)

#guile #smc #dev #lisp #fsm #profiling

Добавил ещё один пример кода для работы с компилятором Guile-SMC:
https://github.com/artyom-poptsov/guile-smc/tree/master/examples/compiler

На выходе, в файле fsm.scm, после выполнения следующей команды:

$ guile -L . main.scm > fsm.scm

будет самодостаточный Guile-код, который можно запустить без наличия Guile-SMC в системе:

$ echo "hello world" | guile -L . run.scm

#guile #smc #fsm #projects

Выпустил релиз Guile-SMC 0.4.0:
https://lists.gnu.org/archive/html/guile-user/2022-03/msg00041.html

В новом релизе:
- Добавлен профайлер для ДКА, который позволяет выявлять "узкие" места в автомате за счёт анализа времени, сколько автомат проводит в каждом состоянии.
- Добавлено два режима (цели) компиляиции: guile-standalone и guile-standalone-copy. Эти режимы позволяют создавать ДКА на основе описания в PlantUML, которые пригодны для использования без наличия Guile-SMC в системе.
- Парсер для PlantUML оптимизирован и стал примерно на 25% быстрее (как раз "узкое" место выявлено с помощью smc profile)
- Добавлена man-страница для smc (см. man smc)
- Дополнена и расширена документация в Info.

#guile #smc #fsm #projects #dev

Работаю над портированием Guile-ICS на мой компилятор детерминированных конечных автоматов (ДКА) Guile-SMC:
https://github.com/artyom-poptsov/guile-ics

Интересная задача, которая позволяет выявить недостатки Guile-SMC и понять сам процесс проектирования и реализации ДКА — чтобы впоследствии адаптировать Guile-SMC.

Поскольку проект Guile-SMC является для меня исследовательским, сразу не всегда понятно, как должны быть реализованы те или иные вещи. Чтобы это понять, надо использовать инструмент и смотреть, подходит ли он под решаемую задачу.

Проекты наподобие Guile-SMC мне интересны во-первых тем, что они являются "инструментами для создания инструментов", и во-вторых, что они потенциально позволят думать о решаемых задачах по-новому (следовательно, лучше контролировать сложность задач.)

В Guile-ICS будет использоваться два ДКА, один будет вложен в другой.

Первый (базовый) ДКА необходим для разбора строк формата iCalendar (RFC5545). Второй (высокоуровневый) ДКА необходим для разобора потока объектов iCalendar.

В целом, первая часть задачи портирования (разработка и реализация ДКА) уже реализована, тесты в процессе написания. Вторая часть портирования заключается в переносе старого кода Guile-ICS на использование Guile-SMC.

#guile #smc #fsm #projects #dev

Выпустил релиз Guile-SMC 0.5.0 — компилятора детерминированных конечных автоматов (ДКА) для GNU Guile:
https://github.com/artyom-poptsov/guile-smc/releases/tag/v0.5.0

Официальный анонс в списке рассылки Guile:
https://lists.gnu.org/archive/html/guile-user/2022-08/msg00071.html

Основные возможности:
- Таблица переходов между состояниями может быть автоматически проверена на наличие тупиковых и недостижимых состояний.
- ДКА Guile-SMC при работе собирают статистику — можно узнать, сколько шагов и переходов делала машина состояний при работе.
- Guile-SMC включает в себя профилировщик, который позволяет по логам работы ДКА узнать, сколько система провела в каждом состоянии времени и какой процент от общего времени работы это составляет. Это позволяет находить "узкие места" и оптимизировать ДКА на основе цифр, полученных в реальной работе.
- Поддержка разных "целей" для компиляции — есть три цели: обычная "guile", которая даёт на выходе код ДКА, который для работы будет требовать наличие Guile-SMC в целевой системе; "автономный" режим ("guile-standalone"), который позволяет получить на выходе код ДКА, который не зависит от наличия Guile-SMC в целевой системе (и также по виду близок к тому, который мог бы быть написан в ручном режиме, где переход между состояниями по сути представлен рекурсивным вызовом процедур, каждая из которых представляет одно из состояний ДКА); и наконец "автономный" режим с сохранением Guile-SMC основы ("guile-standalone-copy"), который копирует в вместе с ДКА часть Guile-SMC, которая необходима для его работы.
- Возможность запустить ДКА напрямую из PlantUML-файла (см. команду smc run)

Цель проекта — автоматизировать и упростить разработку ДКА для различных задач (в первую очередь различных парсеров, как раз одна из областей моих интересов), избежать дублирования работы.

Основные изменения в версии 0.5.0:
- Для цели компиляции guile-standalone добавлены недостающие зависимости в целевой код.
- Для цели компиляции guile-standalone также изменён API: теперь в целевом коде процедура для запуска называется fsm-run!, которая функционирует также, как и при цели компиляции guile — что позволяет обеспечить одинаковый интерфейс запуска ДКА, который не зависит от цели компиляции.
- При компиляции для цели guile-standalone выходной код теперь имеет более аккуратный вид.
- Команда smc context теперь позволяет генерировать промежуточный контекст, который можно использовать для обеспечения минимальной зависимости от внутренней структуры модулей Guile-SMC (это необходимо для совместимости различных целей компиляции, что опять же позволяет использовать разные цели без переписывания пользовательского кода.) В будущем рекомендуется использовать именно этот промежуточный контекст, а не прямой доступ к модулям Guile-SMC.
- smc context теперь может читать описание ДКА в PlantUML из файла.
- Модуль (smc core stack) удалён.
- Исправлены справочные сообщения от команд.
- В команду smc run добавлены дополнительные проверки корректности параметров запуска.
- Документация в Texinfo обновлена.

#guile #smc #fsm #dev #projects

Ещё один генератор конечных автоматов:
https://en.wikipedia.org/wiki/Ragel

#fsm

Выпустил релиз Guile State Machine Compiler (Guile-SMC) 0.5.1:
https://github.com/artyom-poptsov/guile-smc/releases/tag/v0.5.1

Список основных изменений:
- Исправил нежелательное сокрытие внутренней процедуры Guile log процедурой из модуля (smc core log).
- Добавил возможность выставлять драйвер логирования для Guile-SMC — это в частности позволило решить проблемы со сборкой Guile-SMC в изолированных окружениях (и/или с ограниченным доступом к ФС и сервисам). Теперь можно при использовании консольной утилиты smc указывать один из драйверов: syslog (по-умолчанию), file или null (отключение логирования.)
- Добавил более гибкую возможность дублирования логов в stderr — теперь это работает с любым драйвером логирования, не только с syslog.
- При компиляции примера парсера для формата PNG теперь используется драйвер логирования null.
- В тестах теперь логирование использует драйвер file и логи сохраняются рядом с тестами в каталоге tests.
- Описание пакета для GNU Guix обновлено.
- Обновлена документация в формате Texinfo.

Программы, работающие с Guile-SMC 0.5.0 должны без изменений продолжать работать с 0.5.1.

Скоро отправлю патч в GNU Guix с обновлённым пакетом.

#guile #smc #fsm #dev #projects

В релизе Guile-SMC 0.5.1 обнаружилось несколько ошибок, пришлось в срочном порядке делать 0.5.2:
https://lists.gnu.org/archive/html/guile-user/2022-09/msg00002.html

Исправленные ошибки:
- Команды smc context и smc compile теперь добавляют к выходному коду модуль (smc core config).

#guile #smc #fsm #dev #projects

Ломаю голову о дальнейшем развитии компилятора машин состояний Guile-SMC.

В библиотеке есть понятие контекста — то есть, некоторого объекта, который передаётся в обратные вызовы (callbacks) внутри ДКА.

Идея у меня следующая: библиотека должна предоставлять набор базовых контекстов для выполнения однотипных задач (например, для разбора текста, бинарных данных, обработки сетевых запросов и т.п.)

На данный момент у меня получилось выделить следующие виды контекстов:
- Символьный (char) — для чтения потока символов (реализован.)
- Бинарный (binary) — для чтения потока байт (в процессе реализации.)
- Токенизатор (token) — для чтения потока токенов, разделённых согласно определённым правилам (например, символами-разделителями.)
- Построчный (line) — для построчного чтения данных.

Если брать этот набор контекстов, они должны покрывать большинство задач обработки данных (а если и не хватит их, то всегда можно создать свой контекст.)

Но при этом события, обрабатываемые ДКА, могут являться не только неким потоком данных, но и вообще чем угодно. Например, для ДКА чат-бота входные события — это поступающие запросы от пользователя; для обработчика сетевого протокола — это запросы по сети, по некоторому протоколу.

Можно ли охватить весь этот потенциально бесконечный круг задач, решаемых через автоматное программирование, и свести его к некоторым примитивам, при этом не нарушая общность библиотеки? Думаю, что возможно, однако требует построения грамотной архитектуры.

Конечная цель проекта — автоматизировать написание автоматов путём кодогенерации на основе выскокоуровневого описания ДКА в формате PlantUML. Это даёт возможность сразу же получать визуализацию направленного графа переходов, а не пост-фактум, как часто бывает при ручном написании кода.

#projects #fsm #guile #scheme #dev

Очередной подход к продумыванию архитектуры Guile-SMC.

Хочется выделить универсальные строительные блоки для ДКА, при этом сохранив архитектуру гибкой. Думаю, есть смысл вынести предикаты (сторожи переходов, a.k.a.guards) в отдельные модули, т.к. они универсальны. При этом, сами контексты, над которыми оперируют ДКА, будут тоже в отдельных модулях. В итоге, должен получиться конструктор "собери себе ДКА".

Разработчики ДКА не обязаны вообще использовать предоставленные мной контексты и могут сделать всё самостоятельно. Если хочется сэкономить труд, то можно например воспользоваться предоставленными мной предикатами, но при этом полностью игнорировать предоставляемые Guile-SMC контексты.

Хочу также добавить функциональный контекст на базе модуля (srfi srfi-9 gnu), в дополнении к ООП-варианту, который был до этого.

#guile #smc #fsm #projects #dev

Более-менее выстроил структуру контекстов в Guile-SMC.

Отделил предикаты (guard'ы) от собственно контекста как некой структуры, которая передаётся между состояниями ДКА. Кроме того, в дополнении к ООП-контекстам (на базе GOOPS), добавил функциональный контекст на базе неизменяемых записей из модуля (srfi srfi-9 gnu) — теперь конструировать ДКА можно в функциональном стиле.

Для справки: (srfi srfi-9 gnu) позволяет создовать записи, в которых поля невозможно изменить. Все setter'ы для полей просто создают новую версию записи, исходная же остаётся неизменной.

Также для класса <fsm> добавил поля pre-action и post-action — эти поля хранят процедуры, которые должны вызываться перед предикатами и действиями, и после них, соответственно. Каждая подобная процедура должна возвращать контекст (изменённый или исходный.) Благодаря этому нововведению можно например организовать подсчёт прочитанных символов с использованием функциональных контекстов, не меняя их. В случае с ООП, это также даёт дополнительное удобство использования.

Пока вроде неплохо получается.

В итоге, Guile-SMC должен стать конструктором "собери себе ДКА". Можно будет быстро создавать парсеры для текстовых и двоичных форматов, и не только.

Думаю ещё в будущем выкинуть вариант компиляции guile-standalone-copy, так как он требует ресурсов для поддержки и не имеет особого смысла, как мне кажется. Останутся варианты guile (который генерирует ДКА, зависимый от Guile-SMC) и guile-standalone (который генерирует ДКА, который не зависит от Guile-SMC — структурно его код похож на тот, что можно было бы написать вручную.)

#dev #guile #fsm #projects

Постепенно переношу Guile-INI на новый API Guile-SMC, чтобы проверить корректность архитектурных решений и их реализации.

GitHub говорит, что Guile-INI состоит на ~42% из M4 макросов, и лишь на ~27% из кода на Scheme. Основная часть кода генерируется автоматически из описания ДКА в формате PlantUML и подтягивается из Guile-SMC. И это правильно, ведь в большинстве парсеров делаются одни и те же вещи, а значит, реализацию ДКА для парсеров можно обобщить, что я и пытаюсь сделать.

Ещё интересно будет попробовать Guile-SMC в проектах, где вместо чтения файлов есть некий "водоворот событий" ("event loop") — например, при реализации чат-ботов, либо же web-сервисов.

#projects #guile #scheme #fsm

Выпустил релиз Guile-SMC 0.6.0 — компилятора конечных автоматов для GNU Guile:
https://github.com/artyom-poptsov/guile-smc/releases/tag/v0.6.0

Основные новшества:
- Новая реализация контекста. Теперь контекст предоставляет предикаты отдельно от структур данных для обеспечения ДКА памятью. То есть, теперь есть модули (smc context char) и (smc context u8), предоставляющие предикаты для ДКА, работающих с символами и байтами соответственно. При этом, предоставляются также функциональные и ООП-структуры данных для обеспечения ДКА памятью — например, (smc context functional u8) и (smc context oop u8).
- Убрана поддержка цели компиляции guile-standalone-copy, так как смысла в ней мало, а для её поддержки требуются мои (ограниченные) ресурсы. Остались цели guile (генерация кода, зависящего от Guile-SMC) и guile-standalone (генерация кода, не зависящего от Guile-SMC.)
- Класс <fsm> теперь позволяет добавлять специальные процедуры pre-action и post-action, которые выполняются в начале обработки события и в конце, соответственно.
- smc compile и smc context теперь позволяет указывать путь к установленным модулям Guile-SMC через опцию --guile-smc-path.
- smc profile теперь позволяет выдавать статистику в JSON-формате.
- При указании опции --debug, консольные команды больше не включают дублирование логов в stderr — вместо этого теперь предлагается использовать специальную опцию stderr=true в --log-opt.

#dev #projects #guile #smc #fsm

Выпустил релиз Guile-SMC 0.6.1, компилятора конечных автоматов для GNU Guile:
https://github.com/artyom-poptsov/guile-smc/releases/tag/v0.6.1

В новой версии:

- Добавлена возможность установки глобального источника событий для ДКА в разделе legend внутри PlantUML-файла. Например:

legend
event-source: next-char
endlegend

- Команда smc context теперь позволяет установить подтип генерируемого контекста. Если раньше можно было выбрать только из двух вариантов — oop и functional, то сейчас можно использовать такие варианты, как:

oop
oop/generic
oop/port
oop/char
oop/u8
functional
functional/generic
functional/char
functional/u8

Подобная мера позволила сократить объём генерируемого кода для контекста (не берутся те части контекста из Guile-SMC, которые не используются), и кроме того, это позволило решить проблему с дублированием процедур при использовании функционального (functional) контекста, где каждый вариант предоставлял свою копию процедур, но все основные процедуры имели одинаковые имена.

- Исправлена ошибка в процедуре fsm-run!, из-за которой при завершении работы ДКА возвращалась не последнаяя версия контекста, а предыдущая — это приводило к ошибкам работы функциональных вариантов контекста, где контекст не изменялся, а создавался новый на основе предыдущего. В этой ситуации если в конце работы ДКА происходило какое-то заключительное действие с контекстом (например, обновление через действие по выходу из состояния), то данные изменения не были видны. В случае использования ООП-контекста такой проблемы не возникало, так как ООП-контекст использует мутабельные структуры.

- Исправлены ошибки в сериализации/десериализации состояний в модуле (smc core state) — теперь exit-action корректно сохраняется при преобразовании состояния в список, а при обратном преобразовании списка в состояние восстанавливается.

- Обновлена документация.

#dev #projects #guile #smc #fsm