Авторефераты по всем темам >> Авторефераты по техническим специальностям

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

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

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

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

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

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

2011

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

Научный консультант

доктор физико-математических наук

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

Официальные оппоненты

доктор физико-математических наук,

профессор

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

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

профессор

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

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

профессор

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

Ведущая организация

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

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

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

Автореферат разослан л__ ______________ 2011 г.

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

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

.С. Лисицына

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация диссертации. Различные аспекты результатов работы докладывались на многих семинарах и форумах, в том числе, на следующих конференциях: Всесоюзная конференция Методы математической логики в проблемах искусственного интеллекта и систематическое программирование, Вильнюс, 1980; IIIаконференция Применение методов математической логики, Таллин, 1983; IIIаВсесоюзная конференция Автоматизация производства пакетов прикладных программ и трансляторов, Таллин, 1983; III Всесоюзная конференция Автоматизация производства систем программирования, Таллин, 1986; IAU Colloquium 109, Gaithersburg, 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аЧ многотиражные монографии, выпущенные издательствами Питер, БХВ-Санкт-Петербург и Наука и Техника. Основные работы, в которых содержатся результаты, выносимые на защиту, перечислены в конце автореферата. В работах, выполненных в соавторстве, личный вклад автора во всех случаях в равных долях с соавторами.

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

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

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

Во введении рассматриваются следующие вопросы: проблемы технологии разработки прикладного программного обеспечения, необходимость решения этих проблем для алгоритмизации, эффективность применения ПОЯ и МПО, важность опоры на формальные методы. Помимо этого, во введении вводится специфическая терминология, используемая в диссертации, и система обозначений, основанная на унифицированном языке моделирования UML. В частности, вводится понятие степени алгоритмизации. Степень алгоритмизации M определяется как среднее геометрическое двух показателей: доля решаемых типовых задач T (отношение числа типовых задач, которые можно решить средствами оцениваемой алгоритмизации, к числу всех идентифицированных типовых задач), и относительное снижение трудозатрат S (отношение средних трудозатрат на решение типовых задач после оцениваемой алгоритмизации, к средним трудозатратам на решение той же совокупности задач до алгоритмизации):

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

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

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

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

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

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

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

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

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

Рис. 2. Модель использования МПО

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

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

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

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

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

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

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

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

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

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

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

Характеристика	Предметно-ориентированные	Языково- ориентированные	Модельно- ориентированные
Правила решения типовых задач (представление МПО)	Неявные, встроены в ДПФ, неизменяемые пользователем	Неявные, описываются на ПОЯ, изменяемые пользователем	Явные, задаются в МПО, изменяемые пользователем
Класс предметных областей	Узкий, ограничен алгоритмами, встроенными в ДПФ	Широкий, ограничен выразительной силой ПОЯ	Широкий, ограничен мощностью планировщика задач МПО
Трудоемкость / сила пользователя	Высокая / Низкая	Средняя / Средняя	Низкая / Высокая

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

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

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

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

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

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

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

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

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

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

Вторым примером в третьем разделеаЧ последним и самым важнымаЧ является семейство языков таблично-ориентированного программирования. Предложенный автором таблично-ориентированный метод алгоритмизации предметных областей заключается в следующем. Пусть задана предметная область, и пусть в предметной области зафиксирован набор переменных Vа=а{v1,аЕ,аvn}аЧ величин предметной области. Совокупность значений Aа=а{a1,аЕ,аan} этих переменных образует состояние предметной области. Среди значений могут быть как заданные, так и незаданные, то есть неизвестные, подлежащие определению. Имеется также набор функциональных модулей Fа=а{f1,аЕ,аfm}, которые называются действиями. Действия могут изменять состояние системы, например, вычисляя значения неизвестных величин по значениям известных, или могут иметь побочный эффект, например, печать значений. Суперпозицию действий, которые переводят систему из начального состояния в целевое состояние, называется решением элементарной вычислительной задачи в данной предметной области. Табличный подход основан на допущении, что решение любой типовой задачи в данной предметной области сводится к последовательному и независимому решению совокупности элементарных вычислительных задач.

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

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

Для того чтобы подчеркнуть и проиллюстрировать двойственную природу таблицы в таблично-ориентированном подходе, здесь приводятся определения шести базовых операций алгебры таблиц как операций с программами. Определения этих операций для таблиц как структур данных и эквивалентность определений для таблиц как структур данных и таблиц как итераторов приведены в диссертации. В следующих определениях таблица рассматривается как итератор, перебирающий кортежи таблицы. Пусть T, T1, T2 Ч итераторы таблиц; E, E1, E2 Ч наборы переменных в соответствующих таблицах; nаЧ натуральное число; sаЧ список переменных; pаЧ булевское выражение; f Ч действие (процедура); Default Ч функция, возвращающая значения по умолчанию своих аргументов. Тогда операции определяются так.

Сложение.
T = T1+T2 = for E1 ∈ T1 do yield (E1 ∪ Default(E2ЦE1));
for E2 ∈ T2 do yield (Default(E1ЦE2) ∪ E2)
Сложение таблиц Ч это последовательное выполнение двух циклов.
Умножение.
T = T1*T2 = for E1 ∈ T1 do for E2 ∈ T2 do yield (E1∪E2)
Умножение таблиц Ч это вложенность циклов.
Итерация (операция не обозначается).
T = n T1 = for i from 1 to n do T1
Итерация таблицы Ч это цикл со счетчиком.
Проекция.
T = T1 | s = for E1 ∈ T1 do yield (E1 ∩ s)
Проекция таблицы Ч это локализация переменных.
Выборка.
T = T1 [p] = for E1 ∈ T1 do if p(E1) then yield (E1)
Выборка из таблицы Ч это условный оператор в теле цикла.
Действие (операция не обозначается).
T = T1 f = for E1 ∈ T1 do yield (f(E1))
Действие над таблицей Ч это вызов процедуры в теле цикла.

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

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

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

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

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

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

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

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

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

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

Рис. 4. Схема использования автоматного метода

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

Абстрактные знаки языка и их комбинацииаЧ конструкции языкааЧ описываются в виде классов. При использовании порождающих формальных грамматик им соответствуют терминалы и нетерминалы, соответственно.
Определение конструкции языка через её составляющие осуществляется с помощью отношения композиции. При этом композиция классов означает отношение типа часть-целое с наложенным на него ограничением альтернативной декомпозиции: в каждом экземпляре отношения композиции экземпляр конструкции A включается либо в экземпляр конструкции B, либо в экземпляр конструкции C, но не в оба вместе. На языке порождающих формальных грамматик альтернативная декомпозиция соответствует паре правил Bа::=аA и Cа::=аA, где в каждом конкретном случае порождение может пойти только по одному пути.
Совокупность обязательных составляющих некоторой конструкции, включённых в неё по отношению композиции, при реализации образуют одно целое. Такая композиция в диссертации названа конъюнктивной: в конструкцию A включаются и конструкция B, и конструкция C. На языке порождающих формальных грамматик конъюнктивной композиции соответствует правило Aа::=аBаC.
Альтернативное определение конструкции языка может осуществляться с помощью дизъюнктивной композиции: в конструкцию A включаются конструкция B или конструкция C, но не обе вместе. На языке порождающих формальных грамматик это соответствует правилу A ::= B | C.

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

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

α Всякому нетерминалу соответствует класс.

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

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

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

ε Если рекурсия используется для задания итерации, то вводится кратность полюса композиции или атрибут массив.

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

Program ::= Statement . | Statement ; Program
Statement ::= Name = Expression
Expression ::= Expression Operator Expression | Name | { Elements } | ( Expression )
Operator ::= ∩ | ∪
Name ::= A | B | Е| X | Y | Z
Elements ::= Element | Element , Elements
Element ::= a | b | Е | x | y | z

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 7. Автомат, эмулирующий машину Тьюринга

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

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

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

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

Рис. 8. Автоматы конкретного синтаксиса языка ММ

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

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

Здесь рассматривается наиболее интересный третий случай, когда программу можно рассматривать как систему уравнений, задающую конкретную ситуацию в предметной области, например, так: Aа=аBа∩а{b}; Bа=а{a, b, c} . Задавая такой программе вопрос: A = ?, пользователь получает в ответ значение множества A.

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

Рис. 9. Схема взаимодействия автоматов семантики

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 12. Пример описания отношения в графическом синтаксисе языка Ψ

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

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

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

AаЧ множество имен атрибутов, которым соответствуют атрибуты схемы в модели предметной области и переменные в синтезируемой абстрактной программе.
FаЧ множество имен функций, которым соответствуют функциональные связи в модели предметной области и имена функций из программного фонда, доступных в синтезируемой абстрактной программе.
Arg(f)а⊂аAаЧ множество входных параметров функции f∈F.
Res(f)а⊂аAаЧ множество выходных параметров функции f∈F.

Наложим ограничение ∀f∈F (Arg(f) ≠ ∅ & Res(f) ≠ ∅ & Arg(f) ∩ Res(f) = ∅). В таком случае пара <A,аF> определяет модель предметной области. Поскольку здесь не используется вложенные отношения, а все атрибуты находятся на одном уровне, то такую модель уместно называть плоской.

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

C(X, Y, [G]),

где X, Y AаЧ множества имен атрибутов, а Gа=аg1,аЕ,аgnаЧ последовательность имен функций (gi∈F, i∈1..n). Неформально предложение вычислимости C(X,аY,а[G]) означает, что Y может быть вычислено по X применением последовательности функций G.

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

Аксиомы исчисления (предметныеаЧ зависящие от предметной области)аЧ это все формулы вида C(Arg(f), Res(f), [ f ]), где f∈F. Предметные аксиомы иногда называют элементарными предложениями вычислимости. Введем следующее правило композиции:

C(X, Y, [G1]) & C(W, Z, [G2]) & W⊂Y C(X, Y∪Z, [G1; G2]),

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

C(X, Y, [G]) & C(Arg(f), Res(f), [ f ]) & Arg(f)⊂Y C(X, Y∪Res(f), [G; f]).

Задачей Q на модели предметной области <A, F> называется четверка

Q = <A, F, X, Y>,

где <A, F>аЧ модель предметной области, X,аYа⊂аAаЧ множества имен входных и выходных атрибутов соответственно. Решением задачи Q = <A, F, X, Y> называется последовательность G=g1, Е, gn, для которой

∃аU ∃аW (U⊂X & Y⊂W & C(U, W, [G]).

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

Теорема (О полноте правила элементарной композиции). Пусть G=g1, Е, gnаЧ решение задачи Qа=а<A,аF,аX,аY>. Тогда оно может быть получено применением правила элементарной композиции из предложения вычислимости C(X,аX,а[а]).

Поиск вывода в данном исчислении несложен. Пусть дана задача <A,аF,аX,аY>. Выберем в качестве исходного предложения вычислимости C(X, X, [а]) и будем наращивать программу при помощи правила элементарной композиции. Если на определённом шаге имеем C(X, Z, [G]) & Z⊂Y, то решение найдено. Если ∃f∈F (Arg(f) ⊂ Z & & Res(f) ⊄ Z), то применяем правило элементарной композиции для функции f, получая новое предложение вычислимости. Если достигается состояние, в котором ∀f∈F (Arg(f) ⊄ Z ∨ Res(f) ⊂ Z) & Z⊄Y, то решения поставленной задачи не существует.

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

В разделе 4.3 рассматривается вопрос об эффективных (не переборных) алгоритмах синтеза. Предлагается следующая структура данныхаЧ результат предобработки для представления модели <A, F> (рис. 13).

Рис. 13. Результат предобработки модели предметной области

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

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

Алгоритм 1. Линейный алгоритм синтеза программ на плоской модели

Вход: Модель предметной области, заданная парой указателей А и F, как на рис.а13, и условие задачи в виде множеств X, Y входных и выходных атрибутов, соответственно.

Выход: Список G функций, применение которых решает поставленную задачу.

proc Solve (A, F, X, Y): G

H := ∅ // применимые связи

G := [а] // синтезируемая программа

Z := Y \ X // целевые атрибуты

for a∈X do Process (a) end for

while U ∅ do

if H=∅ then return fail

end if

select g ∈ H

G = G + g

U = U \ g.right

for a ∈ g.right do

Process (a)

end for

end while

end proc

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

v.left.right := v.right

v.right.left := v.left

v.up.down := v.down

v.down.up := v.up

Dispose(v)

end proc

proc Process(a) // знаем атрибут a

for s ∈ a.up do // аргументы

if s.left=∅ & s.right∈F then

g := s.right

H := H + g

for r∈g.right do Del (r) end for

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

end if

Del (s) // удаление ячейки

end for

for s ∈ a.down do // результаты

if s.right=∅ & s.left∈F then

g := s.left

H := H Ц g

for r∈g.left do Del(r) end for

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

end if

Del (s) // удаление ячейки

end for

Del (a) // удаление ячейки

end proc

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

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

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

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

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

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

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

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

ПО	Язык	Назначение и область применения	Год	Орг.9
Системное программирование, создание инструментальных средств разработки ПОЯ и МПО	FP/FPG (Fortran Preprocessor / Fortran Program Generator)	расширение Фортрана проблемно-ориентированными типами данных	1978	ИТА 3 года
	STEREOL (STEpwise 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 лет
	АstroTOP (Astro Table Oriented Programming)	табличный подход к обработке данных	1991	ИТА 7 лет
	DELTA (DELphi + TAble)	решение задач эфемеридной астрономии на основе таблично-ориентированного метода с языком Паскаль как включающим языков	2006	ИПА 5 лет
	AMPLE 3 (Adaptable Minor PLanets Ephemerides)	пакет прикладных программ в области динамики малых тел Солнечной системы	2009	ИПА 1 год
Компьютерная верстка	СВИТА (Система Вёрстки ИТА)	входной язык системы верстки табличных изданий	1995	ИПА 15 лет
Графический интерфейс пользователя	GUIDL (GUI Description Language)	язык публикаций, позволяющий описывать алгоритмы работы пользователя графического интерфейса	1995	БХВ 10 лет
Графический интерфейс пользователя	GUIDE (GUI DEclaration)	декларативный язык описания графического интерфейса пользователя	2003
Автоматизация бизнес-процессов	CPDS (Clipper Program Development System)	система программирования для разработки бухгалтерских приложений баз данных	1989	Рот Фронт 5 лет
Автоматизация бизнес-процессов	aCMK (автоматизированная Система Менеджмента Качества)	описание бизнес-процессов и документооборота на основе концепции живого документа	2008	АтДиа 1 год

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

Выявлены механизмы влияния ПОЯ и МПО на степень автоматизации предметных областей; введены и развиты концепции сильного пользователя, циклов повышения продуктивности и доверительного программного фонда.
Обобщен и систематизирован опыт разработки семнадцати ПОЯ для алгоритмизации пяти предметных областей; предложены и опробованы методики выполнения шагов алгоритмизации и выработаны практические рекомендации по применению методов алгоритмизации.
Предложены классификации проблемно-ориентированных языков, моделей предметных областей и методов алгоритмизации.
Разработан таблично-ориентированный метод алгоритмизации предметных областей, обеспечивающий эффективную интеграцию средств работы с данными, представляющими объекты предметной области, и средств работы с программами, представляющими операции предметной области; реализованы и применены на практике несколько таблично-ориентированных ПОЯ. Результат выносится на защиту.
Разработан автоматный метод определения ПОЯ, позволяющий определить все аспекты языкааЧ структуру, внешнее представление, контекстные условия и операционную семантику; предложена модель взаимодействия автоматных объектов, обобщающая возможности автоматных моделей, предложенных ранее. Результат выносится на защиту.
Разработаны новые языковые средства и методы алгоритмизации предметных областей на основе теории структурного синтеза программ. Языковые средства позволяют описывать модели предметных областей, в том числе графически, ставить на них вычислительные задачи и автоматически синтезировать программы решения этих задач. Результат выносится на защиту.
Результаты диссертационного исследования внедрены в учебный процесс по подготовке бакалавров и магистров направления Информатика и прикладная математика в СПбГУ ИТМО и Санкт-Петербургском государственном политехническом университете.

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

Бабаев И.аО., ЛавроваС.аС., НовиковаФ.аА., ПетрушинааТ.аИ. Специализированное программное обеспечение прикладных исследований / Тезисы докладов Всесоюзная конференции "Методы математической логики в проблемах искусственного интеллекта и систематическое программирование". Часть 2. Вильнюс. 1980, с.а7 Ц 25.
Бабаев И.аО., Новиков Ф.аА., Петрушина Т.аИ. Язык Декарт - входной язык системы СПОРА // Прикладная информатика. Выпуск I, М.: Финансы и статистика. 1981, с. 35 - 72.
Бабаев И.аО., Лавров С.аС., Нецветаева Г.аА., Новиков Ф.аА., Шувалов Г.аМ. СПОРА Ц система программирования с автоматическим синтезом программ / Тезисы докладов III конференции "Применение методов математической логики". Таллин. 1983, с. 29 - 41.
Бабаев И.аО., Новиков Ф.аА. Средства оформления функционального наполнения ППП в системе СПОРА / Тезисы докладов III Всесоюзной конференции "Автоматизация производства пакетов прикладных программ и трансляторов". Таллин. 1983, с. 62 - 64.
АгамирзянаИ.аР., БреславаО.аД., КрасинскийаГ.аА., НовиковаФ.аА., Скрипниченко В.аИ. ЭРАаЧ проблемно-ориентируемая система, основанная на табличном подходе / Тезисы докладов III Всесоюзной конференция "Автоматизация производства систем программирования". Таллин. 1986, с.а97 - 99.
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.
Новиков Ф.аА. Архитектура системы ЭРА Ч табличный подход к обработке данных. Сообщения ИПА РАН № 16. 1990, 32 с.
Krasheninnikov S.V., Nazarov A.A., Novikov F.A. Skripnichenko V.I. ASTROTOP: automation of observations storage, retrieval and treatment // Baltic Astronomy. Vol.а6. No 2. 1997, pp. 355, 356.
КрашенинниковаС.аВ., КривоноговаА.аВ., НазароваА.аА., НовиковаФ.аА., СкрипниченкоаВ.аИ. Система таблично-ориентированного программирования: 32-разрядная версия. Сообщения ИПА РАН №а122. 1999, 33 с.
Новиков Ф.аА. Визуальное конструирование программ // Информационно-управляющие системы. 2005, №6, с. 9 Ц 22 (список ВАК).
Михеева В.аД., Новиков Ф.аА. Скрипниченко В.аИ. Дельта - язык и система программирования для решения прикладных задач с табличными данными // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. 2007, № 4-2(52), с.а57 - 59 (список ВАК).
Новиков Ф.аА. Степанян К.аБ. Язык описания диаграмм // Информационно-управляющие системы. 2007, №4, с. 28 Ц 36 (список ВАК).
Новиков Ф.аА. Степанян К.аБ. Использование порождающего программирования при реализации языка описания диаграмм // Информационно-управляющие системы. 2008, №6, с.а32 Ц 35 (список ВАК).
Клебан В.аО., Новиков Ф.аА. Применение конечных автоматов в документообороте // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. Выпуск 53, Автоматное программирование. 2008, с. 286 - 294 (список ВАК).
Новиков Ф.аА., Тихонова У.аН. Определение проблемно-ориентированных языков интерпретируемыми автоматами // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. 2008, №а5(65), с. 93Ц98 (список ВАК).
Новиков Ф.аА., Тихонова У.аН. Применение автоматного программирования для определения проблемно-ориентированных языков // Труды ИПА РАН. Вып. 19. 2008, с. 174 Ц 183.
Новиков Ф.аА., Новосельцев В.аБ. Предварительное сообщение о языке исполняемых программных спецификаций // Программные продукты и системы. 2009, № 2, c. 107 - 111 (список ВАК).
Новиков Ф.аА., Новосельцев В.аБ. Язык исполняемых программных спецификаций // Программирование. 2010, №1, с. 66 - 78 (список ВАК).
Новиков Ф.аА., Тихонова У.аН. Автоматный метод определения проблемно-ориентированных языков (Часть 1) // Информационно-управляющие системы. 2009, № 6, с.а34 - 40 (список ВАК).
Новиков Ф.аА., Тихонова У.аН. Автоматный метод определения проблемно-ориентированных языков (Часть 2) // Информационно-управляющие системы. 2010, № 2, с.а31 - 37 (список ВАК).
Новиков Ф.аА., Тихонова У.аН. Автоматный метод определения проблемно-ориентированных языков (Часть 3) // Информационно-управляющие системы. 2010, № 3, с.а29 - 37 (список ВАК).

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

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

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

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

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

6 Мейер Б. Объектно-ориентированное конструирование программных систем. М.: Русская Редакция, 2005. 1204 с.

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

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

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

Авторефераты по всем темам >> Авторефераты по техническим специальностям

Blog

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

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

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