Система программирования Piet

Содержание

Введение. 2

Глава 1. Описание языка Piet. 3

Что такое язык PIET? 3

Бесполезные или эзотерические? 3

Простой ЭЯП, не полный по Тьюрингу 4

Классификация полных ЭЯП 4

Многомерное программирование 5

Программист Пит Мондриан 6

Основы языка Цвета 6

Коделы 7

Стек 7

Исполнение программ на Piet 8

Другие элементы синтаксиса 9

Глава 2. Программирование на Piet 12

Интерпретатор npiet 12

Среда npietedit 12

Первая программа 12

Как читать трассировку 15

Более сложные программы 16

Заключение 17

Список литературы. 21

Приложения 22

 

 

 

 

Введение

Давно минули времена, когда программирование вычислительных машин выражало строгий язык математики и было уделом профессионалов, представлявших с помощью компьютерных программ серьезные технические задачи. Еще 20-30 лет назад мало кто мог подумать о том, чтобы написать программу, не несущую никакой, с виду, практической пользы. Однако с развитием как самой науки "computer science", так и вычислительной техники в целом множество энтузиастов начало ставить всевозможные эксперименты той или иной степени сумасбродности. Целью подобных экспериментов было выяснение пределов сведения информатики как таковой ad absurdum: создание фантастических языков программирования, сложных для чтения, компиляции, написания программ или всего перечисленного сразу, выдумывание хитроумных логических и математических концепций, реализация невероятно запутанных программных систем и многое другое. Любители головоломок и задач на смекалку получили полную свободу в разминке своего ума с помощью ЭВМ, а специалистам-ученым предоставилась прекрасная возможность понаблюдать за "поведением" компьютеров, как искусственных артефактов, в непредсказуемых условиях. В связи с вышесказанным, актуальной видится тема нашей работы: “Система программирования Piet.” Цель работы: рассмотреть основы эзотерического ЯП Piet. Для достижения поставленной цели необходимо решить следующие задачи:

1. Выявить особенность эзотерического направления.
2. Рассмотреть ЯП Piet.
3. Привести пример решения типичных задач программирование на Piet.

Глава 1. Описание языка Piet

Что такое язык PIET?

Piet — эзотерический язык программирования разработанный Давидом Морган-Маром. Язык Piet использует разноцветные изображения в качестве программ. Программа на Piet выглядит как постживописная абстракция. Piet получил своё название от имени нидерландского художника Пита Мондриана.

Бесполезные или эзотерические?

Стремление человека к  созданию странных, внешне нерациональных и даже бессмысленных объектов и  предметов присутствовало, пожалуй, во все времена. XX век, привнесший невиданное до этого развитие абстрактной математики и средств моделирования, открыл простор для человеческой фантазии.Языки программирования — искусственные языки, целью разработки которых изначально было составление "планов" или "программ" для вычислительных машин. На заре информатики единственными важными качествами любого вид и эффективность работы откомпилированной программы (в первую очередь), а также удобство языка для человека и соответствие его некоторым математическим или философским концепциям. Через некоторое время подобное положение дел наскучило любящим всяческие головоломки математикам, что дало толчок к созданию необычных средств программирования.Языки, которые при первом рассмотрении не имеют никакой практической полезности, то есть отходят от всех общепризнанных парадигм программирования, принято называть эзотерическими.  Как было замеченно ранее, такие языки могут применяться для изучения границ математических и лингвистических концепций, экспериментирования с необычными идеями, в качестве своеобразной гимнастики для ума или просто в роли шутки. В связи с этим стоит разделить все эзотерические языки программирования (ЭЯП) на два класса: тьюринг-полные и тьюринг-неполные. Несмотря на то, что такое разделение привычно для всех, в том числе и не эзотерических, языков программирования, в сфере ЭЯП оно носит более глобальный характер: как правило, тьюринг-неполные ЭЯП вообще непригодны для чего-либо и являются лишь пародиями или утрированными шутками.ЭЯП полные по Тьюрингу обычно представляют собой тьюринговские трясины: несмотря на то, что с их помощью можно вычислить все что угодно, сделать это необычайно трудно — здесь объект нашего рассмотрения, Piet, является ярким примером.

Простой ЭЯП, не полный по Тьюрингу

Одним из простейших эзотерических языков программирования, не обладающих тьюринговской полнотой, является HQ9+, который имеет всего четыре команды:

Н — вывести "hello, world";

Q — вывести исходный код программы (куайн);

9 — вывести текст стихотворения "99 бутылок";

Н увеличить значение регистра-аккумулятора (никаким другим способом не доступен для программиста).

Как легко заметить, на таком  языке даже теоретически невозможно написать какую-либо полезную программу. Подавляющее большинство остальных неполных ЭЯП являются шутливыми вариациями на похожие темы.

Классификация полных ЭЯП

Большинство полных по Тьюрингу эзотерических языков программирования можно разделить на следующие классы (обычно родоначальником каждого класса является один язык):

Семейство INTERCAL. Наиболее яркие представители: INTERCAL, FALSE, Babbage. Основной целью является создание языков, максимально отличных от уже существующих.

Семейство Brainf*ck. Наиболее яркие представители: Brainf*ck, Ook!, Whitespace, BitBitJump. При создании языков этого семейства основное внимание уделяется максимальному сокращению количества управляющих конструкций (инструкций, операторов) при сохранении полноты языка. Существует также похожее направление в проектировании микропроцессоров. Семейство Brainf*ck играет важную роль в оценке полноты "серьезных" ЯП, поскольку сильно приближено к концепции машины Тьюринга. Сюда же можно отнести и минимальные функциональные языки вроде Unlambda, Thue и Lazy К, а также самомодифицирующиеся языки Smetana и Muriel.

Семейство Funge. Наиболее яркие представители семейства: Befunge и его производные, Piet. Основной целью создания таких языков является сложность их компиляции. Как правило, такие ЯП многомерны и используют непривычное кодирование текста программы.

Семейство Malbolge, в котором основным представителем является собственно Malbolge. Главной целью таких языков является максимальная сложность написания программ на них; как правило, это практически неосуществимая задача для человека. Так, к примеру, "Hello world" для Malbolge был сгенерирован программой на языке Lisp.

Недетерминистские языки, вносящие в программирование элементы случайности. Они разнятся от откровенно абсурдных вроде Java2K до довольно полезных, таких как the Dada Engine, позволяющих проводить исследования в областях, требующих случайного поиска, и экспериментах с гипотетическими "супертьюринговскими" вычислениями.

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

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

Многомерное программирование

Поскольку язык Piet относится к семейству так называемых "фунгеоидных" языков, будет нелишне рассмотреть их основные концепции. Язык Befunge был предложен в 1993 году в качестве языка, максимально сложного для компиляции. Основной отличительной особенностью Befunge является то, что код представлен в виде двухмерной таблицы символов, по которой интерпретатор может перемещаться в различных направлениях. Позднее появились вариации языка с представлением кода в виде трехмерных и четырехмерных таблиц. В качестве дальнейшего усложнения можно предложить увеличение числа измерении и возможность движения не в фиксированных дискретных направлениях, а по сложным траекториям. Однако в языке Piet был предложен другой интересный подход.

Программист Пит Мондриан

Уже неоднократно упомянутый ЭЯП Piet  был создан Дэвидом Морганом-Маром, одним из наиболее продуктивных и хитроумных авторов эзотерических языков. Свое название Piet получил в честь голландского художника Пита Мондриана, одного из основателей геометрической абстрактной живописи. Согласно оригинальной задумке, программы на Piet должны выглядеть как абстракционистские картины.

Программы на Piet — это компьютерные изображения, однако правила выполнения кода не столь очевидны, как может показаться сначала, поэтому рассмотрим основные концепции языка.

Основы языка Цвета

Основные цвета, используемые в Piet, показаны в табл. (Приложение 1)

  Согласно первоначальному описанию, используется 20 различных цветов. Восемнадцать цветов в первых трех строках таблицы наделены следующими циклическими отношениями:

Цикл оттенков (слева направо): красный -> желтый -» зеленый -> бирюзовый -» синий —> пурпурный -» красный —» ...

Цикл уровней яркости (сверху вниз): светлый —> обычный —> темный светлый -» ...

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

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

Коделы

Так как программы на Piet являются изображениями, в них важен каждый отдельный пиксель. Однако подобные изображения могут быть слишком маленькими и неудобными для просмотра, поэтому в Piet введено понятие "кодела". Кодел является группой пикселей одного цвета (в самом простом варианте — одним пикселем) и представляет собой "пиксель" в понимании интерпретатора Piet. Это позволяет увеличивать программы на Piet без потери их смысла. Обычно кодел имеет квадратную форму, а его размер регулируется неким принятым соглашением (например, он может быть 8x8 пикселей). При увеличении программ на Piet важно не допустить интерполяции цветов и ненужного "замыливания" изображения. В дальнейшем при разговоре о пикселях будем иметь в виду коделы.

Непрерывный блок смежных  коделов одного цвета является основной составляющей частью программы на Piet. Если коделы смежны только по диагонали, то такой блок не считается непрерывным. В остальном форма блока может быть любой, в том числе иметь внутри себя "дырки", заполненные коделами другого цвета, не входящими в данный блок, а образующими свой собственный. На рис. (Приложение 2) изображены непрерывные блоки коделов в обычном понимании Piet (полость в сложном нижнем блоке не обведена для удобства).

Стек

Основной структурой хранения данных в Piet является стек. Язык подобно Forth — бестиповый, данные существуют только в виде целых неотрицательных чисел, но могут быть интерпретированы разными способами — например, выведены на экран как символы Юникода.

Исполнение программ на Piet

В Piet существует два направляющих регистра. Первый из них — DP (Direction Pointer, Указатель направления) может принимать значения "Север", "Юг", "Запад", "Восток" и по умолчанию указывает на "Восток". Кроме этого, существует второй регистр — СС (Color Chooser, Выборщик цвета), который может принимать значения "Слева" или "Справа" и по умолчанию установлен на "Слева". Направления, на которые указывают эти регистры, могут часто меняться в ходе выполнения программы.

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

Основной цикл обработки  цветовых блоков выглядит следующим образом:

• Интерпретатор находит  границу текущего блока в направлении DP.

Интерпретатор находит наиболее удаленный кодел в данном блоке  в направлении DP, если смотреть в направлении СС.

Интерпретатор пытается перейти  с найденного на предыдущем шаге кодела в соседний цветовой блок в направлении  DP.

Выглядит это довольно запутанно, поэтому необходимо некоторое наглядное пояснение. Представьте, что вы стоите на полу, покрытом разноцветными квадратными плитками (коделы), и смотрите в заданном направлении DP, а в уме держите направление СС. Для начала вам необходимо найти в данном цветовом блоке все такие плитки (коделы), которые наиболее удалены в направлении DP, например, все самые восточные или самые северные. Таких точек может быть несколько, поэтому, чтобы выбрать одну- единственную, надо из всего множества выбрать ту, которая наиболее удалена в направлении DP, скорректированном по СС. Например, если вы нашли все самые северные точки, а СС указывает влево, то надо выбрать среди самых северных самую западную (или самую восточную, если СС указывает вправо). Чуть позже я разберу выполнение реальной программы на Piet, чтобы показать эту концепцию наглядно.

Другие элементы синтаксиса

Числа. Каждый не черный и не белый цветовой блок в Piet представляет целое положительное число, равное количеству коделов в этом блоке. Не положительные числа необходимо специально конструировать с помощью команд, о которых я расскажу позднее. Кроме всего прочего, числа в Piet необходимо явно класть на стек.

Черные блоки и границы. Если на третьем шаге описанного выше цикла интерпретации интерпретатор Piet пытается перейти в черный блок или за границу изображения, он останавливается и изменяет направление СС на противоположное, после чего пытается повторить цикл. Если повторить цикл не удается, то направление DP меняется на 90 градусов по часовой стрелке и производится еще одна попытка. В ходе попыток СС и DP меняются попеременно. Если после восьми попыток интерпретатор не нашел выхода из блока (блок ограничен со всех сторон), программа завершается.