Альфа (система программирования)
Альфа — оптимизирующая система программирования, во многом определившая современную методологию оптимизирующей трансляции. Система «Альфа» была первой в мировой практике оптимизирующей системой программирования для языков, более сложных, чем Фортран. Создана под руководством советского ученого Андрея Ершова.
Разработка системы
Разработка системы «Альфа» началась с создания языка — это было характерно для традиций программирующих программ. Язык этот отталкивается от первоначальной версии Алгола 60 — так называемого Алгола 58. Группа, руководимая Ершовым, вела разработку параллельно с международной группой, разрабатывающей Алгол 60. Во многом работы указанных групп оказались совпадающими, и поэтому после опубликования описания Алгола 60 новый, созданный группой Ершова язык был сформулирован как расширение Алгола 60. Этот язык, носивший предварительные названия «Входной», «Сибирский», окончательно утвердился под названием Альфа-язык.
В Альфа-языке впервые введено понятие многомерных значений и определены операции над ними, в том числе операции конструирования. Все это вошло в стандартный багаж понятий современных языков, таких как ПЛ/1, Алгол 68, Ада. Впервые были введены и такие, естественные для современных языков концепции, как разнообразие циклов, задание начальных значений выражениями. Интересными, но, по существу, не повторенными свойствами языка были перечисления и верхние (временные) индексы. В своих метасредствах язык впервые выходил за пределы контекстно-свободных грамматик.
Система «Альфа» была первой в мировой практике оптимизирующей системой программирования для языков, более сложных, чем Фортран. Существовавший в то же время английский проект (Хоукинс и Хакстейбл) для Алгола 60, аналогичный «Альфе» по функциональным возможностям, так и не был доведен до конца. Это важно отметить потому, что сама возможность существования трансляторов для языков, более сложных, чем Фортран, с приемлемой эффективностью объектных программ в то время многими оспаривалась. Система «Альфа» стала конструктивным доказательством такой возможности, и это существенно, ибо снимало преграды на пути создания новых, семантически более богатых языков. Первоначальное ротапринтное издание по системе появилось в 1964 году.
Научное значение работы
Работы по системе «Альфа» внесли крупный вклад в методологию оптимизирующей трансляции. Была предложена и реализована многопроходная схема трансляции, ориентированная на оптимизацию, впервые введены в практику оптимизации программ оптимизирующие преобразования промежуточного представления программы, выделены и построены промежуточные представления программы, ориентированные на алгоритмы оптимизации.
Реализованные в системе «Альфа» методы экономии памяти, разработанные Ершовым, представляют собой теоретический и практический фундамент последующих работ по экономии памяти. Позже Ершовым было введено понятие информационного графа программы как модели, пригодной для определения такого преобразования, как глобальная экономия памяти, задача экономии памяти была сведена к известной задаче раскраски графа, вместе с Г. И. Кожухиным были заложены основы эвристического алгоритма близкой к оптимальной раскраски графа. Ершовым были даны основы полной теории экономии памяти. Эти труды определили не только работы по экономии памяти, но и другие исследования по оптимизации программ, в частности дали хороший пример построения практичных теоретических моделей для оптимизации программ.
Дальнейшие работы Ершова по оптимизирующей трансляции привели к появлению широко известной и используемой до сих пор системы «Альфа-6».
