Туэ (язык программирования) - Thue (programming language)

Чт (/ˈтueɪ/ ТОЖЕ-ай ) является эзотерический язык программирования изобретен Джоном Колагиоа в начале 2000 года. Это метаязык, который можно использовать для определения или распознавания языков типа 0 из Иерархия Хомского. Поскольку он может определять языки такой сложности, он также Полный по Тьюрингу сам. Thue основан на недетерминированный система перезаписи строк называется полутхуэ грамматика, который назван в честь норвежский язык математик Аксель Туэ. Автор описывает это следующим образом: «Туэ представляет собой один из простейших возможных способов толкования программирование на основе ограничений. Языки любят парадигму, основанную на ограничениях. OISC относятся к императивной парадигме; другими словами, это битумная яма."

Правила производства

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

lhs ::= rhs

База правил заканчивается одиночным производственным символом на строке:

::=

Начальное состояние - это последовательность символов, следующих за базой правил.

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

Thue завершается, когда lhs не может быть найден в результирующем состоянии.

Смотрите также

Примечания

  • ::= произносится возможно.
  • lhs это «левая сторона».
  • rhs это «правая сторона».
  • "::=" никогда не может быть левым.
  • «:::» - это входной поток.
  • «~» - это выходной поток.
  • Системы Полутуэ изоморфны неограниченная грамматика.

Вызов Туэ

При вызове с 'd' (отладка) распечатайте состояние. При вызове с 'l' (левая сторона) примените правила слева направо. При вызове с 'r' (правая сторона) примените правила справа- влево. Последние 'l' или 'r' отменяют предыдущие переключатели.

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

Вот традиционное "Hello World!" в чт:

a :: = ~ Привет, мир! :: = a

Следующая программа Thue выполняет приращение двоичного числа, введенного как начальное состояние, окруженного символами «_», в данном случае числа 1111111111:

1_::=1++0_::=101++::=1011++::=1++0_0::=__1++::=10__::=1::=_1111111111_

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

b :: = ~ 0b :: = ~ 1ac :: = abc :: = abc

внешняя ссылка