Автоматический синтез структурированных программ по примерам их выполнения

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

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

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

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

в интерактивном режиме

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

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

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

примеру

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

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

... ,АК, Ц, ВЫХОД
§4. Построение цикла по размеченным примерам
§5. Синтез кратных циклов
Глава III Эксперименты по синтезу программ. . . . 103 -§1. Экспериментальная система синтеза
§2. Результаты экспериментов
Заключение
Список литературы
Приложение

Вместе с внедрением вычислительных машин в человеческую практику возникла проблема общения человека с ЭВМ. Одним из аспектов данной проблемы является задача рационализации и упрощения процесса составления программы /программирования/ для вычислительной машины. Появление простейших ассемблеров, а затем более развитых языков программирования отражает процесс решения этой задачи.
В настоящее время актуальность её решения еще более возросла, что обусловлено рядом причин. Это и повышение быстродействия ЭВМ, требующее снижения трудовых затрат на составление программы, и значительное расширение области применения ЭВМ, которое привело к росту числа пользователей и изменению их качественного состава от профессиональных программистов до врачей, журналистов и т.п.
Одним из направлений решения стоящей задачи является создание систем автоматического программирования /20/. К ним, в частности, относятся системы автоматического синтеза программ.
В общем случае задача синтеза состоит в следующем: дано описание /в той или иной форме/ действия, которое должно выполниться программой, по этому описанию требуется построить удовлетворяющую ему программу.
Можно выделить три подхода к синтезу: дедуктивный, индуктивный, трансформационный.
Дедуктивный синтез /8-15, 33, 34/ исходит из того, что суть программы -можно выразить отношением, связывающим входные данные с результатом. В общем виде задача дедуктивного синтеза формулируется следующим образом: дан входной предикат и выходной
предикат ]|(Х,У) , построить программу, вычисляющую функцию У= ф(х) так, что если X - входной вектор, удовлетворяющий Р^(х),

то Ф(Х) определена и выполнено условие Ф(Х)).
Предикаты Р^(Х) и Р^Х.У} называются соответственно входной и выходной спецификациями. Задача решается путем построения конструктивного доказательства теоремы УХ [ Р^(х) =^>(3 У)Р^(Х,У)], Найденное доказательство затем переводится в программу. В основе такого решения лежит тот факт, что в некоторых логиках истинность формулы УХ [ Р^(Х)^>(ЗУ) Р2(Х,У)] гарантирует реализуемость по заданному X соответствующего У.
Одни из первых содержательных результатов в области дедуктивного синтеза обсуждаются в статье /34/, их развитие осуществляется в работах /II, 33/.
Бесспорным достоинством данного подхода является то, что по правильным спецификациям строится правильная программа. Однако следует отметить, что для осуществления дедуктивного синтеза необходима достаточно мощная система автоматического доказательства теорем. Кроме того, возникают трудности на этапе задания спецификаций, поскольку, с одной стороны, язык спецификаций должен быть достаточно удобным для пользователя, близок к предметной области программы, с другой стороны, исходная теорема должна формулироваться на языке той теории, в которой строится вывод. Все это затрудняет в настоящее время широкое использование описанных средств для практического синтеза. Но есть области, в которых дедуктивный синтез уже нашел практическое применение. Такой областью являются, в частности, пакеты прикладных программ. Пример такого применения можно найти в системах ПРИЗ и СПОРА /8-10, 12-15/.
Так, в системе ПРИЗ задача формулируется в виде тройки /М, В,
Р/, где М -условие задачи, В - множество входных переменных, Р -множество выходных переменных. Для получения практического результата ограничивается класс решаемых задач, выбирается специальное

способом /например на тестах/ начинает проверять, подходит ли ему данная программа. Если оказывается, что по каким-либо критериям она его не удовлетворяет, то на следующем шаге пользователь задает дополнительную совокупность примеров. Новый вариант программы строится по всем имеющимся примерам и снова выдается пользователю. Процесс продолжается до тех пор, пока очередной вариант программы не удовлетворит пользователя.
Таким образом, на каждом шаге итерации строится программа по совокупности примеров, введенных на всех предыдущих шагах. Причем, каждый раз дополнительные примеры задаются исходя из имеющегося к данному моменту варианта программы, а также из тех требований, которые предъявляются к её конечному варианту. Так, если построенная на некотором шаге программа, выполняющая все заданные примеры, не выполняет каких-то других примеров, известных пользователю, то достаточно на следующем шаге задать эти примеры.
Очевидно, что можно существенно облегчить работу пользователя в интерактивном режиме, если для тех или иных требований, предъявляемых к конечной программе, ввести четкие правила, которые определяют как задавать очередной набор примеров. Но в этом случае возникает вопрос об эффективности таких правил. Эффективность определяется тем, сколько примеров необходимо задать, следуя данным правилам, чтобы получить необходимую программу.
Предположим, что к конечному варианту программы предъявляется требование её полной определенности. Это означает, что
пользователя удовлетворяет программа, в которой у каждого предиката определены обе ветви или, другими словами, в программе
нет ни одного сообщения "НЕТ ИНФОРМАЦИИ".