Предисловие

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

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

Книга состоит из 11 глав, образующих три части.

Задача части I — развитие математического аппарата, ориентированного на исследование оптимизации программ. Эта часть содержит описание основных понятий и свойств операторной модели программы (крупноблочной схемы), в рамках которой формулируются и обосновываются оптимизирующие преобразования. Здесь же рассматриваются абстрактная модель вычислительной машины (РАМ) и методика исследования алгоритмов оптимизации, сочетающая высокий уровень их представления (так называемый ВУ-язык) с простотой получения оценок сложности их выполнения на РАМ.

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

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

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

Монография основывается на работах автора, большинство из которых выполнено в рамках проектов Вычислительного центра СО АН СССР по созданию универсальной многоязыковой системы программирования БЕТА и систем конструирования программ СКАТ. В книгу вошел переработанный и исправленный материал спецкурса по оптимизации программ, читаемого автором в течение ряда лет для студентов старших курсов Новосибирского государственного университета им. Ленинского комсомола.

Автор глубоко благодарен своим коллегам и друзьям из ВЦ СО АН СССР за активное сотрудничество в работе над проектами БЕТА и СКАТ и особенно И.В. Поттосину, С.Б. Покровскому, В.К. Сабельфельду и Г.Г. Степанову. Нельзя не назвать здесь и тех, кто своими работами, советами и поддержкой способствовал появлению этой книги. Прежде всего — это А.П. Ершов, С.С. Лавров, А.А. Летичевский, Э.З. Любимский и В.Е. Котов. Всем им, а также П.В. Карповской и Г.И. Нариньяни, оказавшим большую помощь в технической подготовке рукописи, автор выражает искреннюю признательность.