автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методы алгоритмизации предметных областей

На правах рукописи

Новиков Фёдор Александрович

Методы алгоритмизации предметных областей

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени доетора технических наук

1 9 МАЙ 2011

Санкт-Петербург 2011

4847198

Работа выполнена на кафедре «Технологии программирования» Санкт-Петербургского государственного университета информационных технологий, механики и оптики (СПбГУИТМО)

Научный консультант доктор физико-математических наук

Новосельцев Виталий Борисович

Официальные оппоненты доктор физико-математических наук,"

профессор

Баранов Сергей Николаевич

доктор технических наук, профессор

Калайда Владимир Тимофеевич

доктор технических наук, профессор

Тропченко Александр Ювенальевич

Ведущая организация Государственный научный центр Цен-

тральный научно-исследовательский и опытно-конструкторский институт робототехники и технической кибернетики

Защита диссертации состоится «06» июля 2011 года в 15 часов 30 минут на заседании диссертационного совета Д 212.227.06 в Санкт-Петербургском государственном университете информационных технологий, механики и оптики по адресу: 197101, Санкт-Петербург, Кронверкский пр. 49.

С диссертацией можно ознакомиться в библиотеке СПбГУ ИТМО.

Автореферат разослан « Я& 2011 г.

Ученый секретарь диссертационного совета, ^

доктор технических наук, профессор ^ Л.С. Лисицына

Общая характеристика работы

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

Традиционные, и до сих пор распространенные методы алгоритмизации заключаются в том, что объекты предметной области представляются средствами систем управления базами данных (СУБД), операции программируются на языках программирования общего назначения в форме пакетов прикладных программ (ППЛ), а методы решения типовых задач, частично остаются в форме математических моделей вне компьютера, а частично встраиваются в СУБД и ППП. Традиционные методы алгоритмизации хороши тем, что опираются на универсальные средства, и могут быть применены в любом случае, в котором алгоритмизация вообще возможна. Недостатки традиционных методов также давно известны: процесс алгоритмизации является трудоемким, дорогам и не способствует повторному использованию результатов.

Наряду с традиционными методами, распространение получили методы алгоритмизации, основанные на применении проблемно-ориентированных языков (ПОЯ) и моделей предметных областей (МПО).

Наблюдения автора и других исследователей1 показывают, что реализация ПОЯ и программное представление МПО, при выполнении определенных условий, дает выигрыш в степени алгоритмизации конкретных предметных областей, по сравнению с традиционными методами. Таким образом, разработка методов определения, реализации и применения ПОЯ и МПО для алгоритмизации предметных областей, выбор критериев целесообразности применения ПОЯ и МПО, выявление факторов выигрыша при алгоритмизации, является актуальной и востребованной задачей.

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

Алгоритмизацией предметной области называется разработка методов и программ, которые позволяют прикладным специалистам решать на компьютере все или большинство типовых задач данной предметной области. Алгоритмизация предметной области включает три аспекта: 1) определение предметно-ориентированных структур данных, представляющих объекты предметной области; 2) реализацию программных процедур обработки этих структур — действий, или операций предметной области; 3) разработку методов и алгоритмов решения типовых задач предметной области — последовательностей действий, доставляющих значимый для пользователя результат. Считается, что предметная область достаточно четко очерчена, а множества объектоз, операций и типовых задач надежно идентифицированы. При этом степень алгоритмизации может быть различной. Чем больше типовых задач можно решить, и чем меньше затраты на их решение, тем выше степень алгоритмизации.

' Ward M.P. Language Oriented Programming//Software - Concepts and Tools. 1994, Vol. 15, No. 4, pp. 147-161.

Таким образом, предметом диссертационного исследования явля!Отся методы алгоритмизации предметных областей. Предлагаемые методы развивались постепенно, с конца 70-х годов, в результате анализа опыта выполнения работ по алгоритмизации конкретных предметных областей, сначала под руководством члена-корреспондента АН СССР С. С. Лаврова, а позже под руководством автора. Различные аспекты и элементы методов испытывались и постепенно совершенствовались в практических применениях, перечисленных в диссертации. К настоящему времени сложилась целостная методология, допускающая распространение на различные классы предметных областей.

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

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

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

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

Методы исследования. В диссертации используются методы дискретной математики: теории множеств, теории автоматов, математической логики, теории графов, теории формальных грамматик, а также терминологический и понятийный аппарат технологии программирования. В качестве основного средства формального представления применяется унифицированный язык моделирования \JML-

Научная новизна полученных результатов определяется следующими результатами, выносимыми на защиту.

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

• Автоматный метод реализации проблемно-ориентированных языков, в том числе визуальных, позволяющий определить все аспекты языка— структуру, внешнее представление, контекстные условия и операционную семантику. Полное определение языка автоматным методом является реализацией языка. В основу

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

Практическая значимость. Предлагаемая в диссертации методология многократно применялась автором на практике для определения и реализации разнообразных ПОЯ и МПО (всего 17 случаев) в следующих предметных областях:

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

2) эфемеридные расчеты в астрономии; 3) компьютерная верстка табличных изданий; 4) описание графического интерфейса пользователя; 5) автоматизация бизнес-процессов в системах менеджмента качества. При этом достигнуты и подтверждены положительные результаты алгоритмизации, то есть разработанное программное обеспечение используется прикладными специалистами для решения типовых задач регулярно и в течение продолжительного времени в разных организациях (табл. 2).

Апробация диссертации. Различные аспекты результатов работы докладывались на многих семинарах и форумах, в том числе, на следующих конференциях: Всесоюзная конференция «Методы математической логики в проблемах искусственного интеллекта и систематическое программирование», Вильнюс, 1980; III конференция «Применение методов математической логики», Таллин, 1983; III Всесоюзная конференция «Автоматизация производства пакетов прикладных программ и трансляторов», Таллин, 1983; Ш Всесоюзная конференция «Автоматизация производства систем программирования», Таллин, 1986; IAU Colloquium 109, Gai-thersburg, 1988; Всесоюзное совещание «Эфемеридная астрономия и позиционные наблюдения», Л., 1991; IX научная школа по ППП «Программное обеспечение математического моделирования, управления и искусственного интеллекта», Адлер, 1991; Всероссийское совещание с международным участием «Компьютерные методы небесной механики», СПб., 1992,1995,1997; Международная конференция «Современные проблемы теоретической астрономии», СПб., 1994; Colloquium «International cooperation in dissemination of the astronomical data», St. Petersburg, 1996; Фестиваль Microsoft в Санкт-Петербурге, 1998; International Computer Science Symposium in Russia CSR 2006, СПб, 2006; Международная научная конференция «Космос, астрономия и программирование» (Лавровские чтения), СПб., 2008; Научно-практическая конференция «Научные исследования и инновационная деятельность», СПбГПУ, 2009; Семинар Института программных систем РАН, 2009; International conference «Asteroid-Comet Hazard - 2009», St. Petersburg, 2009; Семинар Института прикладной астрономии РАН, 2010; Семинар Санкт-Петербургского института информатики и автоматизации РАН, 2011; Семинар компании Jet Brains, 2011; Семинар компании Scite, 2011.

Публикации. По материалам диссертации опубликовано 55 работ, из которых 13 — статьи в журналах из списка ВАК, и 7 — многотиражные монографии, выпущенные издательствами «Питер», «БХВ-Санкт-Петербург» и «Наука и Техника». Основные работы, в которых содержатся результаты, выносимые на защиту, перечислены в конце автореферата. В работах, выполненных в соавторстве, личный вклад автора во всех случаях в равных долях с соавторами.

Структура диссертации. Диссертация изложена на 196 страницах. Список литературы содержит 149 наименований. Работа иллюстрирована 44 диаграммами.

Содержание работы

Диссертация состоит из введения, пяти глав и заключения.

Во введении рассматриваются следующие вопросы: проблемы технологии разработки прикладного программного обеспечения, необходимость решения этих проблем для алгоритмизации, эффективность применения ПОЯ и МПО, важность опоры на формальные методы. Помимо этого, во введении вводится специфическая терминология, используемая в диссертации, и система обозначений, основанная на унифицированном языке моделирования 1МЬ. В частности, вводится понятие степени алгоритмизации. Степень алгоритмизации М определяется как среднее геометрическое двух показателей: доля решаемых типовых задач Г (отношение числа типовых задач, которые можно решить средствами оцениваемой алгоритмизации, к числу всех идентифицированных типовых задач), и относительное снижение трудозатрат Б (отношение средних трудозатрат на решение типовых задач после оцениваемой алгоритмизации, к средним трудозатратам на решение той же совокупности задач до алгоритмизации): м - -5Ум = д/Г(1-5).

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

Первая глава посвящена проблемам разработки прикладного программного обеспечения и изложению предлагаемого подхода к их решению.

В разделе 1.1 излагается взгляд автора на структуру дисциплины технология программирования, которая включает модель процесса, модель команды и дисциплину программирования. Задача технологии программирования состоит в повышении управляемости, надежности и продуктивности процесса разработки. Продуктивность процесса разработки — объем произведенного программного продукта на одного работка в единицу времени.

Центральное место в разделе занимает предложенная автором концепция циклов повышения продуктивности. Как хорошо известно, два фактора решающим образом влияют на продуктивность прикладного программирования: 1) сокращение объема внеплановых изменений артефактов; 2) увеличение объема повторно использованных артефактов. Предлагается рассмотреть в этом рзду третий фактор— использование подходящего проблемно-ориентированного языка. Основной тезис автора о влиянии языковых средств на продуктивность разработки представлен на рис. 1. На этой диаграмме изображена традиционная итеративная модель процесса разработки с оригинальными добавлениями. С основным циклом последовательного выполнения фаз процесса разработки сопряжены два внешних цикла движения определенных артефактов, которые называются циклами повышения продуктивности. Верхний цикл, в который вовлечены заказчики, отражает выявление несоответствий требованиям и, тем самым, определяет объем внеплановых изменений. Нижний цикл, в который вовлечены разработчики, отражает преобразование разработанных компонентов в готовые к применению образцы проектирования и, тем самым, определяет объем повторного использования.

Рис. 1. Циклы повышения продуктивности

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

В разделе 1.2 исследуются две концепции: «модель предметной области» и «сильный пользователь» Дня алгоритмизации предметной области необходимо решить три задачи: 1) определить представление объектов предметной области, 2) реализовать операции с этими объектами и 3) разработать методы решения типовых задач, как систем правил применения операций к объектам для получения значимого результата. Решение первых двух задач алгоритмизации в настоящее время надежно обеспечено технологиями систем управления базами данных (СУБД) и пакетов прикладных программ (Г1ПП). Нерешенные вопросы связаны с представлением знаний о методах решения типовых задач. Заметим, что, в любом случае, решение типовых задач предметной области опирается на готовые программы и данные, которые в диссертации называются доверительным программным фондом (ДПФ).

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

Рассмотрим варианты использования МПО (рис. 2).

Рис. 2. Модель использования МПО Важнейшим вариантом использования МПО является решение типовых задач, в этот вариант использования вовлечено основное действующее лицо — пользователь. Возможность решения типовых задач обеспечивается ДПФ. Но модель предметной области допускает и другие варианты использования: создание ПОЯ, что обеспечивается соответствующими инструментальными средствами, или специальных приложений, например, систем с элементами искусственного интеллекта для автоматического решения задач в данной предметной области (так называемых «планировщиков задач»). В последнем случае не обойтись без явного представления в программе концептуальных знаний о предметной области. Действующее лицо, вовлеченное в такие более сложные варианты использования, уместно назвать сильным пользователем. Сильный пользователь (оракул) может ответить на любые вопросы о предметной области: какие задачи являются типовыми, можно ли доверять имеющемуся программному фонду и т.д. Сильный пользователь является центром алгоритмизации, как показано на диаграмме (рис. 3).

Рис. 3. Сильный пользователь как центр алгоритмизации

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

В разделе 13 приводится рекомендуемая автором последовательность шагов алгоритмизации и вводится классификация ПОЯ, классификация МПО и классификация методов алгоритмизации.

Рекомендуемые шаги алгоритмизации предметной области: 1) привлечь сильного пользователя, способного решить любую типовую задачу и знающего ответы на все вопросы о предметной области; 2) построить модель предметной области, достаточно полную и детальную для представления знаний о решении типовых задач; 3) определить проблемно-ориентированный язык, обладающий достаточной выразительной силой для описания всех типовых задач предметной области.

В предложенной классификации ПОЯ выделяются три категории языков по типу взаимодействия с пользователем.

• Командные предметно-ориентированные языки. Языки этой категории, как правило, опираются на развитый ДПФ. Характерным для этой категории является то, что пользователь последовательно, по одной, дает системе команды на выполнение тех или иных действий, причем состав и порядок действий, которые требуются для решения некоторой задачи, пользователь определяет сам по ходу дела, используя как результаты выполнения предыдущих команд, так и другие трудно формализуемые факторы, и не сообщает системе заранее в виде «программы».

• Императивные (графические) языки. Языки этой категории примечательны тем, что (сильный) пользователь описывает решаемую задачу в целом, предъявляя совокупность требуемых шагоз не по отдельности, а во взаимосвязи, часто в виде графической схемы или диаграммы. Система осуществляет решение задачи, опираясь на ДПФ. Также как и в языках первой категории, программу решения задачи определяет пользователь, но в этом случае он в явном виде предъявляет «программу» системе.

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

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

Предлагается использовать две независимых дихотомии для классификации МПО на верхнем уровне. Первая дихотомия: жесткие и гибкие модели. Жесткие модели встроены в ДПФ. Чтобы изменить жесткую модель, пользователь должен изменить программный код системы. Гибкие модели не встроены в систему «намертво». Чтобы изменить гибкую модель, пользователь не должен изменять программный код системы. Ему предоставляется специальный интерфейс или иная возможность отредактировать представление знаний о предметной области. Жесткие модели эффективнее и проще реализуются. Гибкие модели имеют более широкую область применения. Вторая дихотомия: декларативные и императивные модели. Императивные модели в части задания правил решения типовых задач используют алгоритмы, выполнение которых доставляет значимый для пользователя результат. Декларативные модели избегают явных последовательностей при задании правил решения типовых задач, используя логические утверждения, ограничения, уравнения и т. п., которые неявно задают значимый результат через его свойства. Императивные модели эффективнее и проще реализуются. Декларативные модели потенциально дают более высокую степень алгоритмизации.

Существует множество методов и приемов алгоритмизации, основанных на использовании ПОЯ и МПО. Эти методы предлагается классифицировать в соответствии с основными присущими характеристиками, приведенными в табл. 1.

Таблица 1. Классификация методов алгоритмизации

Характеристика Предметно-ориентированные Языково-ориентированные Модельно-ориентированкые

Правила решения типовых задач (представление МПО) Неявные, встроены в ДПФ, неизменяемые пользователем Неявные, описываются наПОЯ, изменяемые пользователем Явные, задаются в МПО, изменяемые пользователем

Класс предметных областей Узкий, ограничен алгоритмами, встроенными в ДПФ Широкий, ограничен выразительной силой ПОЯ Широкий, ограничен мощностью планировщика задач MITO

Трудоемкость / «сила» пользователя Высокая / Низкая Средняя / Средняя Нюхая / Высокая

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

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

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

В разделе 2.1 приводится пример пакета «Ample 3» (см. табл. 2) для решения задач динамики малых тел Солнечной системы. Не касаясь особенностей предметной области, отмечается, что привычный графический интерфейс пользователя, построенный на традиционных элементах управления, является проблемно-ориентированным языком командного типа. Замегим, что при переходе от текстовых

языков командного типа к графическому интерфейсу пользователя произошел скачок в количестве, но не в качестве. Предметно-ориентированный язык графического интерфейса остается языком командного типа, скрытым за двумерными формами.

Вторым примером в этом разделе является язык «GUIDL» (см. табл. 2). Данный язык является текстовым языком для описания действий пользователя графического интерфейса. Подчеркнем, что это язык публикаций, программы на этом языке предназначены для чтения и исполнения человеком. Язык «GUIDL» — это командный язык для записи пошаговых процедур, допускающий ветвления и циклы. Более десяти тысяч страниц публикаций, в которых используется данный язык, доказали его полезность.

В разделе 2.2 обсуждаются визуальные ПОЯ. Большая часть современных визуальных языков в качестве нотации использует «графоподобные» диаграммы. Программная реализация таких языков требует специализированной инструментальной поддержки. Таким образом, реализация визуальных языков сама является ярко выраженной предметной областью, заслуживающей собственных проблемно-ориентированных языков, и такие языки предложены. В качестве примера в диссертации рассматривается язык описания диаграмм «DiaDcL» (см. табл. 2), разработанный автором совместно с К.Б. Степаняном. Основным назначением языка «DiaDeL» является описание нотации (графического синтаксиса) диаграмм и описание связи нотации с существующей семантикой.

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

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

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

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

Первый пример отражает идею применения специализации как средства повышения уровня предметно-ориентированного языка и степени алгоритмизации. Учитывая особенности ограниченной предметной области, можно построить такие специализированные надстройки над универсальными средствами, которые обеспечивают эффективное достижение очень высоких результатов с малыми затратами. Таковы входной язык и система «СВИТА» (см. табл. 2), разработанные при участии автора. С помощью этой системы выпускаются астрономические ежегодники и альманахи — специализированные издания с высокоточными астрономическими данными. Астро-номичесте ежегодники используются в службах навигации, связи, точного времени и в других жизненно важных областях. Для их издания необходима программная система, которая не просто автоматически верстает очень большие и очень сложные таблицы по заранее насчитанному материалу, но и делает это с гарантированной надежностью и с гарантированным качеством результата. Система «СВИТА» совершенствовалась и развивалась течение 15 лет. В результате все таблицы во всех ежегодниках, выпускаемых Институтом прикладной астрономии РАН, в настоящее время изготавливаются с помощью системы «СВИТА». При этом ежегодные трудозатраты на выпуск сократились в шесть раз. Таким образом, достигнутая в данном случае степень алгоритмизации м = ^/1(1-1/6) = 0,91.

Вторым примером в третьем разделе — последним и самым важным — является семейство языков таблично-ориентированного программирования. Предложенный автором таблично-ориентированный метод алгоритмизации предметных областей заключается в следующем. Пусть задана предметная область, и пусть в предметной области зафиксирован набор переменных V- ..., V,,} — величин предметной области. Совокупность значений А = {оь ..., а„} этих переменных образует состояние предметной области. Среди значений могут бьгть как заданные, так и незаданные, то есть неизвестные, подлежащие определению. Имеется также набор функциональных модулей /<■= {/¡, ...,/„,}, которые называются действиями. Действия могут изменять состояние системы, например, вычисляя значения неизвестных величин по значениям известных, или могут иметь побочный эффект, например, печать значений. Суперпозицию действий, которые переводят систему из начального состояния в целевое состояние, называется решением элементарной вычислительной задачи в данной предметной области. Табличный подход основан на допущении, что решение любой типовой задачи в данной предметной области сводится к последовательному и независимому решению совокупности элементарных вычислительных задач.

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

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

Для того чтобы подчеркнуть и проиллюстрировать двойственную природу таблицы в таблично-ориентированном подходе, здесь приводятся определения шести базовых операций алгебры таблиц как операций с программами. Определения этих операций для таблиц как структур данных и эквивалентность определений для таблиц как структур данных и таблиц как итераторов приведены в диссертации. В следующих определениях таблица рассматривается как итератор, перебираюгций кортежи таблицы. Пусть Т, Tl, Т2 — итераторы таблиц; Е, El, Е2 — наборы переменных в соответствующих таблицах; п— натуральное число; s — список переменных; р — булевское выражение; f — действие (процедура); Default — функция, возвращающая значения по умолчанию своих аргументов. Тогда операции определяются так.

1. Сложение.

Т = Т1+Т2 = for El £ Tl do yield (El U Default(E2-El));

for E2 e T2 do yield (Default(E1-E2) и E2)

Сложение таблиц — это последовательное выполнение двух циклов.

2. Умножение.

Т = Т1*Т2 = for Ei £ Tl do for E2 e T2 do yield (E1UE2)

Умножение таблиц — это вложенность циклов.

3. Итерация (операция не обозначается).

Т = n Tl = for i from 1 to n do Tl

Итерация таблицы — это цикл со счетчиком.

4. Проекция.

Т = Tl I s =for El е Tl do yield (El n s)

Проекция таблицы — это локализация переменных.

5. Выборка.

Т = T1 [р] =for El е T1 do if р(Е1) then yield (El) ;

Выборка ib таблицы—это условный оператор в теле цикла. !

6. Действие ¡[операция не обозначается). !

Т = T1 f = for El 6 T1 do yield (f(El))

Действие нал таблицей — это вызов процедуры в теле цикла.

На основе таблично-ориентированного подхода при активном участии автора было разработано три проблемно-ориентированных языка (СЛОН, ТОП, Дельта, см. табл. 2), каждый в нескольких версиях и в нескольких системах программирования. В настоящее время разработанные системы используются для решения разнообразных задач, прежде всего задач эфемеридной астрономии, в том числе важнейших, таких как выпуск высокоточных эфемерид больших планет и Луны. Необходимо подчеркнуть, что несомненный успех этого метода во многом определяется тем, что в разработке участвовал сильный пользователь |Г. А. Красинсюод который фактически построил исчерпывающую МПО в форме встроенного планировщика, решающего все типовые элементарные задачи эфемеридной астрономии. Однако, то обстоятельство, что МПО является встроенной и неотчуждаемой, требует реализации подобных планировщиков для применения подхода в других областях, что ограничивает область применения реализованных таблично-ориентированных ПОЯ, но не ограничивает область применения таблично-ориентированного метода.

Таблично-ориентированный метод алгоритмизации предметных областей является первым результатом, выносимым на защиту. Разработка таблично-ориентированного метода была выполнена автором в 1987-2007 годах в ИПА РАН совместно с Г. А. Красинским и В. И. Скрипниченко.

Третья глава представляет разработанный автором метод определения ПОЯ на основе метамоделей и систем взаимодействующих автоматов.

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

Автоматный метод заключается в определении следующих четырех объектов:

1) абстрактного синтаксиса как иерархической композиции конструкций языка;

2)метамодели как абстрактного синтаксиса, дополненного системой неиерархических отношений между конструкциями языка; 3) конкретного синтаксиса как распознавателя, конструирующего абстрактную программу по её представлению; 4) операционной семантики как интерпретатора абстрактных программ.

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

При использовании автоматного метода рекомендуется строить определение проблемно-ориентированного языка последовательно, причем начинать следует не с

2 Оллонгрен А. Определение клыков программирования интерпретирующими автоматами. М.: Мир, 1977,288 с.

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

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

Далее (этап 3) определяется система автоматов, которая по внешнему представлению строит абстрактную программу, и определяется другая система автоматов (этап 4), которая интерпретирует абстрактную программу (или же генерирует код в какой-нибудь системе программирования).

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

"Ъ,

О

X

Программа (конкретное представление^

Пользователь ПОЯ

Исполняются виртуальной машиной автоматного программирования

Текст, диаграмма, таблица, последовательность активаций элементов управления, звуки,...

Синтаксический анализ

Автоматы

«¡п$1апсеОЬ конкретного

г........... синтаксиса

языка

Экземпляр метамолели «1П51апсе0Ь Метамодель

(абстрактная программа} языка

Семантическая интерпретация

«'пэитсеО?»

Автоматы операционной. семантики языка

' Создатель ПОЯ (сильный пользователь)

Внешняя среда

X"........

Интерпретатор, эмулятор, редаетор внешней системы программирования,...

Ъ,

Рис. 4. Схема использования автоматного метода Рассмотрим более подробно этапы построения абстрактного синтаксиса и метамодели. В автоматном методе абстрактный синтаксис языка определяется с помощью диаграмм классов следующим образом.

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

• Определение конструкции языка через её составляющие осуществляется с помощью отношения композиции. При этом композиция классов означает отноше-

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

• Совокупность обязательных составляющих некоторой конструкции, включённых в ней по отношению композиции, при реализации образуют одно целое. Такая композиция в диссертации названа конъюнктивной: в конструкцию А включаются и конструкция В, и конструкция С. На языке порождающих формальных грамматик конъюнктивной композиции соответствует правило А ::= В С.

• Альтернативное определение конструкции языка может осуществляться с помощью дизъюнктивной композиции: в конструкцию А включаются конструкция В или конструкция С, но не обе вместе. На языке порождающих формальных грамматик это соответствует правилу А ::= В | С.

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

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

Р Если нетерминал непосредственно порождает только терминалы, то вводится леречислимый тип.

у Если нетерминал определяется через другие конструкции (терминалы и нетерминалы), то вводится конъюнктивная композиция или атрибуты. 6 Если нетерминал определяется через другие конструкции альтернативно, то вводится дизъюнктивная композиция или обобщение, е Если рекурсия используется для задания итерации, то вводится кратность полюса композиции или атрибут массив.

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

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

3.

4.

5.

6. 7.

Program ::= Statement. | Statement; Program Statement ::= Name = Expression

Expression ::= Expression Operator Expression | Name | { Elements} | (Expression) Operator ::= n | и Name ::=A|B|...|X|YjZ Elemente ;:= Element | Element, Elements Element ::=a|b |... |x|y|z На рис. 5 приведено определение абстрактного синтаксиса языка «ММ», полученное по указанной методике. Для наглядности указано с помощью комментариев, из какого правила грамматики и по какому правилу методики получилось каждое отношение абстрактного синтаксиса.

definition

«.constraint»

usage.statemfctti.number

3; 5

Set

name: Name usage

Рис. 5. Метамодель языка ММ

Однако правил абстрактного синтаксиса недостаточно для полного задания языка. Например, в мши языке множеств подразумеваются два контекстных условия, которые невозможно описать средствами контекстно-свободной грамматики: 1) все буквы в определении множества перечислением элементов должны быть различны; 2) всякому вхождению имени множества в правую часть равенства должно предшествовать вхождение этого имени в левую часть.

Первое контекстное условие можно задать очень просто: достаточно воспользоваться стандартным ограничением полюса ассоциации {set}, которое появилось в UML2. Второе контекстное условие задано нумерацией предложений программы с помощью дополнительного атрибута number и наложение ограничения на значения этого атрибута в ассоциации, связывающей использующие и определяющие вхождения имени (рис. 5).

Определение структуры проблемно-ориентированного языка необходимо, но не достаточно. Для использования языка, кроме абстрактной структуры, требуются конкретная реализация его абстрактной структуры — конкретный синтаксис — и способ применения абстрактной структуры для конкретных целей—семантика языка.

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

Однако построение абстрактной программы редко является самоцелью— как правило, с построенной абстрактной программой требуется еще что-то сделать: сразу выполнить, или преобразовать в какой-то другой вид для последующего выполнения. Именно этот результат, то есть процесс выполнения в конкретной вычислительной (виртуальной) машине или исполнимый код в конкретной системе программирования считается смыслом программы, а соответствие, сопоставляющее программе ее смысл, называется семантикой программы? Существуют различные способы определения семантики языка, среди которых в программировании чаще всего используется операционная семантика. Операционный подход к определению семантики языка4 предполагает описание алгоритма интерпретации программы в терминах некоторой абстрактной машины.

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

Раздел 3.2 посвящен описанию автоматной модели, предложенной автором, и ее применению для определения конкретного синтаксиса и семантики предметно-ориентированных языков.

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

3 Непейвода Н. Н. Семантика алгоритмических языков. // Итоги науки и техн. Сер. Теор. вероятн. Мат. стат. Теор.

кибернет.. 20. ВИНИТИ. М.: 1983, с. 95-166

4 Лавров С. С. Программирование. Математические основы, средства, теория. СПб.: БХВ-Петербург, 2001. 317 с.

5 Поликарпова Н. И., Шалыто А. А. Автоматное программирование. СПб.: Питер, 2010. 176 с.

»interface» Источник событий

событие1

и

«command» событие

Л текущее ? состояние

Управляющий автомат

эффект

m

сторожевое условие

«query»

текущее состояние

Автоматный объект

Машина состояний

«Interface»

Объект управления

ь-aj

1 Iсторо»

«commands'

сторожевое условие «query»

Рис. 6. Сравнение традиционной и предлагаемой автоматных моделей В соответствии с принципом Б. Мейера.6 операции интерфейса любого объекта следует разделить на запросы, доставляющие значения и не изменяющие состояния объекта (стереотип «query»), и команды, изменяющие состояние объекта, но не доставляющие значений (стереотип «command»). Заметим, что здесь состояние объекта означает совокупность значений всех его локальных переменных, включая управляющее состояние в смысле автоматного программирования. Далее, считая обязательным указание для каждого объекта не только предоставляемых, но и требуемых интерфейсов, получаем четыре возможных типа интерфейса взаимодействия между объектами: предоставляемые команды и требуемые команды, предоставляемые запросы и требуемые запросы. Применяя это наблюдение к автоматам, получаем все четыре возможных типа интерфейса между автоматом {автоматным объектам), его источником событий и объектом управления (рис. б, справа):

• события на переходах автомата являются предоставляемыми командами автоматного объекта, аргументы событий, если они есть, инициализируют локальные переменные автоматного объекта;

• сторожевые условия на переходах являются логическими выражениями над значениями, которые доставляют требуемые запросы к объекту управления;

• эффекты — это требуемые команды объекта управления, в качестве аргументов могут передаваться значения локальных переменных автоматного объекта;

• автоматный объект может предоставлять запросы о своем текущем состоянии и значениях других локальных переменных.

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

Л Мсйер Б. Обьсктно-орис;.*ткрСЕзннос конструирование программных систем. М.: Русская Редакция, 2005. 1204 с.

Предлагаемая автоматная модель алгоритмически полна по Тьюрингу. Этот факт подтверждается эмулятором машины Тьюринга, приведенным на рис. 7.

«Interface» ITuring «commande

start ()

¡"«¿numeration» I Symbol

«enumeration» Move _

{left, right, still}

Рис. 7. Автомат, эмулирующий машину Тьюринга Автомат, приведенный на этой диаграмме — не самый лаконичный вариант реализации машины Тьюринга, но он прямо соответствует обычным словесным описаниям машины, а потому подходит для демонстрации алгоритмической полноты. Кроме того, на примере этого автомата удобно ввести используемые далее обозначения. Диаграмма автомата заключена в рамку по правилам UML 2. В ярлычке рамки написаны названия класса автоматов и перечислены локальные переменные, их имена подчеркнуты.; Предоставляемые и требуемые интерфейсы обозначены в соответствии с нотацией UML2, кроме того указаны имена и типы интерфейсов. Имена интерфейсов используются на переходах автомата.

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

В диссертации приведены методики задания конкретного синтаксиса исходя из метамодели языка и из синтаксических диаграмм Вирта. Приведем пример задания текстового конкретного синтаксиса для языка «ММ». Применяя методику задания конкретного синтаксиса; исходя из метамодели языка, к метамодели на рис. 5, получаем систему из четырех автоматов, два из которых представлены на рис. 8.

Здесь использованы следующие элементы нотации. Обозначение tWs.statements[k] подразумевает, что каждый элемент массива statements разбирается отдельным автоматным объектом класса Statement SM. Вложенные автоматы имеют именованные точки вьаодр. Точки выхода фактически можно считать результатом работы автомата как функции. Результат работы головного автомата как функции, возвращается в окружающую среду через интерфейс I Result. )

irsin - ITuririg

Turing SM

a: Symbol i b: Symbol щ: Move J

{else ] /t.read(a); c.next(a, b, m); t.write(b, m)

main.startO I c.inltQ

Д À 1:

ITape

«Interface» IControl «command»

in«0

next (In a: Symbol, out b : Symbol, out m: Move) «query»

isFinal (): Boolean

«interface» ITape

«command»

write (in a: Symbol, in m : Move ) «query»

read {out a: Symbol)

Program

statements!*! : Statement

«query»

def ( In n : Name) : Integer

Statement

name : Name number : Integer specification : Expression

«enumeration»

_Name__

(A . Z}__

«query»

IsName (In c: Char): Boolean

toName (in c: Char): Name

t: IToken1

this: Program

r : IResuii у

Program SM к : Integer S : Char J

[c==';"I(k++

£

/к = 1:

this.statementsfkl: Statement SM Y

t-t(c)

[c==\']/r.okO

«interface» IResuit

«command»

ok() error ()

[ else ]

K>

/ r.errorQ

Statement SM S : Char

«interface» (Token

«command» t (out с : Char)

t.t.(c)

-o

{else ]

I VVC

Waiting

[ n.isName(c) ] I this.name = n.toName(c)

4>

Waiting

tt(c)

ok

error ol<

[ else ]

Iе"- *-'J[ tnfs-specification:

Expression SM

t: IToksn jl, n: Name ,-i, this: Statement

Рис. 8. Автомата конкретного синтаксиса языка «ММ» Но основным результатом работы всей системы автоматов является побочный эффект, состоящий в построении через интерфейс this набора взаимосвязанных объектов, образующих абстрактную программу.

Рассмотрим теперь задание семантики. Можно представить себе совершенно разные способы использования проблемно-ориентированных языков:

1) преобразование входа программы в её выход — характерно для систем пакетной обработки; 2) последовательность побочных эффектов в процессе выполнения программы — характерно для командных, интерактивных систем управления; 3) сервис или служба, отвечающая на запросы пользователя — характерно для интеллектуальных экспертных систем.

Здесь рассматривается наиболее интересный третий случай, когда программу можно рассматривать как систему уравнений, задающую конкретную ситуацию в предметной области, например, так: А = В л {Ь}; В = {а, Ь, с} . Задавая такой программе вопрос: «А = ?», пользователь получает в ответ значение множества А

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

смотрим пример задания семантики языка «ММ» в следующей постановке. Имеется экземпляр метамодели, заданной на рис. 5. Пользователь (элемент внешней среды) задает имя множества и получает в ответ последовательность событий — элементов этого множества, и в конце подтверждающее событие ok — или получает сообщение об ошибке error, если такое множество не определено. Для реализации такой семантики определим следующие интерфейсы взаимодействия: интерфейс ISet позволяет задать имя множества, интерфейс (Result обрабатывает результат, а интерфейс Iterator воплощает итератор (рис. 9).

Рис. 9. Схема взаимодействия автоматов семантики Семантика может быть задана в форме статически определенной системы автоматов, которая выполняет любую заданную абстрактную программу. Такая система традиционно называется интерпретатором. Можно также по заданной абстрактной программе построить систему автоматов, которая будет выполнять только данную абстрактную программу. Способ построения такой системы традиционно называется компилятором (в данном случае целевой машиной компиляции является виртуальная машина автоматного программирования). Можно рассматривать различные промежуточные случаи, что соответствует смешанным вычислениям.7 Здесь приведен пример (рис. 10)— два автомата из пяти, полученные применением простейшей методики компиляции для системы параллельных автоматов без смешанных вычислений.

^тэт: ЭвГ у г. Жеаи» у I:

Да ¡Expression; ^ в: Iterator

Рис. 10. Автоматы семантики языка «ММ»

7 Ershov A. P. Mixed'Computation: Potential Applications and Problems for Study //Theoretical Computer Science, Voli IS, Issue 1, April 1982, pp. 41 - 67.

В разделе 3.3 определяется место автоматного метода среди других подходов к определению ПОЯ. В целом автоматный метод обладает двумя основными преимуществами по сравнению с классическими методами определения языков: самодостаточность и гибкость. Самодостаточность метода состоит в том, что он позволяет совместно и унифицированными средствами определить сразу всё — абстрактный синтаксис, конкретный синтаксис, контекстные условия и операционную семантику. Никаких дополнительных средств и формализмов не требуется. Гибкость состоит в том, что событийная модель позволяет использовать произвольные представления программ, а не только тексты; вариативная модель взаимодействия автоматов позволяет выбрать адекватный стиль описания конкретного синтаксиса и семантики языка.

Автоматный метод определения пробпемпо-ориентированных языков является вторым положением, выносимым на защиту. Метод разработан автором совместно с У. Н. Тихоновой в 2005 - 2010 годах з СПбГУ ИТМО.

Четвертая глава развивает известные методы определения моделей предметных областей, средств постановки задач и предметно-ориентированных языков, допускающих автоматический синтез вычислительных программ (структурный синтез программ).8

Раздел 4.1 посвящен определение синтаксиса, семантики и прагматики языка исполняемых программных спецификаций. Предлагаемый язык исполняемых программных спецификаций предназначен для алгоритмизации и формализации предметных областей, определения предметно-ориентированных языков и быстрого создания прототипов программных приложений в формализуемых предметных областях. В основу языка Ч* положены следующие принципы.

• Ориентация на декларативную спецификацию предметной области в терминах формальной теории в специальном логическом исчислении.

• Симметричное описание структур (сущностей) и поведения (связей) конкретной задачи в данной предметной области: сущности определяются через связи, а связи определяются через сущности.

• Автоматический синтез схемы решения задачи с последующей компиляцией или интерпретацией схемы на основе готового ДПФ предметной области.

• Открытое определение метамодели языка и предоставление пользователю возможности расширения и изменения метамодели.

• Определение набора конкретных синтаксисов, однозначно отображаемых в ме-тамодель, в том числе графической нотации.

Очень важно четко определить область применимости языка Ч'— тот класс предметных областей и их моделей, для которых спецификация на языке Ч* действительно позволяет автоматически синтезировать программы решения типовых задач. Язык применим в том и только в том случае, когда для предметной области может быть построена такая модель в форме семантической вычислительной сети, которая позволяет решать типовые задачи данной предметной области. С синтаксической точки зрения вычислительная сеть может быть представлена двудольным ориентированным графом. Вершины первой доли называются атрибутами, вершины второй доли называются связями. С семантической точки зрения сеть задает множество воз-

8 Тыугу Э. X. Концептуальное программирование. М.: Наука. 1984.256 с.

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

В языке рассматривается класс вычислительных сетей, в которых «нет программного времени». Другими словами, все атрибуты имеют два состояния: либо их значение определено (и не меняется), либо не определено. Если значение не определено, то его (может быть) можно определить с помощью связей по значениям других атрибутов, значения которых заданы. Непротиворечивость модели постулируется, если значение атрибута может бьггь вычислено разными способами, то считается, что они все дают один результат (или отличия в результатах не имеют значения). Соответственно, запрещены встречные дуги — один атрибут не может быть одновременно входным и выходным для данной связи. С программисткой точки зрения отсутствие «программного времени» означает, что при вычислениях не требуются повторные присваивания значений переменным. С математической точки зрения это означает, что модель предметной области описывается системой уравнений. В языке Ч* не используются условия существования атрибутов. Считается, что если функциональная связь существует, то существуют и связываемые ее атрибуты. На рис. 11 приведена метамодель используемого подкласса семантических вычислительных сетей.

Рис. 11. Метамодель МПО

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

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

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

стве случаев в основу графического языка кладется метафора диаграммы графа: сущности изображаются вершинами, отношениями — ребрами. В предлагаемом графическом языке в основу положена другая метафора —разлинованная страница — разбиение отведенного поля диаграммы на части прямыми линиями. При этом в случае языка Ч* общая картина не двухмерная, а трехмерная. Разлинованные страницы могут быть сложены в стопку и связаны друг с другом, например, таким образом: прямоугольник на одной странице раскрывается в виде другой страницы. Эта структура визуально похожа на таблицу, но таблицей не является: з ней нет идентифицируемых строк и столбцов, только отношения соседства и вложенности областей. Сущности вводятся текстовыми именами, а отношение композиции— вложенностью соответствующих блоков. В текстовой нотации применение отношения композиции передается точкой. Рассмотрим пример (рис. 12).

Основные атрибуты | ^^Имя схемы

S Fib

А л, а : N

Условие варианта _G.n_f; 1 or л = 2 else

Fa«-1 I ! /" Af1. f2 TFib--J

Ffl.n«- n - 1 Ff2.n<-n-2 \ ' F a <- (1 .a + f2.a \

\ Атрибуты варианта

—f Ре курсивная ссыпка

/

Вариантные части

Функциональные связи

Рис. 12. Пример описания отношения в графическом синтаксис« языка Ч* В этом примере определяется отношение Fib, элементами которого являются номер (атрибут п) и соответствующее значение (атрибут а) числа Фибоначчи. Основные атрибуты п и а являются натуральными числами (N — встроенный тип). Отношение имеет две вариантные части, выбор которых производится по условию (else — встроенный предикат). Причем вторая вариантная часть содержит два дополнительных атрибута f1 и f2 того же типа Fib. Собственно отношение определяется имплицитно с помощью функциональных зависимостей. Подобные рекурсивные определения не только являются допустимыми, но и являются одним из основных выразительных средств языка ЧЛ

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

Пусть заданы следующие конечные множества.

• А — множество имен атрибутов, которым соответствуют атрибуты схемы в модели предметной области и переменные в синтезируемой абстрактной программе.

• F— множество имен функций, которым соответствуют функциональные связи в модели предметной области и имена функций из программного фонда, доступных в синтезируемой абстрактной программе.

• Агр,(/) с А — множество входных параметров функции/е Р.

• Кеьф а А— множество выходных параметров функции/е/7.

Наложим ограничение \ZfeF (Arg(/) ^ 0 & ¡^(У) * 0 & Аг§(/) п Иев^ = 0). В таком случае пара <А, г> определяет модель предметной области. Поскольку здесь не используется вложенные отношения, а все атрибуты находятся на одном уровне, то такую модель уместно называть плоской.

Формулы теории называются предлоз:сениями вычислимости и имеют вид:

где X, У. А — множества имен атрибутов, aG=g^, • — последовательность имен функций /е1..я). Неформально предложение вычислимости С(Х, У, [С?]) означает, что Г может быть вычислено по X применением последовательности функций (7.

В исчислении присутствует одна схема аксиом: С(Х, У, [ ]), где У а X, а [ ] — пустая последовательность (пустая абстрактная программа). Такие предложения вычислимости называются тривиальными. В данном фрагменте исчисления достаточно рассматривать схему С(Х, X, [ ]) тривиальных предложений вычислимости.

Аксиомы исчисления (предметные — зависящие от предметной области) — это все формулы вида С(А^(/), Ие8(/), [ /]), где/еР. Предметные аксиомы иногда называют элементарными предложениями вычислимости. Введем следующее правило композиции-.

С{Х, У, ¡61]) & С(!Г, 2, [С2]) & \\fcY. С(Х, Уи2, [в,; С2]Х где бь 02 — конкатенация двух последовательностей функций. Данное правило имеет простую интерпретацию: имея абстрактную программу, вычисляющую У, и другую абстрактную программу, входы которой содержатся в У, последовательным применением этих программ можно расширить множество вычисленных атрибутов. Правило композиции часто используют в форме правша элементарной композиции: С(Х, У, [С?]) & С(Атё(/), Ле5(/), [/]) & Агё(/)с¥. С(Х, У^(/), [в',/]).

Задачей (2 на модели предметной области <А, Р> называется четвепка

д = <А,Р,Х,У>,

где <А,Р> — модель предметной области, Л', Ус А — множества имен входных и выходных атрибутов соответственно. Решением задачи £}=<А, Р, X, У> называется последовательность ..., gm для которой

3 из ¡¥(1!сХ& Yc.1V8с С(и, IV, [б]).

Неформально это означает следующее: при решении задачи могут бьггь использованы не все входные данные и могут быть вычислены ненужные результаты.

Теорема (О полноте правила элементарной композиции). Пусть G=gь — решение задачи 0 = <Л, Р,Х, У>. Тогда оно может быть получено применением правила элементарной композицгт из предложения вычислимости С(Х, X, [ ]).

Поиск вывода в данном исчислении несложен. Пусть дана задача <А, Р, X, У>. Выберем в качестве исходного предложения вычислимости С(Х, X, [ ]) и будем наращивать программу при помощи правила элементарной композиции. Если на определённом шаге имеем С(Х, 2, [С]) & 2с.У, то решение найдено. Если Э/еР (Ащ(/) с 2 & & Ке&(/) <х Ъ), то применяем правило элементарной композиции для функции/ получая новое предложение вычислимости. Если достигается состояние, в котором \ZfeF (А^(/) <г 2 V КеБ(/) с Ъ) & 2фУ, то решения поставленной задачи не существует.

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

Б разделе 43 рассматривается вопрос об эффективных (не переборных) алгоритмах синтеза. Предлагается следующая структура данных — результат предобработки доя представления модели <А, Р> (рис. 13).

Рис. 13. Результат предобработки модели предметной области В результате предобработки модели строится списочная структура из совершенно одинаковых ячеек, имеющих разный смысл. Каждая ячейка хранит четыре указателя (left, right, up, down), что позволяет ей быть элементом двух двусвязных списков одновременно. Модель имеет два входа: А — указатель на список атрибутов (белый цвет) и F — указатель на список связей (серый цвет". Каждая ячейка списка связей F содержит два указателя, поддерживающих двусвязный (но не кольцевой!) список связей, а также указатель на двусвязный список вхождений атрибутов в качестве аргументов связи (горизонтальная штриховка) и указатель на двусвязный список вхождений атрибутов в качестве результатов связи (вертикальная штриховка). Совершенно аналогично усгроен список атрибутов А.

Эта списочная структура дает возможность проводить синтез очень эффективно — число шагов алгоритма не превосходит числа вхождений атрибутов в МПО.

Алгоритм 1. Линейный алгоритм синтеза программ на плоской модели Вход: Модель предметной области, заданная парой указателей А и F, как на рис. 13, и условие задачи в виде множеств X, У входных и выходных атрибутов, соответственно. Выход: Список G функций, применение которых решает поставленную задачу.

proc Solve (A, F, X, Г): G proc Process(a) // знаем атрибут a

Н := 0 // применимые связи for s g a.up do II аргументы

G := [ ] // синтезируемая программа if s. left=0 & s.righteF then

Z У \ X // целевые атрибуты g := s.right

for aeX do Process (a) end for Я := я + g

vrtiile U + .0 do for reg.right do Dal (r) end for

if H=0 then return fail Del (g) // удаление ячейки

end if end if

select g e Я Del (a) // удапениеячейки

G - G + g end for

и - и \ g.right for s e a.down do И результаты

for a e g. right do if s.right=0 & s.lefts.F then

Process (a) g := s.lei't

end for Я := H - g

end while for reg.left do Del(r) end for

end proc Del (g) // удаление ячейки

proc Del (v) /1 удаление ячейки end if

v.left.right := v.right Del (s) II удаление ячейки

v.right.left := v.left end for

v.up.down s= v.down Del (a) // удаление ячейки

v.down.up := v.up end proc

Dispose(v)

end proc

В диссертации приведены алгоритмы синтеза для других случаев в аналогичном виде, с оценками сложности и доказательствами корректности.

Язык исполняемых программных спецификаций и методы его реализации — третье положение, выносимое на защиту. Язык был разработан совместно с В. Б. Новосельцевым в 2009 - 2010 годах и реализован при активном участии автора в Институте программных систем РАН.

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

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

В разделе 5.2 рассматривается внедрение разработанных автором методов повышения степени алгоритмизации в промышленности при автоматизации бизнес-процессов и создании ПОЯ. Всего рассмотрены три проекта, выполненные в ООО «Астрософт», ООО «АтДиа» и СПбГУ ИТМО.

В разделе 5.3 рассматривается применение разработанных автором концепций повышения степени алгоритмизации в университетах в учебном процессе и подготовке кадров. Всего рассмотрены три учебных курса, поставленные в СПбГПУ, СПбГУ ИТМО и других образовательных организациях.

В табл. 2 приведен общий список ПОЯ, разработанных автором.

Таблица 2. Предметные области и разработанные ПОЯ

ПО Язык Назначение и область применении Год Орг."

Системное программирование, создание инструментальных средств разработки ПОЯ и МПО FP/FPG (Fortran Preprocessor / Fortran Program Generator) расширение Фортрана проблемно-ориентированными типами данных 1978 ИТА 3 года

STEREOL (STP.pwise REfinement Oriented Language) составление программ методом пошагового уточнения 1979 ИТА, ИПА 5 лет

Декарт (DESCARTES DESCribe your Area, Realize the Target and Extract the Solution) декларативное описание моделей предметных областей, баз данных и пакетов прикладных программ 1980 ИТА 7 лет

ТАВР (Textual Automata Based Programming) текстовый язык автоматного программирования 2006

DiaDel (DIAgram DEfinition Language) реализация графических языков, использующих нотацию диаграмм 2007 ЗАО 1 год

ИПС (Исполняемые Программные Спецификация) задание программных спецификаций дпя автоматического синтеза программ 2009 ИПС 2 года

AutoLanD (AUTOmata LANguage Definition) определение ПОЯ на основе систем взаимодействующих автоматов 2008 ИТМО 3 года

Эфемеридная астрономия, создание средств автоматизации расчетов и обработки наблюдательных данных СЛОН (СЛежение и Обработка Наблюдений) решения задач эфемеридной астрономии 1986 ИТА, ИПА 25 лет

Improvement улучшение параметров математический моделей из наблюдений методом наименьших квадратов 1990 ИТА 5 лет

AstroTOP (Astro Table Oriented Programming) табличный подход к обработке данных 1991 ИТА 7 лет

DELTA (DELphi + TAble) решение задач эфемеридной астрономии на основе таблично-ориентированного метода с языком Паскаль как включающим языков 2006 ИПА 5 лет

AMPLE 3 (Adaptable Minor PLanets Ephemerides) пакет прикладных программ в области динамики малых тел Солнечной системы 2009 ИПА 1 год

Компьютерная верстка СВИТА (Система Верстки ИТА) входной язык системы верстки табличных изданий 1995 ИПА 15 лет

Графический интерфейс GUmL (GUI Description Language) язык публикаций, позволяющий описывать алгоритмы работы пользователя графического интерфейса 1995 БХВ 10 лет

GUIDE (GUI DEclaration) декларативный язык описания графического интерфейса пользователя 2003

Автоматизация бизнес- CPDS (Clipper Program Development System) система программирования дчя разработки бухгалтерских приложений баз данных 1989 Рот Фронт 5 лет

aCMK (автоматизированная Система Менеджмента Качества) описание бизнес-процессов и документооборота на основе концепции «живого» документа 2008 АтДиа 1 год

4 В таблице указаны основные организации и продолжительность практического применения разработки.

Заключение. В диссертации получены следующие основные результаты.

1) Выявлены механизмы влияния ПОЯ и МПО на степень автоматизации предметных областей; введены и развиты концепции сильного пользователя, циклов повышения продуктивности и доверительного программного фонда.

2) Обобщен и систематизирован опыт разработки семнадцати ПОЯ для алгоритмизации пяти предметных областей; предложены и опробованы методики выполнения шагов алгоритмизации и выработаны практические рекомендации по применению методов алгоритмизации.

3) Предложены классификации проблзмно-ориентированных языков, моделей предметных областей и методов алгоритмизации.

4) Разработан таблично-ориентированный метод алгоритмизации предметных областей, обеспечивающий эффективную интеграцию средств работы с данными, представляющими объекты предметной области, и средств работы с программами, представляющими операции предметной области; реализованы и применены на практике несколько таблично-ориентированных ПОЯ. Результат выносится на защиту.

5) Разработан автоматный метод определения ПОЯ, позволяющий определить все аспекты языка— структуру, внешнее представление, контекстные условия и операционную семантику; предложена модель взаимодействия автоматных объектов, обобщающая возможности автоматных моделей, предложенных ранее. Результат выносится на защиту.

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

7) Результаты диссертационного исследования внедрены в учебный процесс по подготовке бакалавров и магистров направления «Информатика и прикладная математика» в СПбГУ ИТМО и Санкт-Петербургском государственном политехническом университете.

Основные публикации по теме диссертации

1. Бабаев И. О., Лавров С. С., Новиков Ф. А., Петрушина Т. И. Специализированное программное обеспечение прикладных исследований / Тезисы докладов Всесоюзная конференции "Методы математической логики в проблемах искусственного интеллекта и систематическое программирование". Часть 2. Вильнюс. 1980, с. 7-25.

2. Бабаев И. О., Новиков Ф. А., Петрушина Т. И. Язык Декарт - входной язык системы СПОРА // Прикладная информатика. Выпуск I, М.: Финансы и статистика. 1981, с. 35-72.

3. Бабаев И.О., Лавров С.С., Нецветаева Г.А., Новиков Ф.А., Шувалов Г.М. СПОРА - система программирования с автоматическим синтезом программ / Тезисы докладов III конференции "Применение методов математической логики". Таллин. 1983, с. 29-41.

4. Бабаев И. О., Новиков Ф. А. Средства оформления функционального наполнения ППП в системе СПОРА / Тезисы докладов III Всесоюзной конференции "Автоматизация производства пакетов прикладных программ и трансляторов". Таллин. 1983, с. 62-64.

5. Агамирзян И. Р., Бреслав О. Д., Красинский Г. А., Новиков Ф. А., Скрипниченко В. И. ЭРА — проблемно-ориентируемая система, основанная на табличном подходе / Тезисы докладов III Всесоюзной конференция "Автоматизация производства систем программирования". Таллин. 1986, с. 97 - 99.

6. Krasinsky G. A., Novikov F. A., Skripnichenko V. I. Problem Oriented Language for Ephemeris Astronomy and its Realization in System ERA // IAU Colloquim 109 Proc., Gaithersburg, 1988; Celestial Mechanics, 1989, v.45, pp. 219 - 229.

7. Новиков Ф. А. Архитектура системы ЭРА — табличный подход к обработке данных. Сообщения ИПА РАН № 16.1990,32 с.

8. Rrasheninnikov S.V., Nazarov A.A., Novikov F.A. Skripnichenko V.l. ASTROTOP: automation of observations storage, retrieval and treatment // Baltic Astronomy. Vol. 6. No 2.1997, pp. 355,356.

9. Крашенинников С. В., Кривоногое А. В., Назаров А. А., Новиков Ф. А., Скрипниченко В, И. Система таблично-ориентированного программирования: 32-разрядная версия. Сообщения ИПА РАН № 122.1999, 33 с.

10. Новиков Ф. А. Визуальное конструирование программ II Информационно-управляющие системы. 2005, №6, с. 9 - 22 (список ВАК).

11. Михеева В. Д., Новиков Ф. А. Скрипниченко В. И. Дельта - язык и система программирования для решения прикладных задач с табличными данными // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. 2007, № 4-2(52), с. 57-59 (список ВАК).

12. Новиков Ф. А. Степанян К. Б. Язык описания диаграмм // Информационно-управляющие системы. 2007, №4, с. 28 - 36 (список ВАК).

13. Новиков Ф. А. Степанян К. Б. Использование порождающего программирования при реализации языка описания диаграмм // Информационно-управляющие системы. 2008, №6, с. 32 - 35 (список ВАК).

14. Клебан В. О., Новиков Ф. А. Применение конечных автоматов в документообороте // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. Выпуск 53, Автоматное программирование. 2008, с. 286 — 294 (список ВАК).

15. Новиков Ф. А., Тихонова У. Н. Определение проблемно-ориентированных языков интерпретируемыми автоматами // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета 2008, № 5(65), с. 93-98 (список ВАК).

16. Новиков Ф. А., Тихонова У. Н. Применение автоматного программирования для определения проблемно-ориентированных языков // Труды ИПА РАН. Вып. 19. 2008, с. 174-183.

17. Новиков Ф. А., Новосельцев В. Б. Предварительное сообщение о языке исполняемых программных спецификаций // Программные продукты и системы. 2009, № 2, с. 107 -111 (список ВАК).

18. Новиков Ф. А., Новосельцев В. Б. Язык исполняемых программных спецификаций // Программирование. 2010, №1, с. 66-78 (список ВАК).

19. Новиков Ф. А., Тихонова У. Н. Автоматный метод определения проблемно-ориентированных языков (Часть 1) // Информационно-управляющие системы.

2009, № 6, с. 34 - 40 (список ВАК).

20. Новиков Ф. А., Тихонова У. Н. Автоматный метод определения проблемно-ориентированных языков (Часть 2) // Информационно-управляющие системы.

2010, № 2, с. 31 - 37 (список ВАК).

21. Новиков Ф. А., Тихонова У. Н. Автоматный метод определения проблемно-ориентированных языков (Часть 3) // Информационно-управляющие системы. 2010, № 3, с. 29 - 37 (список ВАК).

Тиражирование и брошюровка выполнены в учреждении "Университетские телекоммуникации"

197101, Санкт-Петербург, ул. Саблинская, 14, тел. (812) 233 46 69 Тираж 100 экз. Объем 2,0 у.пл.

ВВЕДЕНИЕ.

Исходные положения и предмет исследований.

Актуальность темы диссертации.

Решаемые проблемы и постановка задачи.

Практическая значимость и накопленный опыт.

Структура диссертации и используемые обозначения.

1. НАЗНАЧЕНИЕ И ОБЛАСТЬ ПРИМЕНЕНИЯ МЕТОДОВ АЛГОРИТМИЗАЦИИ.

1.1. Технология разработки прикладного программного обеспечения.

1.1.1. Технология прикладного программирования.

1.1.2. Модель процесса разработки.

1.1.3. Циклы повышения продуктивности.

1.2. Средства алгоритмизации предметных областей.

1.2.1. Три задачи алгоритмизации.

1.2.2. Доверительный программный фонд.

1.2.3. Модель предметной области.

1.2.4. Сильный пользователь.

1.3. Порядок алгоритмизации предметной области.

1.3.1. Шаги алгоритмизации предметной области.

1.3.2. Классификация предметно-ориентированных языков.

1.3.3. Классификация моделей предметных областей.

1.3.4. Классификация методов алгоритмизации.

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

2. ПРЕДМЕТНО-ОРИЕТИРОВАННЫЕ МЕТОДЫ АЛГОРИТМИЗАЦИИ.

2.1. Командные предметно-ориентированные языки.

2.1.1. Явное и неявное программирование.

2.1.2. Графический интерфейс пользователя как командный предметно-ориентированный язык.

2.1.3. Язык описания пошаговых процедур.

2.2. Визуальные императивные языки.

2.2.1. Визуальное конструирование программ.

2.2.2. Язык описания диаграмм.

2.2.3. Документооборот «живых» документов.

2.3. Проблемно-ориентированные парадигмы.

2.3.1. Специализация как средство алгоритмизации.

2.3.2. Таблично-ориентированное программирование.

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

3. ЯЗЫКОВО ОРИЕНТИРОВАННЫЕ МЕТОДЫ АЛГОРИТМИЗАЦИИ.

3.1. Автоматный метод определения языков.

3.1.1. Назначение и область применения автоматного метода.

3.1.2. Задание абстрактного синтаксиса.

3.1.3. Методика преобразования грамматики в абстрактный синтаксис.

3.1.4. Задание контекстных условий.

3.2. Парадигма автоматного программирования.

3.2.1. Роль автоматного программирования в определении языка.

3.2.2. Взаимодействие автоматных объектов.

3.2.3. Методика задания конкретного синтаксиса исходя из метамодели языка.

3.2.4. Методика преобразования синтаксических диаграмм Вирта в систему автоматов конкретного синтаксиса.

3.2.5. Классификация способов использования операционной семантики языка.

3.2.6. Методика компиляции для системы параллельных автоматов операционной семантики.

3.3. Конкурентные преимущества и открытые вопросы автоматного метода.

3.3.1. Варианты использования автоматного метода.

3.3.2. Достоинства и недостатки автоматного метода.

3.3.3. Самодостаточность и гибкость автоматного метода.

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

4. МОДЕЛЬНО-ОРИЕНТИРОВАННЫЕ МЕТОДЫ АЛГОРИТМИЗАЦИИ.

4.1. Язык исполняемых программных спецификаций.

4.1.1. История структурного синтеза программ.

4.1.2. Принципы организации и область применения языка Т.

4.1.2. Метамодель языка

4.1.3. Графическая нотация языка ¥.

4.1.4. Текстовый синтаксис языка ¥.

4.2. Исчисление структурного синтеза программ.

4.2.1. Сигнатура исчисления структурного синтеза программ.

4.2.2. Аксиомы и правила вывода.

4.2.3. Семантические свойства формальной теории.

4.3. Алгоритмы структурного синтеза программ.

4.3.1. Волновой алгоритм синтеза.

4.3.2. Предобработка модели предметной области.

4.3.3. Линейный алгоритм синтеза.

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

ГЛАВА 5. ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ МЕТОДОВ АЛГОРИТМИЗАЦИИ.

5.1. Алгоритмизация вычислительных предметных областей в академических учреждениях.

5.1.1. Система автоматического синтеза программ по декларативным спецификациям

5.1.2. Табличный подход к обработке данных.

5.1.3. Автоматическая компьютерная вёрстка табличных изданий.

5.1.4. Электронная версия ежегодника «Эфемериды малых Планет».

5.1.5. Структурный синтез программ.

5.2. Внедрение методов алгоритмизации в промышленности.

5.2.1. Модель процесса разработки прикладного программного обеспечения.

5.2.2. Промышленное автоматное программирование.

5.2.3. Автоматизация бизнес-процессов.

5.3. Применение концепций алгоритмизации в учебном процессе и подготовке кадров.

5.3.1. Дискретная математика для программистов.

5.3.2. Моделирование на UML.

5.3.3. Системы представления знаний.

5.3.4. Подготовка кадров.

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

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

Исходные положения и предмет исследований

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

Алгоритмизацией предметной области называется разработка методов и программ, которые позволяют прикладным специалистам решать на компьютере все или большинство типовых задач данной предметной области.1 Предметная область — специфическая область человеческой деятельности — в диссертации трактуется как предмет алгоритмизации: история, социальная значимость предметной области и тому подобное— всё остаётся «за кадром». Алгоритмизация предметной области— очень широкое понятие, включающее различные процессы и принимающее разнообразные формы. Объектно-ориентированные анализ и проектирование [121], моделирование и построение баз данных [106], технология разработки прикладного программного обеспечения [110] — всё это и многое другое, относится к алгоритмизации предметных областей. Таким образом, предмет диссертации — методы алгоритмизации предметных областей— практически необозрим в своих частных проявлениях, поэтому необходимо конкретизировать предмет исследования.

1 Чарнецки и Айзенекер [114] используют термин «инженерия предметной области» (domain engineering).

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

1) определение предметно-ориентированных структур данных, представляющих объекты предметной области;

2) реализация программных процедур обработки этих структур — действий, или операций предметной области;

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

При этом считается, что предметная область достаточно четко очерчена, а множества объектов А, операций ^ и типовых задач надежно идентифицированы (перечислены) независимо от алгоритмизации предметной области.

Например, в предметной области «бухгалтерия»: часто используемый объект — «счёт», операция — «проводка», типовая задача — «начисление зарплаты». В предметной области «астрономия»: объект—«орбита», операция — «вычисление эфемериды», типовая задача — «уточнение параметров орбиты из наблюдений».

Степень алгоритмизации может быть различной. Чем больше типовых задач можно решить, и чем меньше затраты на их решение, тем выше степень алгоритмизации.

Предметом диссертационного исследования являются методы алгоритмизации предметных областей. Предлагаемые методы развивались постепенно, с конца 70-х годов, в результате анализа опыта выполнения работ

2 Эфемерида (от древнегреческого єфгщєро^ — годный на один день)— в астрономии предвычислениое положение небесного тела на определенный момент времени. по алгоритмизации конкретных предметных областей, сначала под руководством члена-корреспондента РАН С. С. Лаврова, а позже под руководством автора. Различные аспекты и элементы методов испытывались и постепенно совершенствовались в практических применениях, перечисленных в диссертации. К настоящему времени сложилась целостная методология, допускающая распространение на различные классы предметных областей.

Актуальность темы.диссертации

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

Традиционные методы алгоритмизации, до сих пор достаточно распространенные, состоят в том, что объекты предметной области представляются средствами систем управления базами данных (СУБД), операции программируются на языках программирования общего назначения в форме пакетов прикладных программ (111111), а методы решения типовых задач, частично остаются в форме математических моделей вне компьютера, а частично встраиваются в СУБД и 111111. Традиционные методы алгоритмизации хороши тем, что опираются на универсальные средства, и могут быть применены в любом случае, в котором алгоритмизация вообще возможна. Недостатки традиционных методов также давно известны: процесс алгоритмизации является трудоемким, дорогим и результаты алгоритмизации трудно использовать повторно в других предметных областях.

В настоящее время, наряду с традиционными методами, распространение получили и другие методы алгоритмизации, и, прежде всего, методы, основанные на применении предметно- и проблемно-ориентированных

3 м языков (ПОЯ) и формализованных моделей предметных областей (МПО). В данном контексте ПОЯ и МПО рассматриваются как формы представления знаний об объектах, операциях и типовых задачах предметной области.

Широко известны, например, такие проблемно-ориентированные языки, как TgX — язык компьютерной вёрстки [47], SQL — язык запросов к реляционным базам данных [106]. В этой работе проблемно-ориентированные языки противопоставляются языкам программирования общего назначения по следующему признаку. Языки общего назначения алгоритмически полны, то есть универсальны, область их применения не ограничена, и в силу своей универсальности такие языки не используют абстракции, характерные для предметных областей и далекие от машинной реализации.4 Специфические понятия предметных областей должны быть выражены в языке программирования общего назначения, то есть запрограммированы. От ПОЯ, напротив, не требуется универсальности, поэтому в них применяются абстракции высокого уровня, прямо соответствующие понятиям предметной области, и затраты на программирование сокращаются, хотя, возможно, возрастают затраты на реализацию ПОЯ. В то же время выбранные абстракции конкретного ПОЯ, разработанного для одной предметной области, могут оказаться неприменимыми в другой предметной области. Поэтому область применения каждого конкретного ПОЯ ограничена.

Известны различные подходы к представлению знаний о предметной области в форме МПО. Например, диаграммы «сущность-связь» в СУБД [106] или онтологии [141] в приложениях Интернета. Важно подчеркнуть, что

3 Терминологическое замечание: предметно-ориентированный язык ориентирован на данные конкретной предметной области; а проблемно-ориентированный язык ориентирован на методы обработки данных в ряде предметных областей. Аббревиатура «ПОЯ» нивелирует это различие, которое в большинстве случаев несущественно.

4 К языкам программирования общего назначения относятся, например, Си, Паскаль, Ада [52]. Абсолютно жесткой границы между проблемно-ориентированными языками и языками общего назначения провести невозможно, да это и не нужно. при использовании любого формализма МПО является абстракцией, которая используется для решения задач алгоритмизации, но не может претендовать на исчерпывающее описание самой предметной области.

Наблюдения автора и других исследователей [19, 24, 63, 114] показывают, что реализация ПОЯ и программное представление МПО, при выполнении определенных условий, дает выигрыш в степени алгоритмизации конкретных предметных областей по сравнению с традиционными методами. Таким образом, исследование методов определения, реализации и применения ПОЯ и МПО для алгоритмизации предметных областей, выбор критериев целесообразности применения ПОЯ и МПО, выявление факторов выигрыша,при алгоритмизации, является актуальной и весьма востребованной задачей.

Решаемые проблемы и постановка задачи

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

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

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

3) Проблема выразительной силы моделей, состоящая в выборе способов представления знаний предметной области. Языковые средства должны быть достаточны для декларативной постановки типовых задач при условии сохранения алгоритмической разрешимости. Заметим, что поставленные проблемы заведомо имеют тривиальные, но неудовлетворительные решения. Предметную ориентацию можно-выполнять индивидуально для каждой типовой задачи, но это очень неэффективно. Языки можно определять с помощью порождающих грамматик [5], но грамматики не позволяют задать контекстные условия и операционную семантику. Задачи на модели можно ставить на языке исчисления предикатов, но задача синтеза программ по пред- и постусловиям, выраженным в языке первого порядка, в общем случае сводится к задаче автоматического доказательства теорем [2] и не может быть решена эффективно. Следовательно, необходим критерий для сравнения методов алгоритмизации с точки зрения решения указанных проблем.

Заметим, что именно решение типовых задач, то есть получение значимого для пользователя результата, является основным требованием к алгоритмизации и ее более сильным формам: автоматизации5 и формализации.6 Таким образом, мерой качества7 алгоритмизации является доля типовых задач, которые можно решить в данной предметной области, не прибегая к дополнительному трудоемкому программированию на языках программирования общего назначения. Численное выражение меры качества алгоритмиза

5 Алгоритмизация, при которой все или некоторые типовые задачи решаются автоматически, без участия пользователя, здесь называется автоматизацией (предметной области).

6 Алгоритмизация, при которой все или некоторые составляющие задаются с помощью формальной математической теории, здесь называется формализацией (предметной области).

7 Качество: степень соответствия совокупности присущих характеристик требованиям. Определение стандарта ГОСТ Р ИСО 9000-2008, пункт 3.1.1. ции называется степенью алгоритмизации. Степень алгоритмизации — это общая мера, позволяющая сравнивать различные методы алгоритмизации. Предлагается определить степень алгоритмизации М как среднее геометрическое двух показателей: доля решаемых типовых задач Т (отношение числа типовых задач, которые можно решить средствами оцениваемой алгоритмизации, к числу всех идентифицированных типовых задач), и относительное снижение трудозатрат <5 (отношение средних трудозатрат на решение типовых задач после оцениваемой алгоритмизации, к средним трудозатратам на решение той же совокупности задач до алгоритмизации): М = л/Т(1 - 5).

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

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

Практическая значимость и накопленный опыт

Работа носит практический характер. Предлагаемая в диссертации методология многократно применялась автором на практике для определения и реализации разнообразных ПОЯ и МПО (всего 17 случаев) в следующих предметных областях: 1) инструментальные средства разработки программного обеспечения; 2) эфемеридные расчеты в астрономии; 3) компьютерная верстка табличных изданий; 4) описание графического интерфейса пользователя; 5) автоматизация бизнес-процессов в системах менеджмента качества.

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

Автор участвовал в создании, реализации и использовании следующих язы-8 ков.

I. FP/FPG (Fortran Preprocessor / Fortran Program Generator) — язык для описания расширения фортрана проблемно-ориентированными типами данных, 1979, [14], совместно с И. О. Бабаевым. Язык был использован в ряде специализированных пакетов аналитических вычислений (систем компьютерной алгебры) для решения астрономических задач. Регулярно использовался в Институте теоретической астрономии АН СССР в течение, примерно, пяти лет.

II. STEREOL (STEpwise REfinement Oriented Language) — язык для составления программ методов пошагового уточнения, 1979, [15]. На основе языка было последовательно реализовано три инструментальных средства, которые регулярно использовались для разработки в Институте теоретической астрономии и в Институте прикладной астрономии АН СССР в течение, примерно, семи лет.

III. Декарт (DESCARTES — DESCribe your Area, Realize the Target and Extract the Solution) — язык описания моделей предметных областей, баз данных и пакетов прикладных программ, ориентированный на автоматический синтез программ (система СПОРА), 1980, [18 — 20, 22, 27 - 29, 37], совместно с И. О. Бабаевым, С. С. Лавровым, Т. И. Петру

8 Языки перенумерованы римскими цифрами. Эти номера используются для ссылок, подтверждающих те или иные наблюдения, сделанные в следующих главах. шиной и другими. Реализация языка была зарегистрирована в Государственном фонде алгоритмов и программ [И. Р. Агамирзян, И. О. Бабаев и др. Система программных средств автоматического синтеза программ СПОРА. ГосФАП СССР, №50860000399, 1986].

IV. CJIOH (СЛежение и Обработка Наблюдений) — язык для решения задач эфемеридной астрономии, основанный на табличном подходе к обработке данных (система ЭРА — Эфемеридные расчеты в астрономии), 1986, [40, 41, 53-55, 122], совместно с Г. А. Красинским и В. И. Скрипниченко. Язык постоянно используется уже более четверти века в Институте теоретической астрономии и в Институте прикладной астрономии РАН для решения сложных задач эфмеридной астрономии, в том числе для построения численных теорий движения планет и Луны, имеющих большое значение для системы ГЛОНАСС и других важных приложений. Язык был реализован на трех программно-аппаратных платформах (БЭСМ-6, MS DOS, MS Windows) и продолжает развиваться.

V. CPDS (Clipper Program Development System) — система программирования для разработки приложений баз данных на языке Clipper, 1989 [не опубликовано], совместно с А. А. Игнатовичем. Система основана на интерпретации описания пользовательского интерфейса и правил обработки данных в базе данных (метаданных), причем метаданные хранятся в таком же формате и обрабатываются теми же средствами, что и основные данные. На основе этой системы было реализовано, внедрено и долгое время эксплуатировалось в различных организациях несколько вариантов системы КРАБ (Компьютерная Регулярная Автоматизированная Бухгалтерия).

VI. Improvement — входной язык пакета прикладных программ для улучшения параметров математических моделей из наблюдений методом наименьших квадратов, 1990 [56, 57, 60-62], совместно с

Т. В. Ивановой и Е. Ю. Парийской. Язык был реализован дважды и использовался совместно с системой ЭРА в течение ряда лет, а затем был интегрирован в эту систему и прекратил самостоятельное развитие.

VII. AstroTOP (Astro Table Oriented Programming) — предметно-ориентируемый язык, основанный на табличном подходе к обработке данных, 1991, [58, 59, 64-66, 70, 72, 73, 77], совместно с С. В. Крашенинниковым, А. А. Назаровым и В. И. Скрипниченко. Язык был задуман и дважды реализован как независимое от предметной области обобщение языка СЛОН. Вторая реализация выполнена как проект по гранту РФФИ № 94-02-05296 «Технология сбора, хранения и обработки астрономической информации» под руководством автора.

VIII. GUIDL (GUI Description Language) — язык публикаций, позволяющий описывать алгоритмы работы пользователя графического интерфейса, 1995, [67, 78, 81, 99], совместно с А. Д. Яценко. Язык был использован автором диссертации и последователями для описания пошаговых процедур действий пользователя популярных офисных пакетов, в частности Microsoft Office. Язык использовался как язык публикаций в целом ряде монографий в период с 1995 по 2004 год.

IX. СВИТА (Система Вёрстки ИТА) — входной язык системы вёрстки табличных изданий, 1998, [74, 75], совместно с Г. А. Нецветаевой и Е. Ю. Парийской. Язык постоянно применяется с 1995 года для подготовки и вёрстки наукоемких табличных изданий (астрономических ежегодников и альманахов) в Институте теоретической астрономии, а теперь в Институте прикладной астрономии РАН.

X. GUIDE - декларативный язык описания графического интерфейса пользователя и связи интерфейса с пакетом прикладных программ,

2003, [98], совместно с Г. А. Нецветаевой, Е. Ю. Парийской и В. И. Скрипниченко. Самостоятельного применения не получил.

XI. DELTA (DELphi + TAble) — язык для решения задач эфемеридной астрономии, основанный на табличном подходе к обработке данных и встроенный в язык Паскаль как включающий язык, 2006, [122] совместно с В.Д. Михеевой и В.И. Скрипниченко. Язык реализован как средство расширения возможностей применения системы ЭРА и регулярно используется для выпуска системы PersAY — электронной версии Астрономического ежегодника в Институте прикладной астрономии РАН.

XII. ТАВР (Textual Automata Based Programming) — текстовый язык автоматного программирования, 2006, [не опубликовано], совместно с Е. А. Цимбалюком. Язык был реализован, и с его помощью выполнено несколько демонстрационных примеров, но дальнейшего развития не получил.

XIII. DiaDel (DIAgram DEfinition Language) — язык описания графических языков, использующих нотацию графоподобных диаграмм, 2007, [124, 125], совместно с К. Б. Степаняном. Язык реализован и применяется в настоящее время для анализа бизнес-процессов в финансовой сфере в форме реализации нотации специальных диаграмм.

XIV. AutoLanD (Automata-based Language Definition) — семейство визуальных языков для определения ПОЯ, 2008, [127, 128, 134- 137], совместно с У. Н. Тихоновой. В настоящее время применяется для реализации автоматного метода в университете г. Эйдховен (Голландия).

XV. аСМК (автоматизированная Система Менеджмента Качества) — язык описания бизнес-процессов и документооборота, 2008 [126], совместно с В. О. Клебаном. Язык был реализован в рамках гранта Фонда Бортника. Получено свидетельство об официальной регистрации программы для ЭВМ №2007612840 от 27 июня 2007 года «Конструктор системы менеджмента качества на базе MS Office».

XVI. ИПС (Исполняемые Программные Спецификации) — язык исполняемых программных спецификаций, основанный на автоматическом синтезе программ, 2009, [132, 133], совместно с В.Б. Новосельцевым. Язык реализован и используется в рамках программы СКИФ-ГРИД (проект «Инструментальный программный комплекс моделирования сложных предметных областей с возможностями автоматического синтеза параллельных программ») в Институте программных систем РАН.

XVII. AMPLE 3 (Adaptable Minor PLanets Ephemerides) — входной язык заданий для пакета прикладных программ в области динамики малых тел Солнечной системы, 2009, [138] совместно с Г. А. Нецветаевой и другими. Пакет распространяется Институтом прикладной астрономии РАН совместно с ежегодником Эфемериды малых планет.

Структура диссертации и используемые обозначения

Диссертация изложена на 196 страницах и состоит из введения, пяти глав и заключения. Список литературы содержит 149 наименований. Работа иллюстрирована 44 диаграммами.

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

1) Автоматический синтез вычислительных программ по декларативным спецификациям —- перспективный метод алгоритмизации и формализации предметных областей.

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

3) Наряду с системным и прикладным программированием существует модельное программирование, и составление МПО является характерным примером модельного программирования.

4) Язык исполняемых программных спецификаций Ч7 предназначен для спецификации МПО, описания ДПФ и постановки типовых задач.

5) Применение формальных (логических) методов совместно с программными эвристиками позволяет получать полезные результаты.

6) Автоматический синтез программ обеспечивает семантическую корректность синтезированных программ с точностью до семантической корректности ДПФ; тестирование и иные методы проверки правильности оказываются излишними.

7) Предобработка МПО позволяет строить эффективные алгоритмы синтеза программ, обладающие требуемыми свойствами.

Язык исполняемых программных спецификаций и методы его реализации — третье положение, выносимое на защиту. Язык разработан автором совместно с В. Б. Новосельцевым в 2009-2010 гг. в ИПС РАН и ИПА РАН. Язык исполняемых программных спецификаций является решением третьей проблемы алгоритмизации (см. стр. 9) для вычислительных предметных областей.

ГЛАВА 5. ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ МЕТОДОВ

АЛГОРИТМИЗАЦИИ

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

• Использование разработанных автором ПОЯ для повышения степени алгоритмизации вычислительных предметных областей в учреждениях Российской академии наук.

• Внедрение разработанных автором методов повышения степени алгоритмизации в промышленности при автоматизации бизнес-процессов и создании ПОЯ.

• Применение разработанных автором концепций повышения степени алгоритмизации в университетах в учебном процессе и подготовке кадров.

5.1. Алгоритмизация вычислительных предметных областей в академических учреждениях

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

5.1.1. Система автоматического синтеза программ по декларативным спецификациям

Шифр: СПОРА, название: «Специальное программное обеспечение работ по астрономии», Институт теоретической астрономии АН СССР, 1978 -1986, [18, 19, 20, 22, 27, 28, 29, 37]. Проект предусматривал разработку семейства проблемно-ориентируемых языков для комплексной алгоритмизации любых предметных областей, связанных с вычислительными задачами и обработкой наблюдений. В рамках проекта был разработан язык Декарт [III] — декларативный язык спецификаций очень высокого уровня (40Ь) и выполнена реализация существенного подмножества языка на ЭВМ БЭСМ-6. Разработанное программное обеспечение прошло приемо-сдаточные испытания (протокол приемо-сдаточных испытаний Межведомственной комиссии при Совмине СССР) и было сдано в государственный фонд алгоритмов и программ [И/Р. Агамирзян, И. О. Бабаев и др. Система программных средств автоматического синтеза программ СПОРА. Свидетельство ГосФАП СССР, №50860000399].

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

54 Некоторые из упоминаемых документов нужно искать в архивах уже несуществующих учреждений. Тем не менее, эти документы существуют. сти 01.01.10 «математическое обеспечение вычислительных машин и систем» на тему «Реализация абстрактных типов и отображений в программном обеспечении прикладных исследований» [29].

5.1.2. Табличный подход к обработке данных

Шифр: ЭРА, название: «Эфемеридные расчеты в астрономии», Институт теоретической астрономии АН СССР 1984 - 1988, Институт прикладной астрономии АН СССР 1988 - 1990, Институт теоретической астрономии РАН 1994 - 1997, Институт прикладной астрономии РАН 2007-2010, [40, 41, 53, 54, 55, 58, 59, 64, 65, 66, 68, 69, 70, 72, 73, 77, 122]. В этой многочисленной группе проектов были разработаны несколько таблично-ориентированных языков (СЛОН [IV], АстроТОП [VII], Дельта [XI]) для решения задач в предметной области «эфемеридная астрономия».55 Разработанные ПОЯ и ДПФ были реализованы на трех программно-аппаратных платформах (ЭВМ БЭСМ-6 + Паскаль, MS DOS + Turbo Pascal, MS Windows + Delphi), причем каждый язык был реализован в нескольких версиях.

В 1994 - 1997 годах на основе таблично-ориентированного метода алгоритмизации предметных областей был выполнен проект по гранту РФФИ № 94-02-05296 «Технология сбора, хранения и обработки астрономической информации» (руководитель Новиков Ф. А.).

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

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

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

5.1.3. Автоматическая компьютерная вёрстка табличных изданий

Шифр: СВИТА, название: «Система вёрстки ИТА», Институт теоретической астрономии РАН, Институт прикладной астрономии РАН, 19931999, [74, 75]. В этом проекте была создана предметно ориентированная система для подготовки и верстки ответственных табличных изданий (астрономических ежегодников и альманахов) в Институте теоретической астрономии, а теперь в Институте прикладной астрономии РАН. Астрономические ежегодники используются в службах навигации, связи, точного времени и в других жизненно важных областях. Эти издания являются чрезвычайно наукоемкими — всего несколько стран в мире имеют научный потенциал, достаточный для выпуска подобных изданий. Основная цель проекта достигнута: «Астрономический ежегодник» издается с помощью системы СВИТА с 1995 года, о чем имеется специальная запись в выходных данных издания. В последующие годы с помощью системы был автоматизирован выпуск других изданий, в настоящее время с помощью системы СВИТА издаются все астрономические издания ИПА РАН.

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

5.1.4. Электронная версия ежегодника «Эфемериды малых Планет»

Шифр: AMPLE 3, название «Adaptable Minor PLanets Ephemerides», Институт прикладной астрономии РАН, 2009 - 2010, [138]. Проект является реализацией третьей версии электронного приложения к международному изданию «Эфемериды малых планет» [XVII]. В этом проекте автор разрабатывал язык заданий, и осуществлял общее руководство проектом. В рамках проекта в окончательной форме было подтверждено наблюдение, состоящее в том, что графический интерфейс пользователя является командным предметно ориентированным языком. Разработанный пакет доступен по адресу http://www.ipa.nw.ru/PAGE/DEPFUND/LSBSS/ample3.hti-nl

5.1.5. Структурный синтез программ

Шифр: VP, название: «Инструментальный программный комплекс моделирования сложных предметных областей с возможностями автоматического синтеза параллельных программ» Институт программных систем РАН, 2008-2010, [132, 133]. В рамках программы СКИФ-ГРИД, Мероприятие 4: «Научно-исследовательские работы по перспективным областям применения создаваемых вычислительных установок, в том числе: разработка пилотных образцов различных систем; проведение проектов, демонстрирующих возможности создаваемых вычислительных средств, а также исследований, посвященных решению актуальных задач науки и техники на основе использования суперкомпьютеров» был выполнен проект 2010р424 [XVI].

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

5.2. Внедрение методов алгоритмизации в промышленности

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

5.2.1. Модель процесса разработки прикладного программного обеспечения

Шифр: ASDH, название: «Astro Software Development House», ООО «АстроСофт», 1997-2000, [113, 140, 146]. С целью повышения продуктивности разработки прикладного программного обеспечения в компании «АстроСофт» автором была создана оригинальная модель процесса разработки и подготовлены регламенты проведения типового проекта по разработке программного обеспечения.56 В этот период получили значительное развитие и практическое внедрение аспекты работы автора, связанные с технологией программирования, в частности, концепции циклов повышения продуктивности и сильного пользователя.

56 Общий объем разработанной автором документации — несколько сот страниц. К сожалению, эта внутренняя документация компании «АстроСофт» является корпоративной собственностью и не была опубликована в открытой печати. Некоторые положения модели были опубликованы позднее.

5.2.2. Промышленное автоматное программирование

Шифр: UniMod, название «Автоматное программирование», Санкт-Петербургский государственный университет информационных технологий, механики и оптики, ИТМО, 2005-2007. Данный проект является весьма объемным государственным заказом, полученным по конкурсу ФЦНТП «Исследования и разработки по приоритетным направлениям развития науки и техники на 2002-2006 годы» (извещение №9-к-663 от 2 мая 2005 г.). Автор выполнял обязанности ответственного исполнителя в отчетах по госконтракту ИТ-13.4/004 «Технология автоматного программирования: применение и инструментальные средства».

В этот период автором была разработана модель взаимодействующих автоматных объектов, которая использована в автоматном методе определения проблемно-ориентированных языков [127, 128, 131, 134— 137]. В настоящее время У. Н. Тихоновой выполняется новая реализация предложенной автором автоматной модели и машины автоматного программирования в Техническом университете г. Эйдховен (Голландия).

5.2.3. Автоматизация бизнес-процессов

Шифр: аСМК, название «Автоматизированная система менеджмента качества», ООО «АтДиа», 2007—2008, [126]. Проект был реализован на грант, полученный в результате конкурса фонда Бортника «СТАРТ 07». Документами, подтверждающими результаты внедрения, являются отчеты по проекту «Разработка инструментальных программных средств на базе © MS Office для внедрения автоматизированной Системы Менеджмента Качества (СМК) в компаниях с проектным типом организации производства» и свидетельство об официальной регистрации программы для ЭВМ №2007612840 от 27 июня 2007 года «Конструктор системы менеджмента качества на базе MS Office». Этот проект является сугубо практическим приложением идей использования ки (множеств, отношений, графов, формул, функций) в виде структур данных в языках программирования. Математическое знание должно быть доведено до программного кода, в противном случае его трудно использовать в приложениях. Курс подкреплен учебником «Дискретная математика» [149], 2011 года, и учебным пособием «Дискретная математика для программистов», три издания, 2000, 2003, 2008 годы [141]. Все издания подготовило издательство Питер. Курс поставлен в СПбГПУ с 1986 года и в ИТМО с 2010 года.

5.3.2. Моделирование на UML

В этом курсе излагается основа основ— lingua franca современных модельных программистов — унифицированный язык моделирования UML. Уметь понимать диаграммы UML прикладным программистам сейчас так же необходимо, как уметь понимать математические формулы. Курс подкреплен монографией «Моделирование на UML» (с Ивановым Д. Ю.), 2010 [146]. В 2008 году вариант этого курса под названием «Анализ и проектирование на UML» был удостоен премии Sun Microsystems Teaching Grant. Курс поставлен в СПбГПУ с 2000 года, в ИТМО с 2005 года, преподавался на мат/мехе в 2006-2007 годах, а также в виде семинаров в Интернете (http://uml3.ru) и корпоративных курсов в организациях [139].

5.3.3. Системы представления знаний

Этот курс сейчас активно развивается в сотрудничестве с В.Б.Новосельцевым (ИПС РАН), со следующего 2011/2012 учебного года курс будет содержать, в частности, материал четвертой главы диссертации в полном объеме. Курс подкреплен монографией «Искусственный интеллект: представление знаний и методы поиска решения» (с Новосельцевым В. Б.), которая планируется к выходу в 2011 году в издательстве «Наука и Техника». Курс поставлен в СПбГПУ с 1992 года. сколько таблично-ориентированных ПОЯ. Результат выносится на защиту.

5) Разработан автоматный метод определения ПОЯ, позволяющий определить все аспекты языка— структуру, внешнее представление, контекстные условия и операционную семантику. Предложена модель взаимодействия автоматных объектов, обобщающая возможности автоматных моделей, предложенных ранее. Результат выносится на защиту.

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

7) Результаты диссертационного исследования внедрены в учебный процесс по подготовке бакалавров и магистров направления «Информатика и прикладная математика» в СПбГУ ИТМО и Санкт-Петербургском государственном политехническом университете.

Методы повышения степени алгоритмизации

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

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

• Целесообразно определить предметно-ориентированный язык, обладающий достаточной выразительной силой для описания решения всех типовых задач предметной области, причем определение языка должно быть достаточно формализованным, в основе определения должна лежать метамодель, а класс типовых задач должен быть достаточно представительным.

Положения, выносимые на защиту

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

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

• Автоматный метод реализации проблемно-ориентированных языков, в том числе визуальных, позволяющий определить все аспекты языка — структуру, внешнее представление, контекстные условия и операционную семантику. Полное определение языка автоматным методом является реализацией языка. В основу метода положена модель взаимодействующих автоматных объектов, обобщающая возможности автоматных моделей, предложенных ранее.

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

1. Тыугу Э.Х. Решение задач на вычислительных моделях // ЖВМ и МФ, 1970, 10, №3, с. 716-733.

2. Manna Z., Waldinger R. Towards automatic program synthesis // Communications of the ACM, 1971, Vol. 14, No 3, pp. 151 166.

3. Линдси Ч., Мюйлен С. Неформальное введение в Алгол-68. М.: Мир, 1973, 407 с.

4. Wegbreit D. The treatment of types in EL/1 // Communications of the ACM, 1974, Vol. 17, No. 5, pp. 251 264.

5. Братчиков И. Л. Синтаксис языков программирования. М.: Наука, 1975, 232 с.

6. Оллонгрен А. Определение языков программирования интерпретирующими автоматами. М.: Мир, 1977, 288 с.

7. Ершов А. П., Грушецкий В. В. Метод описания алгоритмических языков, ориентированный на реализацию. Новосибирск, Препринт ВЦ СО АН СССР. 1977, №74, 39 с.

8. Guttag J. Abstract data types and the development of data structures // Communications of the ACM, 1977, vol. 20, No. 6, pp. 396 404.

9. Gehani N. Units of measure as a data attributes // Computer languages, 1977, vol. 2, No. 3, pp. 93-111.

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

11. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Том 2. Компиляция. М.: Мир, 1978, 487 с.

12. Кнут Д. Искусство программирования для ЭВМ. Том 3. Сортировка и поиск. М.: Мир, 1978, 844 с.

13. Брукс-мл. Ф. П. мл. Как проектируются и создаются программные комплексы. Мифический человеко-месяц. Очерки по системному программированию. М.: Наука, 1979, 151 с.

14. Бабаев И. О., Новиков Ф. А. Руководство по использованию системы FP/FPG. Препринт «Алгоритмы небесной механики» № 22. Л.: 1979, 32 с.

15. Новиков Ф. А. Программа для составления программ методом пошагового уточнения. Препринт «Алгоритмы небесной механики» № 26. Л.: 1979, 16 с.

16. Тыугу Э. X., Харф М. Я. Алгоритмы структурного синтеза программ // Программирование, 1980, № 4, с. 3 13.

17. Майерс Г. Надежность программного обеспечения. М.: Мир, 1980, 360 с.

18. Новиков Ф. А. Декарт — язык для работы с пакетами прикладных программ и базами данных / Тезисы докладов III всесоюзного совещания «Алгоритмы небесной механики». Рига. 1980, с. 15, 16.

19. Новиков Ф. А. Абстрактные типы данных в языке Декарт / там же, с. 227 229.

20. Кахро М. И., Калья А. П., Тыугу Э. X. Инструментальная система программирования ЕС ЭВМ (ПРИЗ). М.: Финансы и статистика, 1981, 158 с.

21. Бабаев И. О., Новиков Ф. А., Петрушина Т. И. Язык Декарт — входной язык системы СПОРА // Прикладная информатика, сборник статей подред. В.М.Савинкова. Выпуск I, М., "Финансы и статистика". 1981, с. 35-72.

22. Солтан В. П., Мейдман С. И. Тождества и неравенства в треугольнике. Кишинев, Штиинца, 1982, 59 с.

23. Лавров С. С. Синтез программ // Кибернетика, 1982, № 6, с 11-16.

24. Ershov А. P. Mixed Computation: Potential Applications and Problems for Study // Theoretical Computer Science, Vol. 18, Issue 1, 1982, pp. 41 67.

25. Автоматический синтез программ / Сб. статей под ред. Г. Е. Минца и Э. X. Тыугу. Таллин, 1983, 202 с.

26. Бабаев И. О., Лавров С. С., Нецветаева Г. А., Новиков Ф. А., Шувалов Г. М. СПОРА система программирования с автоматическим синтезом программ / Тезисы докладов III конференции "Применение методов математической логики". Таллин, 1983, с. 29-41.

27. Бабаев И. О., Новиков Ф. А. Средства оформления функционального наполнения ППП в системе СПОРА / Тезисы докладов III Всесоюзной конференции "Автоматизация производства пакетов прикладных программ и трансляторов". Таллин, 1983, с. 62 64.

28. Новиков Ф. А. Реализация абстрактных типов и отображений в программном обеспечении прикладных исследований. Дисс. канд. физ.-мат. наук по спец. 01.01.10. Л.:, 1983, 85 с.

29. Ульман Дж. Основы систем баз данных. М.: Финансы и статистика, 1983, 334 с.

30. Непейвода Н. Н. Семантика алгоритмических языков. // Итоги науки и техн. Сер. Теор. вероятн. Мат. стат. Теор. кибернет., 20, ВИНИТИ, М., 1983, с. 95- 166.

31. Тыугу Э.Х. Концептуальное программирование. М.: Наука, 1984, 256 с.

32. Диковский А. Я. Детерминированные вычислительные модели // Техническая кибернетика, 1984, №5, с. 84 — 105.

33. Новосельцев В. Б. Синтез рекурсивных программ в системе СПОРА. Препринт «Алгоритмы небесной механики», № 43. Л.: ИТА АН СССР, 1985,24 с.

34. Диковский А. Я. Решение в линейное время алгоритмических проблем, связанных с синтезом ациклических программ // Программирование, 1985, №3, с. 38-49.

35. Новикова Е. В. Планирование циклических программ в системе СПОРА. Препринт «Алгоритмы небесной механики», № 45. Л.: ИТА АН СССР, 1986,31 с.

36. Новиков Ф. А., Сахаров А. Л. Типизация данных посредством пакетовпрограмм / Тезисы докладов III Всесоюзной конференции "Автомати*зация производства систем программирования". Таллин. 1986, с. 199, 200.

37. Агамирзян И. Р. Система технологической поддержки разработки трансляторов «ШАГ». Подсистема построения анализаторов. Препринт «Алгоритмы небесной механики» № 46. Л.: ИТА АН СССР, 1986, 50 с.

38. Шувалов Г. М. Система технологической поддержки разработки трансляторов «ШАГ». Подсистема управления библиотеками и установки параметров. Препринт «Алгоритмы небесной механики» № 47. Л.: ИТА АН СССР, 1986, 48 с.

39. Агамирзян И. Р., Красинский Г. А., Новиков Ф. А., Скрипниченко В. И. Автоматизированная система эфемеридных расчетов астрономии / Тезисы докладов Всесоюзной школы-семинара "Динамика механических систем". Томск, 1986.

40. Лавров С.С. Представление и использование знаний в автоматизированных системах // Микропроцессорные средства и системы, 1986, № 3, с. 14-20.

41. Канович М. И. Оценки сложности синтеза программ в концептуальных базах знаний / Логические методы построения эффективных алгоритмов. Междуведомственный тематический сборник научных трудов. Калинин, 1986, с. 32 52.

42. Нейман В. С. Безразверточный синтез программ на вычислительных моделях с R-формулами / Логические методы построения эффективных алгоритмов. Междуведомственный тематический сборник научных трудов. Калинин, 1986, с. 71 — 81.

43. Новикова Е. В. Об алгоритме синтеза циклических программ по системам рекуррентных соотношений / Логические методы построения эффективных алгоритмов. Междуведомственный тематический сборник научных трудов. Калинин, 1986, с. 86 90.

44. Пакеты прикладных программ. Инструментальные системы. Сб. статей под ред. А. А. Самарского. М.: Наука, 1987, 148 с.

45. Knuth D. The TeXbook. American Mathematical Society, Addison Wesley Publishing Company, 1988, 481 p.

46. Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. 2-е изд. перераб. и доп. М.: Энергоатомиздат, 1988, 480 с.

47. Брябрин В.М. Программное обеспечение персональных ЭВМ. М.: Наука, 1988, 272 с.

48. Джоунз Г. Программирование на языке Оккам. М: Мир, 1989, 208 с.

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

50. Языки программирования Ада, Си, Паскаль. / Сб. статей под ред. А. Фьюэра и Н. Джехани. М.: Радио и связь, 1989,

51. Васильев И. А., Игнатович А. А., Красинский Г. А., Новиков Ф. А., Скрипниченко В. И. Табличный подход к обработке данных и его реализация в системе ЭРА / Тезисы докладов конференции "Диалог "Человек-ЭВМ". Часть 3. Свердловск. 1989, с. 77, 78.

52. Krasinsky G. A., Novikov F. A., Skripnichenko V. I. Problem Oriented Language for Ephemeris Astronomy and its Realization in System ERA // IAU Colloquim 109 Proc., Gaithersburg, 1988; Celestial Mechanics, 1989, v.45, p. 219 229.

53. Новиков Ф. А. Архитектура системы ЭРА — табличный подход к обработке данных. Сообщения ИПА РАН № 16. 1990, 32 с.

54. Иванова Т. В., Новиков Ф. А. Пакет программ улучшения наблюдаемых параметров для IBM PC. Сообщения ИПА РАН № 21. 1990, 40 с.

55. Иванова Т. В., Новиков Ф. А. Улучшение параметров орбит небесных тел на IBM PC / Материалы II Всесоюзной астрономической школы-семинара по программе "Орбита". Тирасполь, 1990.

56. Новиков Ф. А., Скрипниченко В. И. Система таблично-ориентированного программирования / Тезисы докладов Всесоюзного совещания "Компьютерные методы небесной механики". СПб., 1991, с. 48, 49.

57. Иванова Т. В., Новиков Ф. А. Автономный пакет программ улучшения параметров орбит небесных тел на IBM PC / Тезисы докладов Всесоюзного совещания "Эфемеридная астрономия и позиционные наблюдения". Л.:, 1991, с. 60, 61.

58. Иванова Т. В., Новиков Ф. А., Парийская Е. Ю. Автономный пакет программ улучшения параметров движения небесных тел для IBM PC / Всероссийское совещание "Компьютерные методы небесной механики". СПб.: 1992, с. 21, 22.

59. Иванова Т. В., Новиков Ф. А., Парийская Е. Ю. Автономный пакет программ улучшения наблюдаемых параметров для IBM PC. Препринт ИТА РАН № 29. 1992, 70 с.

60. Ward М.Р. Language Oriented Programming // Software — Concepts and Tools. 1994, Vol. 15, No. 4, pp. 147 161.

61. Крашенинников С. В., Назаров А. А., Новиков Ф. А. АстроТОП: таблично ориентированное программирование астрономических задач / Тезисы докладов совещания Компьютерные методы небесной механи-ки-95. СПб.: ИТА РАН. 1995, с. 135-137

62. Крашенинников С. В., Новиков Ф. А. АстроТОП — технология сбора, хранения и обработки астрономической информации / Тезисы докладов совещания «Информационные системы в науке-95». М.: Фазис, 1995, с. 63-64.

63. Новиков Ф. А., Яценко А. Д. Microsoft Office в целом. — СПб.: BHV-Санкт-Петербург, 1995, 336 с.

64. Крашенинников С. В. Управление данными в системе Таблично-ориентированного программирования. Дисс. канд. физ.-мат. наук по спец. 05.13.11. СПб.:, 1995, 91 с.

65. Крашенинников С. В. ТОП-модель: формальное описание. СПб.: Препринт ИТА РАН, 1995, № 45, 91 с.

66. Solomon K. Developing Applications with Microsoft Office 95. Microsoft Press, 1996, 609 p.

67. Krasheninnikov S. V., Nazarov A. A., Novikov F. A. Skripnichenko V. I. ASTROTOP: automation of observations storage, retrieval and treatment // Baltic Astronomy. Vol. 6, N 2, 1997, p. 355, 356.

68. Нецветаева Г. А., Новиков Ф. А., Парийская Е. Ю. Система автоматической верстки табличных изданий (СВИТА). Сообщения ИПА РАН№ 118. 1998, 60 с.

69. Нецветаева Г. А., Новиков Ф. А., Парийская Е. Ю. Система автоматической верстки табличных изданий (СВИТА): аспекты реалии-зации. Сообщения ИПА РАН №119. 1999, 32 с.

70. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. 2-е изд. М.: Бином, СПб.: Невский диалект, 1999, 560 с.

71. Крашенинников С. В., Кривоногое А. В., Назаров А. А., Новиков Ф. А., Скрипниченко В. И. Система таблично ориентированного программирования: 32-разрядная версия. Сообщения ИПА РАН № 122. 1999,33 с.

72. Новиков Ф. А., Яценко А. Д. Microsoft Office 97 в целом. — СПб.: BHV-Санкт-Петербург, 1999, 624 с.

73. Брукс. Ф. Мифический человеко-месяц или как создаются программные системы. СПб.: Символ-Плюс, 1999, 304 с.

74. Горбатов В. А. Фундаментальные основы дискретной математики. Информационная математика. М.: Наука, 1999, 544 с.

75. Гарнаев А. Ю., Матросов А. В., Новиков Ф. А., Усаров Г. Е., Харитонова И. A. Microsoft Office 2000: разработка приложений / Под общ. ред. Ф. А. Новикова. — СПб.: БХВ-Санкт-Петербург. 2000, 656 с.

76. Ларман К. Применение UML и шаблонов проектирования. М.: Вильяме, 2001, 496 с.

77. Гордеев А. В., Молчанов А. Ю. Системное программное обеспечение. СПб: Питер, 2001, 736 с.

78. Лавров С. С. Программирование. Математические основы, средства, теория. СПб.: БХВ-Петербург, 2001, 317 с.

79. Леоненков А. В. Самоучитель UML. СПб.: БХВ-Петербург, 2001, 304 с.

80. Карпов Ю. Г. Теория автоматов. СПб.: Питер, 2002, 224 с.

81. Орлов С. А. Технологии разработки программного обеспечения: учебник. СПб.: Питер, 2002, 464 с.

82. Якобсон А., Буч Г., Рамбо Дж. Унифицированный процесс разработки программного обеспечения. СПб : Питер, 2002, 492 с.

83. Бек К. Экстремальное программирование. СПб.: Питер, 2002, 224 с.

84. Леффингуэлл Д., Уидриг Д. Принципы работы с требованиями к программному обеспечению. Унифицированный подход. М.: Вильяме, 2002, 448 с.

85. Фаулер М., Скотт К. UML. Основы. СПб.: Символ-Плюс, 2002, 192 с.

86. Рамбо Дж., Якобсон А., Буч Г. UML: специальный справочник. СПб.: Питер, 2002, 656 с.

87. Скотт К. Унифицированный процесс. Основные концепции. М.: Вильяме, 2002, 160 с.

88. Хопкрофт Д., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. 2-е изд. М.: Вильяме, 2002, 528 с.

89. Арнольд В. И. Что такое математика? М.: МЦНМО, 2002, 104 с.

90. Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты. М.: Вильяме, 2003, 788 с.

91. Бурдонов И. Б., Косачёв А. С., Кулямин В. В., Петренко А. К. Подход UniTesK к разработке тестов // Программирование, 2003, №6, с. 25-43.

92. Нецветаева Г. А., Новиков Ф. А., Парийская Е. Ю., Скрипни-ченко В. И. Автоматическая генерация интерфейсов пользователя. Сообщения ИПА РАН №159. 2003, 10 с.

93. Матросов А. В., Новиков Ф. А., Усаров Г. Е., Харитонова И. А. Microsoft Office ХР: разработка приложений / Под ред. Ф.А.Новикова. — СПб.: БХВ-Санкт-Петербург. 2003, 944 с.

94. Ауэр К., Миллер Р. Экстремальное программирование: постановка процесса. С первых шагов и до победного конца. СПб.: Питер, 2003, 368 с.

95. Бобровский С. Технологии Пентагона на службе российских программистов. СПб.: Питер, 2003, 222 с.

96. Новиков Ф. A. Microsoft Word 2003. СПб.: БХВ-Петербург, 2004, 976 с.

97. Frankel D. Model Driven Architecture. Applying MDA to Enterprise Computing. Wiley Publishing, 2003, 328 p.104105106107108109110111112113114,115116117,

98. Орлов С. А. Технологии разработки программного обеспечения. Учебное пособие. 2-е изд. СПб.: Питер, 2003, 480 с. Thomas D. UML — Unified or Universal Modeling Language? // Journal of Object Technology, 2003, Vol. 2, No 1, pp.7 12.

99. Крёнке Д. Теория и практика построения баз данных. 8-е изд. СПб.: Питер, 2003, 800 с.

100. Бейзер Б. Тестирование черного ящика. Технология функционального тестирования программного обеспечения и систем. СПб.: Питер, 2004, 318 с.

101. ДоротВ. JL, Новиков Ф. А. Толковый словарь современной компьютерной лексики. 3-е изд., перераб. и доп. СПб.: БХВ-Петербург, 2004, 608 с.

102. Брауде Э. Технология разработки программного обеспечения. СПб.: Питер, 2004, 655 с.

103. Константайн Л., Локвуд Л. Разработка программного обеспечения. СПб.: Питер, 2004, 592 с.

104. Леоненков A.B. Самоучитель UML. 2-е изд., перераб. и доп. СПб.: БХВ-Петербург, 2004, 432 с.

105. Терехов А. Н. Технология программирования: Учебное пособие. М.: БИНОМ, 2006, 148 с. '

106. Буч Г., Якобсон А., Рамбо Дж. UML. Классика CS. 2-е изд. СПб.: Питер, 2006, 736 с.

107. Новосельцев В.Б. Теория структурных функциональных моделей // Сибирский математический журнал. 2006. №5. Т. 47. с. 1014—1030.

108. Рамбо Дж., Блаха М. UML 2.0. Объектно-ориентированное моделирование и разработка. 2-е изд. СПб: Питер, 2007, 544 с.

109. Аалст В., Хей К. Управление потоками работ: модели, методы и системы. М.: ФИЗМАТЛИТ, 2007, 316 с.

110. Новиков Ф. А. Степанян К. Б. Язык описания диаграмм // Информационно-управляющие системы. 2007, №4, с. 28 36 (список ВАК).

111. Новиков Ф. А. Степанян К. Б. Использование порождающего программирования при реализации языка описания диаграмм // Информационно-управляющие системы. 2008, №6, с. 32 — 35 (список ВАК).

112. Новиков Ф. А., Тихонова У. Н. Определение проблемно-ориентированных языков интерпретируемыми автоматами // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. 2008, № 5(65), с. 93-98 (список ВАК).

113. Новиков Ф. А., Тихонова У. Н. Применение автоматного программирования для определения проблемно-ориентированных языков // Труды ИПА РАН. Вып. 19. 2008, с. 174 183.

114. Новиков Ф. А., Сотскова М. Ф. Microsoft Office Word 2007. СПб.: БХВ-Петербург, 2008, 960 с.

115. Тихонова У. Н. Новый метод определения проблемно-ориентированных языков // XIII молодежная научная конференция «Наукоемкие информационные технологии» Институт программных систем РАН УГП имени А. К. Айламазяна, Переславль-Залесский, 2009, с. 183-194.

116. Новиков Ф. А., Новосельцев В. Б. Предварительное сообщение о языке исполняемых программных спецификаций // Программные продукты и системы. 2009, № 2, с. 107-111 (список ВАК).

117. Новиков Ф. А., Новосельцев В. Б. Язык исполняемых программных спецификаций // Программирование. 2010, №1, с. 66 — 78 (список ВАК).

118. Новиков Ф. А., Тихонова У. Н. Применение автоматного метода определения проблемно-ориентированных языков / Материалы научнопрактической конференции «Научные исследования и инновационная деятельность». СПбГПУ, 2009.

119. Новиков Ф. А., Тихонова У. Н. Автоматный метод определения проблемно-ориентированных языков (Часть 1) // Информационно-управляющие системы. 2009, № 6, с. 34 40 (список ВАК).

120. Новиков Ф. А., Тихонова У. Н. Автоматный метод определения проблемно-ориентированных языков (Часть 2) // Информационно-управляющие системы. 2010, № 2, с. 31 37 (список ВАК).

121. Новиков Ф. А., Тихонова У. Н. Автоматный метод определения проблемно-ориентированных языков (Часть 3) // Информационно-управляющие системы. 2010, № 3, с. 29 37 (список ВАК).

122. Иванов Д. Ю., Новиков Ф. А. Моделирование на UML: опыт преподавания в Интернет // Компьютерные инструменты в образовании. 2009, №4, с. 53 61 (список ВАК).

123. Иванов Д. Ю., Новиков Ф. А. Влияние UML на процесс разработки программного обеспечения // Компьютерные инструменты в образовании. 2009, №6, с. 3 11 (список ВАК).

124. OWL 2 Web Ontology Language, http://www.w3 .org/TR/2009/REC-owl2-overview-20091027/ Последнее обращение 30.03.11.

125. Новиков Ф. А. Дискретная математика для программистов. Учебник для вузов. 3-е изд. — СПб.: Питер, 2009, 384 с.

126. Поликарпова Н. И., Шалыто А. А. Автоматное программирование. СПб.: Питер, 2010, 176 с.

127. Карпов Ю. Г. MODEL CHECKING. Верификация параллельных и распределенных программных систем. СПб.: БХВ-Петербург, 2010, 560 с.

128. Бычков И.В., Корсуков A.C., Опарин Г.А., Феоктистов А.Г. Инструментальный комплекс для организации гетерогенных распределенных вычислительных сред // Информационные технологии и вычислительные системы, 2010, № 1, с. 45 -54.

129. Новиков Ф. А. Иванов Д. Ю. Моделирование на UML. Теория, практика, видеокурс. — СПб:, Наука и Техника, 2010, 640 с.

130. Fowler М. Domain Specific Languages. Addison-Wesley Professionals, 2010, 640 p.

131. Опарин Г. А., Феоктистов А. Г., Горский С. А. Язык описания модели предметной области в пакетах прикладных программ // Программные продукты и системы, 2011, №1.

132. Новиков Ф. А. Дискретная математика: Учебник для вузов. Стандарт третьего поколения. СПб.: Питер, 2011, 384 с.