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

Введение

Глава I Синтез программы, не содержащей циклов.

§1. Построение программы по полной системе примеров.

§2. Построение программы по неполной системе примеров.

§3. Итерационный метод построения программы в интерактивном режиме.

§4. Построение программы по примерам с опущенными предикатами.

Глава II Синтез циклов.

§1. Построение цикла по одному исходному примеру.

§2. Построение цикла по совокупности примеров.

§3. Построение программы вида ВХОД, А1, А2, ,АК, Ц, ВЫХОД.

§4. Построение цикла по размеченным примерам.

§5. Синтез кратных циклов.

Глава III Эксперименты по синтезу программ.

§1. Экспериментальная система синтеза.

§2. Результаты экспериментов.

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

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

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

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

Дедуктивный синтез /8-15, 33, 34/ исходит из того, что суть программы -можно выразить отношением, связывающим входные данные с результатом. В общем виде задача дедуктивного синтеза формулируется следующим образом: дан входной предикат и выходной предикат Б^(Х,У) , построить программу, вычисляющую функцию У= Ф(х) так, что если X - входной вектор, удовлетворяющий Р/Х^), то $(Х,) определена и выполнено условие Р (X, Ф(Х)). Предикаты и Р£(Х,У) называются соответственно входной и выходной спецификациями. Задача решается путем построения конструктивного доказательства теоремы

Найденное доказательство затем переводится в программу. В основе такого решения лежит тот факт, что в некоторых логиках истинность формулы УХ[Р^(Х)^(ЗУ) Р2(Х,У)] гарантирует реализуемость по заданному X соответствующего У.

Одни из первых содержательных результатов в области дедуктивного синтеза обсуждаются в статье /34/, их развитие осуществляется в работах /II, 33/.

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

Так, в системе ПРИЗ задача формулируется в виде тройки /М, В, Р/, где М -условие задачи, В - множество входных переменных, Р -множество выходных переменных. Для получения практического результата ограничивается класс решаемых задач, выбирается специальное представление для условия задачи. Кроме того, синтез автоматизирован частично - только те участки программы, для которых достаточно просто задать условия М, описываются в виде тройки /М,В,Р/. Разработан входной язык описания задачи УТОПИСТ.

Трансформационный подход к синтезу /28-31, 35/ основывается на интерпретации процесса создания программы как целенаправленной последовательности модификаций /трансформаций/ некоторой начальной программы, приводящих к требуемой результирующей программе. Действительно, часто программист тратит много сил на модификацию уже написанной программы, в тех или иных целях. Так, очень важна ясность программы, простота понимания алгоритма. Но это требование иногда противоречит требованию эффективности, причем, разница между соответствующими вариантами программы может быть существенной. Как правило, программа в этом случае пишется сначала в виде, удобном для понимания алгоритма, а затем преобразуется в эффективную форму. Естественно попытаться формализовать и автоматизировать процесс такой трансформации. Кроме того, при написании новой программы оправданным является стремление применить те приемы, которые были успешно использованы в других программах.

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

-6, спецификации программ должны быть выражены так, чтобы их можно было сравнивать. Приведение их к такому виду является одним из этапов /вообще говоря достаточно сложным/ всего трансформационного процесса.

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

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

В настоящее время исследования в области трансформационного синтеза ведутся в различных направлениях. Теоретические разработки и экспериментальные системы ориентированны на практическое применение.

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

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

Основополагающие идеи индуктивного синтеза нашли уже своё практическое воплощение в системе БВА /38, 39/, которая позволяет описать конкретное приложение реляционной базы данных и работать с этим приложением специалисту данной предметной области, а не профессиональному программисту. Для этого необходимо задать на специальном языке "примеры" монипулирования с информацией.

В настоящее время исследования в области синтеза программ . по примерам их выполнения ведутся в двух направлениях: 1/ синтез программ по примерам вида /X, У/, где X - это конкретное входное значение параметров программы, а У - соответствующее ему результирующее значение,

2/ синтез программ по историям или следам их работы, соответствующим конкретным входным данным.

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

Пусть есть набор операторов, которые могут входить в синтезируемую программу. Тогда метод синтеза по примерам типа вход-выход можно представить так: получив некоторую совокупность примеров, синтезатор перебирает все возможные программы в указанном языке в порядке увеличения числа операторов, проверяя каждый раз, выполняет данная программа исходные примеры или нет. Найдя такую программу, выдает результат. Известно, что для произвольной программы проблема завершения работы неразрешима, поэтому нельзя в общем случае сказать, получает ли программа по данному входу требуемый выход. Следовательно, программа для произвольной частично рекурсивной функции, вообще говоря на может быть синтезирована по примерам типа вход-выход. Подробнее эти вопросы обсуждаются в работах /2, 3, 27/.

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

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

I/ для каждого примера /Х^, У£/ определить последовательность операторов Т^ , которая переводит Х^ в У^ /след программы/, 2/ найти программу, которая выполняет последовательность Т^ при входе XI для всех .

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

Ряд исследований в данной области посвящен синтезу ЛИСП-функций /26, 32, 36, 37/. Как правило, алгоритмы синтеза таких программ имеют структуру, приведенную выше, причем для рассматриваемого класса программ на первом этапе синтеза соответствующую последовательность операторов для /X;, У;/ часто получить достаточно просто. Например, в работе /37/ предлагается методология синтеза программы на ЛИСПе по совокупности примеров типа вход-выход, основанная на реализации следующих идей:

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

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

Алгоритм, описанный в /36/, позволяет построить программу по одному примеру, опираясь на набор эвристик, которые выражают различные методы программирования на ЛИСПе. В статье /26/ описывается метод синтеза для класса так называемых регулярных ЛИСП-программ.

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

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

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

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

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

В статье /22/ А.Бирманом предложен алгоритм синтеза машины Тьюринга по следам её работы. Суть этого алгоритма состоит в следующем: строится машина с данным числом состояний, которая может выполнять первые К инструкций примера, затем осуществляется поиск изменений, которые необходимо в неё внести, чтобы выполнилась К+1 инструкция. Идея такого пошагового синтеза лежит в основе метода построения программы по историям её выполнения, разработанного и реализованного А.Бирманом и др. /23-25/.

Метод не накладывает никаких ограничений на синтезируемую программу. Программа представляется в виде ориентированного графа, каждой вершине которого соответствует некоторый оператор программы, обязательно есть одна вершина с оператором НАЧАЛО и одна вершина с оператором КОНЕЦ. Из вершин графа может выходить несколько дуг. Если исходящих дуг больше одной, то каждой из них должен быть сопоставлен предикат, однозначно определяющий путь из такой вершины. Пример - последовательность инструкций Щ, И?, С^, И^,., И^ где ^ - безусловная инструкция типа А:=В+К, а С^ - выполненная в данном примере условная инструкция или предикат типа А ^ 0.

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

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

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

Основным недостатком приведенного метода является то, что для относительно сложных программ число возвратов в процессе синтеза чрезвычайно велико. Это приводит к быстрому росту времени синтеза с увеличением сложности программы. Так, среднее время синтеза машины Тьюринга с одним, тремя, пятью состояниями, приведенное в работе /22/, равно соответственно 1сек., 5сек., ЮОсек.

Как отмечают сами авторы в /24/, для того, чтобы с приемли-мой скоростью строить программы, представляющие практический интерес, необходимо усовершенствовать описанный алгоритм синтеза или создать новый. Средства такого усовершенствования предлагаются в статье /24/. Суть их заключается в дополнительной обработке следа для получения информации, которая используется в основной процедуре. Дополнительные данные позволяют в некоторых случаях выявить некорректность очередного объединения инструкции примера и оператора программы в тот момент, когда оно осуществляется, и тем самым сократить число возвратов. Предлагается два способа получения такой информации - статический и динамический.

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

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

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

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

-13в которых пропущены следы операторов инициации и продвижения переменной цикла /индекса/. При этом, в следах операторов, содержащих переменные с индексами, последние заменены их конкретными значениями.

Индексный механизм пытается обнаружить команды вида Х'= К, X :=Х+К, где X - введенная переменная цикла, К - целая константа, и приписать их к дугам графа программы. При этом индекс X вставляется в соответствующие операторы. Работая в рамках описанного алгоритма синтеза, механизм на каждом шаге рассматривает следующую задачу: для данного следа и программы, выполняющей часть этого следа, ввести индекс X и найти множество индексных команд, которые можно приписать к дугам графа так, что некоторое множество последующих инструкций следа можно объединить с уже построен* ными операторами программы. Для поиска решения к каждой и-той дуге приписывается выражение X или X /выбор индексной конфигурации/, составляется и решается система линейных алгебраических уравнений относительно всех Очевидно, что если в некоторый момент в программе есть уже т* дуг, то существует, вообще говоря, 2 возможных индексных конфигураций. Осуществляется их перебор до тех пор пока не будет найдено решение соответствующей системы уравнений.

Другой метод синтеза описан М.Бауэром в работе /20/, Для задания примеров предложен некоторый язык, близкий к естественному, Примеры на этом языке переводятся в специальную древовидную структуру» и в таком виде обрабатываются алгоритмом. По сути данный алгоритм мало отличается от метода А.Бирмана.

Исследованию проблемы индуктивного синтеза посвящен ряд работ БарздиняЯ .М. /4-7, 19/. В статье /7/ описываются правила вывода, ориентированные на синтез программ по историям их выполнения. Правила работают чисто графически, отвлекаясь от семантики примера, представляя его как конечную последовательность слов в некотором алфавите. Цель правил - найти закономерности в примере и обобщить их. Средством для записи обобщений является так называемый графический 1)0-оператор. Заголовок его имеет вид Хг^СТОЗ или X : 3 , где X - переменная цикла, шаг цикла равен 1 или -1 соответственно в операторах с заголовком первого или второго типа. Тело 1)0-оператора - конечная последовательность слов в выбранном алфавите. По крайней мере в од* 0 /о ном из них должно содержаться подчеркнутое слово вида I или 1±С], /£.- переменная цикла, ££ - целая константа/. Тело 1)0-оператора может содержать другой ££?-оператор. При разворачивании 2>0-оператора для каждого значения переменной цикла Ь берется свой экземпляр его тела, при этом, подчеркнутые выражения заменяются их значениями.

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

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

Третье правило применяется только тогда, когда больше невозможно применить ни первое ни второе.

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

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

В работе /19/ в качестве исходного примера рассматривается индуктивное описание программы, которое фактически является описанием нескольких первых шагов её работы. Индуктивное описание получается из программы следующим образом:

- каждому ХЮ-оператору программы сопоставляется некоторый уникальный идентификатор /например А /,

- каждый Д?-оператор развертывается, при этом ¿--тый экземпляр тела оператора обозначается К1 и часть шагов заменяется точками - А1 , А2 .

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

1)0 -оператор программы может содержать стрелку выхода из тела оператора.

Предлагается алгоритм построения программы по её индуктивному описанию. Он заключается в свертывании каждого Х>0-оператора в порядке увеличения их глубины. Под глубиной 1)0-оператора понимается количество вложенных в него других Д)0-операторов. Поскольку все ])0 -операторы помечены и обозначен каждый экземпляр соответствующей развертки, то поиск свертываемых участков примера сводится к нахождению соответствующих идентификаторов. В статье приводится теорема о полноте алгоритма.

Можно выделить два подхода к созданию алгоритмов синтеза программ по историям выполнения. Назовем их соответственно прямым и структурным синтезом. Приведенные выше алгоритмы /23-25/ и /5-7/ иллюстрируют соответственно первый и второй подход.

Характерной чертой прямого синтеза является его универсальность, которая заключается в том, что на синтезируемую программу не накладывается никаких ограничений. Такая универсальность подхода, с одной стороны, является его преимуществом, поскольку предполагает создание алгоритмов, предназначенных для синтеза любой программы. Но, с другой стороны, исключается возможность использования тех или иных свойств результирующей программы в процессе синтеза, что могло бы в значительной мере увеличить эффективность алгоритма. Универсальность прямого синтеза обуславливает еще одну его особенность, которая заключается в том, что алгоритм синтеза рассматривается как разновидность процедуры перечисления или перебора программ в порядке увеличения числа операторов. Поэтому искомая программа строится пооператорно сверху вниз /от оператора НАЧАЛО к оператору КОНЕЦ/ параллельно с просмотром примера. Увеличение эффективности алгоритма в этом случае может быть достигнуто с помощью введения различных вспомогательных средств ограничения перебора, таких, например, как упомянутые выше средства, описанные в статье /24/.

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

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

Упомянутый выше метод, разработанный в /7/ предназначен для класса графических программ, содержащих графические Х>0-операторы. Этот оператор является основной структурной единицей. Пример обрабатывается итерационным способом так, что на каждом К+1 шаге итерации рассматривается история, полученная после К-ого шага. Причем решения, принятые на некотором шаге, не отменяются ни на одном из последующих шагов. Другими словами, ни один однажды свернутый Х>0-оператор в дальнейшем не может быть снова развернут.

В данной работе также применяется структурный подход к проблеме синтеза программ по историям их работы. Цель исследования состоит в разработке эффективного алгоритма синтеза простых структурированных программ и экспериментальной проверке его свойств. Рассматриваются программы двух типов: I/ структурированная программа, не содержащая циклов, первым оператором которой является оператор ВХОД, а последним - ВЫХОД, 2/ программа вида ВХОД Ар A¿,., А^ , Ц, ВЫХОД, где все Аl -безусловные операторы, Ц - цикл с шагом I, заголовок которого имеет вид POR T-XqTO N DO , где X - переменная цикла, Х0~ начальное значение переменной цикла / целое/, А/ - переменная, граница цикла; тело цикла - программа первого или второго типа, в которую могут входить операторы, содержащие индексные выражения вида J ± С / С- - целая константа/.

Пусть А - набор входных параметров программы. Тогда каждому конкретному допустимому значению этого набора соответствует история или след её выполнения. Фактически история выполнения программы есть последовательность следов выполненных операторов. г- ^

Примером будем называть пару /#., / /, где cL - значение набора входных параметров, Т - история выполнения программы, соответствующая данному Я- .

В этом случае будем говорить, что программа выполняет некоторый пример Е = /¿£» ' /» если история её работы, соответствующая значению набора входных параметров и некоторым значениям границ цикла / для программ второго типа/, совпадает с Т .

Очевидно, что все истории выполнения программ указанных выше типов начинаются со следа оператора ВХОД и заканчиваются следом оператора ВЫХОД. Предполагается, что в историях программ второго типа во всех следах операторов, содержащих индексные выражения, последние заменены на соответствующие числовые значения.

Пусть история выполнения программы задается в виде линейной цепочки: ВХОД, Н^ \\%кг ,., НК кк, ВЫХОД, где если

И1 - след оператора-условия /предиката/, имеющего в данном примере значение "истина", если И^- след предиката, имеющего значение "ложь", = 0 /пусто/, если Н^ - след безусловного оператора. Назовем Н^ узлом примера /условным или безусловным/ .

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

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

В первой главе описывается алгоритм синтеза структурированной программы, не содержащей циклов, вида ВХОД, П, ВЫХОД, где

П - суперпозиция конструкций следования и выбора.

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

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

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

На первом этапе осуществляется построение так называемого дерева примеров путем объединения /склеивания/ историй сверху вниз, начиная от следов оператора ВХОД, по правилам, основанным на выработанных условиях склеиваемости узлов примеров. Корень дерева - след оператора ВХОД, листья - следы оператора ВЫХОД, все остальные узлы - следы безусловных операторов программы или операторов-условий, имеющие соответственно ровно одного потомка, одного или двух потомков. В зависимости от исходной совокупности примеров дерево может быть полным /в этом случае все узлы, являющиеся следами условных операторов, имеют ровно двух потомков/ или неполным /есть неполные узлы, т.е. условные узлы, имеющие одного потомка/.

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

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

Если построенное дерево неполное, то сначала осуществляется его дополнение, а затем полученное полное дерево склеивается в граф программы. Процедура дополнения делится на два этапа: поиск дополнений для каждого неполного узла и непосредственно дополнение дерева. Содержательно первый этап состоит в следующем: для каждого неполного узла в дереве ищутся все узлы, которые могут считаться следами того же оператора программы, следом которого является данный неполный узел, кроме того, найденные узлы должны иметь потомка, недостающего неполному узлу.

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

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

В четвертом параграфе первой главы рассматривается модификация разработанного алгоритма синтеза, предназначенная для так называемых сокращенных примеров. Сокращенный пример - это пара

V —^

5.»7^/, где О, - значение набора входных параметров, Т^- сокращенная история программы, полученная путем удаления всех еле-дов предикатов из её обычной истории, соответствующей данному В процессе синтеза на этапе построения дерева примеров вместо пропущенных предикатов вставляются пустые узлы. Таким образом, в дереве не только объединяются все исходные примеры, но и восстанавливаются позиции пропущенных предикатов. Каждому ребру дерева в процессе его построения сопоставляется метка, которая имеет вид / , 2^,., 2-^/» где значение набора входных параметров примера . Далее построенное дерево склеивается в граф программы. При этом к двум правилам, лежащим в основе алгоритма склеивания дерева, построенного по несокращенным примерам, добавляются два новых правила склеивания деревьев определенной структуры. В результате работы алгоритма получается управляющий граф, в котором пустые узлы соответствуют условным операторам программы, а путь определяется метками на ребрах.

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

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

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

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

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

Наиболее трудоемкой операцией при поиске требуемого разбиения примера является проверка на склеиваемость в дерево отрезков каждого выбранного варианта, т.к. она предполагает поочередное сравнение узлов всех отрезков. Разработан метод, который позволяет избежать многократного повторения указанной проверки. Вводится промежуточная таблица, элементами которой являются целые числа. Она строится в процессе проверки на склеиваемость в дерево отрезков так называемого базового разбиения и имеет вид квадратной матрицы, количество строк и столбцов которой равно числу отрезков базового разбиения. Базовое разбиение примера состоит из отрезков, начинающихся с узлов, которые по определенным критериям считаются следами одного и того же оператора программы, причем первый отрезок начинается со второго узла примера /первый узел - ВХОД/. В таблице отражена взаимосвязь между этими отрезками. Дальнейший поиск нужного разбиения осуществляется по таблице без повторного обращения к примеру. Описанный алгоритм требует не более, чем Щ2- Оп-В- сравнений, где ьг - количество узлов примера, в то время как верхняя оценка для количества сравнений при прямом переборе равна т 2(гп~^ ) +. т+

Нужно отметить, что в отличии от алгоритма, предложенного в /25/, в данном алгоритме нет отдельного индексного механизма как некоторой дополнительной переборной процедуры. Так как априорно задан вид цикла, то переменная цикла вводится автоматически. Кроме того, нет необходимости во введении операторов её инициации и продвижения. Разбиение примера производится с учетом возможности введения индекных выражений в операторы результирующей программы, поэтому на этапе свертки цикла эти выражения вводятся без дополнительной проверки.

В результате работы алгоритма по примеру строится программа данного типа, при этом формируется заголовок цикла вида РОК X = Хд ТО А/ 1)0 . Начальное значение переменной цикла определяется в процессе синтеза, переменная N вводится автоматически. Вместе с результирующей программой выдается количество повторений построенного цикла в исходном примере.

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

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

В третьем переграфе предлагается два варианта модификации разработанного алгоритма для синтеза программы вида ВХОД, А1,

А2,.,АК, Ц, ВЫХОД, где АI - безусловный оператор, Ц - однократный цикл. Обе модификации отличаются от первоначального алгоритма, а также различаются между собой лишь методом поиска базового разбиения.

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

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

-27В диссертации было уделено внимание указанной модификации т.к. во-первых, разметка примеров во многом упрощает алгоритм синтеза, а также позволяет расширить класс синтезируемых программ, во-вторых, реальной является ситуация, когда задавая пример цикла, пользователь представляет себе каким образом происходит повторение; естественно предоставить ему возможность передать эту информацию синтезатору. При наличии разметки в примерах отпадает необходимость в самом трудоемком этапе синтеза -построении подходящего разбиения примеров. Такое разбиение определяется однозначно расставленными метками. Априорное задание разбиения примера обеспечивает возможность синтеза циклов, имеющих операторы, которые содержат индексные выражения не только вида X ± С- » но и ЗхТ ± С- > гДе В и С - целые константы. Возможность введения в операторы тела цикла индексных выражений последнего вида фактически снимает ограничение, что шаг цикла равен I.

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

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

выход где , К^^О для ¿¿w , шаг каждого цикла равен df

A'íj для всех I , j являются безусловными операторами, тело M+J-QTO цикла s - структурированная программа без циклов, в которую могут входить операторы, содержащие индексные выражения для переменных всех циклов вида JT; + • j j

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

Суть алгоритма, решающего поставленную задачу, состоит в многократном применении модифицированного алгоритма синтеза однократного цикла /назовем его АЛЛОД/. На каждом шаге АЛГМОД применяется к дереву, полученному после предыдущего его применения, рассматривая его как исходное дерево примеров. Процесс продолжается до тех пор пока будут строиться циклические разбиения. Далее результирующее дерево склеивается в граф программы,

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

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

Рассмотрим базовое разбиения примера & , ,., ет . Пусть //у , И2. »•••» Им - узлы примера, порождающие это разбиение / Щ - первый узел (2'и /. По определению базового разбиения для всех и узлы Иу , //¿' параметрически эквивалентны. Обозначим хк = / » ¿г , • • •, / /2 »у набор номеров позиций параметров для пары узлов И^ , И\ . Разобьем все данные узлы на группы первого уровня /^ , ,. •, /£ » так, чтобы в каждую группу Г] входили только те узлы ///,/// ,., ///, , для которых Х;= х/ =. = х/. . ] . ^ ' ^ И; - ¿-тый узел /'-той группы, X; ~ набор позиций пара

4- , и метров для пары //^ , //У /. Группа состоит из узлов эк

Бивалентных Иу , т.е. для этой группы Л ^ = Л д =.= л^ = = 0 /пустое множество/. Назовем группу Гщ нулевой.

Если ^ ={ ч то исходное базовое разбиение является приведенным. Из всех найденных групп выделим такие группы /у , Г^ , ., для каждой из которых выполнено следующее неравенство:

X? » гДе " совокупность подмножеств множества 1 2ср п 2 »• • •'](/"(* ДРУГИМИ словами, набор позиций параметров для узлов каждой выделенной группы не является объединением соответствующих наборов для узлов, принадлежащих каким-либо другим группам, исключая нулевую.

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

Выберем первую по порядку группу. Узлы этой группы вместе с //у и узлами нулевой группы дают приведенное базовое разбиение. Если по этому базовому разбиению нельзя построить циклическое, то выбирается следующая по порядку группа второго уровня, которая дает новое приведенное базовое разбиение. Если все группы второго уровня исчерпаны, то выбираются по очереди группы первого уровня.

Например, пусть первоначальное базовое разбиение было порождено последовательностью , » Л/У.37» А [ гЛ] , >4 С Данные узлы разбиваются на группы первого уровня г< ={А[<{,г] , А, гг гл1} , Г5 ={А[2.Ц для которых = *М3) ' Ху = {3,4} . Группами второго уровня будут и Рг и первой из них будет выбрана Г? • Таким образом, приведенное базовое разбиение по

-100рождается узлами , А [ Zt'f] .

В том случае, когда синтезируемая программа удовлетворяет некоторым дополнительным условиям, можно доказать, что при каждом L -том применении алгоритма АЛГМОД первое найденное приведенное базовое разбиение содержит все следы первого внутреннего оператора L -того цикла при всех его проходах в данном примере и не содержит ни одного следа этого оператора при проходах по внутренним циклам. Приведем эти условия. Условие I. В синтезируемой программе нет ни одного оператора, оставляющего след, параметрически эквивалентный следам операторов А'ц , А[г f»*Aij(i //^ М- I И следу первого оператора тела самого внутреннего цикла 5 • Условие 2. Для всех {^ i * т к^ 0.

Условие 3. Если существует м + { vi ПЪ 4 , такие, что

Kj = =• • = fy+f0 » то либо /а/ А j+n 4 содержит все индексы Zj , Z]+i /если j +yt Ф rn + 4 /, либо /б/ первый оператор тела м + 4-ого цикла 5 содержит индексы Zj , ,., Jj+rL /если j +/z = M + i /. Утверждение 2.5 Если синтезируемая программа удовлетворяет условиям V, z или Y,3, то при каждом I-том применении алгоритма АЛГМОД первое найденное приведенное базовое разбиение ф содержит все следы первого внутреннего оператора ¿.-того цикла при всех его проходах в данном примере и не содержит ни одного следа этого оператора при проходах по внутренним циклам. Доказательство.

I/ Пусть выполнены условия >/ и 2 .

Очевидно, что в этом случае каждое Д-тое приведенное базовое разбиение совпадает с неприведенным и состоит только из следов оператора Ац //-^ — / или из следов первого оператора тела цикла 5 /1= Wi+i/.

2/ Пусть выполнены условия I и За/. Это означает, что в программе есть участок вида т ij ■=1? го Nj J>O por ijh-ljh ro tffa do FOR TO Nj+n V0(Aj+n<

Предположим, что это первый такой участок в программе, т.е. для * • * * l<j к- ф 0 . Тогда для всех итераций работы алгоритма АЛГМОД утверждение справедливо /доказано выше/. Не ограничивая общности, положим , т.е. участок программы имеет вид: por то д/j do

POR IZ=I¡ TO Nz

Возьмем историю выполнения такой программы и построим её базовое разбиение, которое порождается узлами И-f > Иг >•••» Им • Так как программа удовлетворяет условию { , то каждый узел Hi является следом оператора /4?/ . Пусть X/ = ¿ /у > L¿ >. • •»1к} и i Ji » Л 9''' *Jt } множбств9- позиций индексных выражений, содержащихся в Ац для переменных Jj и Jz соответственно. Из условия За/ следует, что Xj ¿ 0 » Xz ^ 0 • Рассмотрим каждый след оператора

Ац как набор символов, заменив символы во всех позициях кроме позиций индексных выражений точками. Пусть для определенности в примере внешний цикл прокручен К раз, а внутренний п. раз К* п , X/= f 3,8},

Хг = . Последовательность, порождающая базовое разбиение имеет вид:

•-1027° • • • г; +* -л Гг. -Л, Им =. Х°г+кЧ.

Легко убедиться в том, что группами второго уровня будут у = / » » ' * * *' ^м-/ / = ! Иг » ^з »• • •» Ип /.

Из них будет выбрана /у , т.к. М - 4 п * Таким образом,приведенное базовое разбиение состоит из узлов /// * Ипн » Иь+\ »•••' Им-1 » кот°Рые являются следами Ац при проходах по внешнему циклу.

3/ Пусть выполнены условия I и 36/. Справеливость утверждения в этом случае доказывается так же .:;:. как и в предыдущем.

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

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

ГЛАВА III» Эксперименты по синтезу программ.

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

§1. Экспериментальная система синтеза. Экспериментальная система синтеза реализована на языке ПАСКАЛЬ БЭСМ-6. Она состоит из двух модулей - программы синтеза /синтезатора/ и генератора примеров.

Объем синтезатора составляет 1870 строк языка реализации. Основная его часть представляет собой реализацию разработанного алгоритма синтеза программы вида ВХ0Д,А1, А2,.,АК, Ц, ВЫХОД где Ц - цикл любой кратности, по совокупности исходных примеров с использованием первого из двух, приведенных в третьем параграфе второй главы, методов построения базового разбиения примера или дерева примеров. Кроме того синтезатор содержит ряд вспомогательных процедур, таких как процедура обработки входных примеров, процедуры выдачи на печать результирующей программы и т.п.

Программа синтеза расчитана как на размеченные, так и на неразмеченные примеры. Каждый неразмеченный пример задается в следующем виде: ВХОД, И^Н^ , Иг кг , •., Иц /гл , ВЫХОД, где ="+", если И1 - предикат, имеющий значение "истина", ="-"> если /// - предикат, имеющий значение "ложь", 0 пусто/, если - не является предикатом. В размеченном примере перед некоторыми узлами /// стоят метки "+".

Каждый узел примера может содержать любые символы, кроме букв "Г", " /\/ Запятая является разделителем между узлами одного примера, точка с запятой разделяет примеры входной последовательности, " J¿ " обозначает переменную /-того цикла, которая вводится системой в процессе синтеза, " b¡l " -граница I -того цикла, также вводится синтезатором.

Основные этапы работы программы синтеза следующие: I/ ввод и начальная обработка примеров, 2/ построение дерева примеров,

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

5/ свертка дерева по циклическому разбиению, если последнее найдено,

6/ склеивание дерева в граф программы.

Шаги 3-5 повторяются до тех пор, пока находятся базовые разбиения.

Таким образом, результатом работы синтезатора является управляющий граф искомой программы, который выдается на печать. При записи программы используются конструкции следования -AI, А2,.; выбора -JP£ 1HBN М EUíB Al ; повторения -FOR Ij=Tj° ТО tfj J>0 A / , где p - предикат, Á¿ - суперпозиция конструкций следования, выбора и повторения.

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

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

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

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

§2. Результаты экспериментов.

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

Нужно отметить, что синтез реальных программ, как правило оказывается практически беспереборным. Это относится как к процедуре построения графа программы по неполному дереву примеров, так и к поиску циклического разбиения по данному базовому разбиению. Синтез таких программ, как поиск максимального элемента массива, вычисление полинома степени д с коэффициентакми, расположенными в массиве А10'К1 > по схеме Горнера, нахождение суммы двух вектором и т.п. осуществляется за время, меньшее 0,5 секунды. При этом достаточно задать один пример, в котором цикл повторяется 2-4 раза.

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

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

Результаты эксперимента, в ходе которого было синтезировано около 40 программ, говорят о том, что разработанные алгоритмы являются работоспособными и достаточно эффективными.

-108-ЗАКЛЮЧЕНИЕ.

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

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

2/ Разработан алгоритм синтеза однократного цикла, тело которого может содержать ветвления и операторы с индексными выражениями вида X + С- • Допускаются примеры, в которых все индексные выражения задаются их конкретными числовыми значениями. Доказано, что разработанный метод сворачивает примеры максимальным образом, т.е. разбивает их на максимально возможное число отрезков, соответствующих повторениям цикла.

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

4/ На базе разработанных алгоритмов осуществлена реализация экспериментальной системы синтеза программ.

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

-по

1. Барздинь Я.М. Трахтенброт Б.А. Конечные автоматы /поведение и синтез/. "Наука" 1970.

2. Барздинь Я.М. Фрейвалд Р.В. О прогназировании общерекурсивных функций. ДАН СССР 206, 1972, сс. 521-524.

3. Барздинь Я.М. Фрейвалд Р.В. Прогнозирование и предельный синтез эффективно перечислимых классов функций. Теория алгоритмов и программ. Ученые записки Латв. гос. ун-та 210, 1974.

4. Барздинь Я.М. Замечания о синтезе программ по историям их работы. Теория алгоритмов и программ. Ученые записки Латв. гос. ун-та. 210, 1974, сс. I45-I5I.

5. Барздинь Я.М. О синтезе программ по отдельньм примерам. Теория программирования. Труды симпозиума ч.1, Новосибирск 1972.

6. Барздинь Я.М. Об индуктивных правилах вывода для синтеза программ. Всесоюзная конференция "Синтез, тестирование, верификация и отладка программ" Рига 1981.

7. Барздинь Я.М. Некоторые правила индуктивного вывода и их применение. Семиотика и информатика. Вып.19, 1982.

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

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

10. Кахро М.И. Мянисалу М.А. Caan Ю.П. Тыугу Э.Х. Система программирования ПРИЗ. Программирование I, 1976.

11. Bierman A.W, Automatic Insertion of Indexing Instruction in Program Synthesis. Int. Jour, of Comp. and Inform. Science. v*7 n.1 1976 pp. 65-90.

12. Bierman A.W. The Inference of Regular LISP Programs from Examples. IEEE Trans. Syst. Man Cybern. v. 8 n.8 1978.

13. Blum i. Blum M. Toword a mathematical theory of inductive inference. Information and Control n.28 1975 pp.125-155.

14. Burstall R.M. A system which automatically improves programs. Acta Informatica. v.6 1974 pp. 41-60.

15. Burstall R.M. Darlington J.A. A transformation System for developing recursive programs. J. ACM. v.24 n.1 1977.

16. Darlington J.L. A system of several sortihg algorithms Acta Informatica v.11 n.1 1978 pp. 1-31.

17. Dershowitz N. Manna Z. The Evolution of Programs: A System for Automatic Program Modification. IEEE Trans. Software Eng. v.se-3 n.6 1977.

18. Kodratoff Y. A Class of Functions Synthesired from a Finit Number of Example Scheme Int. Jour, of Comp. and Inf. Sc. v.8 n.6 1979 pp. 489-521.

19. Manna Z. Waldinger R.J. Knowledge and Reasoning in Program Synthesis. Artif. Intell. v.6 n.2 1975.

20. Manna Z. Waldinger R.J. Toward Automatic Program Synthesis. Comm. of ACM v.14 n.2 1971 pp. 151-164.

21. Manna Z. Darlingtin J. Synthesis: Dreams Programs. IEEE Trans, on Software Eng. v.SE-5 n.4 1979.

22. Hardy S. Synthesis of LISP Functions from Example. Fourth1.t. Joint Conference on Artif. Int. Advance Paper. 1975.

23. Мянисалу М.А. Тыугу Э.Х. Язык описания задач УТОПИСТ. Управляющие системы и машины. И, Киев 1974.

24. Тыугу Э.Х. Система программирования с автоматическим синтезом алгоритмов. Труды всесоюзного симпозиума по методам реализации новых алгоритмических языков. ч.2, Новосибирск 1975.

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

26. Тыугу Э.Х. Алгоритмы структурного синтеза программ. Программирование. 4, I960.

27. Хопкрофт Дж. Алгоритм для минимизации конечного автомата. Кибернетический сб. Новая серия, вып.II, 1974, сс.177-185.

28. Этмане И.Э. Синтез программ по примерам. Всесоюзная конференция "Синтез, тестирование верификация и отладка программ" Рига 1981.

29. Этмане И.Э. Об одном методе индуктивного синтеза программ. Некоторые вопросы прикладной математики и програмного обеспечения ЭВМ. Моск. гос. ун-т. 1982 сс.45-47.

30. Barzdin J.M. On Inductive Synthesis of Programs. Lecture

31. Notes on Computer Sciense 122, 1981.

32. Bauer M. Programming by Examples. Artificial Intelligence v; 12, 1979 pp. 1-21.21• Bierman A.W. Approaches to Automatic Programming.

33. Advanc es in Computers. (Academic Press Hew York 1976).

34. Bierman A.W. On the Inference of Turihg Mashines from sample computations. Artifi Intel!, v.3 n.3 1972.

35. Zloff M.M. Query-by-example: A data base managementlangyage. IBM RES. Rep. (December 1976).

36. Zloff M.M. de Jong S.P. The system for business automation (SBA): Programming language. Comm. ACM. v.20 n.6 1977.

37. Семенова Т.В. Восстановление программы, не содержащей циклов, по дереву примеров. Вестн. Моск. Ун-та. Сер. 15 Вычисл. матем. и кибернет. 3, 1983 сс. 50-53.

38. Семенова Т.В. Об одном методе синтеза циклов по примерам их выполнения. Моск. ун-т. M.I983, Г^копись деп. в ВИНИТИ АН СССР №5442-83 Деп. 30с.

39. Семенова Т.В. Об одном методе синтеза программ по примерам. Двадцать четвертая конференция Литовского матем. общества тезисы докладов. Ин-т. метематики и кибернетики АН Лит.ССР 1983 сс.174-176.

40. Семенова Т.В. Построение программы, не содержащей циклов, по полной системе сокращенных примеров. Вестн. Моск. Ун-та. Сер. 15 Вычислительная математика и кибернетика 2, 1984 сс.58-61.