Содержание к диссертации
Введение
Глава 1 Синтез программы, не содержащей циклов. 28
1. Построение программы по полной системе примеров 31
2. Построение программы по неполной систе ме примеров 43
3. Итерационный метод построения программы в интерактивном режиме 49
4. Построение программы по примерам с опущенными предикатами 55
Глава 2 Синтез циклов 67
1. Построение цикла по одному исходному примеру 68
2. Построение цикла по совокупности примеров 84
3. Построение программы вида вход, AI, А2,,АК, Ц, выход 90
4. Построение цикла по размеченным примерам 93
5. Синтез кратных циклов 96
Глава 3 Эксперименты по синтезу программ . 103
1. Экспериментальная система синтеза. 103
2. Результаты экспериментов 106
Заключение 108
Список литературы 110
Приложение 114
- Построение программы по неполной систе ме примеров
- Итерационный метод построения программы в интерактивном режиме
- Построение цикла по совокупности примеров
- Построение цикла по размеченным примерам
Построение программы по неполной систе ме примеров
Рассмотрим неполную систему примеров. В ней отсутствуют некоторые пути графа программы. Поэтому дерево, построенное по таким примерам также является неполным. Это означает, что оно содержит условные узлы, у которых определен только один потомок. Нашей задачей по-прежнему остается построение минимальной программы, выполняющей все заданные примеры. Для этого мы попытаемся сначала дополнить дерево до полного, а затем применить уже известный алгоритм.
Дополнить дерево - это значит для каждого неполного узла найти в этом дереве ветвь, которую можно было бы подставить вместо отсутствующего потомка. При этом каждый неполный узел необходимо дополнить так, чтобы в результате склеивания соответствующего полного дерева получился бы минимальный граф программы. Пусть / - общее количество нелистовых узлов дерева, /п -количество неполных узлов. Тогда число возможных вариантов дополнения дерева в общем случае не превосходит (Уі -і) Несмотря на то, что теоретическая верхняя оценка является высокой, используя описываемый ниже эвристический алгоритм поиска дополнений неполного дерева, практически удается существенно сократить перебор. Предположим, что для каждого предиката программы система примеров включает по крайней мере два примера, содержащих его след. Причем в одном из них данный предикат имеет значение "истина", а в другом - "ложь". Множество примеров, обладающих указанным свойством и содержащее минимильное число примеров, назовем г -покрывающим множеством. Тогда для любого неполного узла дерева есть условный узел, являющийся следом того же оператора программы, что и этот неполный узел, но у которого определен противоположный потомок. Назовем такой узел дополнением данного неполного узла. В этом случае каждый неполный узел дерева можно дополнить, т.е. взять в качестве недостающей ветви соответствующую ветвь его дополнения /дополняющую ветвь/. Таким образом, получится полное дерево. Если какой-либо неполный узел не имеет в дереве дополнения, что говорит о недостаточной информации в примерах, то он дополняется ветвью, состоящей из двух узлов: нет информации, выход. Очевидно, что для того, чтобы получить полностью определенную программу, т е. программу, не содержащую сообщений НЕТ ИНФОРМАЦИИ, достаточно покрывающего множества примеров. Остановимся подробнее на поиске дополнений неполных узлов. Поскольку неполный узел и его дополнение должны быть следами одного оператора программы, для них необходимо выполнение следующих условий: I/ неполный узел и его дополнение эквивалентны и не лежат на одном пути дерева, 2/ поддерево с корнем в неполном узле склеивается с поддеревом, корнем которого является дополнение, /1.2/ 3/ при склеивании дерева в граф неполный узел и его дополнение склеиваются. Легко убедиться в том, что никакие два узла дерева /неполный узел и его дополнение/, не удовлетворяющие условиям /1.2/, не могут быть следами одного оператора программы. Найдем для каждого неполного узла все узлы дерева, обладающие первыми двумя свойствами. Это можно сделать, не прибегая к склеиванию дерева.
Назовем найденные узлы потенциальными дополнениями /П-дополнениями/. Для каждого неполного узла может быть вообще говоря,.несколько П-дополнений. Выбрав конкретные П-до-полнения для всех неполных узлов, получим один из возможных вариантов дополнения дерева. В соответствии с выбранным вариантом дополнения строится полное дерево. Процесс дополнения неполных узлов состоит в копировании дополняющих ветвей, т.е. установлении соответствующих ссылок из неполных узлов к их дополнениям.
Итерационный метод построения программы в интерактивном режиме
При задании исходного множества примеров, вообще говоря, достаточно сложно подобрать примеры так, чтобы в результате синтеза получилась программа, удовлетворяющая тем или иным требованиям пользователя. Эту трудность можно преодолеть используя итерационный метод построения программы, работая в интерактивном режиме. Суть такого метода заключается в следующем. На первом шаге вводится некоторое количество примеров, по которым строится программа и выдается пользователю. Пользователь определенным способом /например на тестах/ начинает проверять, подходит ли ему данная программа. Если оказывается, что по каким-либо критериям она его не удовлетворяет, то на следующем шаге пользователь задает дополнительную совокупность примеров. Новый вариант программы строится по всем имеющимся примерам и снова выдается пользователю. Процесс продолжается до тех пор, пока очередной вариант программы не удовлетворит пользователя.
Таким образом, на каждом шаге итерации строится программа по совокупности примеров, введенных на всех предыдущих шагах. Причем, каждый раз дополнительные примеры задаются исходя из имеющегося к данному моменту варианта программы, а также из тех требований, которые предъявляются к её конечному варианту. Так, если построенная на некотором шаге программа, выполняющая все заданные примеры, не выполняет каких-то других примеров, известных пользователю, то достаточно на следующем шаге задать эти примеры.
Очевидно, что можно существенно облегчить работу пользователя в интерактивном режиме, если для тех или иных требований, предъявляемых к конечной программе, ввести четкие правила, которые определяют как задавать очередной набор примеров. Но в этом случае возникает вопрос об эффективности таких правил. Эффективность определяется тем, сколько примеров необходимо задать, следуя данным правилам, чтобы получить необходимую программу.
Предположим, что к конечному варианту программы предъявляется требование её полной определенности. Это означает, что пользователя удовлетворяет программа, в которой у каждого предиката определены обе ветви или, другими словами, в программе нет ни одного сообщения "нет информации".
Определим правила задания примеров для этого случая. 1/ На каждом шаге вводится один дополнительный пример. 2/ Пусть . , А,..., Р - совокупность путей построенного после итераций графа программы, ведущих от вершины к ближайшему недоопределенному предикату. Тогда К+{ пример должен совпадать с одним из этих путей от начала и до этого не-доопределенного предиката, а далее идти по той ветви, которая не определена. Утверждение 1.3 Если примеры задаются по указанным правилам, то полностью определенная программа будет построена не более, чем по М + { примеру, где ҐІ - число предикатов в искомой программе. Доказательство.
Заметим, что поскольку на каждом шаге добавляется только один пример, то количество примеров, по которым построена результирующая программа, равно количеству итераций в процессе синтеза. Докажем утверждение по индукции по количеству предикатов в искомой программе. Пусть в программе один предикат. Очевидно, что такая программа будет построена за два шага или по двум примерам. 2/ Пусть программа содержит два предиката. В этом случае может быть два способа их расположения - вложенный /Рис. 2а./ и последовательный /Рис. За./. Рассмотрим оба варианта. Предикаты вложены. На рисунке 2 приведен один вариант построения такой программы /пунктиром обозначены незаданные пути/. Последовательность примеров и соответствующих программ - аі, а2, аЗ. Результирующая программа строится по трем примерам. Очевидно, что и три других возможных варианта дадут такое же количество примеров.
Построение цикла по совокупности примеров
Предположим, что задано несколько примеров - . , Ez ,..., Вы . По ним необходимо построить программу вида ВХОД, Ц, ВЫХОД. Как и в случае одного примера, главным является разбиение исходных примеров на подпримеры так, чтобы каждый из них можно было бы принять за след тела цикла при соответствующем его проходе. Такое разбиение одного примера было названо циклическим. В данном случае есть несколько примеров одного и того же цикла,- поэтому их циклические разбиения не являются независимыми. Между ними должна быть согласованность, позволяющая объединить /склеить в дерево/ подпримеры всех циклических разбиений. Будем обрабатывать все исходные примеры параллельно, т.е. искать циклические разбиения каждого из них, учитывая структуру всех остальных примеров. Этот путь представляется более экономным, чем последовательное независимое рассмотрение каждого примера и их дальнейшее совмещение, т.к. при одновременном анализе всех примеров те их циклические разбиения, которые по каким-либо критериям противоречат друг другу, могут быть выявлены и отброшены, вообще говоря, раньше, что сократит перебор вариантов при поиске. Для того, чтобы осуществить параллельную обработку исходных примеров объединим их, склеив в дерево. Это можно сделать, поскольку все исходные примеры являются примерами одной и той же программы.
После такой склейки будем искать циклическое разбиение каждого примера, учитывая его положение в построенном дереве. Для этого найдем базовое разбиение дерева eL/( , іг ,...,CUh . Строится оно так же как и в одном примере путем нахождения всех узлов, параметрически эквивалентных второму узлу каждого примера или второму узлу дерева /первый узел примеров или корень дерева - след оператора ВХОД/. При этом, если в процессе поиска очередной проверенный узел является условным, то поиск продол- жается сначала в левом его поддереве, а затем в правом. Этот алгоритм достаточно очевиден, поэтому не будем его описывать , детально. Легко видеть, что базовому разбиению дерева соответствует совокупность базовых разбиений отдельных примеров. Фактически первое является объединением последних, исключая дубли, т.е. те подпримеры разных примеров, которые полностью склеиваются в данном дереве. Для подпримеров базового разбиения введем двойную нумерацию: J , где у - относительный номер, j - абсолютный. Абсо-лютный номер подпримера - это его номер в сквозной нумерации всего разбиения, поэтому .все абсолютные номера различны. Относительный номер - это номер данного подпримера в соответствующем базовом разбиении отдельного примера. С помощью относительной нумерации такие разбиения можно выделить из базового разбиения дерева. Другими словами, относительная нумерация дает характеристику повторяемости цикла в одном примере.
Очевидно, что несколько подпримеров могут иметь один и тот же относительный номер. Из алгоритма построения и нумерации базового разбиения де-рева следует, что подпримеры Є.1 " ,. к , имеющие один относи-тельный номер / Д/, = Ьк I , либо не имеют в дереве общих узлов, либо склеены в нем от первого узла и до некоторого условного узла /не последнего для них/, после которого идут по разным ветвям. Назовем подпримеры, обладающие последним свойством связанными. Рассмотрим пример базового разбиения дерева. Пусть даны три исходных примера: . ВХОД, АІ, В2, АІ, РІ-, ВЗ, АІ, ВЫХОД; ВХОД, АІ, В2, АІ, РІ+, АІ, Р2+, АІ, В4, ВЫХОД; ВХОД, AI, В2, AI, PI+, AI, P2-, B5, AI, ВЫХОД. Дерево, построенное по этим примерам изображено на рисунке 7. Базовое разбиение этого дерева будет следующим: Є - AI, В2; е\- AI, PI-, ВЗ; ?J - AI; Є - AI, PI+; - AI, Р2-, В5; Є% - AI; Є - AI, P2+; ЄІ - AI, B4: 7 о Обозначим C\f А/ А,-тый подпример базового разбиения /-того примера, соответствующего данному базовому разбиению дерева. Тогда базовые разбиения рассматриваемых примеров будут следующими: ПерВЫЙ Пример - 6-jHl, Є-lMly $ Ніч второй пример - //2/, &ІШі eg/2/, e\lZI% третий пример - е /ЗД, е%&/, Є?/3/, ag W- В каждом базовом разбиении отдельного примера выделим под-множество следующим образом: если Є А/, &„ /J/ такие, что L j , ifi-1-к и либо /С = /г , либо подпримеры связаны, то они или оба входят в подмножества разбиений примеров . HJ , или оба в них не входят /определение подмножества базового разбиения одного примера было дано в первом параграфе/.
Построение цикла по размеченным примерам
Возможна ситуация, когда описывая алгоритм на конкретных примерах, пользователь представляет себе как повторяется цикл, т.е. он знает, какой узел примера является началом очередного повторения или следом первого оператора тела цикла. В этом случае естественно предоставить пользователю возможность передать эту информацию синтезирующей системе. Это можно сделать, например, с помощью отметки нужных узлов. Будем называть примеры, в которых отмечены все следы первого оператора тела цикла, размеченными. Очевидно, что такие примеры несут в себе больше информации о цикле, который требуется построить, чем неразмеченные примеры. Поэтому следует ожидать, что возможности синтеза по размеченным примерам будут более широкими. Прежде всего ясно, что любой цикл описанного выше типа в данном случае будет свернут без перебора. Это следует из того, что известны все следы первого оператора тела цикла, которые однозначно определяют циклическое разбиение исходного примера или дерева примеров. Кроме того возможен синтез циклов, в теле которых есть операторы, содержащие индексные выражения вида MX + В » гДе А и В - некоторые целые числа. Отличие алгоритма синтеза такого цикла от предыдущего заключается в формировании индексного выражения в результирующем узле при склейке под-примеров циклического разбиения в дерево и последующей склейке дерева в граф тела цикла. Опишем подробнее этот алгоритм. Выделим в исходном примере все следы первого оператора тела цикла - ИJ у И2, » Мп Это можно сделать, т.к. они помечены. Такая последовательность узлов разбивает пример на подпримеры е , Єї ,..., 6п. , причем это разбиение будет циклическим. Далее все подпримеры склеиваются в дерево так, как было описано в предыдущих параграфах.
При этом, склеивая параметрически эквивалентные узлы с ненулевым шагом, необходимо ввести индексные выражения в результирующий узел, т.е. определить константы А и и ВЦ в индексном выражении в позиции lj . Зная вид индексного выражения и номера подпримеров, которым принадлежат склеиваемые параметрически эквивалентные узлы, можно решить эту задачу. Пусть узлы //f , И; склеиваемые в дереве и принадлежа-щие подпримерам , Єт соответственно, являются параметрически эквивалентными относительно позиций lj, її ,..., Д% . .Значение параметров в этих позициях в узле И - Р- , Пусть X0=i , тогда каждому подпримеру . соответствует значение переменной цикла J+fc- f = . . Рассмотрим некоторую позицию As . В ней в результирующем узле должно стоять индексное выражение вида А Х- + 8;, причем Al K + Bl = Pi , A L to+ BL=P; . ИЗ этих уравнений можно определить Ais и Bls : Если множество склеиваемых узлов содержит больше двух узлов, то константы индексных выражений определяются по любой паре. Найденные константы будут удовлетворять всем остальным узлам, т.к. склеиваемые подпримеры - следы одного тела цикла.
Покажем, что возможность введения индексных выражений вида А Т± В снимает ограничения, которые заключаются в том, что 20 = і , шаг цикла равен J . Лемма, Для любых констант индексного выражения А и В , начального значения переменной цикла Л0 , шага цикла К су- А I Г) I ществует А и о такие, что для любого U выполнено равенство A ti + д1 =AlI0+b{i ))+B / /. Доказательство. Пусть t =/ , тогда из равенства А +3 = А 1о + В следует, что В1 - Ах2о А +В Возьмем произвольное значение U { и подставим в равенство /I найденное значение для В , получим A L +10 А -А +В =/4( +h(i-"f)) + Б , из этого равенства найдем А = А 1г . Значения /4;и В1 найдены. Из данной леммы следует, что любой цикл указанного выше типа, но имеющий шаг отличный от единицы и J , можно преобразовать с помощью замены констант в индексных выражениях к циклу с шагом и начальным значением переменной цикла равными единице. Поэтому указанные ограничения практически не являются существенными. В третьем параграфе первой главы были определены правила задания примеров в интерактивном режиме при итерационном синтезе программы без циклов. Доказано, что если следовать этим правилам, то полностью определенная программа будет построена не более, чем по М + / примеру, где М - количество предикатов в искомой программе. Рассмотрим правила задания размеченных примеров, цель которых также получить полностью определенную программу. Поскольку наличие последовательности безусловных операторов перед циклом не влияет на выполнение требований, предъявленных к программе, ограничимся рассмотрением программы, состоящей только из цикла. I/ На каждом шаге вводится один пример. 2/ Пусть Р ,А ,..., Рк - совокупность путей построенного после п. итераций графа тела цикла, ведущих от вершины к ближайшему недоопределенному предикату. Тогда К+1 пример должен содержать по крайней мере один след тела цикла совпадающий с одним из путей Р; от начала и до данного недоопределенного предиката, а далее идущий по той ветви, которая не определена. Утверждение 2.4 Если размеченные примеры задаются по указанным правилам, то полностью определенный цикл будет построен не более, чем по М + і примеру, где М - количество предикатов в искомой программе. Доказательство. Заметим, что т.к. исходные примеры размечены, то дерево тела цикла будет построено из подпримеров, которые точно являются следами тела цикла. Возьмем произвольное К и построим тело цикла как программу без циклов, задавая К его примеров по правилам, приведенным в первой главе /обозначим это множество примеров tM j / . Теперь зададим К примеров по рассматриваемым правилам. Сравнив два набора правил, легко убедиться в том, что совокупность подпримеров, соответствующая разбиению исходных примеров цикла на отрезки, будет содержать все пути /следы/ из множества JULR. Таким образом, если в первом случае тело цикла - полностью определенная программа, то и во втором случае тело цикла будет полностью определено. Утверждение доказано.
