Пифагор (язык программирования)
Пифагор — функционально-потоковый язык программирования, предназначенный для разработки переносимых (архитектурно-независимых) параллельных программ.
| Пифагор | |
|---|---|
| Семантика | функциональный, потоковый |
| Класс языка | язык программирования |
| Появился в | 1995 |
| Автор | Легалов Александр Иванович [1] |
| Система типов | динамическая |
| Испытал влияние | Haskell, Sisal |
История
правитьЯзык «Пифагор» разработан в Красноярском Государственном Техническом Университете в 1995 году, в настоящее время разработка ведется в Институте Космических и Информационных Технологий Сибирского Федерального Университета.
Название является сокращением фразы «Параллельный Информационно-Функциональный АлГОРитмический» или «Parallel Informational and Functional AlGORithmic».
Особенности
правитьРазработка программы на Пифагоре ведется для машин с бесконечными ресурсами, это упрощает процесс программирования, так как нет необходимости учитывать ресурсные ограничения (максимальный параллелизм). Ресурсные ограничения учитываются на этапе выполнения, осуществляется сжатие параллелизма. Эта особенность обеспечивает архитектурную независимость разрабатываемых программ.
Синтаксис
правитьРазделители
правитьК символам-разделителям на Пифагоре относятся пробелы, символы табуляции и переноса строки. В качестве разделителя может применяться любое количество таких символов.
Комментарии
правитьВ Пифагоре поддерживаются однострочные и многострочные комментарии.
Однострочные комментарии начинаются парой символов «//» и заканчиваются символом перевода строки.
Многострочные комментарии начинаются парой символов «/*» и заканчиваются парой «*/». Вложенность многострочных комментариев не допускается.
// однострочный комментарий
/* многострочный
комментарий */
Идентификаторы
правитьИдентификаторы используются для обозначения имен констант, переменных, функций и типов данных. Идентификатор может состоять из произвольного количества символов латинского алфавита, цифр и символа подчеркивания. Первым символом идентификатора не может быть цифра.
Зарезервированные слова
правитьДля ключевых слов встроенных типов данных, функций и предопределенных обозначений используются зарезервированные слова. Далее приводится их общий список:
block break bool char const
dup datalist delaylist else error
false float func funcdef int
nil parlist prefunc return signal
true type typedef
Зарезервированные слова пишутся строчными латинскими буквами и они не могут являться идентификаторами.
Обозначения
правитьПоскольку данный язык построен на основе принципа единственного присваивания, здесь отсутствует понятие переменной. Вместо этого вводится понятие обозначения как идентификатора, поставленного в соответствие с каким-либо программным фрагментом. В пределах некоторой области видимости использование идентификатора в качестве обозначения должно быть уникальным. Обозначение получает тип и величину сопоставленного элемента и может использоваться для дальнейшей передачи этих параметров в любую точку программы, обеспечивая тем самым копирование объекта, полученного в ходе вычислений. В языке определены два способа задания обозначений:
- префиксное, при котором знак идентификатор пишется слева от знака «<<», а определяемый объект справа;
- постфиксное, когда слева от знака «>>» задается определяемый объект, а справа его идентификатор.
Элементом является любой из объектов языка, выражение, блок или ранее введенное обозначение. Имя ранее обозначенного элемента задается на идентификатором.
Объекты
правитьК объектам языка относятся конструкции, рассматриваемые при выполнении операций интерпретации как единое целое. Каждый объект характеризуется двойкой:
<тип, значение>.
Существует неупорядоченное множество типов предопределенных объектов, задаваемых соответствующими именами. Предопределенные объекты делятся на атомарные и составные. Типы атомарных объектов (атомов) и области их допустимых значений определяются аксиоматически. Составные объекты являются комбинацией атомарных и уже существующих составных объектов. Они конструируются по заданным правилам. К составным объектам относятся описания функций и списки.
Константы
правитьАтомы данного вида обеспечивают задание различных величин. Величина принадлежит области её допустимых значений, которая, в зависимости от типа, может задаваться одним из следующих способов: диапазоном, диапазоном и точностью, перечислением элементов упорядоченного множества, перечислением элементов неупорядоченного множества (если нет необходимости устанавливать между элементами отношение порядка), функцией. В настоящее время в языке реализованы следующие виды констант: целые, действительные, булевские, символы, константы ошибок, специальные знаки. Тип константы в программе определяется её внешним видом, задаваемым синтаксическими правилами.
Функции
правитьФункция — составной объект, конструируемый специальным образом. Она задается определением, начинающимся с ключевого слова funcdef. Состоит из заголовка и тела. В заголовке указывается идентификатор аргумента, обеспечивающего передачу в тело функции необходимых данных. В теле описывается алгоритм обработки аргумента. Доступ к исходным данным осуществляется только через аргумент, тип которого и значение в данной версии языка могут быть произвольными. Тело функции состоит из элементов, заключенных в фигурные скобки и разделяемых между собой символом «;». В ходе выполнения функции обычно формируется результат, который возвращается после обозначения его зарезервированным идентификатором «return»: результат >> return или return << результат
Возвращаемый результат может быть любым допустимым значением, полученным в ходе вычислений. Возврат результата может осуществляться до завершения выполнения всех операций в теле функции, которая продолжает существования до завершения всех внутренних операций.
Блоки
правитьБлок — это объединение элементов внутри тела функции, служит для логического соединения группы операторов выполняющих законченное действие, а также для локализации обозначений. Он начинается с ключевого слова block, за которым следует тело блока, аналогичное телу функции. Отличие тела блока заключается в том, что выход из него осуществляется по обозначению результата зарезервированным идентификатором break, с которым связывается значение, возвращаемое из блока:результат >> break или break << результат
Примеры программ
правитьРасчет факториала числа
правитьmath.fact << funcdef X
{
fl << ((X,1):[<=,>]):?;
act << (X,
{ (X, (X,1):-:math.fact ):* } );
return << act:fl:.;
}
Получение модуля числа
правитьmath.abs << funcdef X
{
val << ({(0,X):-},X);
kluch << ((X,0):[<,>=]):?;
return << val:kluch:.;
}
Сортировка методом Хоара
правитьsort.hoar.mind << funcdef Y
{
X << Y:2;
cind << Y:1;
fl << ( (X:|,cind):[=,>] ):?;
act << ( cind,
{
block
{
ncind << ((cind,1):+,X):sort.hoar.mind;
fl2 << ( (X:cind, X:ncind ):[>,<=]):?;
act2 << (ncind,cind);
break << act2:fl2:.;
}
}
);
return << act:fl:.;
}
sort.hoar.getmind << funcdef X
{
minind << sort.hoar.mind^(1,X);
return << minind;
}
sort.hoar.getsort << funcdef X
{
fl << ( (X:|,1):[=,>] ):?;
act << (X,
{
block
{
gm << X:sort.hoar.getmind;
mgm << (0,gm):-;
minel << X:gm;
tail << X:mgm;
ktail << tail:sort.hoar.getsort;
break << (minel,ktail:[]);
}
}
);
return << act:fl:.;
}
Применение
правитьДанный язык имеет на данный момент теоретическую значимость, и в перспективе планируется применение его для разработки параллельных структур в смежных научных областях. Для данного языка разработаны транслятор[2], интерпретатор[3] и генератор управляющего графа[4]. В настоящее время ведутся работы в области верификации[5] функционально-потоковых программ, при этом в ряде работ применяется язык «Пифагор».
Примечания
править- ↑ Легалов Александр Иванович[1] Архивная копия от 15 января 2012 на Wayback Machine
- ↑ Легалов А. И., Непомнящий О. В., Редькин А. В., Матковский И. В. Транслятор с функционально-потокового языка параллельного программирования. / Свидетельство о государственной регистрации программы для ЭВМ № 2011615829. Зарегистрировано в реестре программ 27 июля 2011 года.
- ↑ Легалов А. И., Непомнящий О. В., Редькин А. В., Матковский И. В., Хабаров В. А. Интерпретатор функционально-потоковых параллельных программ. / Свидетельство о государственной регистрации программы для ЭВМ № 2011615832. Зарегистрировано в реестре программ 27 июля 2011 года.
- ↑ Легалов А. И., Непомнящий О. В., Редькин А. В., Матковский И. В. Генератор управляющего графа функционально-потоковых параллельных программ. / Свидетельство о государственной регистрации программы для ЭВМ № 2011615830. Зарегистрировано в реестре программ 27 июля 2011 года.
- ↑ Удалова Ю. В., Легалов А. И., Сиротинина Н. Ю., Кропачева М. С. Об отладке и верификации функционально-потоковых параллельных программ. / Параллельные вычислительные технологии (ПаВТ’2009): Труды международной научной конференции (Нижний Новгород, 30 марта — 3 апреля 2009 г.). — ISBN 978-5-696-03854-4 — Челябинск: Изд. ЮУрГУ, 2009. С. 757—764.[2] Архивная копия от 10 июня 2015 на Wayback Machine
Литература
править- Легалов А. И. Функциональный язык для создания архитектурно-независимых параллельных программ // Вычислительные технологии : журнал. — 2005. — Т. 10, № 1. — С. 71-89.
- Легалов А. И. Стратегии управления вычислениями // Проблемы техники и технологий XXI века. Материалы научной конференции : сборник. — Красноярск: КГТУ, 1994. — С. 122-126.
- Легалов А. И., Казаков Ф.А., Кузьмин Д.А., Водяхо А.И. Модель параллельных вычислений функционального языка // Известия ГЭТУ : сборник. — СПб.: ГЭТУ, 1996. — Вып. 500. — С. 56-63.
- Легалов А. И. Использование асинхронно поступающих данных в потоковой модели вычислений // Третья сибирская школа-семинар по параллельным вычислениям : сборник. — Томск: Томского ун-та, 2006. — С. 113-120.
- Стасенко А. П. Обзор потоковых языков программирования // Проблемы интеллектуализации и качества систем информатики : сборник / Под ред. В.Н. Касьянова. — Новосибирск: Институт систем информатики имени А. П. Ершова СО РАН, 2006. — С. 207-216.
- Легалов А.И., Редькин А.В., Матковский И.В. Функционально-потоковое параллельное программирование при асинхронно поступающих данных // Параллельные вычислительные технологии (ПаВТ'2009) : Труды международной научной конференции (Нижний Новгород, 30 марта – 3 апреля 2009 г.). — Челябинск: Изд. ЮУрГУ, 2009. — С. 573-578. (недоступная ссылка)
- Удалова Ю.В., Легалов А.И., Сиротинина Н.Ю. Средства отладки функционально-потоковых параллельных программ : Доклады АН ВШ РФ. — 2008. — Т. 10, № 1. — С. 96-105.
- Васильев В.С., Легалов А.И., Постников А.И. Особенности преобразования хвостовой рекурсии в функционально-потоковом языке параллельного программирования // Системы. Методы. Технологии. 2013. №3(17). С. 106-111.
Ссылки
править- Статьи о функционально-потоковом параллельном программировании Архивная копия от 16 апреля 2017 на Wayback Machine
- Форум с примерами программ на языке Пифагор Архивная копия от 1 октября 2018 на Wayback Machine