Программистская игрушка

[plakhov]

Придумал очень красивую штуку, чисто программистскую, остальным будет неинтересно.

Каждому программисту известно, что такое регулярные выражения. Каждому человеку, прошедшему базовый курс CS, известно, что базовые регулярные выражения (без backtracking-а) хорошо моделируются недетерминированными конечными автоматамиВ интересах этой записи

Comments

[soloviewoff]

А потом приходит кто-нибудь и говорит: "короче, надо, чтобы можно было ключи копить и постепенно тратить на двери". А мы такие: "ну, мы такое сейчас не сможем - у нас регулярный язык, а тут context free / pushdown automata уже нужен, это все переписывать" :) Вечная дилемма to DSL or not to DSL...

[plakhov]

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

Я еще думаю над тем, какие на самом деле языки так можно распознавать и нельзя ли из этого всё-таки извлечь пользу.

[soloviewoff]

"Чуть сильнее регулярных языков" не очень понятно. Язык RE же регулярный - т.е. FA без памяти. Какой бы ни был алгоритм матчинга сложность решаемых вычислительных задач определяется мощностью языка, нет?

[plakhov]

Это довольно любопытная история. Сложность решаемых задач определяется мощностью языка в смысле ХХ века ("множества решаемых задач совпадают"), но не в смысле XXI века ("множества эффективно решаемых задач совпадают

[slobin]

Мне кажется, у Вас нечаянно CSP Хоара получилось (то самое, на чём в рекламе основаны всякие Оккамы и Голанги... хотя, если почитать исходную книжку (переведена и издана ещё в СССР), то там это очень хитро запрятано).

Регулярное выражение -- направленный граф (когда мы его рисуем в виде "синтаксических диаграмм", это очень наглядно). Пусть мы матчим не текст, а другой направленный граф. Некоторые вершины первого графа соответствуют некоторым вершинам второго графа. Нужно выяснить, существует ли последовательность вершин, являющаяся путём в обоих графах. Так, не так?

... Правовой нигилизм и компьютерная грамотность ...

[slobin]

Я, пожалуй, наберусь наглости и кратко изложу CSP как я её понимаю (если вы хотите узнать, как её понимает сам Хоар - почитайте книжку, она доступна!). Потому что утверждение "каналы в Go основаны на CSP" верно примерно так же, как "строительство мостов основано на теории множеств". Ну да, основано. Через сопромат, теормех, матан и теорию вещественных чисел (ну, это примерно :-). А самые основы выглядят, если на пальцах, так

[plakhov]

Спасибо! Книжку про CSP я по рекомендации Руслана Абдикеева читал когда-то давным-давно, но я совершенно не помню в ней обсуждения конкретных алгоритмов определения того, совместимы ли два недетерминированных конечных автомата. Сам формализм в CSP гораздо богаче (например, недетерминизм там шире, чем в автоматах, ближе к https://en.wikipedia.org/wiki/Transition_system). Так что универсального алгоритма, я так подозреваю, и нет. Иначе непонятно, почему бы было много разных тулзов для CSP, в том числе коммерческих.

Впрочем, в главном-то вы правы, аналогия действительно очень классная.

[clayrat]

есть расширения протоколов/сессионных типов на КСГ, в частности http://rss.di.fc.ul.pt/tools/freest/

[jakobz]

Интересно, а это можно как-то отцепить от синтаксиса регулярок, в какую-то монаду/eDSL? Ну типа также как вместо регексов можно брать parser combinators.

Можно из этого получить некий красивый паттерн того, как построить некий map/reduce-like API для depth/breadth-first search? Чтобы один и тот же подход юзать и для поиска пути, и для поиска каких-то паттернов, и может для каких-нибудь там частичных сумм весов узлов...

[rdia]

Методу широко применяют в компиляторах (как мне рассказали):

1. Для peephole выбора инструкций на уровне ассемблера.

2. Техника статического анализа, применяющая контекстно-свободный парсер к графу переходов функции (CFG) (regular path querying и context-free path querying соответственно)