SoftCraft
разноликое программирование

Отправная точка
Программирование
Windows API
Автоматы
Нейроинформатика
Парадигмы
Параллелизм
Проектирование
Теория
Техника кодирования
Трансляторы
Учебный процесс
Прочие вопросы

Разное

Беллетристика
Брюзжалки
Цели и задачи
Об авторе


Функциональная модель параллельных вычислений и язык программирования "Пифагор"


[ <<< | Содержание | Предисловие | Введение | 1 | 2 | 3 | 4 | 5 | Заключение | П1 | П2 | П2 | Источники | >>> ]


© 2002-2003 А.И. Легалов, Ф.А. Казаков, Д.А. Кузьмин, Д.В. Привалихин

Предисловие

31.01.2002. Пришествие первое

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

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

Работа имеет бородатую историю. Первые рецидивы болезни, называемой параллеломанией, у меня появились еще в 1980 г. При подготовке в аспирантуру, наряду с традиционным чтением книги Энслоу [МВС], я случайно наткнулся на двухстраничную журнальную статью по процессору потока данных Денниса (сей эпохальный источник утерян). Идея настолько захватила, что три последующих года я только и занимался принципами их организации. За это время у меня скопилась картотека на пару тысяч публикаций и несколько коробок из под «Беломора» с ксерокопиями статей (не путайте с коробкой из под ксерокса). Этот балласт, составивший большую часть багажа, затем переехал со мной из Ленинграда в Красноярск, где, в связи с потерей актуальности был успешно использован для черновиков (обратная сторона бумаги была чистой).

Однако, принципы организации потоковых вычислений, а особенно модель потока данных Денниса [Dennis, Деннис, Алгоритмы, Майерс], надолго засели в голове и не давали спокойно заниматься другими делами. Интерес к теме подогревался и лекцией Бэкуса [Backus], раскрывающей особенности функционального языка FP, использующего программо-формирующие операции.

Очередное обострение болезни вылилось в авантюрное мероприятие: переезд в Ярославль на работу в Институт проблем вычислительной техники (ИПВТ) АН СССР (1989 год). В ходе работы над языком параллельного программирования, обобщающим семейство рекурсивно-параллельных архитектур, в голову пришла мысль о создании языка, позволяющего писать программы с неявно задаваемым максимальным параллелизмом, последующая адаптация которых к реальным архитектурам заключалась бы в сжатии этого параллелизма в соответствии с существующими ресурсными ограничениями. То есть, идея была противоположной автоматическому распараллеливанию последовательных программ.

Основной задачей, решаемой при построении такого языка, является создание текстового представления программы, воспринимаемого человеком. Не существует проблем в описании параллельных программ в виде графа. Однако построение языка, обеспечивающего поддержку управления на основе потока данных, опирающегося на модель вычислений с бесконечными ресурсами, проходило не столь гладко. В начале 90-хх общая структура языка «Пифагор» (Pifagor), вылившаяся в наброски синтаксических диаграмм и даже фрагменты транслятора (в последствии заброшенные), была сформирована.

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

Другим вдохновителем при создании языка с желаемыми свойствами явился функциональный стиль программирования. Наибольшее влияние оказала работа Бэкуса, определяющая язык FP. Самым впечатляющим была компактная и лаконичная запись функциональной программы. Однако данный язык не устраивал меня, так как не обеспечивал поддержку выполнения функций по готовности данных.

Основное решение было найдено в использовании операции интерпретации, которая позволяла рассматривать любой программный объект как функцию или данные. Уже позже, на основе анализа получаемых текстов программ, была разработана соответствующая модель вычислений. Самое забавное в том, что подобная метафора тоже может иметь аналогии в реальной жизни. Так что, весь мир – это не только ОО агенты.

Последующие события привели в 1992 г. к еще одному аналогу пожара, связанному с обратным переездом. Для языка это обернулось активным подключением к работе Ф. Казакова и Д. Кузьмина. В ходе перекрестных пыток (соображений на троих) были окончательно сформированы аксиоматика и алгебра преобразований (по аналогии с FP). В это же время мною была впервые перечитана Тьюринговская лекция Бэкуса в русском переводе. В 1995 г. появилось описание языка и его модели вычислений, которые затем мало изменились за прошедшее время.

В дальнейшем работа приняла застойный характер, что обуславливалось постоянным стремлением всех ее участников выжить за счет разношерстных халтур. Ряд весьма сырых реализаций языка, сделанных в ходе дипломного проектирования даже не привлек к себе нашего общего внимания. В 2001 году Д. Привалихин написал транслятор и интерпретирующую среду, используемые для выполнения простых программ. Эта система, являвшаяся консольным приложением, была результатом его дипломной работы. Позже им была написана оболочка, что привело к формированию окончательной версии системы, понемногу развиваемой в настоящее время.

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

«Параллельный Информационно- Функциональный АлГОРитмический»

или

«Parallel Informational and Functional AlGORthmic».

Величина получившегося имени как-то не позволяла совести явно заявить его в ранних публикациях. Появился даже алиас «Smile», намекающий на то, что в тексте языка достаточно часто появляются комбинации символов, складывающиеся в смайлики. Однако существование исходного названия более десяти лет, а также ориентация не только на текстовое представление языка, не позволили, в последний момент, изменить внутренним убеждениям и заставили пойти наперекор совести.

Данный язык вряд ли приобретет массовую популярность. Скорее всего, материал будет интересен только другим «чудакам в квадрате». Надеюсь, что (помимо меня) таковые еще существуют. Но, на наш взгляд, модель вычислений и некоторые принципы построения параллельных программ являются оригинальными и могут представлять общий интерес.

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

За всех отписал А.Л.


31.05.2003. Пришествие второе

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

В результате затяжных, но не интенсивных боев, проходивших с переменным успехом, в язык удалось частично внедрить: работы с предопределенными типами данных, возможность использования пользовательских типов, перегрузку функций с одинаковой сигнатурой. Наряду с продолжением работ над последовательным интерпретатором. Начата и дала первые результаты попытка реального параллельного выполнения программ с использованием Mosix. Правда, приходится констатировать, что там постоянно приходится использовать более старую версию языка. Один процесс просто не поспевает за другим. Итак, жизнь вокруг языка продолжается. А ее результаты будут понемногу обнародованы.

Первым шагом на этом пути является обновление документации и замена версии системы. Увеличилось и количество программ, пытающихся сделать вид, что система частично работоспособна. Изменилась несколько и стратегия подачи. Учитывая то, что язык постоянно изменяется, а времени и ресурсов на обновление нескольких форм документации постоянно не хватает, было принято решение о представлении основного материала только в варианте рабочего документа. Приношу свои извинения за замену некоторых html-страниц на документы в формате pdf.

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

В очередной раз за крайнего А.Л.


[ <<< | Содержание | Предисловие | Введение | 1 | 2 | 3 | 4 | 5 | Заключение | П1 | П2 | П2 | Источники | >>> ]