Модели и реализация транслирующих компонентов системы функционального программирования тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Стасенко, Александр Павлович

• Стасенко, Александр Павлович
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Стасенко, Александр Павлович

Введение.

1. Язык Sisal 3.1.

1.1. Потоковые языки программирования.

1.2. История развития языка Sisal.

1.2.1. Язык Val.

1.2.2. Sisal 1.2.

1.2.3. Sisal 2.0.

1.2.4. Sisal 90.

1.2.5. Sisal 3.0.

1.3. Нововведения языка Sisal 3.1.

1.3.1. Пользовательские типы.

1.3.2. Другие нововведения.

1.4. Ограничения языка Sisal 3.1.

1.5. Анализ изменений в языке Sisal 3.1.

1.5.1. Улучшение межъязыкового взаимодействия с языком Си.

1.5.2. Повышение читаемости программ.

1.5.3. Упрощение синтаксического разбора.

1.5.4. Устранение неоднозначностей синтаксического разбора.

1.5.5. Улучшение синтаксиса.

Выводы по главе 1.

2. Первое внутреннее представление IR1.

2.1. Требования к внутреннему представлению.

2.2. Обзор промежуточных представлений программ.

2.2.1. Модель потока данных Дениса.

2.2.2. Расширяемая модель расширяемого языка Берса.

2.2.3. Модель вычислений языка Пифагор.

2.3. Описание языка промежуточной формы IF1.

2.3.1. Основные понятия.

2.3.2. Задание последовательного выполнения.

2.3.3. Альтернатива.

2.3.4. Итерация.

2.4. Модель внутреннего представления IR1.

2.4.1. Моделирование языково-независимых понятий языка IF1.

2.4.2. Система интерфейсов модели.

2.5. Система дополнительных интерфейсов.

2.5.1. Преобразование IR1 в XML и обратно.

2.5.2. Визуализация IR1 в ActiveX компоненте.

Выводы по главе 2.

3. Графический метаязык описания транслятора.

3.1. Обзор методов построения трансляторов.

3.1.1. Нисходящие методы.

3.1.2. Восходящие методы.

Введение диссертации (часть автореферата) на тему «Модели и реализация транслирующих компонентов системы функционального программирования»

В настоящий момент намечается существенное замедление роста производительности вычислительных систем за счет увеличения тактовой частоты вычислительных устройств, связанное с ограниченностью современных технологических возможностей. Поэтому для сохранения существующих темпов роста скорости вычислений, косвенно декларируемых законом «Moore's Law» [1], возобновляется интерес к параллельным вычислениям. Ярким тому подтверждением является появление процессоров с двумя независимыми вычислительными ядрами, ориентированных на массовый рынок. Прослеживается общая тенденция увеличения значимости роли многих процессорных ядер, что в обозримом будущем может привести к значительному росту возможностей вычислительных систем по параллельной обработке данных.

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

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

Однако и в функциональных языках существуют ограничивающие параллелизм факторы. Одной из таких причин является набор языковых операций, специально ориентированный на последовательные вычисления или ограниченный параллелизм. В частности, в функциональном языке Лисп (Lisp) [2] операторы для работы с данными обеспечивают выборку только одного компонента, а функциональный язык FP [3] не предусматривает распараллеливание на уровне независимых операторов. Также в модели вычислений, присущей функциональному языку, могут присутствовать элементы управления, тем или иным образом приводящие к разделению процессами общих вычислительных ресурсов. Например, в схемах потока данных Дениса [4] таким ресурсом является узел слияния потоков данных.

Указанные недостатки обычно обходятся в потоковых языках программирования [5], явно описывающих вычисления в виде графа потока данных и обычно являющихся также и функциональными языками. Эти языки, как правило, содержат операторы размножения информационных потоков, их группирования в списки данных различного уровня вложенности и одновременного выделения из списков нескольких независимых и разнородных по составу групп. Потоковые языки программирования изначально ориентировались на потоковые архитектуры вычислительных систем [6], имевших распространение в 80-90-х годах XX века, и с тех пор практически не развивались.

Тем самым, актуальность работы обуславливается:

1) технологическими трудностями роста производительности последовательных машинных архитектур и, как следствие, ростом интереса к параллельным вычислениям;

2) высокой изменчивостью параллельных машинных архитектур и, как следствие, необходимостью в машинно-независимом представлении параллелизма;

3) естественной пригодностью потоковых языков программирования для описания машинно-независимого параллелизма;

4) малой распространенностью и устарелостью существующих потоковых языков и систем программирования на их основе.

Язык программирования Sisal (Сисал) [7] является одним из самых известных потоковых языков промышленного уровня и позиционируется [8] как замена языка Фортран (Fortran) [9] для научных применений. Язык Sisal имеет следующие отличия от других функциональных языков, упрощающие переход с популярных императивных языков программирования:

• приближенный к языку Паскаль (Pascal) [10] синтаксис;

• развитая система типов;

• явно выделенные циклические выражения.

Последняя спецификация языка Sisal версии 2.0 [11] датируется 1991 годом, а последнее обновление транслятора OSC [12], работающего только с языком Sisal версии 1.2 от 1985 года, было в 1995 году. В 1995 году также появилось пользовательское описание языка Sisal 90 [13], не содержащее, однако, точных спецификаций языка.

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

В виду того, что работа проводится в рамках коллективной деятельности по созданию системы функционального программирования, было принято решение выполнить её в виде независимых программных компонентов. В данной работе, в основном, рассматривается компилятор переднего плана языка Sisal 3.1 в разработанное для него внутреннее представление (ВП) IR1 (Internal Representation 1), так как за остальные крупные части компилятора ответственны другие участники проекта [80].

Во время работы над компилятором переднего плана возникало множество промежуточных задач, связанных с хранением, передачей и отладкой ВП IR1. Для решения этих задач были разработаны вспомогательные компоненты для преобразования ВП IR1 в XML-представление и обратно, а также для просмотра ВП IR1 в графическом виде.

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

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

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

1. Разработка языка Sisal версии 3.1, развивающего базовую, функциональную часть языка Sisal 3.0, являющегося входным языком системы SFP и основанную на языке Sisal 90.

1.1. Уточнение описания языка Sisal 90.

1.2. Расширение языка Sisal 90 средствами модульного программирования (Sisal 3.0) и пользовательскими типами.

1.3. Улучшение синтаксиса и семантики языка Sisal 90.

2. Разработка машинно-независимого ВП IR1 программ языка Sisal 3.1, основанного на графах информационных зависимостей.

2.1. Разработка модели внутреннего представления (ВП) IR1 для машинно-независимого описания функциональных программ и её специализация для языка Sisal 3.1.

2.2. Разработка и реализация вспомогательных компонентов ВП IR1 для его сохранения, восстановления и визуализации.

3. Исследование методов трансляции и создание компилятора переднего плана из текста программ языка Sisal 3.1b ВП IR1.

3.1. Разработка модели построения компоненты компилятора переднего плана, основанной на теории автоматов, и её графического представления.

3.2. Разработка компоненты поддержки трансляции из текстового представления во ВП IR1 (для поддержки нескольких входных языков системы SFP).

Методы исследования. В диссертационной работе использовались понятия и методы теории графов, теории алгоритмов и элементы теории множеств. Также применялась теория синтаксического анализа и построения трансляторов. В качестве сравнения применялись различные классы потоковых схем. Для описания синтаксиса языка программирования использовались расширенные формы Бэкуса-Наура (БНФ).

Научная новизна. В диссертационной работе получены новые научные результаты.

1. Спроектирована и формально описана новая версия языка Sisal 3.1, развивающая функциональную часть предыдущих версий языка Sisal и приближающая её к уровню современных языков программирования.

2. Разработаны модели для удобного построения, хранения, анализа, преобразования и использования машинно-независимого внутреннего представления программ функциональных языков программирования.

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

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

Sisal 3.1, его ВП IR1 и транслятор из первого во второе являются неотъемлемой частью системы функционального программирования (SFP) [81, 82], разрабатываемой в рамках проекта ПРОГРЕСС [14]. Данные разработки будут использоваться другими участниками проекта SFP в качестве основы для создания своих частей проекта и будут внедрены в учебный процесс в Новосибирском госуниверситете.

Апробация работы. Основные положения диссертации обсуждались на следующих конференциях и семинарах: th •

1. 9 International Conference on Parallel Computing Technologies,

Pereslavl-Zalessky, 2007 год.

2. Европейская конференция по вычислениям (ЕСС-2007), г. Афины, 25-27 сентября, 2007.

3. V Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (с участием иностранных ученых), Новосибирск, ИВТ СО РАН, 2004 год.

4. Конференция-конкурс «Технологии Microsoft в информатике и программировании», Новосибирск, 2005 год.

5. Конференция-конкурс «Технологии Microsoft в теории и практике программирования», Новосибирск, 2006 год.

6. XLIV Международная научная студенческая конференция «Студент и научно-технический прогресс», Новосибирск, 2006 год.

7. XII Международная научно-методическая конференции «Новые информационные технологии в университетском образовании», 2007 год.

8. Семинар спецкурса «Введение в функциональное программирование», 2007 год.

9. Семинары «Конструирование и оптимизация программ», Новосибирск, ИСИ СО РАН, 2002-2008 годы.

Публикации. Основные результаты диссертационной, работы опубликованы в 19 печатных работах, из которых 2 препринта [83, 84], 12 статей [85, 86, 87, 81, 88, 89, 80, 90, 91, 92, 93, 94] и 6 тезисов докладов [95, 96, 97, 98, 82, 99]. Исследования поддерживались грантами УР.04.01.027 и УР.04.01.0201 научной программы «Университеты России» Министерства науки и образования Российской Федерации. Исследования выполнялись в соответствии с планами научно-исследовательских работ ИСИ СО РАН по проекту 3.15 «Методы и средства трансляции и конструирования программ». Проект проводился в рамках программы 3.1 СО РАН «Информационное и математическое моделирование в различных областях знаний, задачи поддержки принятия решений, экспертные системы, системное и теоретическое программирование».

Структура диссертации. Диссертация состоит из введения, четырёх глав, заключения, списка литературы и девяти приложений. Работа содержит 109 страниц в формате машинописного текста (за исключением приложений и библиографии), 78 рисунков и 22 таблиц. Список литературы содержит 99 наименований.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Стасенко, Александр Павлович

Выводы по главе 4

В главе рассматриваются существующие компиляторы языка Sisal 1.2, а также общие характеристики построенного компилятора переднего плана языка Sisal 3.1, транслирующего текст модуля программы в ВП IR1. Описывается интерфейс взаимодействия с компилятором переднего плана, задачи лексического анализа, общая структура и устройство синтаксического и семантического разборов. В приложениях А8.2 и А8.3 частично приводятся схемы для лексического и семантически-синтаксического разбора.

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

С помощью формализма схем ^Р написан работоспособный, легко-встраиваемый компилятор переднего плана языка Sisal 3.1, обеспечивающий:

• простоту учёта модификаций языка;

• достаточно высокую скорость трансляции;

• довольно качественные сообщения об ошибках и предупреждениях;

• развитые механизмы восстановления после ошибок разбора.

Использование графического метаязыка позволило сократить объём текста транслятора переднего плана языка Sisal 3.1 до десяти тысяч строк, по сравнению с тридцатью тысячами строк кода аналогичной части транслятора OSC 12.0 для более простой версии языка Sisal 1.2.

ЗАКЛЮЧЕНИЕ

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

1. Разработана и формально описана новая версия языка Sisal 3.1. Новая версия языка Sisal 3.1 получена путём упрощения, улучшения, расширения и уточнения пользовательского описания языка Sisal 90, а также использования идей языка Sisal 3.0 и пользовательских типов. Формальное описание синтаксиса языка Sisal 3.1 является первым формальным описанием синтаксиса языка Sisal со времен языка Sisal Л .2. Семантика языка Sisal 3.1 приводится в нестрогом виде пользовательского описания, которое, по замыслу, претендует на полноту и непротиворечивость. Введение пользовательских типов в язык Sisal 3.1 повлекло введение средств переопределения операций и статического полиморфизма. Изменение языка Sisal 90 в языке Sisal 3.1 было обусловлено повышением удобства разбора и улучшением читаемости программ этого языка.

2. Разработаны модель внутреннего представления (МВП) IR1 для машинно-независимого описания функциональных программ и её специализация для языка Sisal 3.1.

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

3. Разработаны и реализованы модели описания вспомогательных компонентов МВП IR1: компоненты преобразования в эквивалентную XML-форму и компоненты визуализации.

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

Модель компонента визуализации обеспечивает отображение и перемещение по ВП IR1 в терминах графического языка промежуточной формы IF1. Реализация модели основывается на тесно интегрированном исходном коде размещения графов свободно-распространяемой системы GraphViz и для визуализации использует интервальные деревья для эффективного отображения больших графов и проверки наличия их вершин и портов в данной точке.

4. Разработана и реализована модель описания компонента для поддержки трансляции из текстового представления во ВП IR1. Модель компонента поддержки трансляции из текстового представления во ВП IR1 также описывается системой интерфейсов и реализуются с помощью СОМ-компонента. Модель описывает общий вид компилятора переднего плана в виде лексического и синтаксически-семантического разборов. Моделью определяются понятия потока символа, потока лексем, средств сообщения о событиях трансляции и' поддержки модульности. Реализация модели задаёт стандартные реализации её понятий, а также дополнительную функциональность, наподобие порождения потока символов файла в заданной кодировке, перечисление элементов которого вызывает дисковое чтение.

5. Разработана модель построения компонента компилятора переднего плана и её графическое представление.

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

6. Создан компонент компилятора переднего плана, позволяющий преобразовывать модуль программы на языке Sisal 3.1 во внутреннее представление IR1.

Разработанный в виде СОМ-компонента транслятор переднего плана является первой реализацией языка Sisal со времен языка Sisal 1.2 и успешно апробирует предложенные модели. К особенностям реализации транслятора относится его разделение на графическую, текстовую и интерпретирующую части. Графическая часть описывает автомат, распознающий синтаксис языка. Текстовая часть содержит раздельное описание «семантики отношений» языка и «операционной семантики», порождающей объекты внутреннего представления IR1. Интерпретирующая часть транслятора связывает воедино его графическую и текстовую части.

Список литературы диссертационного исследования кандидат физико-математических наук Стасенко, Александр Павлович, 2009 год

1. Moore G. Е. Cramming more components onto integrated circuits // Electronics Magazine. — NY: McGraw-Hill, 1965. — Vol. 38, No. 8. — P. 114-117.

2. McCarthy J. Lisp 1.5 programmer's manual / McCarthy J., Abrahams P. W., Edwards D. J., Hart T. P. and Levin M. I. т- 2nd ed. — Cambridge, MA: M.I.T. Press, 1962. — 106 p.

3. Backus J. Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs // Communications of the ACM.—NY: ACM Press, 1978. — Vol. 21, No. 8. —P. 613-641.

4. Dennis J. B. Data flow schemas / Dennis J. В., Fosseen J. B. and Linderman J. P. // Proc. of the Internat. Symp. on Theoretical Programming. — London, UK: Springer-Verlag, 1972. — Lect. Notes Comput. Sci. —Vol. 5,—P. 187-216.

5. Ackerman W. B. Data flow languages // IEEE Computer Magazine. —■ Los Alamitos, CA: IEEE Computer Society Press, 1982. — Vol. 15, No. 2.1. P. 15-25.

6. Veen A. H. Dataflow machine architecture // ACM Computing Surveys.

7. NY: ACM Press, 1986. —Vol. 18, No. 4.— P. 365-396.

8. Cann D. C. Retire Fortran?: a debate rekindled // Communications of the ACM.—NY: ACM Press, 1992. — Vol. 35, No. 8. —P. 81-89.

9. ISO/IEC 1539-1:2004(E). Information technology: Programming languages: Fortran: Part 1: Base language. — Geneva: Internat. Organization for Standardization (ISO), Central Secretariat, 2004.

10. ISO 7185:1990(E). Information technology:, Programming languages: Pascal. — Geneva: Internat. Organization for Standardization (ISO), Central Secretariat, 1990.

11. Bohm A.,P. W. The Sisal 2.0 reference manual / Bohm A. P. W., Cann D. C., Feo J. T. and Oldehoeft R. R. — Livermore, CA, 1991. — 128 p. — (Tech. Rep. / Lawrence Livermore National Laboratory; UCRL-MA-109098).

12. Cann D. C. The optimizing Sisal compiler. — Livermore, CA, 1992. — 74 p. — (Tech. Rep. / Lawrence Livermore National Laboratory; UCRL1. MA-110080).

13. Feo J. T. Sisal 90 user's guide / Feo J. Т., Miller P. J., Skedzielewski S. K. and Denton S. M. — Livermore, CA: Lawrence Livermore National Laboratory, Draft 0.96, 1995. — 80 p.

14. Kasyanov V. N., Evstigneev V. A. et al. The system PROGRESS as a tool for parallelizing compiler prototyping // Proc. of Eighth SIAM Conf. on Parallel Processing for Scientific Computing (PPSC-97). — Minneapolis, 1997. — P. 301-306.

15. Church A. The calculi of lambda-conversion // Annals of Mathematics Studies. —New Jersey: Princeton University Press, 1941. — 77 p.

16. Ashcroft E. A. and Wadge W. W. Lucid: A formal system for writing and proving programs // SIAM J. on Computing. — 1976. — Vol. 5, No. 3. —P. 336-354.

17. Nikhil R. S. Id language reference manual (version 90.1). — Cambridge, MA, 1991. — 54 p. — (Tech. Rep. / Massachusetts Institute of Technology, Laboratory for Computer Science, Computation Structures Group; Memo-284-2).

18. McGraw J. R. Val language, description and analysis. — Livermore, CA, 1980. — 51. p. — (Tech. Rep. / Lawrence Livermore National Laboratory; UCRL-83251, Rev. 1).

19. Ravishankar С. V. Post: a language for dataflow programming // Ph.D. thesis. — Madison: University of Wisconsin, Computer Sciences Department, 1987. — 213 p.

20. McGraw J. R. Parallel functional programming in Sisal: fictions, facts, and future. — Livermore, CA, 1993. — 40 p. — (Tech. Rep. / Lawrence Livermore National Laboratory; UCRL-JC-114360).

21. Hemmendinger D. Lazy evaluation and cancellation of computations // Proc. of the IEEE Internat. Conf. on,Parallel Processing (ICPP'85). — University Park, PA: IEEE Computer Society Press, 1985. — P. 840-842.

22. Finkel R. A. Advanced programming language design. — Мёп1о Park, CA: Addison-Wesley, 1995. — 480 p.

23. Cann D. C. Compilation techniques for high-performance applicative computation. — Fort Collins, CO, 1989. — 145 p. — (Tech. Rep. / Colorado State University, Computer Science Department; CS-89-108).

24. Cann D. C. Sisal multiprocessing support / Cann D. C., Lee C.-C., Oldehoeft R. R. and Skedzielewski. S. K. — Livermore, CA, 1987. — (Tech. Rep. / Lawrence Livermore National Laboratory; UCID-21115).

25. Beard P. C. An implementation of Sisal for distributed-memory architectures. — Livermore, CA, 1995. — 45 p. — (Tech. Rep. / Lawrence Livermore National Laboratory; UCRL-LR-122353).

26. Gurd J. P., Kirkham С. C. and Watson I. The Manchester prototype data flow computer // Communications of the ACM. — NY: ACM Press, 1985. — Vol. 28, No. 1. — P. 34-52.

27. Ranelletti J. E. Graph transformation algorithms for array memory optimization in applicative languages // Ph.D. thesis. — Davis, CA: University of California, Computer Science Department, 1987. — 222 p.

28. Cann D. C., Wolski R. M. and Feo J. T. Sisal: Toward, resolving the parallel programming crisis. — Livermore, CA, 1992. — 8 p. -— (Tech. Rep. / Lawrence Livermore National Laboratory; UCRL-JC-109774).

29. Hendrickson C. PI Programming a real code in a functional language (part 1) // Proc. of the Cray User Group (CUG) conf., Santa Fe, New Mexico, September 23-27, 1991. — 1991. — P. 333-344.

30. Stapleton L. Livermore labs offers Cray time free // Supercomputing Review. — San Diego, CA: London Manhattan Group of Companies, 1991. —Vol. 4, No. 5. —P. 14-15.

31. Watson I. and Gurd J. R. A prototype data flow computer with token labeling // Proc. of the AFIPS National Computer Conf., June 1979. — 1979. — Vol. 48, No. 6. — P. 623-628.

32. Adams J. C. Fortran 90 handbook: complete ANSI/ISO reference / Adams J. C., Brainerd W. S., Martin J. Т., Smith В. T. and Wagener J. L. — NY: Intertext Publications, Inc. / McGraw-Hill, Inc., 1993. — 740 p.

33. Бирюкова Ю. В. Sisal 90 Руководство пользователя. — Новосибирск, 2000. — 84 с. — (Препр. / РАН. Сиб. Отд-е. ИСИ; № 72).

34. Skedzielewski S. К. and Yates R. K. Fibre: An external format for Sisal and IF1 data objects, version 1.1. — Livermore, CA, 1988. — lip. — (Tech. Rep. / Lawrence Livermore National Laboratory; M-154, Rev. 1).

35. Касьянов В. H., Бирюкова Ю. В. и Евстигнеев В. А. Функциональный язык Sisal // Поддержка супервычислений и интернет-ориентированные технологии. — Новосибирск, 2001. — С. 54-67.

36. Касьянов В. Н. Оптимизирующие преобразования программ. — М.: Наука, 1988, —336 с.

37. Котов В. E. Сети Петри. — M.: Наука, 1984. — 160 с.

38. Бсрс А. А. Операторные структуры // Тр. симпозиума теоретическому программированию, 7-11 августа, 1972. —Новосибирск: ВЦ СО АН СССР, 1972. — Ч. 2. — С. 44-82.

39. Касьянов В. Н. Иерархические графы и графовые модели: вопросы визуальной обработки // Проблемы систем информатики и программирования. — Новосибирск, 1999. — С. 7-32.

40. Легалов А. И., Казаков Ф. А. и Кузьмин Д. А. Потоковая модель параллельных вычислений // Вестник КГТУ. Сб. научных трудов. — Красноярск: КГТУ, 1996. — Вып. 6. — С. 60-67.

41. Дейкстра Э. Дисциплина программирования / Пер. с англ., под ред. Любимского Э. 3. — М.: Мир, 1978. — 275 с.

42. Cormen Т. Н. Introduction to algorithms / Cormen Т. H., Leiserson С. Е., Rivest R. L. and Stein C. — 2nd ed. — NY: McGraw-Hill, 2001. — 1180 P

43. Ахо А. и Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т.1. Синтаксический анализ. — М.: Мир, 1978. — 612 с.

44. Ершов А. П. и Грушецкий В. В. Метод описания алгоритмических языков, ориентированных на реализацию. — Новосибирск, 1977. — 40 с. — (Препр. / АН СССР. Сиб. отд-ние. ВЦ.; № 74).

45. Lesk М. Е. and Schmidt Е. Lex a lexical analyzer generator. — NY: Murray Hill, 1975. — 13 p. — (Tech. Rep. / AT&T Bell Labs; No. 39).i

46. Евстигнеев В. А. и Касьянов В. Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука, 1994. — 360 е.: ил.

47. Moll R. N., Arbib М. A. and Kfoury A. J. An introduction to formal language theory. —NY: Springer-Verlag, 1988. —203 p.

48. Appel A. W. and Palsberg J. Modern compiler implementation in Java. — 2nd ed. — UK: Cambridge University Press, 2002. — 501 p.

49. Johnson S. C. YACC yet another compiler compiler. — NY: Murray Hill, 1975. — 33 p. — (Tech. Rep. / AT&T Bell Labs; No. 32).

50. Gagnon E. M. SableCC, an object oriented compiler framework // M. S. thesis. — Montreal, Canada: McGill University, 1998. — 97 p.

51. Кузнецов Б. П. Психология автоматного программирования // Журнал BYTE. — 2000. — №11. — С. 22-29.

52. Легалов А. И. Разработка трансляторов в учебном курсе // Тез. t междунар. научно-методической конф. «Новые информационныетехнологии в университетском образовании», Новосибирск, 19-22 марта, 1996. — 1996.

53. Gurevich Y. Evolving algebras 1993: Lipari guide // Specification and validation methods. —NY: Oxford University Press, 1995. —P. 9-36.

54. Шалыто A. A. Switch-технология // Алгоритмизация и программирование задач логического управления. — СПб.: Наука, 1998. —628 с.

55. Штучкин А. А. и Шалыто А. А. Совместное использование теории построения компиляторов и SWITCH-технологии // Тр. X Всеросс. научно-методической конф. «Телематика-2003». — СПб.: СПбГИТМО (ТУ), 2003.

56. Любченко В. С. Конечно-автоматная технология программирования // Тр. междунар. научно-методической конф. «Телематика '2001». — СПб.: СПбГИТМО(ТУ), 2001. — С. 127-128.

57. Вирт Н. и Иенсен К. Паскаль. Руководство для пользователя и описание языка. — М.: Финансы и статистика, 1989. — 255 с.

58. Kutter P. W. and Pierantonio A. Montages specifications of realistic programming languages // J. of Universal Computer Science. — 1997. — Vol. 3, No. 5. —P. 416-442.

59. ITU-T Recommendation Z.100. Specification and Description Language (SDL). — Geneva: ITU-T, 1994.

60. Вельбицкий И. В. Технология программирования. — Киев: Техника, 1984. —274 с.

61. Касьянов В. И. и Поттосин И. В. Методы построения трансляторов / Отв. ред. Ершов. А. П. — Новосибирск: Наука, 1986. — 344 с.

62. Sarkar V. and Cann D. С. POSC: A partitioning and optimizing Sisal compiler. — Livermore, С A, 1990. — 14 p. — (Tech. Rep. / Lawrence Livermore National Laboratory; UCRL-102737).

63. Bohm A. P. W. and Sargeant J. Efficient dataflow code generation for Sisal. — Manchester, UK, 1985. — 29 p. — (Tech. Rep. / University of Manchester, Department of Computer Science; UMCS-85-10-2).

64. Freeh V. W. and Andrews G. R. fsc: A Sisal compiler for both distributed and shared-memory machines // Conf. on High-Performance Functional Computing, Denver, CO, April 9-11, 1995. — 1995. — 11 p.

65. Garza-Salazar D. A., Bohm A. P. W. D-OSC: A Sisal compiler for distributed memory machines // Proc. of the 2nd Parallel Computation and Scheduling Workshop (PCSW'97). — Ensenada, Mexico, 1997. — 13 p.

66. The Unicode Standard / The Unicode Consortium. — Version 4.0. — Boston, MA: Addison-Wesley, 2003.

67. ISO/IEC 10646:2003(E). Information technology: Universal Multiple-Octet Coded Character Set (UCS). — Geneva: Internat. Organization for Standardization (ISO), Central Secretariat, 2003.

68. ANSI X3.4:1986. Information systems: coded character sets: 7-Bit American national Standard Code for Information Interchange (7-Bit ASCII). — NY: American National Standards Institute (ANSI), 1986.

69. Робинсон У. C# без лишних слов / Пер. с англ. — М.: ДМК Пресс, 2002. — 352 е.: ил. (Серия «Для программистов»).

70. ISO/IEC 9899:1999(Е). Programming languages: С. — Geneva: Internat. Organization for Standardization (ISO), Central Secretariat, 1999."

71. ISO/IEG 14882:2003(E). Programming languages: С++.— Geneva: Internat. Organization for Standardization (ISO), Central Secretariat, 2003.

72. ISO/IEC 14977:1996(E). Information technology: Syntactic metalanguage: Extended BNF. — Geneva: Internat. Organization for Standardization (ISO), Central Secretariat, 1996.

73. ANSI/IEEE 754-1985. IEEE standard for binary floating-point arithmetic. — NY: Institute of Electrical and Electronics Engineers, 1985 (Reprinted in SIGPLAN Notices, 22(2):9-25, 1987).

74. Стасенко А. П., Пыжов К. А., Идрисов P. И. Компилятор в системе функционального программирования SFP // Вестник НГУ. Сер. Информационные технологии. — Новосибирск: Изд-во НГУ, 2008. — 11 с.

75. Kasyanov V. N., Stasenko А. P., Gluhankov М. P., Dortman Р. А., Pyjov К. A., Sinyakov A. I. SFP An interactive visual environment for supporting of functional programming and supercomputing // WSEAS

76. Transactions on Computers. — Athens: WSEAS Press, 2006. — Vol. 5, N 9. — P. 2063-2070.

77. Стасенко А. П. Система функционального программирования языка Sisal // XII Международная научно-методическая конференция «Новые информационные технологии в университетском образовании». — Новосибирск: НГУ, 2007. — С. 162-165.

78. Стасенко А. П. Внутреннее представление системы функционального программирования Sisal 3.0. — Новосибирск, 2004.54 с. — (Препр. / РАН. Сиб. отд-е. ИСИ; № 110).

79. Стасенко А. П., Синяков А. И. Базовые средства языка Sisal 3.1.

80. Новосибирск, 2006. — 60 с. — (Препр. / РАН. Сиб. отд-е. ИСИ; № 132).

81. Глуханков М. П., ДоргманП. А., Павлов А. А., Стасенко А. П.

82. Транслирующие компоненты системы функционального программирования SFP // Современные проблемы конструирования программ. — Новосибирск: Институт систем информатики имени А. П. Ершова СО РАН, 2002. — С. 69-87.

83. Стасенко А. П. Система интерфейсов транслятора во внутреннее представление IR1 // Методы и инструменты конструирования и оптимизации программ. — Новосибирск: Институт систем информатики имени А. П. Ершова СО РАН, 2005. — С. 229-238.

84. Стасенко А. П. Графический метаязык для описания транслятора // Сборник трудов аспирантов и молодых ученых «Молодая информатика». — Новосибирск: Институт систем информатики имени А. П. Ершова СО РАН, 2005. — С. 105-113.

85. Стасенко А. П. Обзор потоковых языков программирования // Проблемы интеллектуализации и качества систем программирования.

86. Новосибирск: Институт систем информатики имени А. П. Ершова СО РАН, 2006. — 12 с.

87. Stasenko A. P. Sisal 3.1 language structures decomposition // Bull. Novosibirsk Сотр. Center. Ser. Computer Science. — Novosibirsk, 2006. — Iss. 24. — 8 p.

88. Стасенко А. П. Автоматная модель визуального описания синтаксического разбора // Методы и инструменты конструирования программ. — Новосибирск: ИСИ СО РАН, 2007. — С. 186-209.

89. Стасенко А. П. Автоматная модель визуального описания синтаксического разбора // Вычислительные технологии. — Новосибирск: ИВТ СО РАН, 2008. — Т. 13, N. 5. — С. 70-87.

90. Kasyanov V. N., Stasenko A. P. Sisal 3.1 language structures decomposition // Parallel Computing Technologies. — Lecture Notes in Computer Science, 2007. — Vol. 4671/2007. — P. 62-73.

91. Kasyanov V. N., Stasenko A. P. Sisal 3.2 language structures decomposition // Lecture Notes in Electrical Engineering. — Berlin: Springer-Verlag, 2009. — Vol. 28. — P. 582-594.

92. Стасенко А. П. Графический метаязык для описания транслятора // Тез. докл. V Всеросс. конф. молодых ученых по математическому моделированию и информационным технологиям. — Новосибирск: ИВТ СО РАН, 2004. — С. 53.

93. Стасенко А. П. Совмещение достоинств Microsoft Dynamic HTML и W3C-coBMecTHMbix HTML в системе HTML-справки // Конф.-конкурс «Технологии Microsoft в информатике и программировании»: Тез. докл. — Новосибирск, 2005. — С. 45-47.

94. Стасенко А. П. Использование автоматного подхода для построения компилятора переднего плана // Конф.-конкурс

95. Технологии Microsoft в теории и практике программирования»: Тез. докл. — Новосибирск, 2006. — С. 37-39.

96. Kasyanov V. N., Stasenko А. P. Sisal 3.1 language structures decomposition // European Computing Conference. Book of Abstracts. — Athens: WSEAS Press, 2007. — P. 92.список иллюстрация

97. Рис. 1. Иерархия основных интерфейсов внутреннего представления.421. Рис. 2. Вход—>вход.461. Рис. 3. Выход—>вход.461. Рис. 4. Вход—>выход.461. Рис. 5. Выход—>выход.46

98. Рис. 6. Иерархия интерфейсов коллекций внутреннего представления.47

99. Рис. 7. Иерархия интерфейсов итераторов коллекций ВП.48

100. Рис. 8. Иерархия интерфейсов пар внутреннего представления.49

101. Рис. 9. Иерархия интерфейсов библиотеки irlxml.dll.49

102. Рис. 10. Иерархия интерфейсов библиотеки irlview.dll.51

103. Рис. 11. Иерархия эффективно разбираемых грамматик.56

104. Рис. 12. Иерархия языков эффективно разбираемых грамматик.57 '

105. Рис. 13. Переход 1-го типа.71

106. Рис. 14. Переход 2-го типа.71

107. Рис. 15. Переход 3-го типа.71

108. Рис. 16. Расширенная схема задающая контекстно-зависимые языки.75

109. Рис. 17. Аналог входа в блок try.76

110. Рис. 18. Аналог выхода из блока try.76

111. Рис. 19. Применение схем VF для разбора лексики и синтаксиса.77

112. Рис. 20. Схема транслятора модуля программы на языке Sisal 3.1 в ВП IR1 .86

113. Рис. 21. Иерархия основных интерфейсов транслятора (txt2irl.dll).89

114. Рис. 22. Иерархия интерфейсов потоков символов и лексем транслятора.91

115. Рис. 23. Иерархия интерфейсов событий трансляции.92

116. Рис. 24. Иерархия интерфейсов поддержки межмодульных связей.92

117. Рис. 25. Граф функции phi.180

118. Рис. 26. Граф составной вершины Select.180

119. Рис. 27. Первый граф составной вершины Select.181

120. Рис. 28. Второй граф составной вершины Select.181

121. Рис. 29. Третий граф составной вершины Select.181

122. Рис. 30. Четвертый граф составной вершины Select.181

123. Рис. 31. Граф функции nri.184

124. Рис. 32. Граф составной вершины LoopA.184

125. Рис. 33. Первый граф составной вершины LoopA.184

126. Рис. 34. Второй граф составной вершины LoopA.184

127. Рис. 35. Третий граф составной вершины LoopA.184

128. Рис. 36. Четвертый граф составной вершины LoopA.184

129. Рис. 37. Граф функции sum.193

130. Рис. 38. Пример схемы задающей регулярный язык.;.197

131. Рис. 39. Пример схемы задающей детерминированный КС язык.197

132. Рис. 40. Пример схемы задающей контекстно-зависимый язык.;.198

133. Рис. 41. Лексический анализ. Часть 1.199

134. Рис. 42. Лексический анализ. Часть 2.:.2001. Рис. 43. Комментарий.200

135. Рис. 44. Идентификатор или ключевое слово. Часть 1.201

136. Рис. 45. Идентификатор или ключевое слово. Часть 2.202

137. Рис. 46. Двойственные лексемы. Часть 1.203

138. Рис. 47. Двойственные лексемы. Часть 2.203

139. Рис. 48. Символьный литерал.204

140. Рис. 49. Символьный литерал, десятичный код.205

141. Рис. 50. Символьный литерал, шестнадцатеричный код.205

142. Рис. 51. Символьный литерал, восьмеричный код.206

143. Рис. 52. Числовой литерал.207

144. Рис. 53. Целочисленный литерал.208

145. Рис. 54. Вещественный литерал.208

146. Рис. 55. Вещественный литерал одинарной точности.209

147. Рис. 56. Вещественный литерал двойной точности.210

148. Рис. 57. Строковой литерал.211

149. Рис. 58. Буквальный строковой литерал.212

150. Рис. 59. Окончание строкового литерала.213

151. Рис. 60. Обычный строковой литерал.214

152. Рис. 61. Обычный строковой литерал, десятичный код.215

153. Рис. 62. Обычный строковой литерал, восьмеричиый код.216

154. Рис. 63. Обычный строковой литерал, шестнадцатеричный код.217

155. Рис. 64. Синтаксический анализ.218

156. Рис. 65. Трансляция типа.•.2191. Рис. 66. Тип массива.2201. Рис. 67. Тип потока.:.220

157. Рис. 68. Тип выражения.220

158. Рис. 69. Трансляция множества типов.220

159. Рис. 70. Трансляция типа записи.221

160. Рис. 71. Трансляция типа функции.222

161. Рис. 72. Трансляция имени типа.223

162. Рис. 73. Трансляция типа союза.224

163. Рис. 74. Трансляция операнда алгебраического выражения. Часть 1.225

164. Рис. 75. Трансляция операнда алгебраического выражения. Часть 2.225

165. Рис. 76. Трансляция выражения if.226

166. Рис. 77. Пропуск содержимого выражения if.227

167. Рис. 78. Разбор части else выражения if.228