Синтез циклических программ над многомерными структурами данных тема автореферата и диссертации по математике, 01.01.10 ВАК РФ

ВВЕДЕНИЕ.

ГЛАВА 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. Пример 2.

3.4.3. Пример 3.

3.4.4. Пример

У пользователей ЭВМ есть потребность в более мощных и удобных средствах программирования, в частности, в приближении языков программирования к языкам спецификаций. Как отмечает С.С.Лавров /16/, "автоматический синтез программ был и остается идеалом программиста, особенно программиста-прикладника" ,

К исследованиям по синтезу программ можно отнести довольно широкий и разнообразный круг работ. Проблематика автоматического синтеза программ отражается в его синонимах /16/: автоматизация программирования, автоматизация второго этапа программирования, технология программирования. Суть синтеза программ основана на желании писать не саму программу, а ее спецификацию, т.е. не как решить задачу, а что нужно решить. К синтезу программ можно отнести трансляцию с менее традиционных языков, имеющих прежде всего непроцедурные элементы, например, LUCID /32/, PROLOG /25/. Синтез программ соприкасается с искусственным интеллектом (см., например, работы З.Манны и Р.Уолдингера /36,37/). Сильный тол-чек проблематика синтеза программ получила в связи с развитием пакетов программ /15,26/. Возникла проблема планирования вычислений.

Обзоры работ по синтезу программ сделали Э.Х.Тыугу /28, 29,42/, Н.И.Ильинский и А.В.Мясников /13/. В обзоре последних авторов выделены четыре направления автоматического синтеза программ: дедуктивный, трансформационный, индуктивный, на основе представления знаний. Обзор по трансформационному синтезу приводят В.А.Непомнящий и В.К.Сабельфельд /23/.

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

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

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

Понятие локального соотношения на массиве берет истоки из предложенной в 1956 г. С.С.Камыниным и Э.З.Любимским /17, 18/ формы описания задачи, получившей название параметрической записи. В этой постановке спецификация задачи выражается совокупностью расчетных формул, на применение которых могут быть наложены некоторые условия. И.Б.Задыхайло /II/ исследовал задачу построения циклического процесса счета по пара-метричекой записи на одномерных массивах Х-* »•••»Х™:

ХтН =/т(Х с;- ДтЛ, ■ . . , Хти-дтп1])

Здесь д^ - целые числа. Заданными считаются значения элементов хч I] для ^гп] » • •» гп ; требуется найти значения Х^З для т^ 6 Л^ , где и М^ фиксированные целые числа. В /II/ показано, что для разрешимой задачи существует такой порядок применения функций , приняв который за тело цикла, можно получить цикл по индексу I , вычисляющий по одному новому элементу каждого массива и использующий для этого заданные или полученные на предыдущих шагах элементы.

Р.М.Карп, Р.Е.Миллер и Ш.Виноград /35/ рассматривали вопросы существования и степени параллельности процесса счета по рекуррентным соотношениям на о -мерных- массивах. На одном П -мерном массиве X рекуррентное соотношение является уравнением вида

Х^Г] [ (ХсТ-Х,], . . . , ХпТ-д^]).

Здесь Дj - целочисленные векторы. Требуется подсчитать значения на множестве элементов V/ • Заданными считаются значения всех остальных элементов массива. В работе формулируются необходимые и достаточные условия, чтобы существовал процесс явного счета на множестве V/ специальных видов. Приведем пример такой теоремы. Процесс явного счета на множестве V/ , являющемся положительным ортантом П -мерного пространства, существует тогда и только тогда, когда существует гиперплоскость, отделяющая этот ортант от векторов -Д^ >•••> ~Лт (см. рис. I на след. стр.). В упомянутой работе не говорится о построении программы счета.

А.Пнуэли и Р.Зархи /38/ рассматривали трансляцию спецификации в виде уравнений

ХЛСЧ;.;ЧП3 ~ [л (ХЧЬ,,.;^], . . . Д^Е^.-.Д^])

Рис. I. Процесс счета на положительном ортанте по рекуррентному соотношению ХИН = (* ( 1. - - - ?Хс£-ЛтЗ) существует тогда и только тогда, когда существует гиперплоскость, отделяющая этот ортант от векторов -Д.,.♦,,-Ат « К

Здесь E: - целочисленные выражения. Требуется подсчитать W элементы с положительными индексами, т.е. для всех Ij-^O .

Ь. Ij.

Основные результаты получены в случае Lj r ij -Aj , где Aj целые числа. Приводятся алгоритмы построения циклической программы, имеющей вид композиции вложения циклов и следования Алгоритмы находят порядок индексов, по которому циклы должны быть вложены, и порядок применения функций fj в телах циклов. В некоторых случаях могут быть сделаны линейные трансформации индексов. Полученные таким образом циклы подпитывают себя, т.е. новые элементы массивов вычисляются по заданным или полученным на предыдущих шагах цикла элементам. В синтезируемых циклах счетчики пробегают положительные числа от 0 с шагом А . Например, по спецификации Хг i] -f(XCi-'O) строится цикл for L^O Леи (ЧХ Е1->П) end .

Спецификация же Х^З ~з) считается некорректной.

Построение циклической программы предполагается при трансляции с непроцедурного языка MObEL /39/, а также с разрабатываемого под руководством И.Б.Задыхайло непроцедурного языка НОРМА /31/. Язык MObEL использовался для обработки экономической информации. Язык НОРМА предназначен для решения задач, спецификация которых выражается разностными соотношениями на сетках. В обоих языках спецификация задается в виде уравнений. В левой части стоит одна переменная, возможно, имеющая свободные индексы. Счетчики цикла, в который транслируется спецификация, пробегают все значения из области, которой принадлежат свободные индексы уравнения. Транслятор устанавливает порядок вычисления переменных, проверяет корректность спецификации, не пересчитываются ли переменные.

Е.В.Новикова /24/ рассматривает синтез циклических программ по системам рекуррентных соотношений в системе СПОРА /1,2/. Язык системы СПОРА ДЕКАРТ располагает средствами описания рекуррентных соотношений вида

XJE¿] = fOOEE^ .;ХтЕЕт], А >|, . . . А п ]) , где Ej - индексные выражения, построенные из символов nexfc , pred , pirsb и lasb . Цикл синтезируется при трансляции отношения и оператора постановки задачи. Если применяется правило индукции X£i] ~-»-Х ГпехЬ , то строится цикл типа for I - . . . , в котором i пробегает некоторый отрезок. Если применяется правило индукции с предикатом Tqí) => Xa] —X Гпеу-b I ] , то строится цикл fec 1= . . while 1Г Qi) . . . • В /16/ приводится следующий пример. На отношении рдд ехр отнощ ря^длЯ-. ехр Гп • Целое] х : teal • схп j so : лдсхссц Ь ГС»- • целое] 0.n]iea|jj onpeg ao ГперЬ L] : - Л ; : ~ an[nepb L ] • ar» Г i 3 :-((afl í Пред i ] * X) / i ) sn[¿] : - ( snf пред i] +aoLC]) bce ОП1Н может быть поставлена задача вычислить sn[n] по х . В качестве решения будет получена программа

Ovnfo] : = 1 ; sn [о] : - an ^о] ;

-ог i'= Л Ьо п do ao[C] o»nti-1] X / i j sn [С] {L-Л] + an ^¡.^ od

В области синтеза циклов по рекуррентным соотношениям положительные результаты достигнуты благодаря тому факту, что программа достаточно полно предопределяется своей спецификацией. Логической основой возникновения цикла является применение принципа математической индукции. А, как отмечает Э.Х.Тыугу /42/, на практике можно использовать лишь ограниченные формы математической индукции в особо определенных ситуациях. З.Манна и Р.Уолдингер /36/ уже в 1971 г. отметили, насколько вид программы зависит от используемого правила индукции.

Про синтез циклов в системе ПРИЗ Э.Х.Тыугу пишет /29/: "Следует отметить, что тело цикла можно синтезировать как программу решения подзадачи. Управляющие структуры циклов, соответствующих разным схемам индукции, могут быть заранее запрограммированы и представлены в виде аксиом. Именно так происходит синтез циклов (и рекурсивных программ) в системе программирования ПРИЗ /41/". Язык системы ПРИЗ УТОПИСТ ориентирован на описание семантики модулей терминами вычислительной модели. Семантика модулей, представляющих управляющие структуры циклов, описывается как, например, "интеграл", "сумма", "максимум". В /14/ приводится следующий пример, иллюстрирующий отношение с подзадачей. Отношение с подзадачей - это зависимость результата от характера связи между аргументами, так же как интеграл ^ = ^ р- ¿х зависит от

То функции р . Переменная 5 (путь) зависит от связи V (скорость) с Т (время) и, конечно, пределов по времени ТО и "И . Предположим, что связь V с Т определяется моделью. Тогда для определения зависимости У-^Т) необходимо решить подзадачу ВЫЧИСЛИТЬ' V ПО* Т . В языке предусмотрена возможность описания подзадачи в описании отношения МОДУЛЬ* ЙНгТ вх' ТО ,та вык'5 , N ввх' Т ввых'у. Переменные типа ВВХ* являются входными для подзадачи, а переменные типа ВВЫХ* - искомые для подзадачи. Система синтезирует модуль для вычисления V по Т и присваивает ему уникальный номер. Для передачи этого номера в модуль ЦН1 служит параметр К •

Некоторые направления исследований по распараллеливанию циклических фрагментов программ /6,7,8,9/ можно отнести к синтезу параллельных программ над структурами данных. В.Е.Малышкин /20,21/ дал формальную модель задачи синтеза параллельных программ на вычислительных моделях с массивами. Постановка ориентирована на синтез параллельных программ на многопроцессорных вычислительных комплексах. Понятие вычислительной модели с массивами является расширением простых вычислительных моделей /27/ и отличается от последних наличием массивов и счетчиков. Предложен язык ОПАЛ /22/, предназначенный для задания алгоритма в форме вычислительной модели с массивами, т.е. в максимально непроцедурной форме. Это позволяет строить по ней оптимальные параллельные программы, учитывающие свойства вычислительной системы.

Отметим некоторые системы, синтезирующие программы обработки массивов, но по спецификации, задавемой не в виде рекуррентных соотношений. Система Г.Гушо /33/ по спецификации высокого уровня синтезирует алголоподобную рекурсивную программу. Используется дедуктивная техника, похожая на подход З.Манны и Р.Уолдингера /37/. Приведем пример спецификации вида "найти индекс 1 такой, #то 1Г(йНде1г:с^ ЬЬосЛ ",

- II где TT некоторый предикат. find I between Л o^A Ъ such hhab =Z

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

Подход к синтезу в системе PROFIT /34/ основывается на методах искусственного интеллекта. Система трансформируя программу работает по правилам продукций. Синтез циклов происходит следующим образом. Если нужна программа, устанавливающая истинность условия IT для всех элементов из множества S » T.e.1T\s) Vs е , то она разбивается на программу, реализующую T(heacJ($)) и ТГ^tcxi2 (S)) , если нужна рекурсивная версия, или min ($) ^ ^ ^mc\x (S) , если нужна итеративная версия. Пример разработанной программы: суммировать все элементы массива, которые больше чем заданное число.

В настоящей работе вслед за /11,24,35,38,39/ исследуется синтез из модулей ^ ,., F^ , реализующих счет по локальным соотношениям на структурах данных. Эти модули мы будем называть вычислительными модулям и. Однако для синтеза предлагается использовать также и библиотеку заранее заготовленных программ , умеющих циклически применять вычислительные модули, организуя различные обходы на структурах. Такие программы мы будем называть структурными модулями. Таким образом, предлагаемый подход является пакетным подходом к синтезу, а структурные модули можно считать новым видом функционального наполнения пакета.

Предлагаемый нами подход к синтезу мы начнем излагать с замечания, что программу вычислений на массиве по локальному соотношению можно разделить на счет и обход. Счетом является часть программы, представляющая непосредственные вычисления значений элементов массива. А обход это та часть программы, которая организует продвижение локального соотношения по массиву. Например, пусть на трехмерном массиве X определено соотношение КХСр^р^рзН], ХГр.+^р^рзМ];

XIр<, 1Х[р4, fa.11 > ]>3 -И д^

Графически это соотношение изображено на рис. 2. Тогда можно написать программу, вычисляющую значения внутренних элементов области формы стержня £см. рис. 4 на стр. 14), если заданы значения на поверхности этой области.В такой программе счет представляется операторами, вычисляющими по формуле (I), а обход - циклами по координатам р„ , рА , р3. . Внутренние циклы по р,, и р.2. организуют обход прямоугольника с отверстием. Они вложены во внешний цикл по р5 . Счет по формуле (I) можно представить в виде вычислительного модуля с параметрами р„ , р^ , р2 . Тогда программу расчета стержня можно применить к различным вычислительным модулям, представляющим различные функции (•■ в (I), а также учесть нужные размеры стержня, т.е. значения параметров Р^ , В. » » »Ру » , р>? (см. рис. 4). Важно только, чтобы все такие вычислительные модули вырабатывали значение элемента ХСр/^р^рз! по р^Рг + ^Ра-'О Рз-1)

Рз л р^Гг-^Гь-А

Рис, 2, Графическое изображение структурной семантики соотношения ХСр« ,р4,р3] = К^Рл^ Рз^] , ХГр, + 1, Ра. , ] ) Сръ Ра)

Ср-1, Р2.;

Р*

РЧ

Р-1; Р^2-)

Рис. 3. Графическое изображение структурной семантики соотношения ХЕр^рзЛ-Р'СХИр^р^рзЧЬ XСр1 ^2.^3-1]) .

Рис. 4. Расчет стержня по соотношению рЗ'^; ра.+ Ч, Рз-^З). значениям элементов р31 ] , ХСр^ + 1, р^-^З »

ХГр1, Рг-^, рз -4] » Хср^ь рз-^] • Другими словами, все они должны иметь одинаковую структурную семантику, графически изображенную на рис. 2. К вычислительному модулю, представляющему счет по соотношению

Хгрл,р*,рз3 = (Х1рЛ/р*, р3-2] , ХГр^р^ рз-ч]) применить данную программу расчета стержня нельзя. Графически структурная семантика такого вычислительного модуля изображена на рис. 3 на стр. 13.

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

Ьх ~~ь" ^ Ьых • ЗДесь ЮЛ Ьх и УА. и* "" множества элементов массивов. Задача синтеза понимается как построение программы, осуществляющей расчет элементов из множества Ж Ьуу. по элементам Ю(\ьх . Какие возможны пути решения поставленной таким образом задачи синтеза? Можно ее решать».используя только структурную семантику вычислительных модулей »• • •» ^ и спецификацию Ш ЙК1 Ьыу • Такую постановку можно назвать задачей прямого синтеза из вычислительных модулей. Она рассматривалась в упомянутых работах, посвященных синтезу по рекуррентным соотношениям. Конечно, в каждой работе выбраны свои ограничения на .вид рекуррентных соотношений и множеств ЭДъх > ^Ьы>< • Сразу отметим, что по нескольким причинам мы считаем нецелесообразным для решения задачи прямого синтеза следующий путь. Даются уникальные имена всем элементам массивов, а планирование по спецификации вход-выход проводится методами, принятыми в простых вычислительных моделях /5,27/. Во-первых, такой путь не учитывает нашу специфику - регулярность локального соотношения, т.е. что оно определено на большом и регулярном множестве элементов. Во-вторых, так как размеры массивов могут быть очень большими, то практически неприемлем даже перебор, зависящий лишь линейно от числа элементов массивов. Втретьих, мы предполагаем синтез программы, которая вычисляет не пятый или десятый элемент массива, а Р -ый, где Р - параметр синтезируемой программы. Параметр Р является границей цикла. Нас интересуют методы синтеза, сложность которых не растет с ростом Р .

Предлагаемый нами путь к синтезу программы из вычислительных модулей К, ,., по спецификации к* """ Ьык основывается на использовании структурных модулей 5ч ,., Зп .Мы уже отмечали, что одни и те же структурные модули можно сочетать с различными вычислительными модулями. Теперь мы добавим, что их можно использовать для построения изоморфных обходов на других массивах. Приведем пример. Пусть на массиве У выделена область формы стержня.(см. рис. 5), трансформированного по отношению к стержню на массиве X (см. рис. 4). Трансформация выражается поворотом относительно третьей координаты массива. Пусть заданы значения на поверхности стержня. Требуется вычислить значения внутренних элементов. Для этого имеется вычислительный модуль, реализующий соотношение

Графически структурная семантика соотношения (2) изображена на рис. 6. Изображение соотношения (2) трансформировано по отношению к изображению соотношения (I) на рис. 2, Но, не

Рис. 5. Расчет стержня по соотношению У^Ч^Лз] ~ З^ЧЛ ; ^ЧЛ ^МЬ УПцМН ] ; УГц+1, ^

Г^П^-'1)

1; LZ

Л) Ч

Рис. 6. Структурная семантика соотношения '■З 1 =

- 18 смотря на трансформацию, для расчета стержня на массиве V можно использовать программу расчета стержня на массиве X , Только при обращении к вычислительному модулю, вырабатывающему значение элемента массива V , должна учитываться трансформация координат р^ , , р3 в ц , Циклическую программу, организующую такой обход, можно каталогизировать в виде структурного модуля и использовать при синтезе программ расчета самых различных стержней.

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

- 19

Применив с-модуль к в-модулю Р способом структурного сопряжения , т.е. подставив Р в $> , получаем программу , осуществляющую счет на той же структуре, что и Р . Эта программа, которую мы сокращенно будем обозначать 5 (^Р] » снова является вычислительным модулем. Если к в-модулю можно применить другой с-модуль ч> , то процесс можно продолжить - (^Р)) является еще более сложным вычислительным модулем. Возможны также структурные модули, которые применяются к нескольким вычислительным, например, . Композицией некоторых операций, например, применения с-модуля к в-модулю и следования " можно строить программы расчета структур. Пример программы такого вида: (^1); ^2.(^2.)) . Существенно,что в-модуль вставляется в с-модуль, вследствие чего синтезируемая программа имеет более сложную структуру управления по сравнению с цепочкой вызовов вычислительных модулей.

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

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

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

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

Фиксированный структурный модуль Б можно, как правило, применить к фиксированному вычислительному модулю Р" различными способами структурного сопряжения . Полученные таким образом программы имеют различную структурную семантику. Например, к в-модулю от параметров^ ,12. может оказаться возможным применить с-модуль для осуществления цикла как по ц , так по (.2. .

В пакетах программ имеет место проблема системного сопряжения. Это вопросы размещения модулей в памяти и организации вызовов, вопросы размещения и представления данных и т.д. Проблемы системного сопряжения вычислительных и структурных модулей в данной работе не исследуются. Вопросы системного сопряжения подробно исследованы в системе ПНФ /3,4, 12/, предназначенной для разработки пакетов программ на базе нестандартизированных программных фондов.

Критерием правильности определения структурной семантики вычислительных и структурных модулей является ее пригодность для синтеза программ. В связи с этим в работе рассмотрена задача синтеза для программ специального вида • (Р)) •") • Программу такого вида мы будем называть цепочкой. Из двух этапов синтеза цепочки, -выбора последовательности модулей и построения их структурного сопряжения, - мы ограничиваемся рассмотрением второго этапа. Кроме того предполагается, что структурная семантика с-модулей ^ ,., , в-модуля ^ , а также спецификация ^ ^ Ьых описаны линейными выражениями специального вида. Таким образом, задача синтеза цепочки состоит в автоматическом построении способов структурного сопряжения

Л с

Е , таких, что программа с С • • • ^ ((=) ■••)

-г-» С л имеет заданную структурную семантику ^Ьы*

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

В процессе структурного сопряжения цепочки (даже не обязательно автоматического) удобно использовать понятия перейодных множеств МЛ ,., М° • Переходным множеством М-^АЛ,-1 ~мы называем структур

Ьу. ЬЫХ. ную семантику частичной цепочки, в-модуля, ^ ^ • • • Из этого видно, что переходные множества задаются на фактическом массиве. По определению Мс ~ АД . Структурное сопряжение СЕН 0 с-модуля ^ с остальной частью цепочки

• • ^ (Р) • • • ) - зависит от М^ и М^"1 . Поэтому для построения способов структурного сопряжения ,., 1~ 1 удобно иметь ввиду переходные множества. По М1 и структурной семантике К можно строить . По М2* и Л/^ можно строить Е. И так далее. По Мс и Мс~л можно строить [52е . Причем это построение можно провести в любом порядке.

Реализована экспериментальная система, решающая поставленную выше задачу автоматического структурного сопряжения цепочки. Экспериментальная система доведена до реализации с целью обоснования и проверки предлагаемой теории, проверки "стыкуемости" внутреннего и внешнего шаблона, а также для демонстрации возможности автоматического синтеза над массивами, проверки алгоритмов структурного сопряжения с- и в-мо-дулей. Системе задаются описания структурной семантики с-мо-дулей ^ ,., , в-модуля ^ , задается спецификация М-Щ, -'"йПиых, • Система строит способы структурного сопряжения ,., ? и затем интерпретирует цепочку.

Такой режим называется режимом синтеза.

В другом режиме, называемом режимом интерпс ре т а ц и и, система интерпретирует заданные человеком с способы структурного сопряжения Е »•••»^ » вызывает программы с-модулей ^ ,., 5е и в-модуля Г . Интерпретатору не требуются описаний структурной семантики модулей. Модули могут принадлежать более богатому классу, нежели предполагается в режиме синтеза. Интерпретатор также не проверяет корректности заданного структурного сопряжения.

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

Основные результаты диссертации состоят в следующем,

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

2, Введено понятие структурной семантики. Определена структурная семантика операторов следования, цикла и выбора.

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

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

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

- из

ЗАКЛЮЧЕНИЕ

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

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

3. Басс Л.П., Зусман И.Х., Камынин С.С., Корягин Д.А., Луховицкая Э,С,, Кротов В,И., Хиздер Л.А. Средства описания расчетных цепочек в языке системы ПНФ. Препринт №2. М.: ИПМ АН СССР, 1981.

4. Бухштаб Ю.А., Горлин А.И., Камынин С,С., Корягин Д.А,, Любимский Э.З. Интеллектуальный пакет, использующий при планировании вычислений знания о предметной области и функциональных модулях. Известия АН СССР, Техническая кибернетика, 1981, №5, с. II3-I24.

5. Вальковский В.А., Котов В.Е., Марчук А,Г., Миренков H.H. Элементы параллельного программирования. М.: Радио и связь, 1983. 240 с.

6. Глушков В.М., Капитонова Ю.В,, Летичевский A.A. Теория структур данных и синхронные параллельные вычисления. -Кибернетика, 1976, №6, с. 2-15.- 114

7. Глушков В.M., Капитонова Ю.В., Летичевский A.A., Горлач С.П. Макроконвейерные вычисления функций над структурами данных. Кибернетика, 1981, №4, с. 13-21.

8. Глушков В.М., Капитонова Ю.В., Летичевский A.A. Алгебра алгоритмов и динамическое распараллеливание последовательных программ. Кибернетика, 1982, №5, с. 4-10.

9. Дейкстра Э. Дисциплина программирования. М.: Мир, 1978. 276 с.

10. Задыхайло И.Б. Организация циклического процесса счета по параметрической записи специального вида. Журнал вычислительной математики и математической физики, 1963, №2, с. 337-357.

11. Зусман И.Х., Камынин С,С. Корягин Д.А., Кротов В,И., Луховицкая Э;.С., Хиздер Л.А. Средства модуляризации программного фонда в языке системы ПНФ. Препринт №24. М.: ИПМ АН СССР, 1981.

12. Ильинский Н.И., Мясников A.B., Автоматический синтез программ: направления, исследования. В сб.: Интеллектуальные системы программирования. М.: Энергоатомиздат, 1982, с. 13-19.

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

14. Корягин Д.А., Мартынюк В.В. Развитие проблематики системного обеспечения пакетов прикладных программ в СССР. -В кн.: Пакеты прикладных программ: Проблемы и перспективы. М.: Наука, 1982, с. 124-139.

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

16. Любимский Э.З, Об автоматизации программирования и методе программирующих программ. Дисс. канд. физ.-мат. наук. М., 1958.

17. Любимский 3.3. Вопросы автоматизации программирования. -Вестник АН СССР, i960, №8, с. 47-55.

18. Мак-Кракен Д., Дорн У. Численные методы и программирование на Фортране. М.: Мир, 1977. 584 с.

19. Малышкин В.Э. Синтез параллельных программ на вычислительных моделях с массивами. I. Формальная модель. Препринт №379. Новосибирск: ВЦ СО АН СССР, 1982.

20. Малышкин В.Э. Основные принципы и этапы синтеза параллельных программ на вычислительных моделях с массивами. В сб.: Автоматический синтез программ. Таллин: Институт кибернетики АН ЭССР, 1983, с. 89-109.

21. Малышкин В.Э. ОПАЛ язык описания параллельных алгоритмов. - В кн.: Теоретические вопросы параллельного программирования и многопроцессорные ЭВМ. Новосибирск, 1983, с. 91-109.

22. Непомнящий В.А., Сабельфельд В.К. Трансформационный синтез корректных программ. В кн.: "Оптимизация и преобразования программ". Материалы всесоюзного семинара, ч. 2. Новосибирск, 1983, с. 99-118.

23. Новикова Е.В. Синтез циклических программ по системам рекуррентных соотношений в системе СПОРА, III конференция "Применение методов математической логики". Тезисы докладов. Таллин, 1983, с. 146-148.

24. Середи П., Футо И. ПРОЛОГ. Пер. с венгерского. Будапешт, 1979. 241 с.- 116

25. ТаммБ.Г., Тыугу Э.Х, Пакеты программ. Известия АН СССР, Техническая кибернетика, 1977, №5, с. III-I24,

26. Тыугу Э.Х, Решение задач на вычислительных моделях. -Журнал вычислительной математики и математической физики, 1970, т. 10, №3, с. 716-733.

27. Тыугу Э.Х. На пути к практическому синтезу программ. -Кибернетика, 1976, №6, с. 34-43,

28. Тыугу Э.Х. Синтез программ (обзор). Всесоюзная конференция "Методы математической логики в проблемах искусственного интеллекта и систематическое программирование". Тезисы докладов и сообщений, ч, Вильнюс, 1980, с. 70-89.

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

30. Церевитинова Т.С, Алгоритмы реализации языка НОРМА, Дипломная работа. Московский государственный университет, факультет вычислительной математики и кибернетики, 1983.

31. E,A.Ashcroft,; W.W.Wadge. LUGE), a nonprocedural language vdth iteration. Communications of the ACM, 1977, v. 20, no 7,p. 519-526.

32. MJBidoit, C.Gresse, G.Guiho. A system which synthesizes array-manipulating programs from specifications. In: Eroc. 6th Int. Joint Conf. on Art. Int., Tokyo, 1979, p. 63-65.

33. G.Gini. The automatic synthesis of iterative programs. Information ^Processing Letters, 1982, v. 14, no 2, p. 67-73.

34. R.M.Karp, R.E.Millerj S.Winograd. The organization of convputa-tions for uniform recurrence equations. Journal of the ACM, 1967, v. 14, no 3, p. 56>590.

35. Z.Manna, R.J.Waldinger. Toward automatic program synthesis. -Communications of the ACM, 1971, v. 14, no 3, p. I5I-I65.

36. Z.Manna, R.J.Waldinger. Synthesis: Dreams ^ Programs.

37. EE Trans, on Software Engineering, 1979, v. 5, no 4, p. 294-328.

38. A.Pnueli, R.Zarhi. Realizing an ecpational specification. -Lecture Notes in Computer Science, v. 115» 1981, p. 459-478.

39. N.S.Prywes, A.Prraeli. Compilation of nonprocedural specifications into computer programs. IEEE Trans, on Software Engineering, 1983, v. 9, no 3, p. 267-279.

40. A.L.Rosenberg. Addresable data graphs, Journal of the ACM, 1972, v. 19, no 2, p. 309-340.

41. E.H.Tyugu. A programming system with automatic program synthesis. Lecture Notes in Computer Science, v. 47, Methods of Algor. Lang. Implementation, Springer-Verlag, Berlin, 1977,p. 251-267.

42. E.H.Tyugu. Toward practical synthesis of programs. In: "Information Processing 80". Proceedings of IFIP Congress 80, Amsterdam e.a., 1980, p. 207-219.