birmaga.ru
добавить свой файл

1 2 ... 6 7




РОССИЙСКАЯ АКАДЕМИЯ НАУК

ДАЛЬНЕВОСТОЧНОЕ ОТДЕЛЕНИЕ

Институт автоматики и процессов управления


И.Л. Артемьева, М.А. Князева, О.А. Купневич

МОДЕЛЬ ОНТОЛОГИИ ПРЕДМЕТНОЙ ОБЛАСТИ "ОПТИМИЗАЦИЯ ПОСЛЕДОВАТЕЛЬНЫХ ПРОГРАММ". ТЕРМИНЫ ДЛЯ ОПИСАНИЯ

ОБЪЕКТА ОПТИМИЗАЦИИ



Препринт 29-2000


Владивосток

2000
УДК 519.68:15:681.5
Артемьева И.Л., Князева М.А., Купневич О.А. МОДЕЛЬ ОНТОЛОГИИ ПРЕДМЕТНОЙ ОБЛАСТИ "ОПТИМИЗАЦИЯ ПОСЛЕДОВАТЕЛЬНЫХ ПРОГРАММ". ТЕРМИНЫ ДЛЯ ОПИСАНИЯ ОБЪЕКТА ОПТИМИЗАЦИИ. Препринт 29-2000. Владивосток: ИАПУ ДВО РАН, 2000.31 с.

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

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


Библ. 19.

ОТВЕТСТВЕННЫЙ РЕДАКТОР д.ф.-м.н., профессор А.С.Клещев
РЕЦЕНЗЕНТ к.т.н., доцент Е.И.Антонова

Институт автоматики и процессов управления

ДВО РАН, 2000
Проблема оптимизации программ была впервые осознана практически одновременно с построением первых трансляторов с языков программирования. Практика показала, что повышение уровня исходного языка программирования отрицательно сказывается на эффективности объектных программ, полученных в результате трансляции. В связи с этим в конце 50-х годов в области программирования была поставлена задача повышения эффективности программ с помощью выполнения над ними в процессе трансляции ряда преобразований. Эту задачу принято называть задачей оптимизации программ, а преобразования, выполнение которых над программами может повысить их эффективность, – оптимизирующими преобразованиями (ОП). Под системой оптимизирующих преобразований будем в дальнейшем понимать набор ОП вместе со стратегией их применения [Error: Reference source not found, a]. К настоящему времени теория оптимизации программ обогатилась фундаментальными результатами (развит аппарат схем программ, выделен богатый набор оптимизирующих преобразований, найдены достаточные условия корректности применения ряда преобразований и т.д.), а практика - примерами эффективно работающих оптимизирующих компиляторов [Error: Reference source not found, b - e].

В силу наличия большого числа языков программирования, теоретические результаты в области оптимизации программ обычно формулируются в терминах абстрактных математических моделей программ, независимых от конкретных алгоритмических языков, причем число таких моделей исчисляется десятками [Error: Reference source not found, a]. Это приводит к тому, что оптимизирующие преобразования описываются в терминах различных моделей, что затрудняет объединение различных преобразований в рамках одной системы ОП, а также затрудняет изучение различных оптимизирующих преобразований студентами. Кроме того, для многих преобразований не опубликованы формальные описания, условия применимости и описание результатов их применения. Систематизация и унификация знаний об оптимизации программ позволяет описать все преобразования в единой терминологии и, как следствие, облегчает изучение основных понятий предметной области "Оптимизация программ" [Error: Reference source not found,Error: Reference source not found], поэтому является актуальной задачей.


Описание терминологии некоторой предметной области вместе с определением смысла терминов в современном мире получило название модели онтологии [Error: Reference source not found]. Термины предметной области "Оптимизация программ (классические оптимизирующие преобразования)" можно разбить на две группы: термины, при помощи которых описываются программы (термины этой группы будем называть терминами для описания объекта оптимизации), и термины, при помощи которых описывается процесс оптимизации. Поэтому модель онтологии данной предметной области также состоит из двух частей.

Объектом оптимизации является некоторая программа. Свойства программы всегда формулируются в терминах математической модели этой программы. Характеристикой любой программы является язык (множество программ), которому эта программа принадлежит. Свойства языка также формулируются в терминах математической модели этого языка. Тем самым, множество терминов для описания объекта оптимизации может быть разбито на две группы: термины для описания модели языка и термины для описания модели конкретной программы. Прежде чем будет оптимизироваться конкретная программа, должен быть определен язык, которому эта программа принадлежит. Следовательно, термины для описания модели языка являются параметрами модели онтологии, а термины для описания модели программы – неизвестными модели онтологии [Error: Reference source not found]. Тогда модель языка задается указанием значений параметров, а модель конкретной программы – указанием значений неизвестных.

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


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


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

Целью настоящей работы является определение терминов для описания объекта оптимизации: терминов для описания модели конкретной программы и терминов для описания модели языка. Работа имеет следующую структуру: раздел 1 содержит определения терминов для описания объекта оптимизации и ограничений на их интерпретацию, а в разделе 2 приведена модель языка описания структурных программ как множество значений параметров модели онтологии. Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект 99-01-00634).
1. ОПРЕДЕЛЕНИЕ ТЕРМИНОЛОГИИ ДЛЯ ОПИСАНИЯ ОБЪЕКТА ОПТИМИЗАЦИИ
Описание онтологии моделей программ будем вести при помощи формализма, предложенного в [Error: Reference source not found, Error: Reference source not found]. Модель онтологии предметной области "Оптимизация последовательных программ" состоит из двух модулей. Первый модуль содержит определение терминов для описания объекта оптимизации, а второй – терминов для описания процесса оптимизации. Первый модуль представляет собой необогащенную систему логических соотношений с параметрами, записанную с использованием предложений многосортного языка прикладной логики: при помощи предложений – описаний значений имен в п. 1.1 определяются вспомогательные термины, при помощи предложений – описаний сортов имен в п. 1.2. и 1.3. определяются параметры и неизвестные, при помощи предложений – ограничений на интерпретацию имен в п.1.4 определяются онтологические соглашения, определяющие ограничения целостности модели языка, ограничения целостности модели программы, а также взаимосвязь между моделью программы и моделью языка. Для большей ясности изложения опишем вначале неизвестные и параметры неформально.

Любая программа состоит из фрагментов, причем каждый фрагмент, в свою очередь, также состоит из фрагментов [Error: Reference source not found, Error: Reference source not found], т.е. любая программа имеет синтаксическую структуру, которую отражает математическая модель этой программы.


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

Будем считать, что все фрагменты могут быть разбиты на три группы: операторы описания, исполнимые операторы и элементы операторов. Каждый фрагмент характеризуется своим классом, например, фрагмент может иметь класс оператор присваивания, оператор цикла, оператор описания функций и т.д. Функция FragClass возвращает для указанного адреса фрагмента класс этого фрагмента. Множество названий классов фрагментов (каждой группы) в программе задают значения параметров Операторы описания, Исполнимые операторы, Элементы операторов.

Синтаксическую структуру программы задают дуги управления. Каждая дуга управления связывает два фрагмента программы. Каждая дуга управления имеет метку, которая определяет тип связи между фрагментами. Для задания дуги управления используется функция, имя которой совпадает с меткой дуги. Значение параметра Имена дуг управления задает, какие метки могут иметь дуги управления в программе. Для каждой дуги управления определена область действия дуги управления. Эту область задает значение функционального параметра Область действия дуг управления –функция, которая сопоставляет каждой метке дуги пару, состоящую из двух множеств имен классов фрагментов: первое множество определяет, фрагменты каких классов могут быть аргументами, а второе – результатами дуги управления с данной меткой.

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


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

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

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

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

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

Значение параметра Элементарные типы задает для языка множество идентификаторов типов данных, являющимися базовыми для всех остальных типов данных этого языка.

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


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

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

1.1. Null 0
Термин “Null” обозначает адрес пустого фрагмента

1.2. Значения атрибутов ({}N) I ({}I) ({}{}I) R L
Термин “значения атрибутов” обозначает множество всевозможных допустимых значений всех атрибутов

1.3. Универсальный аргумент ((n:I[2, ] ) Значения атрибутов n )
Термин “Универсальный аргумент” обозначает множество кортежей значений атрибутов, причем кортежи могут иметь различную длину

1.4. Классы фрагментов Операторы описания Исполнимые операторы Элементы операторов
Термин “Классы фрагментов” обозначает множество имен классов фрагментов

1.5. Идентификаторы ((v: Виды идентификаторов) j(v))
Термин "Идентификаторы" обозначает объединение множеств идентификаторов всех типов, входящих в модель программы

1.6. Виды идентификаторов {Types, Vars, Funcs, Consts } Другие виды идентификаторов

Термин "Виды идентификаторов" обозначает множество названий видов идентификаторов, среди которых обязательно присутствуют "идентификаторы типов" (Types), "идентификаторы переменных" (Vars), "идентификаторы функций" (Funcs) и "идентификаторы констант" (Consts)


1.7. Адреса фрагментов Адреса не пустых фрагментов {Null}
Термин "Адреса фрагментов" обозначает множество адресов фрагментов программы, в том числе содержащее адрес пустого фрагмента
1.2. Термины для описания модели языка
2.1. (Другие виды идентификаторов) = {}N \ {Types, Vars< Funcs, Consts}
Термин “Другие виды идентификаторов” обозначает конечное множество возможных видов идентификаторов в программе, отличных от видов Types, Vars, Funcs и Consts

2.2. (Операторы описания) = {} N
Термин “Операторы описания” обозначает конечное множество названий фрагментов, которые являются операторами описания (например, операторы описания переменных, функций, параметров).

2.3. ( Исполнимые операторы) = {} N
Термин “исполнимые операторы” обозначает конечное множество названий фрагментов, которые являются только исполнимыми операторами (например, операторы присваивания, цикла, условный).

2.4. ( Элементы операторов) = {} N
Термин “Элементы операторов” обозначает конечное множество названий фрагментов, которые являются частями или объединениями фрагментов (например, подвыражения или последовательности операторов).

2.5. (Знаки операций) = {}N
Термин “Знаки операций” обозначает конечное множество знаков операций в программах.

2.6. (Число аргументов) = (Знаки операций {}({1} {2} {1,2}))
Термин “Число аргументов” обозначает функцию, которая сопоставляет знаку операции возможную арность этого знака; одним и тем же знаком могут быть обозначены операции, имеющие разную арность.

2.7. (Приоритет) = (Знаки операций I)
Термин “Приоритет ” обозначает функцию, которая сопоставляет знаку операции ее приоритет (целое число).

2.8. (Имена дуг управления) = {}N

Термин “Имена дуг управления” обозначает конечное множество возможных имен дуг управления.


2.9. (Область действия дуг управления) = (Имена дуг управления
{}( {}Классы фрагментов, {}Классы фрагментов))
Термин “Область действия дуг управления” обозначает функцию, которая сопоставляет каждой метке дуги множество пар, каждая из которых состоит из двух множеств имен классов фрагментов: первое множество определяет, фрагменты каких классов могут быть аргументами, а второе – фрагменты каких классов могут быть результатами дуги управления с данной меткой, т.е. первое множество задает область определения дуги управления, а второе – область значения дуги управления с данным именем.

2.10. (Имена атрибутов) {} N
Термин “Имена атрибутов” обозначает конечное множество возможных имен атрибутов.

2.11. (Область определения атрибута) = (Имена атрибутов
(Адреса фрагментов Идентификаторы
L))
Термин “Область определения атрибута” обозначает функцию, которая сопоставляет имени атрибута предикат, показывающий, принадлежит ли данный идентификатор или фрагмент области определения этого атрибута.

2.12. (Область значения атрибута) = (Имена атрибутов
(Значения атрибутов
L))
Термин “Область значения атрибута” обозначает функцию, которая сопоставляет имени атрибута предикат, истинный, если данное значение принадлежит области значений этого атрибута.

2.13. (Имена функций) = {}N
Термин “Имена функций” обозначает множество имен функций

2.14. (Область определения функции) = (Имена функций
(Универсальный аргумент
L))
Термин “Область определения функции” обозначает функцию, которая сопоставляет имени функции предикат, показывающий, принадлежит ли данный кортеж фрагментов и идентификаторов области определения этой функции.

2.15. (Область значения функции) = (Имена атрибутов
(Значения атрибутов
L))

Термин “Область значения функции” обозначает функцию, которая сопоставляет имени функции предикат, истинный, если данное значение принадлежит области значений этой функции.


2.16. (Имена отношений)= {}N
Термин “Имена отношений” обозначает множество имен отношений в языке описания моделей программ.

2.17. (Определение отношения)= (Имена отношений
(Универсальный аргумент
L))
Термин “Определение отношения” обозначает функцию, которая сопоставляет имени отношения предикат, истинный, если это отношение существует между элементами кортежа аргумента.

2.18. (Определение корректности) = (Классы фрагментов
(Адреса не пустых фрагментов
L)
Термин “Определение корректности” обозначает функцию, которая сопоставляет каждому классу фрагмента предикат, истинный, если у фрагмента с данным адресом имеются все управляющие дуги и атрибуты, необходимые для фрагментов этого класса.

2.19. (Элементарные типы) = {}N
Термин “Элементарные типы” обозначает подмножество идентификаторов типов данных, которые считаются элементарными.

2.20. (Способы порождения) = {}N
Термин “способы порождения” обозначает множество названий конструкторов типов данных в языке, обозначающих способ создания нового типа на основе ранее описанного.

2.21. (Зарезервированные имена)= {} N
Термин "Зарезервированные имена" обозначает множество имен ролей, которые могут играть фрагменты или идентификаторы программы.

2.22. (Область значения зарезервированного имени) =
(Зарезервированные имена (Адреса фрагментов Идентификаторы
L))
Термин “ Область значения зарезервированного имени ” обозначает функцию, которая сопоставляет зарезервированному имени предикат, определяющий, какими свойствами должен обладать фрагмент или идентификатор, играющий в программе эту роль.

2.23 (Совместимость типов)= (( Types, Types) L)

Термин “Совместимость типов” обозначает предикат, истинный, если второй идентификатор типа является совместимым по присваиванию с первым

1.3. Термины для описания модели программы
3.1. (v: Виды идентификаторов) (v) = {} N
Каждый термин из множества "Виды идентификаторов" обозначает конечное множество идентификаторов данного вида в модели программы.

3.2. (Адреса не пустых фрагментов) = {} I[1, ]

Термин "Адреса фрагментов" обозначает конечное множество адресов всех фрагментов программы

3.3. (FragClass)= (Адреса фрагментов {}Классы фрагментов)
Термин “FragClass” обозначает функцию, возвращающую множество классов фрагментов, к которым принадлежит фрагмент с указанным адресом.

3.4. (v: Имена дуг управления) (v) =
(
( (v2: Область действия дуг управления(v)) {(v1: Адреса фрагментов) FragClass(v1) (1, v2))}) Адреса Фрагментов)
Каждый термин из множества “Имена дуг управления” обозначает функцию, которая фрагменту – началу дуги управления сопоставляет фрагмент – конец дуги управления, причем начало дуги принадлежит области определения функции, обозначенной этим термином.

3.5. (v: Имена атрибутов) (v)=
({(v
1: Адреса фрагментов Идентификаторы) Область определения атрибута(v)(v1)} {(v2: Значения атрибутов) Область значения атрибута(v)(v2)})
Каждый термин из множества “Имена атрибутов” обозначает функцию, которая сопоставляет идентификатору или адресу фрагмента, принадлежащему области определения этой функции, значение этого атрибута, принадлежащее области значений этой функции.

3.6. (v: Имена функций) (v)=

({(v1: Универсальный аргумент) Область определения функции(v)(v1)} {(v2: Значения атрибутов) Область значения функции(v)(v2)})

Каждый термин из множества “Имена функций” обозначает функцию, которая сопоставляет кортежу идентификаторов или адресов фрагментов, принадлежащему области определения этой функции, значение функции от этого кортежа идентификаторов или адресов фрагментов.

3.7. (v: Имена отношений) (v)= ((Универсальный аргумент) L)
Каждый термин из множества “Имена отношений” обозначает предикат, который сопоставляет кортежу адресов фрагментов и идентификаторов истину, если между элементами этого кортежа существует данное отношение.

3.8. (Корректность) = (Адреса не пустых фрагментов L)
Термин “Корректность” обозначает предикат, возвращающий истину для фрагмента с указанным адресом в случае, если у него имеются все управляющие дуги и атрибуты, необходимые для фрагментов этого класса.

3.9. (BaseType)= (Types \ Элементарные типы ((n:I[2, ] ) (Types n))
Термин “BaseType” обозначает функцию, которая сопоставляет идентификатору типа данных последовательность идентификаторов типов, которые были использованы при его конструировании.

3.10. (ConstructMethod)= (Types \ Элементарные типы Способы порождения)
Термин “ConstructMethod” обозначает функцию, которая сопоставляет идентификатору типа название конструктора, при помощи которого он был сконструирован из базовых типов.

3.11. (v: Зарезервированные имена) (v)= {(v1: Адреса фрагментов Идентификаторы) Область значения зарезервированного имени(v)(v1)}
Каждый термин из множества "Зарезервированные имена" обозначает идентификатор или адрес фрагмента, играющий в программе роль, имя которой совпадает с этим термином.
1.4. Онтологические соглашения



следующая страница >>