Реферат: Андрей Петрович Ершов (1931-1988)
Альфа-транслятор стал первым в мире транслятором с Алгола с большими оптимизирующими возможностями. Похожий английский проект Хоукинса и Хакстебла, который разрабатывался в это время, так и не был до конца завершен из-за сложности задачи. Конечно, успеху способствовало не только механическое соединение многих оптимизаций, но и существенное развитие существовавшей методологии оптимизации программ. Была выдвинута идея внутреннего языка, к программе на котором и применяются оптимизации, которая, хотя и не совсем в чистом виде, была реализована. Был реализован практически глобальный анализ контекста, хотя и разрозненно для различных оптимизаций, учет которого существенно увеличил мощность оптимизаций - зародыш современного потокового анализа. Стремление практически всегда получать эффективный код привело к отказу от некоторых средств Алгола, важнейшим из которых была рекурсивность процедур.
Альфа-транслятор активно использовался в большом числе организаций страны. Хотя его интерфейсы с пользователем и простота эксплуатации желали много лучшего, но высокая эффективность получаемого кода обеспечила хороший интерес пользователей к этой системе. Поэтому когда на смену М-20 пришла существенно более высокопроизводительная машина БЭСМ-6, организации, связанные с большими задачами, стимулировали создание версии Альфа-транслятора для БЭСМ-6. Самым быстрым решением была простая переделка Альфа-транслятора, при которой та его часть, которая отвечала за генерацию кода, была заменена генератором кода для БЭСМ-6. Возник транслятор Алгибр (“Альфа гибридный”), который был одним из первых отечественных кросс-трансляторов. Такое решение имело ряд недостатков, но зато оно было реализовано быстро, и транслятор Алгибр стал первым транслятором для новой машины БЭСМ-6. Решение существенно облегчалось тем, что в Альфе-трансляторе уже существовал внутренний язык, хотя и не до конца единый для всех оптимизирующих преобразований.
Основным затруднением при Алгибр-трансляции была передача оттранслированного кода с М-20 на БЭСМ-6. В ВЦ СО АН СССР был даже разработан специальный канал передачи информации между инструментальной и объектной ЭВМ, однако это не могло быть серийным решением при массовой трансляции. Возникла необходимость "родного" транслятора для БЭСМ-6.
У разработчиков Альфа-транслятора возникала и внутренняя потребность модифицировать и улучшить как схему трансляции, так и пользовательские свойства транслятора, в первую очередь, его интерфейс с пользователем. Альфа-транслятор, несмотря на его достаточно широкую используемость, носил черты эксперимента и поиска - хотя идейные решения были найдены верно, но реализационные решения были характерны скорее для экспериментального, чем производственного транслятора (большое число просмотров программы - 24, некоторое дублирование анализа контекста, не всегда оправданное усложнение оптимизирующих преобразований). Не нужно забывать, что этот транслятор был первым оптимизирующим транслятором с Алгола. Дополнительный опыт - транслятор Алгибр, незавершенный проект Альфа-транслятора для ЭВМ Урал-14 (проект ТАУ) - давал основу для новых решений.
Новый транслятор - транслятор Альфа-6 - был улучшенной версией оптимизирующего транслятора с Алгола. Ряд предыдущих решений был приведен к более чистому и эффективному виду. Более четко был выделен внутренний язык и этап потокового анализа программ на внутреннем языке. Общая схема трансляции уже могла рассматриваться как типовая схема оптимизирующей трансляции (для одноязыкового транслятора), она насчитывала всего 10 просмотров. Лучше была решена проблема взаимного влияния различных оптимизирующих преобразований. Идентификация и визуализация ошибок пользователя была более совершенной, что облегчало эксплуатацию. В результате система Альфа-6 стала достаточно широко используемой системой у пользователей БЭСМ-6.
Лексикон
В некотором смысле из анализа общих понятий языков программирования и осознания их определенной ограниченности выросла предложенная Ершовым в статье «Математическое обеспечение четвертого поколения» («Кибернетика», 1973, №1) фундаментальная и многообещающая идея лексикона программирования как общей среды для разработки и обоснования программ. Он определяет лексикон как "лингвистическую систему с фразовой структурой, содержащую в себе формальную нотацию для выражения всех общезначимых конструкций, употребляемых при формулировании условий задач, при синтезе и преобразовании программ". Лексикон, говорит Ершов, "выражает не только и не столько программы, сколько их свойства и наши суждения о них. Язык программирования кодирует объекты предметной области задачи, а наше знание об этих объектах остается за пределами программного текста. Лексикон же является средством описания объектов предметных областей и содержит нотацию для построения баз знания о предметных областях. Программа, выраженная средствами лексикона, в определенном смысле содержит в своем тексте описание своей семантики в виде совокупности нетривиальных фактов о вычисляемой ею функции - в отличие от "чистых" программ, которые не говорят ничего о своих функциональных свойствах. Лексикон, в отличие от конкретного языка программирования, является открытой системой. Для него в целом не ставится задача трансляции любого его текста в машинную программу, хотя любая машинная программа в случае необходимости может быть выражена в лексиконе. Аналогично естественному языку лексикон обладает способностью описания одной своей части средствами другой своей же части. Не надо думать, что лексикон - это все и навсегда. Это тщательно отобранная, но развивающаяся система удачных обозначений. Степень его успеха определяется степенью общезначимости и общепонятности его нотации".
Смешанное вычисление и
трансформационная машина
Смешанное вычисление представляет собой некоторый универсальный процесс, определяемый над парами (программа, данные) и приводящий в общем случае к получению остаточной программы и частичных результатов. Математическим аналогом смешанного вычисления является функционал, который для определенного класса функций с несколькими аргументами строит (при задании некоторых аргументов) функции с меньшим числом аргументов. Процесс смешанного вычисления может быть, в свою очередь, задан в виде программы (смешанного вычислителя), что позволяет ставить вопрос о самоприменимости смешанных вычислений, а сам смешанный вычислитель уподобить s-n-m - функции Клини.
Понятие смешанного вычисления (и смешанного вычислителя) в применении к процессорам обработки программ, для которых программы и их атрибуты есть данные, позволяет с общей точки зрения исследовать и определить различные виды обработки программ: от трансляции и интерпретации до анализа программ, их преобразования и генерации самих языковых процессоров. В ряде работ по смешанным вычислениям и трансформационному подходу Ершов методологически исследует эту концептуальную сторону смешанных вычислений.
Именно определение принципа смешанных вычислений как общей основы большого числа процессов работы над программами отличает работу Ершова от ряда предыдущих работ и догадок Ломбарди, Футамуры, Турчина и др. Это и стало причиной того, что работы Ершова легли в основу нового и активно развивающегося направления в программировании, связанного с теоретическими исследованиями и практическими приложениями смешанных вычислений. Применение смешанных вычислений оказалось весьма полезным методологически для понимания и трактовки различных понятий и сущностей программирования.
Понятие смешанных вычислений, введенное Ершовым как общая модель для различных видов обработки программ, с необходимостью потребовало широкого круга исследований, как по свойствам самой модели, так и по ее трактовке в различных областях возможного применения. Было введено понятие корректности смешанных вычислений и определены модели смешанных вычислений и получения остаточной программы, для которых можно было доказывать корректность. Одной из таких моделей, на которых фокусировалось внимание, стала трансформационная модель, для которой смешанное вычисление задавалось набором базовых трансформаций. Сама модель смешанных вычислений и их корректность рассматривались как для императивных языков, так и для рекурсивных программ. Был получен ряд важных результатов по определению механизма задержки (замораживания) вычислений и данных, по описанию процесса смешанных вычислений для различных языков представления программ, по формулированию набора базовых трансформаций, по надежности (незацикливанию) процесса смешанных вычислений и пр.
Для реальных приложений смешанных вычислений помимо, разумеется, необходимых свойств корректности и надежности важными оказываются их гибкость и глубина. И здесь Ершову и его ученикам удалось существенно продвинуться в исследованиях. Гибкость смешанных вычислений может быть заметно увеличена, если смешанный вычислитель будет при получении остаточной программы учитывать не только свойства данных иметь конкретное значение, но и более тонкие свойства, определяемые известными соотношениями между данными (предикаты над данными). В этом случае смешанный вычислитель оперирует с некоторой определенной на данных обстановкой. Глубина смешанных вычислений определяется схемой смешанных вычислений. Наряду со строгой схемой смешанных вычислений, введенной вначале, была определена поливариантная схема, связанная с продвижением смешанных вычислений в альтернативы, даже если выбор альтернатив не может быть определен при таком вычислении.
Совместно с Островским Ершов исследовал применение смешанных вычислений в такой традиционно важной области, как трансляция, а именно построение трансляторов для заданного описания входного языка. Существенно отметить, что здесь были получены не только результаты, демонстрирующие практическую применимость принципа смешанных вычислений (удавалось строить трансляторы существенно более эффективные, чем это достигается при обычном автоматическом построении), но и ряд фактов и наблюдений, важных для сопоставления методов трансляции и понимания сущности трансляции и показывающих методологическую важность принципа смешанных вычислений.
Таким образом, в области смешанных вычислений Ершову принадлежит не только определение основополагающих понятий и моделей, но и определяющий вклад в теорию и методологию этой области. Он по праву считается основателем и лидером этого направления, активно развиваемого сейчас в разных коллективах и странах.
Отталкиваясь от трансформационной модели смешанных вычислений и от своих работ в области трансляции и оптимизации программ, Ершов определяет концепцию трансформационной машины. Трансформационная машина есть абстрактное вычислительное устройство, выполняющее программы в некотором "сверхязыке", действиями которого являются трансформации пар (программа, данные). Действия эти поддерживают сохранение некоторого инварианта, что обеспечивает корректность трансформаций. Концепция трансформационной машины представляется весьма многообещающей - и как теоретическая модель для описания и обоснования процессов обработки программ, и как методологическая основа построения различных инструментальных процессов.
Концепция трансформационной машины является тем важным вкладом в трансформационный подход к построению программ, энтузиастом и пропагандистом которого был А.П.Ершов, и различные аспекты которого исследуются в ряде его работ 80-х гг. Трансформационный подход развивается сейчас в ряде коллективов у нас и за рубежом и представляется весьма перспективным, так как он дает возможность получать программы с хорошими показателями таких качеств, как надежность и эффективность, а также повышает степень переиспользования программного обеспечения. Работы Ершова по трансформационному подходу дают естественную точку роста для последующих исследований.
Следует заметить, что наряду с работами по языкам и методам трансляции работы по смешанным вычислениям и трансформационному подходу были источником уже упоминавшейся идеи Ершова о лексиконе программирования.
Заключают работы Ершова по теории программирования его публикации, посвященные понятию вычислимости. Сам он определяет эти работы как попытку синтеза взглядов на вычислимость, сложившихся как в математической логике, так и в теоретическом программировании. Так как понятие вычислимости является одним из главных как в той, так и в другой области и имеет фундаментальное значение для других программистских понятий, очевидно, что определение понятия вычислимости, абстрагированного от несущественных синтаксических или модельных понятий и вместе с тем вбирающего необходимые для теории и многочисленной практики сущности, является одной из главных задач, определяющих дальнейшее взаимовлияние математики и программирования. В фундаментальной работе «Проблемы программирования: Всесоюзная конференция в Новосибирске» (Вестник АН СССР, 1970, №6) проводится глубокий анализ большого числа определений вычислимости, сложившихся в указанных областях, их сопоставление и оценка вклада в общую теорию. На основании данного анализа Ершов нащупывает идею определения вычислимости: свести определение вычислимой функции к понятию детерминанта, т.е. того, что является инвариантным к различным способам задания вычислений. По-видимому, эти работы Ершова будут иметь такое же стимулирующее значение для исследований в данной области, как и его работы начала 70-х гг. для теории схем программ.
Проект АИСТ
Одной из важных заслуг Ершова перед отечественным и мировым программированием является то, что он умел оценить текущее состояние науки и практики и наметить те реальные точки роста и перспективы исследований, которые будут определять развитие программирования. Так, во второй половине 60-х гг. он одним из первых в стране осознал те новые возможности общения с ЭВМ, которые создают системы разделения времени. В 1966 г. он организует работы по автоматическим информационным станциям (проект АИСТ). Проект АИСТ, создателем и руководителем которого был А.П.Ершов, объединял широкий круг исследований по архитектуре вычислительных комплексов, их программному обеспечению и моделированию вычислительных систем. В рамках этого проекта была создана первая в стране развитая система разделения времени АИСТ-0, проект которой был предметом доклада на Конгрессе AFIPS 1967 г. («Входной язык системы автоматического программирования» предварительное сообщение — М.: ВЦ АН СССР, 1961), а итоговый доклад был сделан на 2-й Всесоюзной конференции по программированию в 1970 г. («Программирующая программа для машины» Третье Всесоюзное совещание по вычислительной математике и применению средств вычислительной техники, 1961). Реализованная на многомашинном комплексе из отечественных ЭВМ, эта система была во многом пионерской и внесла большой вклад в развитие отечественных работ по архитектуре ЭВМ и операционным системам, которые, к сожалению, были в дальнейшем заторможены ориентацией на копирование зарубежных разработок. Ряд таких свойств системы, как разделение в процессорах комплекса управления и обработки, иерархичность строения программного обеспечения, выделение ядра операционной системы, естественное сочетание различных режимов общения и обработки, обеспечили хорошую эффективность и гибкость системы.
Осмысливая опыт проекта АИСТ и других подобных работ у нас в стране и за рубежом в своем докладе на Конгрессе ИФИП-68, Ершов выдвигает несколько насущных тезисов: о специализации процессов в многопроцессорном комплексе для разделения времени, об универсальных и специализированных системах разделения времени и областях их применимости, о различии требований профессионалов и непрофессионалов в программировании к общению с системами разделения времени и о том аспекте систем, который впоследствии будет назван дружественностью к пользователю.
Опыт руководства такими большими проектами, как АЛЬФА и АИСТ, и работы в этих проектах дали Ершову осознание общих проблем программирования и создания программного обеспечения. В 1973 г. - появляется оказавшая большое влияние на развитие отечественных работ статья. В этой работе проводился глубокий и развернутый анализ как внешних свойств машин четвертого поколения, так и различных видов программных систем: операционных систем, систем программирования и их входных языков, специализированных систем обработки информации, в том числе пакетов прикладных программ (в работе дается классификация ППП, сохраняющая свою ценность и в наше время). Выделен ряд характерных систем обработки информации и определены их внешние и внутренние свойства. Очерчена общая модель операционной системы - так называемая базовая операционная система с концентрическим строением. Отмеченная в работе общность в реализации языков программирования, создании процессоров диалоговых языков и систем отображения хотя и не вылилась, как предполагал автор, в создание универсальных систем, но стимулировала работы по нахождению общей методологии создания таких систем (впрочем, некоторая ограниченная в своей универсальности многоязыковая транслирующая система на данной общности была построена - это система БЕТА, о которой говорилось выше).
