Предлагаю читателям Хабра "эзотерический" язык программирования, удобно обобщающий и совмещающий нормальные алгоритмы Маркова (НАМ) и полусистемы Акселя Туэ (semi-Thue systems). В языке есть возможность интерактивного ввода и вывода, выбора поиска замены подстрок с начала, конца строки или случайным образом, условного рекурсивного вызова одного блока подстановок из другого, а также условного перехода между блоками. Это позволяет совмещать подстановку строк с элементами императивного и даже функционального программирования, а также исследовать недетерминированные алгоритмы.

Интерпретатор написан на языке Common Lisp, который я считаю одним из самых мощных и удобных, в том числе для экспериментальногого программирования. При желании большого труда не составит переписать его на любом популярном языке: например, сделать онлайновую версию в Javascript. Просто для запуска программ Лисп знать практически не нужно: достаточно инсталлировать любую версию Common Lisp и ввести нужный файл парой простых функций. Скачать репозиторий интерпретатора Marthue можно здесь.

История

В 1914 году норвежский математик Аксель Туэ предложил простую формальную систему, кортеж {Σ, R}, состоящий из конечного алфавита Σ и бинарного отношения между множеством всех возможных строк Σ*, которое представляет собой список допустимых замен подстрок. Если допустимы замены в обе стороны, такое отношение называется полной системой Туэ; если только в одну сторону, то полусистемой. Полная система полезна для исследования моноидов, но в информатике обычно рассматривается полусистема, в которой "выходная" замена может быть и пустой. Одна из основных задач, поставленных Туэ, состояла в решении вопроса, входит ли то или иное слово во множество всех возможных результатов подстановок по данному списку. К примеру, исследуем следующее отношение и применяем его к алфавиту {a,b,c}:

{a→ccba, bc→aa, ca→∅, acb→c, cc→b}

Из "a" выводится любая строка, в том числе и пустая (проверьте), однако из "b" и "с" не выводится ничего. В 1947 году, независимо друг от друга, Эмиль Пост и Андрей Марков (младший) доказали неразрешимость выводимости заданной строки в общем случае. Идея доказательства в том, что системы подстановки строк позволяют моделировать любую машину Тьюринга. Отсюда следует, что они обладают полнотой по Тьюрингу и в принципе пригодны для вычислений любой сложности. Марков предложил так называемый "нормальный" алгоритм подстановки строк, в котором на каждом шаге первая подходящая подстановка в списке применяется к первой подходящей позиции в строке слева направа. Помимо дальнейшей невозможности применить какую-либо подстановку, некоторые ключевые подстроки в списке могут служить стоп-сигналами для завершения вычисления.

Если мы применим приведенный выше список подстановок к строке "a" по алгоритму Маркова, то получим бесконечно растущую последовательность "ccba", "ccbccba", "ccbccbccba"... Однако, поскольку в его алгоритме список подстановок строго упорядочен, при изменении его порядка получаем совсем другой результат. Берем ту же строку "a" и применяем следующий упорядоченный список:

{bc→aa, acb→c, ca→∅, a→ccba, cc→b}

За 6 шагов получаем "c". Пишем иначе:

{ca→∅, acb→c, bc→aa, a→ccba, cc→b}

Теперь наша строка за 10 шагов просто изчезает.

Если отклониться от "нормального" алгоритма и применить подстановки случайным образом в случайном месте, за 3 шага мы можем получить 7 различных результатов:

{bba, bbccba, ccaacba, ccba, ccbbba, ccbccba, ccbccbccba)

Тем не менее, при правильном выборе системы подстановок и начальной строки вывод на каждом следующем шаге может быть вполне однозначным. Еще интереснее недетерминированные алгоритмы, которые всегда приводят к однозначному результату, независимо от маршрута вычисления. Американский программист Джон Колагойя придумал в 2000 году язык Thue, который на каждом шаге случайным образом выбирает одну из возможных подстановок. Для одной и той же подстроки можно там задать сколько угодно альтернативных правил, выбираемых с равной вероятностью. Некоторые правила также могут вызвать вывод произвольного текста; исходная ключевая подстрока при этом удаляется. Другие подстроки вызывают ввод и заменяются введенной с клавиатуры строкой. На этом языке, помимо прочего, написан интерпретатор известного эзотерического языка BrainFuck. Интересны в этом интерпретаторе списки подстановок строк, позволяющие анализировать многократно вложенные скобки и другие элементы синтаксиса, а также реализация условных переходов, которые в принципе могут быть использованы для реализации более серьезных языков.

Из-за очевидной близости языка Thue к алгоритмам Маркова у меня еще два года назад возникла идея их совмещения и обобщения в язык несколько более высокого уровня. Marthue позволяет запускать как все найденные мной в сети программы Thue, так и большинство алгоритмов Маркова. Несколько моих знакомых недавно заинтересовались этой небольшой разработкой, поэтому я решил ее описать здесь по-русски (ранее было написано краткое описание только на английском). Полную совместимость с любыми валяющимися в сети алгоритмами Маркова без модификации не гарантирую, поскольку там иногда используется несколько разный синтаксис.

Краткое описание

Программа Marthue состоит из блоков, каждый из которых состоит из опционального описания блока, опциональной метки и символов :: , которыми обозначаются все контрольные структуры языка. Описания могут включать следующие буквы, в том числе и несколько букв подряд в любом порядке:

М - алгоритм Маркова (по желанию; любой блок по умолчанию считается алгоритмом Маркова.
T - алгоритм Thue.
F (Forward) - поиск первой позиции для подстановки слева направо. Актуально только для алгоритмов Thue. Декларация TF означает, что правила выбираются случайным образом, однако позиции для подстановки детерминированы.
B (Back) - поиск первой позиции справа налево. Действует аналогично в обоих типах алгоритмов.
X или FB - поиск позиции случайным образом. При этом правила в алгоритмах Маркова все равно выбираются по порядку. Специально обозначать поиск правил снизу вверх смысла нет, поскольку их можно изначально записать задом наперед.

Метка пишется через как минимум один пробел и может содержать практически любые символы, кроме маркеров :: и ->. Строка с меткой без описания должна начинаться с пробелов. Для удобства чтения программы лучше перед пробелами поставить какой-нибудь символ, не совпадающий с ключами описания. Например:

_ Label1::

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

F (Forward) - поиск замены слева направо.
B (Back) - поиск замены справа налево.
X или FB - поиск случайной позиции.
I (Input) - ввод. При наличии строки для подстановки она сохраняется, а введенная строка добавляется справа, слева от нее или со случайно выбранной стороны, если добавлена и декларация направления. Например, IB или IX.
O (Output) - вывод. Если скомбинировать IO, строка справа от -> выводится, а исходная заменяется на введенную.
N (Next) - при отсутствии метки переход на следующий блок, при наличии - условный переход. Условиям является сама подстрока, которая его вызывает. Перед переходом она заменяется на указанную справа. При отсутствии указанной метки вся программа останавливается. Это не обязательно ошибка: несуществующая метка удобна для немедленного останова. Стек возвратов при переходе сохраняется.
C (Call) - вызов блока по метке. Исходный адрес блока записывается с стек возвратов. Блок может быть и без метки. Не обязательно указывать эту букву, поскольку метка внутри блока по умолчанию означает вызов. Он может быть рекурсивным, но попытка вызова того же блока из самого себя игнорируется, поскольку в нашей системе подстановок строк эта операция бессмысленна и только засорила бы стек.
R (Return) - возвращение из вызова. При наличии метки действует как специальный оператор (return-from) в Common Lisp: ищется метка в стеке возвратов и управление передается сразу на нее, игнорируя промежуточные вызовы. При отсутствии соответствующей метки попытка перейти на нее игнорируется. При пустом стеке происходит останов всей программы.
NR - тоже возвращение из вызова. При отсутствии соответствующей метки или при пустом стеке происходит переход к следующему блоку.

Бессмысленные сочетания CR и NC не определены (на практике CR интерпретируется на данный момент как R, CN как C, а CNR как R).

Маркер ->. с точкой обозначает, как в стандартном синтаксисе алгоритмов Маркова, завершение вычисления, в нашем случае выход из блока и переход в следующий. При наличии метки интерпретируется не как вызов, но как переход в соответствующий блок.

Внутри блока метка с пустым описанием тоже должна предваряться кк минимум одним пробелом. Опять же, для удобства чтения лучше поставить перед пробелами какой-нибудь символ, не совпадающий с ключами описания. \n обозначает перенос. Сочетания :: и -> можно использовать и в самих строках, но через \. Чтобы вставить \:, \- или \>, пишите \\:, \\- или \\>.

Любая строка, не содержащая :: или ->, интерпретируется как комментарий. Комментарии можно также начинать с #::. Последняя строка, если в ней нет маркеров, интерпретируется как начальная. Во избежание путаницы, программы Marthue следует записывать с расширением mrt, чистые алгоритмы Маркова - с расширением m, а программы Thue традиционно имеют расширение t.

Примеры

Случайным образом выбрать вариант вывода:

T::
->.Hello!
->.HELLO WORLD!
->.Hello, World!

Ввести двоичное число, уменьшить его на 1 алгоритмом Маркова, вывести результат, затем спросить, хотим ли мы попробовать другое число:

_ Begin::
ON::->Input a binary number:
::
IN::->
::
N::->_
B::
N::->_
T::
0_->0--
1_->0
10--->01
00--->0--1
_1--->@
_0--->1
_0->

::

1->*1
0->*0
O::*1->1
O::*0->0
_->

:: Print the result
1->*1
0->*0
O::*1->1
O::*0->0
_->
# Try again?
::
O::->.\nTry again? (y/n)
::
I::->.
::
_ Begin::y->.
_ End::n->.

Вычислить цифровой корень введенного натурального числа и вывести результат. Автор алгоритма - некто Keymaker. Изначально написан в Thue, работает без изменений и как алгоритм Маркова.

::
O::->.Enter a natural decimal number:
::
->..abc.
T::
I::b->
0->
1->!
2->!!
3->!!!
4->!!!!
5->!!!!!
6->!!!!!!
7->!!!!!!!
8->!!!!!!!!
9->!!!!!!!!!
!!!!!!!!!!->!
O::a!!!!!!!!!c->9
O::a!!!!!!!!c->8
O::a!!!!!!!c->7
O::a!!!!!!c->6
O::a!!!!!c->5
O::a!!!!c->4
O::a!!!c->3
O::a!!c->2
O::a!c->1
O::ac->0
O::..->

Использование

Самый простой способ загрузки и запуска программ - макросы (load-run) и (load-program), а также функция (run). Загружаете в REPL (интерактивном шелле Лиспа) пакет интерпретатора или просто интерпретатор без отдельного пакета.

>(asdf:load-system 'marthue)

>(load "marthue-no-package.lisp")

Чтобы загрузить и сразу запустить программу:

>(load-run program1 "program1")

При этом загружается файл program1.mrt, создается объект program1 и запускается программа. Чтобы перезапустить и после останова подготовить к перезапуску:

>(run program1 :reset t)

К слову, самый лучший открытый и бесплатный Лисп - SBCL:

http://www.sbcl.org/

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

Практическое применение

В отличие от забавных, но в целом малополезных "трясин Тьюринга" типа BrainFuck, алгоритмы Маркова - стандартный, хорошо изученный инструмент дискретной математики и теории алгоритмов. На Западе они менее известны, зато популярна полусистема Туэ, которая соответствует неограниченным грамматикам типа 0 по Хомскому. Язык Marthue позволяет практически моделировать рекурсивно определяемые абстрактные языки. Разумеется, он интересен и в качестве головоломки.

Лисп чрезвычайно удобен для написания небольших импровизированных программ "на лету". Если взять приведенный выше пример с алфавитом из 3 букв и 5 подстановками, можно интерактивно исследовать поведение случайных цепочек подстановок. В интерпретаторе Marthue есть возможность пошагового исполнения программ и подключения внешних функций для наблюдения за исполнением. Например, если на всякий случай достаточно долго, сотни миллионов раз, применить 8 шагов случайных подстановок к a, получаем список из 2136 возможных результатов подстановок. Из них терминальная только c. Она получается единственным способом за 6 шагов. Чтобы получить пустую строку, нужно 10 шагов, а чтобы получить b - 13. Например, по такому маршруту из многих возможных, который моментально находится случайным поиском:

a
ccba
bba
bbccba
baacba
baacbccba
bacccba
bacccbccba
bacccaacba
bacccaca
baccca
bacba
bca
b

В репозитории я надеюсь собрать как можно более обширную коллекцию алгоритмов Маркова и программ на языке Thue, параллельно с их вариантами в Marthue. На сегодня там пара десятков примеров со ссылками на источники, включая пару алгоритмов с Хабра.