Piet

Piet (назван в честь художника Пита Мондриана (Piet Mondrian)) — один из известнейших эзотерических языков программирования, использующих изображения в качестве исходного кода. В языке используется 20 цветов, и команды задаются переходами между цветами.

Piet был создан Дейвидом Морган-Маром (David Morgan-Mar) с целью создания языка, код на котором выглядел бы как абстрактные картины. Язык не породил диалектов; существует ряд реализаций, несколько отличающихся в нюансах обработки цветов. Доказательство Тьюринг-полноты не проводилось.

Язык использует модель, состоящую из следующих элементов:

• программа — двухмерное изображение, состоящее из отдельных пикселей. Пиксели могут быть любых цветов, но элементами программы являются только 20 из них: черный, белый и 18 цветов, организованных в таблицу (см. рис.) по оттенку и яркости. Связные группы пикселей одного цвета называются блоками и являются минимальными единицами конструирования программ. Отметим, что программы на Piet часто рассматриваются в увеличенном виде; в таком случае группа пикселей, соответствующая одному пикселю исходной программы, называется кодел.
• память — организована как стек. Единственным типом данных в Piet являются целые числа. Символы можно обрабатывать как их ASCII-коды.
• указатель инструкций. В отличие от более простых языков, в Piet указатель инструкций имеет сложную структуру и состоит из указателя на текущий блок (понятия текущего пикселя в блоке нет), указателя направления (Direction Pointer — может указывать влево, вправо, вверх или вниз) и указателя выбора коделов (Codel Chooser — может указывать только влево или вправо, причем направление отсчитывается относительно DP).

Движение указателя инструкций по программе и ее интерпретация выполняются следующим образом. Для текущего блока находится его край в направлении DP (этот край может не быть непрерывным, если блок сложной формы). Из всех пикселей, образующих этот край, выбирается крайний в направлении, указанном CC (либо самый левый, либо самый правый относительно DP). Из этого пикселя указатель инструкций переходит в соседний в направлении DP. Смена цветов при смене текущего блока определяет следующую команду.

В общем случае при смене блока направление указателей не меняется. Меняется оно, когда очередной блок оказывается черным. Черные блоки являются ограничителями программы и управляющими структурами, перейти в них невозможно. Если следующий блок — черный, то переход в него не выполняется, вместо этого меняется направление указателей — сначала CC, потом DP, и так до тех пор, пока переход не будет в цветной блок. Кроме того, выполнение команд pointer и switch меняет направление указателей.

Таблица соответствия переходов между цветами и команд.

Смена             Смена яркости
оттенка  Нет        -1          -2
  0                 push        pop
  1     add         subtract    multiply
  2     divide      mod         not
  3     greater     pointer     switch
  4     duplicate   roll        in(int)
  5     in(char)    out(int)    out(char)

Список команд:

• push: добавляет в стек количество пикселей в блоке, из которого произошел переход. Отрицательные и нулевые значения в стек могут попасть только как результат арифметических операций.
• pop: извлекает элемент из стека и выбрасывает его.
• add, subtract, multiply, divide, mod: извлекает из стека два верхних элемента, выполняет соответствующую операцию и добавляет результат в стек. Первым операндом является элемент, который был глубже в стеке.
• not: заменяет верхний элемент стека на 0, если он был не нулевым, и на 1 в противном случае.
• greater: извлекает из стека два верхних элемента и добавляет в него 1, если более глубокое значение больше, и 0 в противном случае.
• pointer: извлекает из стека элемент и поворачивает DP на (90*значение) градусов по часовой стрелке (для отрицательных значений — против часовой).
• switch: извлекает из стека элемент и меняет направление CC на противоположное, если элемент нечетный.
• duplicate: добавляет в стек копию его верхнего элемента.
• roll: извлекает из стека верхнее значение M и следующее за ним N и выполняет M операций roll на глубину N каждая. Одна операция roll на глубину N определяется как перемещение верхнего элемента стека на N элементов в глубину стека и перемещение всех элементов выше N на 1 вверх. Глубина N не может быть отрицательной, тогда как количество операций M может быть (тогда roll выполняется в обратном направлении).
• in: читает из потока ввода значение (число или ASCII-код символа в зависимости от типа команды) и добавляет его в стек.
• out: извлекает элемент из стека и выводит его на печать как число или символ в зависимости от типа команды.

Команды, которые выполнить невозможно, просто игнорируются.