УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

Преобразования программ, сохраняющие поведение

© 2007 А.П.Лукьянова

Санкт-Петербургский государственный университет информационных технологий, механики и оптики

Полный текст работы

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

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

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

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

Приведено сравнение метода и результатов работы с результатами и методами аналогичных исследований.