Синтез циклических программ над многомерными структурами данных

• Автор: Чирас, Витаутас Александрович
• Шифр специальности: 01.01.10
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Москва
• Количество страниц: 168 c. : ил

С ОДЕРЖАНИЕ ВВЕДОНИЕ

ГЛАВА I. СТРУКТУРНАЯ СЕМАНТИКА ОШРАТОРОВ

§1,1. Семантика присваивания

§ 1,2, Семантика следования . . . . ;

§ 1.3. Семантика цикла

§ 1.4, Семантика выбора

ГЛАВА 2. СТРУКТУРНАЯ СЕМАНТИКА МОДУЛЯ

§2.1. Семантика вычислительного модуля

§ 2.2. Семантика структурного модуля

§2.3. Применение структурного модуля к вычислительному

ГЛАВА 3. СИНТЕЗ ЦЕПОЧКИ

§3.1. Структурное сопряжение цепочки. Переходное множество
§ 3.2. Язык структурной семантики класса модулей
3.2.1. Язык класса вычислительных модулей
3.2.2. Язык класса структурных модулей
§3,3. Алгоритмы синтеза структурного сопряжения
3.3.1, Сопряжение цепочки из одного структурного модуля
3.3.2, Роль параметров в синтезируемых переходных множествах
3.3.3, Алгоритм установления сходства внешнего шаблона
и переходного множества
§ 3.4, Примеры
3.4.1. Пример I
3.4.2. Пример
3.4.3. Пример
3.4.4. Пример
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
ПРИЛОЖЕНИЯ

У пользователей ЭВМ есть потребность в более мощных и удобных средствах программирования, в частности, в приближении языков программирования к языкам спецификаций. Как отмечает С.С.Лавров /16/, "автоматический синтез программ был и остается идеалом программиста, особенно программиста-при-кладника",
К исследованиям по синтезу программ можно отнести довольно широкий и разнообразный круг работ. Проблематика автоматического синтеза программ отражается в его синонимах /16/: автоматизация программирования, автоматизация второго этапа программирования, технология программирования. Суть синтеза программ основана на желании писать не саму программу, а ее спецификацию, т.е, не как решить задачу, а что нужно решить. К синтезу программ можно отнести трансляцию с менее традиционных языков, имеющих прежде всего непроцедурные элементы, например, LUCID /32/, PROLOG /25/. Синтез программ соприкасается с искусственным интеллектом (см., например, работы 3.Манны и Р.Уолдингера /36,37/). Сильный тол-чек проблематика синтеза программ получила в связи с развитием пакетов программ /15,26/. Возникла проблема планирования вычислений.
Обзоры работ по синтезу программ сделали Э.Х.Тыугу /28, 29,42/, Н.И.Ильинский и А.В.Мясников /13/. В обзоре последних авторов выделены четыре направления автоматического синтеза программ: дедуктивный, трансформационный, индуктивный,
на основе представления знаний. Обзор по трансформационному синтезу приводят В.А.Непомнящий и В.К.Сабельфельд /23/.

В диссертации предлагается подход к синтезу из модулей, представляющих счет по локальным соотношениям на структуре данных, имеющей регулярное, повторяющееся строение. Такой структурой является, например, массив. Предлагаемый нами подход к синтезу можно отнести к направлению, основывающему* ся на представлении знаний в пакете программ.
Круг задач, к решению которых можно применить предлагаемый подход, довольно широк. Рекуррентными соотношениями специфицируются много численных методов /19/. Использование при решении дифференциальных уравнений с частными производными разностных методов приводит к появлению соотношений на сетках. В первую очередь предлагаемые понятия адекватно отражают специфику вычислений по явным разностным схемам.
Сделаем краткий обзор нескольких работ, в которых при постановке проблемы синтеза и при ее решении предполагается регулярность, присущая массиву, а также синтезируемая программа содержит цикл.
Понятие локального соотношения на массиве берет истоки из предложенной в 1956 г. С.С.Камыниным и Э.З.Любимским /17, 18/ формы описания задачи, получившей название параметрической записи. В этой постановке спецификация задачи выражается совокупностью расчетных формул, на применение которых могут быть наложены некоторые условия. И.Б.Задыхайло /II/ исследовал задачу построения циклического процесса счета по пара-метричекой записи на одномерных массивах X* , •.. »Х:
X Сл] - ^ (X Сс-Д/иЗ; • } ХтЦ-Длт1)
Хт[Л =ЫХ''С£-дт,]; - • ■ , Х"р-дтт])
Здесь д^ - целые числа. Заданными считаются значения

скобки. Множество такого вида мы назовем сегментом внешнего шаблона и запишем
-t^= ^ ^ f tf* * fa (2,12)
Аналогично мы будем описывать вход и выход внутреннего шаблона. Только сегменты внутреннего шаблона зависят от параметров рл и, возможно, от Рл 15,.
Предполагается, что программа с-модуля представлена как процедура с заголовком
procedure S (£> t.,.; г integer • procedure ^(integer,..." integer))
(2.13)
Тело процедуры содержит вызовы вида са.П ^ . Подставив
вместо них обращения к фактическому в-модулю, получаем программу, осуществляющую счет на том же массиве, как и в-модуль. Как понимается упомянутая подстановка, а также другие вопросы, связанные с применением с-модуля к в-модулю, рассматриваются в следующем параграфе.
Операторы программы с-модуля организуют только обход, а счета на структуре не производят. Весь счет - присваивание значений вычисленным элементам, доступ к элементам структуры - происходит в вычислительном модуле.
Приведем пример с-модуля, организующего обход области, имеющей форму квадрата (см. рис. 2.6), при помощи узла
Цикл с заголовком
do ± Ьо £
do рч - ± to £
для осуществления желаемого обхода не годится, так как не подпитывается (хотя он годен для организации обхода узлом Pi-11-*-ХГр4 / Pil 5 • Подпитывание учиты-