Thue

Thue (/ˈtuːeɪ/) — эзотерический язык программирования, разработанный Джоном Колагойя^[англ.] в начале 2000 года. Это мета-язык, который демонстрирует нулевой тип в иерархии Хомского, то есть неограниченную грамматику. Thue позволяет определять любые языки и является полным по Тьюрингу.

Автор описывает его следующим образом: «Thue представляет собой простейшую демонстрацию программирования в ограничениях. Именно за счёт этой парадигмы язык аналогичен языкам URISC императивной парадигмы. Другими словами это Тьюринговская трясина».

Правила

Программа на языке Thue состоит из таблицы правил и начального состояния. Таблица правил состоит из простых определений вида

A ::= B

A и B могут состоять как из отдельных букв и символов так и из их групп. Может существовать множество правил с одинаковым A и разными B. Таблица правил заканчивается пустым правилом:

::=

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

Работа программы состоит в поиске исходных (левых) символов и замене их на правые в соответствии с правилом.

Работа завершается когда к строке нельзя применить ни одного правила.

Таким образом программа на Thue аналогична машине Тьюринга: имеется лента символов и имеется набор правил по которым они заменяются.

Недетерминированность

Одна из ключевых особенностей языка заключается в недетерминированном порядке выбора.

Если в строке имеется несколько символов, к которым может быть применено правило, то оно будет применено к случайно выбранному символу.

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

Ввод / вывод

Для реализации ввода и вывода в языке есть особая форма правил. Для вывода символов используется тильда:

A::=~строка символов

Это правило убирает A из строки и выводит все символы, идущие после тильды.

Для ввода три двоеточия:

A::=:::

Это правило заменяет A на строку, прочитанную из ввода.

Примеры программ

«Hello World!» на Thue:

a::=~Hello World!
::=
a

В языке нет переменных как понятия. Поэтому для каких-либо вычислений нужно задавать соответствующие системы правил. Следующая программа демонстрирует инкрементацию двоичного числа (увеличение на единицу). Число записано символьно и отмечено по краям знаком подчёркивания:

1_::=1++
0_::=1

01++::=10
11++::=1++0

_0::=_
_1++::=10

::=

_1111111111_

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

Следующая программа демонстрирует реализацию циклов и недетерминизм правил:

b::=~0
b::=~1
xx::=xbx
::=
xbx

Эта программа выводит бесконечную строку единиц и нулей. Цикличность обеспечивается следующим образом: после каждого вывода символ b удаляется из строки xbx, оставшиеся символы xx заменяются на xbx, воспроизводя начальное состояние. Таким образом возможно создание ограниченных циклов, число итераций которых задаётся числом определённых символов или наборов символов в строке:

_x::=i_
i::=~test!
::=
_xxxxx

Эта программа 5 раз выведет строку test! Обратите внимание, что порядок замены i и _x при этом неопределён. То есть в процессе выполнения программа может как сразу обрабатывать i по мере их появления, так и выбрать из строки все x сразу.