Новиков Фёдор Александрович Методы алгоритмизации предметных областей Специальность 05. 13. 11 «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей» автореферат

Вид материала

Содержание

Автоматный метод
Конкретный синтаксис
Автоматный метод определения проблемно-ориентированных языков
Четвертая глава
Определение набора конкретных синтаксисов
Функциональность связей
Постановка задачи на вычислительной сети
В разделе 4.2
A — множество имен атрибутов
Пусть G=g
В разделе 4.3
Алгоритм 1. Линейный алгоритм синтеза программ на плоской модели
Язык исполняемых программных спецификаций
Пятая глава
Stereol (

Подобный материал:

1 2 3 4

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

Автоматный метод заключается в определении следующих четырех объектов: 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.2 посвящен описанию автоматной модели, предложенной автором, и ее применению для определения конкретного синтаксиса и семантики предметно-ориентированных языков.

Слева на рис. 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. Схема взаимодействия автоматов семантики

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

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

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

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

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

Раздел 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 = g₁, …, g_n — последовательность имен функций (g_i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, [G₁]) & C(W, Z, [G₂]) & WY ⇒ C(X, YZ, [G₁; G₂]),

где G₁; G₂ — конкатенация двух последовательностей функций. Данное правило имеет простую интерпретацию: имея абстрактную программу, вычисляющую 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=g₁, …, g_n, для которой

 U  W (UX & YW & C(U, W, [G]).

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

Теорема (О полноте правила элементарной композиции). Пусть G=g₁, …, g_n — решение задачи 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. Предметные области и разработанные ПОЯ

ПО	Язык	Назначение и область применения	Год	Орг.^⁹
Системное программирование, создание инструментальных средств разработки ПОЯ и МПО	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 год

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

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

Blog

Содержание