Предлагаю читателям Хабра очередной "эзотерический" язык программирования, обобщающий нормальные алгоритмы Маркова (НАМ) и полусистемы Акселя Туэ (semi-Thue systems). В языке есть возможность интерактивного ввода и вывода, выбора поиска замены подстрок с начала, конца строки или случайным образом, условного рекурсивного вызова одного блока подстановок из другого, а также условного перехода между блоками. Это позволяет совмещать подстановку строк с элементами императивного и даже функционального программирования, а также исследовать недетерминированные алгоритмы.
Интерпретатор написан на языке Common Lisp, который я считаю одним из самых мощных и удобных, в том числе для экспериментальногого программирования. При желании большого труда не составит переписать его на любом популярном языке: например, сделать онлайновую версию в Javascript. Просто для запуска программ Лисп знать практически не нужно: достаточно инсталлировать любую версию Common Lisp и ввести нужный файл парой простых функций. Скачать репозиторий интерпретатора Marthue можно здесь:
https://github.com/yoelmatveyev/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 - поиск позиции случайным образом. При этом правила в алгоритмах Маркова все равно выбираются по порядку. Специально обозначать поиск правил снизу вверх смысла нет, поскольку их можно изначально записать задом наперед.
Метка пишется через как минимум один пробел и может содержать практически любые символы, кроме маркеров :: и ->. Строка с меткой без описания должна начинаться с пробелов.
Каждое правило подстановки содержит ->, но может также содержать описание контрольных структур, тоже обозначаемых маркером :: с возможной меткой:
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. На сегодня там пара десятков примеров со ссылками на источники, включая пару алгоритмов с Хабра.