«СТАНОВЛЕНИЕ НОВОСИБИРСКОЙ ШКОЛЫ ПРОГРАММИРОВАНИЯ (мозаика воспоминаний) Под редакцией проф. Игоря Васильевича Поттосина Новосибирск 2001 УДК 007.621.391 ББК 32.81 Становление новосибирской школы программирования ...»

Российская академия наук

Сибирское отделение

Институт систем информатики

им. А. П. Ершова

СТАНОВЛЕНИЕ НОВОСИБИРСКОЙ ШКОЛЫ

ПРОГРАММИРОВАНИЯ

(мозаика воспоминаний)

Под редакцией

проф. Игоря Васильевича Поттосина

Новосибирск 2001

УДК 007.621.391

ББК 32.81

Становление новосибирской школы программирования (мозаика воспоминаний). — Новосибирск: Ин-т систем информатики им. А. П. Ершова СО РАН, 2001. — 194 с.

Сборник содержит материалы, представляющие становление и развитие новосибирской школы программирования.

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

Подготовка и издание сборника поддержаны грантом РГНФ № 00-03-00277а.

c Институт систем информатики им. А. П. Ершова СО РАН, 21.02.33–15.12. Пока готовился этот сборник пришла печальная весть о кончине Игоря Васильевича Поттосина. Он был одним из инициаторов его издания, главным редактором и автором нескольких статей.

Игорь Васильевич Поттосин — профессор, доктор физико-математических наук, один из старейших сотрудников Сибирского отделения Российской академии наук, заведующий кафедрой программирования Новосибирского государственного университета, главный научный сотрудник Института систем информатики им. А.П. Ершова СО РАН, Заслуженный деятель науки Российской Федерации, лауреат премии Совета Министров СССР — скончался 15 декабря 2001 г. после тяжелой непродолжительной болезни.

И. В. Поттосин родился 21 февраля 1933 г. в Куйбышевской области, в 1955 г. окончил спецотделение физического факультета Томского государственного университета по специальности "баллистика". В период с 1955 по 1958 г. он работал в одной из организаций Министерства обороны. В 1958 г. И. В. Поттосин стал сотрудником Сибирского отделения АН СССР, где прошел путь от младшего научного сотрудника Института математики до директора Института систем информатики им. А.П.

Ершова СО РАН. Последние годы И.В. Поттосин руководил лабораторией системного программирования Института, возглавлял кафедру программирования НГУ.

И.В. Поттосин был одним из ведущих российских ученых в области информатики. Он внес значительный вклад в становление и развитие этого направления отечественной науки. За время работы в Сибирском отделении им опубликовано более 120 печатных трудов, в том числе монографии.

Основные научные интересы И.В. Поттосина были сосредоточенны в области инструментальной системы поддержки информационных технологий и разработки инструментальных программных средств и их прототипов. Он внес определяющий вклад в разработку методики оптимизирующей трансляции, создал основные принципы реализации и типовые схемы оптимизирующих трансляторов и процессоров, разработал эффективные алгоритмы основных оптимизаций. Эти научные результаты нашли свое воплощение в таких системах, как оптимизирующий транслятор АЛЬФА, система программирования АЛЬФА-6, многоязыковая транслирующая система БЕТА и др.

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

И.В. Поттосин активно участвовал в подготовке специалистов высшей квалификации. Среди его учеников один доктор наук, 11 кандидатов наук, сотни выпускников Новосибирского университета.

Научные и производственные заслуги И.В. Поттосина отмечены премией Совета министров СССР, орденом "Знак Почета", тремя медалями, званием "Заслуженный деятель науки РФ".

Коллектив Института систем информатики им. А.П. Ершова СО РАН искренне и глубоко скорбит о безвременной кончине Игоря Васильевича Поттосина и выражает соболезнования его родным и близким.

ПРЕДИСЛОВИЕ

Предлагаемый читателям сборник содержит материалы по истории новосибирской школы программирования.

Одна из ведущих советских школ в этой области, она ведет свою историю с 1958 года, когда в Институте математики СО АН СССР создается отдел программирования, руководителем которого был с момента основания отдела и до своей кончины Андрей Петрович Ершов — и все публикуемые материалы так или иначе связаны с его именем.

Мы стремились включить в сборник разноплановые материалы — анализ выполненных проектов, историю их создания и использования в российском, советском и международном контекстах, информацию о деятельности отдела, воспоминания о людях и событиях, в которых отразился дух тех 50-х, 60-х, 70-х годов. Часто все это переплетается в одном и том же материале, что нами приветствовалось. И по форме публикации различны — здесь и аналитический обзор, и простой перечень событий и мероприятий, и воспоминания об отдельных событиях, и диалог собеседников: мы не стремились свести все к единому стилю, полагаясь на вкус и желания авторов. Для нас важно, что все публикации — это не взгляд со стороны, они принадлежат людям, принимавшим активное участие в той работе, о которой идет речь. В их основе лежат живые воспоминания, поэтому возможна небольшая аберрация зрения, как это обычно бывает, когда глядишь на давние события.

Первые три публикации дают некоторую общую картину и посвящены основателю новосибирской школы Андрею Петровичу Ершову и работам этой школы периода ее становления. Они в известном смысле являются повторными: первая из них — расширенный вариант доклада, представленного на 4-й международной конференции «Перспективы систем информатики» (Новосибирск, 2001 г.) и опубликованного на английском языке в ее трудах (Lecture Notes in Computer Science, Vol.

2244, 2001), две следующие были опубликованы в Трудах Международного симпозиума «Computers in Europe. Past, Present and Future» (Киев, 1998 г.). Учитывая связь этих работ с тематикой сборника и то, что они опубликованы в изданиях, малодоступных широкому кругу читателей, мы сочли возможным открыть ими наш сборник.

Далее следуют две заметки, посвященные университетским годам А. П. Ершова (так сказать, “внутриутробному” периоду развития новосибирской школы) и истории одной из первых прикладных работ отдела программирования.

Последующие шесть работ освещают историю первых проектов отдела в области языков программирования и трансляторов в 60-х годах.

Диалог А. А. Берса и А. Ф. Рара рассказывает об участии новосибирцев в международном проекте создания языка Алгол-68. Публикация С. Б. Покровского — это лишь малая часть того, что можно рассказать о столь многолетнем проекте, как многоязыковая транслирующая система БЕТА. Работы Л. В. Городней и Д. Я. Левина освещают новосибирский вклад в реализацию языков, предложенных нашими американскими коллегами и друзьями. А. В. Замулин рассказывает о том, с чего начинались новосибирские работы по информационным системам и базам данных.

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

Дополнением к данному сборнику служит отдельно публикуемый препринт В. А. Евстигнеева, в котором даются итоги работ новосибирской школы к концу 70-х.

Сборник заведомо не полон — история ряда других заметных проектов новосибирской школы еще не описана: это предмет следующих публикаций.

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

Написание, подготовка и издание сборника осуществлялись при поддержке Российского гуманитарного научного фонда, грант № 00-03а.

А. П. ЕРШОВ — ПИОНЕР И ЛИДЕР ОТЕЧЕСТВЕННОГО

ПРОГРАММИРОВАНИЯ

19 апреля 2001 года исполнилось 70 лет со дня рождения Андрея Петровича Ершова. Он был одним из пионеров отечественного программирования и стал его лидером — ученым, влияние которого на становление и развитие отечественного программирования было значительным и определяющим. Этот мемориальный доклад я хотел бы посвятить не столько обзору его научных результатов — я попытался это сделать в другой статье, которая опубликована в сборнике избранных трудов А. П. Ершова — сколько рассказу о нем, как об одном из пионеров программирования и многолетнем лидере в этой области наук. Это будет рассказ о том, кем был Андрей Петрович в отечественном программировании, и чем отечественное программирование ему обязано.

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

Начальной точкой возникновения отечественного программирования следует считать 1950 год, когда появился макет первой советской ЭВМ МЭСМ (и первой ЭВМ в континентальной Европе). Ершов связал свою жизнь с программированием двумя годами позже — когда он стал специализироваться на кафедре вычислительной математики мехмата Московского университета. Он принадлежал к первому в СССР выпуску дипломированных специалистов по программированию — так же, как и его однокашники Э. З. Любимский, В. С. Штаркман, И. Б. Задыхайло, В. В. Луцикович, О. С. Кулагина, Н. Н. Рикко и другие.

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

Ершов и его однокашники выглядели среди них элитой — только у них было базовое образование, специализирующее в новой области. Ершов, впрочем, мечтал быть физиком, и только стечение обстоятельств вынудило его прийти учиться на мехмат. Следует заметить, что по словам Е. А. Жоголева, приложившего руку к ориентации Ершова на программирование, именно интерес Ершова к физическому устройству ЭВМ и привел его на кафедру вычислительной математики — единственную кафедру на мехмате, где такое устройство изучалось.

Специфика возникавшей научной дисциплины была таковой, что при своем зарождении она выступала под другой — не чужой, но другой — крышей. Все приходившие в программирование приобретали — независимо от изначальной специализации — марку “математик”. Заметим, что все, работавшие вокруг ЭВМ, делились грубо на два клана.

Принадлежавшие к одному клану носили марку “инженер”, принадлежавшие к другому — марку “математик”. Именно последние и были программистами, людьми, создававшими программное обеспечение.

Пребывание под другой крышей, с одной стороны, было естественным — надо было расти под чьей-то кроной, и крона математики была наиболее подходящей: требования к точности и корректности решений, “чистая” интеллектуальность продукта характеризовали как математику, так и программирование. С другой стороны, такие черты программирования, как ценность прагматики, невозможность (по крайней мере, до сих пор) исходить всегда только из доказательных рассуждений, отличали программирование от математики, делали ее в глазах математиков-пуритан некоторой “грязной” ветвью математики. Характерно здесь запомнившееся мне замечание М. И. Каргаполова: «Вот до сих пор существовала, так сказать, теоремная математика, а теперь появилась этакая “бестеоремная” математика». Многие математики, особенно специалисты в вычислительной математике, считали, что единственная роль программистов — это обслуживать запросы вычислительных задач, никакой внутренней проблематики в программировании нет и быть не может. Мнение, что программирование не самостоятельная научная дисциплина, а обслуживающая деятельность, было Поттосин И. В. А. П. Ершов — пионер отечественного программирования достаточно распространено. С другой стороны, правда, бытовало такое отношение к программистам, как жрецам нового, непонятного и таинственного бога — компьютера. Если уменьшить эту патетику, разговор программиста с автором задачи напоминал приход сантехника в интеллигентскую квартиру — “мы не знаем и знать не можем эту грубую работу, а вот он знает”.

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

Ершов как один из пионеров программирования в полной мере испытал трудности становления программирования. Его кандидатская диссертация, законченная в 1959 году и посвященная такой модели программ, как операторные алгоритмы, была защищена только в 1962 году.

“Чистые” математики не могли понять той ее ценности, что предлагаемая модель хорошо отражает существенные свойства реальных программ. С постоянной оппозицией Ершову приходилось сталкиваться и при осуществлении его знаменитого Альфа-проекта. Многие не могли понять — как это, коллектив высококвалифицированных программистов вместо того, чтобы писать прикладные, очень полезные программы, занят созданием какого-то транслятора — вещи и бесполезной, и, по своему замыслу создания процессора с языка типа Алгол, получающего программы, близкие по качеству к программам, написанным вручную, невозможной.

Реакция на те внешние трудности, которые возникали на пути становления программирования, могла быть двояка. Можно было “сломаться” — уйти либо в исследование только чисто математических проблем, связанных с программированием (их, слава Богу, достаточно много), либо в обслуживание вычислительных задач, не претендуя ни на какую самоидентификацию. Можно было обидеться и порвать с математикой, занимаясь лишь конструированием программных систем без всякой попытки привлекать точные методы. Мудрость Ершова была в том, что он не пошел ни по одному из этих путей. Его решением было — одновременное и связанное развитие понятийного фундамента программирования и точных математических моделей, формализующих эти понятия в той мере, в какой возможно. Именно на таком сочетании основывается созданная им новосибирская школа программирования.

10 Становление новосибирской школы программирования Как и для подавляющего большинство пионеров программирования, первые научные результаты Ершова связаны с вычислительными задачами. Его первой статьей была опубликованная в 1985 году в Докладах Академии наук работа “Об одном методе обращения матриц”, но Ершов не был бы программистом, если бы он сам не написал стандартную программу для БЭСМ, реализующую этот новый, предложенный им метод. Кстати, здесь сказались его начальные математические интересы — прежде чем пойти на кафедру вычислительной математики, он собирался специализироваться по алгебре. Однако с появлением идей, связанных с внутренними проблемами программирования, он, как и многие пионеры программирования, ушел полностью на новую, неизведанную область. Первой такой областью программирования были языки и системы программирования. Он не был самым первым в этой области, но был одним из первых, и сразу выдвинулся. Действительно, целый ряд активных и ищущих программистов с громадным интересом устремились в такую область, которую потом назовут системным программированием. Это были, как и Ершов, будущие лидеры нашего системного программирования — М. Р. Шура-Бура, Э. З. Любимский, С. С. Камынин, Л. Н. Королев, В. М. Курочкин и другие. Ершов был одним из основных разработчиков программирующей программы для БЭСМ — одного из первых отечественных трансляторов. Его идеи были сильными и сразу стали составляющими фундамента концепций языков и методов трансляции. Достаточно вспомнить, что им были предложены (во всяком случае, впервые в отечественном программировании) такая языковая конструкция, как цикл, и такой метод, как функция расстановки (хэш-функция). Им была написана первая в мировой практике монография по трансляции, ставшая широко известной — русское издание 1958 год, английское издание 1959 г., китайское 1960 г.

Начиная со своих ранних работ, Ершов становится одним из ведущих мировых ученых в этой области — области языков программирования и языковых процессоров. Предложенные им идеи и опыт задуманных им и руководимых им проектов — первого оптимизирующего транслятора с языков типа Алгол Альфа, первого кросс-транслятора АЛГИБР, транслятора Альфа-6 для ЭВМ БЭСМ-6, многоязыковой транслирующей системы Бета — стали составной частью современного фундамента трансляции. Методы оптимизации памяти, зачатки методов анализа программ, понятие внутреннего языка как семантического представления программ одного (в Альфа-системах) или широкого класса языков Поттосин И. В. А. П. Ершов — пионер отечественного программирования (в проекте Бета), предназначенного для целей оптимизации программ и/или кросс-компиляции, унифицированная схема трансляции — вот его личный вклад в такой фундамент, основанный на этих системах.

Даже такой долговременный и не до конца решивший намеченные проблемы проект, как Бета (некоторыми ехидными коллегами расшифровывающийся как Большая Ершовская Трансляторная Авантюра — что несло оттенок истины: действительно большая и действительно в чем-то авантюрная) внес большой вклад в методику трансляции — и в методах определения внутреннего языка, и во влиянии опыта этого проекта — положительного и отрицательного — на последующие многоязыковые системы.

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

Предложенный им язык Сигма был примером языкового ядра, расширяемого за счет механизма подстановки.

Широко известными являются его результаты по специализации программ путем смешанных вычислений. Здесь у него были предшественники — Футамура, Турчин — но именно ему принадлежит кристаллизация принципа смешанных вычислений, давшая толчок к появлению большого числа теоретических и практических работ по смешанным и частичным вычислениям. Ученикам Ершова принадлежат работы по практическим и высокоэффективным смешанным вычислениям. Его идеи дали толчок к появлению похожих подходов к специализации программ, в частности, конкретизации. Ершов же сформулировал понятие трансформационной машины как подхода к построению надежных и качественных программ. Все эти идеи Ершова являются основой нового направления создания программ — трансформационного программирования, которое пока еще не нашло большого практического применения, но имеет большое будущее.

Особое место в его работах занимает проект АИСТ. На мой взгляд, значимость и ценность этого проекта были недооценены, а его новаторство было значительным. Здесь Ершов выступал как руководитель создания всей вычислительной системы — и ее архитектуры, и ее программного обеспечения. Начальный этап этого проекта — АИСТ-0 — представлял собой одну из первых отечественных мультипроцессорных систем, снабженную богатым программным обеспечением, реализуюСтановление новосибирской школы программирования щим различные режимы обслуживания — от пакетного до разделения времени.

Работы по программному обеспечению в проекте АИСТ происходили практически одновременно с другими работами у нас и за рубежом по созданию развитых ОС, прототипов современных ОС (Малтикс, ОС ИПМ и др.) и были в ряду этих работ достаточно яркими и оригинальными. Архитектура же системы АИСТ была первым серьезным архитектурным проектом, выполненным в Новосибирске, за которым последовали другие оригинальные проекты, выполненные в Институте математики и Вычислительном центре Сибирского отделения. Само программное обеспечение было реализовано по трехуровневой модели:

ядро ОС, специализированные ОС и диалоговые системы, прикладное программное обеспечение. Работа была прервана, и последующие этапы не были реализованы из-за принятия, по-видимому, ошибочной национальной программы, о которой Эдсгар Дейкстра как-то сказал: “Наибольшей победой Запада в холодной войне было то, что Советский Союз принял архитектуру ИБМ”.

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

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

Ряд фундаментальных терминов русского программистского языка — “информатика”, “программное обеспечение”, “технология программирования” и другие — был привнесен им. Но дело тут, конечно, не только в изобретении названия. За этим стояла и серьезная понятийная и методологическая работа.

По поводу термина “информатика”. Как уже говорилось, Ершов, как и все мы, достаточно долгое время считал себя человеком, работающим в некоторой особой, но математической области, не осознавая до конца специфику того дела, которым занимался. Расстаться с привычной крышей было не так то просто. Однако накопление специфического для новой научной дисциплины багажа рано или поздно потребовало и соответствующего осознания. Но как только этот факт — существование Поттосин И. В. А. П. Ершов — пионер отечественного программирования новой научной дисциплины — был Ершовым осознан, он делает решительный шаг, предлагает новый термин — “информатика”, и в работе 1984 года “О предмете информатики”, опубликованной в Вестнике Академии Наук, очерчивает контуры новой науки, ее смысл и предмет изучения. Он дал термину “информатика” более широкое толкование, чем то, что вкладывается в его традиционный английский эквивалент “Computer Science”, а именно — фундаментальная естественная наука, изучающая процессы передачи и обработки информации. Компьютерная же наука — как она понимается — составляет “рабочее” содержание информатики лишь на сегодняшний день.

Не менее значительную роль сыграл запуск Ершовым в обиход термина “технология программирования”. Программисты из первого поколения привыкли к тому, что создание программ есть высокоинтеллектуальный труд, сродни исследовательскому. В чем-то они были правы, на первых порах так и было. Ершов первым (во всяком случае, среди отечественных программистов) увидел другую ипостась программирования — не исследовательскую, а производственную — как основу новой возникающей промышленности, софтверной промышленности. Очень важно, что Ершов предвидел роль и значимость этой промышленности, необходимость готовить ее кадры, причем разноплановые — архитекторов, руководителей проектов, тестовиков, разработчиков. Иногда он сознательно обострял свою позицию — говорил о “дегероизации трансляции” в том смысле, что создание “хороших” трансляторов с известных языков пусть и сложная, но конструкторская, а не исследовательская задача; ввел термин “фабрика трансляторов”. Такая “промышленная” точка зрения вызвала резкие возражения среди многих, и Ершов достаточно долго и упорно пробивал свою позицию, которая, как оказалось впоследствии, была верной. Термин “технология” в применении к программированию и отражал эту позицию.

Если говорить о фундаменте новой дисциплины — а Ершов с его осознаваемым лидерством понимал всю ответственность формирования такого фундамента и четко видел нужды всего направления — то он подчеркивал две проблемы. Первая — это создание понятийной основы, системы связанных и формализованных понятий, отражающих на хорошем уровне абстракции все, что нужно для процессов создания программ, того, что Ершов назвал лексиконом программирования. Многое в его работах идет в этом направлении, достаточно вспомнить его работы вокруг проекта Бета или работы по смешанным вычислениям. ВтоСтановление новосибирской школы программирования рая, связанная с первой, — развитие теории, формальных методов, того, что сейчас четко прослеживается в новых методологиях и технологиях создания программ, в математизации процесса создания программ. В этом направлении он тоже сделал много. О его вкладе в теорию схем программ еще будет говориться, а я хотел бы остановиться на том, что он всегда видел связь между теорией и практикой программирования и умел как увидеть в практических результатах основу для теоретических моделей, так и применить теоретические исследования для практических целей. Еще в Альфа-трансляторе он использовал теорию экономии памяти, созданную им совместно с С. С. Лавровым для построения соответствующих оптимизирующих преобразований. Это было первое практическое применение теории схем программ к обоснованию оптимизирующих преобразований. Эта работа имела далеко идущие последствия. Большое число последующих работ новосибирской школы по созданию моделей программ — линейных, кратных схем, линейных программ, крупноблочных схем, регулярных схем — и по их применению к обоснованию оптимизирующих преобразований выросли из этой работы. Это была, так сказать, наша “Шинель”, из которой мы росли.

Еще один пример — наряду с проектом АИСТ, которым он руководил, с его многопроцессной и многопроцессорной обработкой он инициирует работы по формальным моделям параллельных программ.

Ершову принадлежит великолепная и в чем-то уникальная книга — “Введение в теоретическое программирование. Беседы о методе”. Особая значимость этой книги в том, что там ясно показывается, как на основе рассмотрения практических проблем возникают теоретические модели и как эти модели позволяют решать практические задачи. Книга издана в 1977 году, а программистские монографии, мы хорошо знаем, быстро стареют. Но эта монография вне этого — увы — общего правила: в годы вышел ее английский перевод.

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

Он был признанным главой этой деятельности в нашей стране.

С одной стороны, он занимался проблемой того, как готовить профессиональных программистов — этому был посвящен ряд его работ, а также деятельность на мехмате НГУ, где он создавал коллектив препоПоттосин И. В. А. П. Ершов — пионер отечественного программирования давателей, обучающих программированию, и сам ставил курс программирования, с другой стороны, он начинал школьную информатику у нас в стране. Здесь его деятельность была многообразна: телевизионный курс лекций, один из первых учебников по информатике для средней школы (он был переведен на многие национальные языки Советского Союза), организация летних школ юных программистов, организация поездки юных программистов в Соединенные Штаты и многое другое.

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

Ершов был лидером советского программирования и осознавал это.

Лидерство воспринималось им как ответственность — за судьбу и развитие нового направления, за судьбу людей, работающих в этом направлении. Он умел отстаивать значимость программирования и программистов перед внешним миром. У него было прекрасное, далеко не частое свойство: он ценил авторитет знаний, кругозора, ума, а не авторитет должности и положения, и это он относил и к себе. Его высказывания всегда были продуманными, аргументированными, он внимательно следил за собой и никогда не рассчитывал на то, чтобы они воспринимались как неоспоримые истины, неоспоримые потому, что высказываются “большим человеком”.

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

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

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

Его широко известные работы, такие как “Two faces of programming”, “Aesthetics and the human factors of programming”, “Programming, the second literacy”, ясно и выпукло определяли дух и специфику нового вида деятельности.

Он был лидером и в общественной программистской жизни: организатором совещаний и конференций, отечественных и международных, 16 Становление новосибирской школы программирования руководителем всесоюзных комиссий и комитетов, проводником международных связей, создателем информационных потоков (след, оставленный им — Мемориальная библиотека А. П. Ершова при ИСИ СО РАН).

Его безусловное и всеми признаваемое лидерство связано и с его личностными свойствами.

Он обладал истинной стратегией мышления, предвидя будущность только что появившегося явления, прекрасно видел точки роста. Достаточно вспомнить, какие работы он в свое время инициировал — реализацию одного из первых языков спецификации СЕТЛ, работы по технологии создания интеллектуальных систем, работы по теории параллельного программирования, создание системы Школьница — методологически обоснованного инструмента обучению программированию в школе. Уже при появлении персональных компьютеров он понял их громадную будущность, образно назвав первые персональные компьютеры “предками млекопитающих в динозавровом мире ЭВМ”. Помню, как-то мы с Геной Кожухиным, обсуждая основы нашего программистского бытия, пришли к заключению, что если в тактике мы “сами умные”, то в стратегии нам надо доверять мнению Андрея Петровича больше, чем своим собственным — его стратегическая мудрость была для нас очевидной.

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

Я знаю много людей, для которых поддержка Ершова была весьма существенной. Среди них и эстонец Тыугу, и грузин Цуладзе, и украинец Вельбицкий, и молдаванин Тодорой, и петербуржец Терехов и многие, многие другие. Я уже не говорю о нас, сибиряках.

Итак, Ершов был и одним из пионеров, и лидером отечественного программирования. Если первому он обязан во многом временем, то второму — личным заслугам, величине и значимости своей личности.

Э. З. Любимский, И. В. Поттосин, М. Р. Шура-Бура

ОТ ПРОГРАММИРУЮЩИХ ПРОГРАММ К СИСТЕМАМ

ПРОГРАММИРОВАНИЯ

Трансляция — это область, с которой начиналось системное программирование. Первыми программами, принадлежащими системному программному обеспечению, были те или иные трансляторы — ассемблеры и автокоды на Западе, программирующие программы (ПП) у нас.

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

Начальные идеи по трансляции были выдвинуты в 1952 году, на самом раннем этапе развития программирования. В этом году Рутисхаузер опубликовал работу [1], в которой изложил идею о том, что по естественной записи арифметического выражения можно построить эквивалентный ей фрагмент машинного кода. Соответствующий алгоритм (многопроходный) был сформулирован. Эта работа дала толчок к возникновению процессоров, в своем входном языке допускающих естественную запись выражений. А. А. Ляпунов в те же годы атаковал проблему с другой стороны. Он заметил, что структура программы включает в себя операторы из небольшого набора типовых операторов и может быть представлена формально в виде строки, соответствующей последовательности операторов программы. На языке операторных схем программа представляется как схема, соответствующая управляющему графу программы, и совокупность спецификаций каждого оператора.

Эти идеи А. А. Ляпунов положил в основу курса по программированию, читавшегося им в Московском Университете. Понятие программы как некоторой операторной структуры, взгляд на программу сверху, было революционной идеей, которая практически сразу же легла в основу первых отечественных трансляторов. К сожалению, из-за специфики организаций, в которых работал А. А. Ляпунов, развернутая публикация этого подхода была осуществлена только в 1958 г. [2].

18 Становление новосибирской школы программирования Первые отечественные трансляторы носили мнемоническое название программирующих программ. В основе входного языка каждой из программирующих программ лежал общий концептуальный базис, фиксирующий типы операторов и общую идею их спецификации. Унификация языков не ставилась как практическая задача. Как модельный пример может быть приведена следующая схема алгоритма суммирования элементов вектора (в осовремененном виде):

1: А1; 2:А2; 3:А3; 4:А4; 5:F1; 6:P1(3, 7); 7: О1.

со спецификацией операторов:

А1 : S := A2 : i := A3 : S := S + ai F1 : переадресация A3 по i P1 : если i n, то на оператор 3, иначе - на О1 : восстановление A3 в начальном виде.

Типы операторов соответствовали подавляющему большинству решаемых тогда задач, а именно — вычислительным задачам. Выделялись арифметические операторы Аi, ведущие вычисление по формулам, логические операторы Рi, осуществляющие управление счетом, операторы переадресации Fi, позволяющие переходить к следующему значению индекса (и обратные им операторы восстановления), все же неарифметические вычисления объединялись в так называемые нестандартные операторы Hi, для которых спецификацией был их машинный код. Специального подъязыка описания данных, зачатки которого появились в более поздних ФОРТРАНе и Алголе, не существовало.

Начиналось все с ПП-1. Молодые тогда программисты С. С. Камынин и Э. З. Любимский исследовали реализуемость операторных схем и возможность автоматического построения соответствующих машинных программ. Это было самое начало, и то, что стало очевидным и даже тривиальным сейчас, считалось тогда проблематичным. Законченная в 1954 году программирующая программа ПП-1 [14] являлась одним из первых в мировой практике трансляторов и, по-видимому, имела самый высокий уровень входного языка.

Успешное решение проблемы реализуемости операторных схем как входного языка программирующих программ, осуществленное в ПП-1, дало толчок для двух проектов, разработанных для двух основЛюбимский Э. З. и др. От ПП к системам программирования ных тогда отечественных машин — Стрела и БЭСМ.

Программирующая программа ПП-2 [3], созданная под руководством М. Р. Шура-Буры в 1955 г. для машины Стрела-1, основывалась на ПП- как прототипе. Разработчиками были И. Б. Задыхайло, С. С. Камынин, Э. С. Луховицкая, Э. З. Любимский и В. С. Штаркман. В ПП-2 были усовершенствованы алгоритмы трансляции и было уделено заметное внимание оптимизации программ — экономии выражений, оптимальному сочетанию переадресации и восстановления (иначе говоря, наилучшей реализации вычисления индексных выражений), оптимальному отведению памяти для так называемых рабочих ячеек. Это был, по-видимому, первый оптимизирующий транслятор.

ПП для БЭСМ [4], разработанная А. П. Ершовым, Л. Н. Королевым, В. М. Курочкиным, Л. Д. Паниной и В. Д. Поддерюгиным, развивала входной язык программирующих программ. Во-первых, она объединяла схему и спецификацию операторов в одном тексте, во-вторых, был введен первый структурный оператор, а именно — столь существенный оператор цикла (соответствующий современным циклам с параметром).

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

С использованием идей и алгоритмов этих работ была развернута деятельность по созданию следующего слоя программирующих программ.

Следующие программирующие программы создавались в 1957–58 гг.

для различных модификаций ЭВМ Стрела. Надо вспомнить, что серийного производства ЭВМ как такового тогда не существовало, и все производимые экземпляры Стрелы расходились в деталях архитектуры.

ПП-2 послужила идейной основой двух проектов — ПП для Стрелы [5] (разработчики Н. М. Ершова, Е. А. Жоголев, Т. С. Росляков, Н. П. Трифонов и др. при идейном руководстве М. Р. Шура-Буры) и ПП для Стрелы 7 [6] (разработчики А. М. Бухтияров, Л. В. Войтишек, Н. А. Криницкий, А. А. Левина, И. В. Поттосин, Г. Д. Фролов). Важно отметить, что первая из них представляла собой зачаток настоящей системы программирования: помимо собственно транслятора она содержала систему сборки модулей и некоторые средства отладки. Транслятор получал такие фрагменты объектной программы, которые потом назовут модулями, а система сборки создавала программу из оттранслированных модулей и библиотечных программ.

20 Становление новосибирской школы программирования ПП для Стрелы 3 [7] (разработчики Т. М. Великанова, А. П. Ершов, К. В. Ким, В. М. Курочкин, Ю. А. Олейник-Овод, В. Д. Поддерюгин) создавалась под идейным влиянием ПП БЭСМ. В ней был реализован ряд идей, новых тогда, но ставших классическими сейчас — табличный подход к синтаксическому анализу, оптимальное (по числу рабочих переменных) программирование арифметических выражений. А. П. Ершовым был независимо (и практически одновременно с Петерсеном) изобретен метод хеширования [8], который применялся к экономии арифметических выражений.

Итак, как и обычно при становлении нового направления, одновременно с созданием первых российских трансляторов — программирующих программ — шел процесс кристаллизации и оформления базовых идей и подходов и одновременно процесс создания коллективов квалифицированных исследователей, сказавших свое слово и на последующих этапах развития этого направления. Как некоторый итог этого начального этапа представляется вышедшая в 1958 г. первая в мировой науке монография А. П. Ершова [9], посвященная проблемам трансляции. Монография практически сразу была переведена и издана за рубежом [10].

Нужно заметить, что с трансляции начиналось не только системное, но и теоретическое программирование. Именно работы по входным языкам (операторным схемам) и трансляторам (программирующим программам) послужили толчком к созданию первой математической модели программ — схемам Янова [11]. Начальным толчком к появлению такой известной модели, как стандартные схемы стала работа А. П. Ершова, одного из создателей первых трансляторов по операторным алгоритмам [12].

Советские работы 1953–58 гг. развивались независимо от мирового опыта. Практически параллельно с отечественными работами появились серьезные труды по трансляции и в США. Сопоставимый по уровню входного языка известный транслятор с ФОРТРАНа был описан в статье Дж. Бэкуса [12], появившейся в 1957г. Реальное привлечение мирового опыта к отечественным разработкам по трансляторам началось с возникновением Алгола, точнее — Алгола-58.

Параллельно с работами по программирующим программам развивался и подход к автоматизации программирования с помощью библиотек стандартных программ. Е. А. Жоголевым была разработана станЛюбимский Э. З. и др. От ПП к системам программирования дартная составляющая программа — ССП [15], которая осуществляла статическую загрузку и связывание стандартных программ из достаточно обширной библиотеки, был предложен достаточно амбициозный проект организации библиотеки и подключения подпрограмм [16].

По-видимому, кульминацией этого подхода было создание М. Р. ШураБурой интерпретирующей системы (ИС) ИС-2 [17], которая использовалась повсеместно на новых машинах М-20 и учитывалась всеми трансляторами нового поколения. В ИС-2 был весьма эффективно реализован способ динамического подключения библиотечных подпрограмм.

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

Существенно новым шагом в развитии направления трансляции стало создание совокупности алголовских трансляторов для появившейся массовой (и уже серийно производившейся) машины М-20. Хотя язык операторных схем имел уже достаточно высокий уровень, вполне сопоставимый с уровнем тогдашней версии ФОРТРАНа, Алгол-60 был качественно новым языком, ставившим ряд новых важных задач. Вместе с тем в стране уже был накоплен багаж базовых идей и созданы коллективы высокопрофессиональных специалистов в области трансляции, что привело к возникновению оригинальных и широко использовавшихся систем программирования.

При всех своих достоинствах программирующие программы не имели достаточно широкого практического использования: даже при их наличии почти во всем множестве архитектур, существовавшем в стране, доля программирования непосредственно в машинном языке была преобладающей. Переход к современному стилю программирования на языках программирования высокого уровня был осуществлен благодаря созданию первых алголовских трансляторов. Произошло так, что первая тройка отечественных алголовских трансляторов, созданная для наиболее массовой тогда ЭВМ М-20, различалась по своим потребительским возможностям так, что своей совокупностью они удовлетворяли практически всем категориям пользователей.

Работы над этими трансляторами (ТА-2 [18], ТА-1 [19] и Альфа [20]) 22 Становление новосибирской школы программирования начались практически сразу после публикации завершенного международной рабочей группой описания языка. Хотя, по-видимому, первым алголовским транслятором стал транслятор Айронса [21], но и ТА-1, и ТА-2 были завершены в 1963г., т.е. практически одновременно с другими известными западными работами — П. Наура [22] и Э. Дейкстры [23]. Транслятор Альфа ввиду объемности реализации был завершен годом позже.

Транслятор ТА-2 (разработчики И. Х. Зусман, С. С. Камынин, Д. А. Корягин, А. С. Луховицкая, В. В. Луцикович, Э. З. Любимский, В. Б. Мартынюк, Г. М. Олейник-Овод, В. И. Собельман под руководством М. Р. Шура-Буры) встретил вызов Алгола-60 грудью, не вводя практически ограничений ни на язык, ни на размеры входных программ. В трансляторе был разработан оригинальный алгоритм программирования процедур (понимаемых как потенциально рекурсивные), мощные механизмы управления математической памятью как единства оперативной и внешней, систематически применялся метод таблично-управляемой генерации кода. В мае 1963 г. первым из всех трех этот транслятор уже демонстрировался на международной конференции по автоматизации программирования в Киеве.

Транслятор ТА-1 (разработчики В. Н. Попов, В. А. Степанов, А. Г. Стишева, И. А. Травникова под руководством С. С. Лаврова) основывался на быстрой и простой схеме трансляции (в частности, был разработан стековый подход к программированию выражений). Для достижения такой схемы авторы отказались от ряда средств Алгола-60: рекурсивности процедур, наличия статических (собственных — own) объектов в блоках, от возможности введения параметров процедур без их типизации и пр. Вместе с тем, что существенно для современных систем, особое внимание было уделено простоте и удобству эксплуатации.

В Альфа-трансляторе (разработчики Г. И. Бабецкий, М. М. Бежанова, Ю. М. Волошин, Б. А. Загацкий, Л. Л. Змиевская, Г. И. Кожухин, С. К. Кожухина, Ю. И. Михалевич, Р. Д. Мишкович, И. В. Поттосин, Л. К. Трохан под руководством А. П. Ершова) особое внимание уделялось эффективности получаемых программ. Большой набор оптимизирующих возможностей (квазилокальная экономия выражений, оптимальное и весьма изощренное программирование процедур, циклов и индексных вычислений, глобальная экономия памяти и пр.) давал возможность получать объектные программы, мало отличающиеся по времени исполнения от созданных вручную программ. Платить за это приЛюбимский Э. З. и др. От ПП к системам программирования ходилось большим объемом транслятора, большим числом проходов ( прохода), отказом от некоторых средств Алгола, оптимальная реализация которых не была найдена (в частности, как и в ТА-1, рекурсивность была запрещена). Вместе с тем входной язык являлся расширением Алгола (точнее, его подмножества), включавшим ряд таких типичных для современных языков средств, как операции над многомерными значениями, комплексный тип, начальные значения переменных и пр. В целом в Альфа-трансляторе начала складываться современная методология оптимизирующей трансляции с такими ее понятиями, как внутренний язык, многопроходная реализация оптимизирующих преобразований, потоковый анализ.

В целом, как уже говорилось, эта совокупность трансляторов покрывала разнообразные запросы пользователей. Для большого потока сравнительно небольших программ без особых требований к эффективности подходил ТА-1, программистам, которые хотели воспользоваться всеми возможностями Алгола, в том числе и возможностями транслировать большие задачи, был пригоден ТА-2, а для тех, кому надо было программировать задачи с большим счетом и, значит, обязательно иметь эффективный код, существовал Альфа-транслятор.

В отличие от программирующих программ все алголовские системы были уже настоящими системами программирования, близкими к современным: они включали в себя не только собственно транслятор, но также отладочные и некоторые редактирующие средства. В ТА-1 и Альфа-систему входили отладочные редакторы, которые по заданию на отладку создавали отладочную версию программ. Говоря посовременному, платформой для всех систем была ИС-2, все системы включали ее средства в свой входной язык и строили программы, ориентированные на ИС-2.

Языки системного программирования Инициированное созданием трансляторов появление системного программирования поставило задачу создания адекватных языков программирования. Все языки, появившиеся к началу 60-х годов — Фортран, Кобол, Алгол-60 и др., — не учитывали этой области программистской деятельности, и алголовские системы, будучи достаточно большими программными системами, писались еще в машинных кодах вручную. Адекватные языки нужны были не только для трансляторов, но и для всей возникающей области системного программирования: начаСтановление новосибирской школы программирования ли появляться и другие языковые процессоры, и первые операционные системы, и информационные системы — все то, что потом назовут базовым программным обеспечением.

В связи с этим и у нас, и на Западе начали появляться специальные языки, предназначенные для системного программирования. Характерной чертой для первого поколения этих языков (связанной с необходимостью хорошо учитывать архитектуру и машинное представление данных) была машинная ориентированность. Разрабатывались эти языки, как правило, в коллективах, имевших большой опыт в создании системных программ — а таковыми в тот период были системы программирования. Отечественные языки Алмо [24], Эпсилон [25], Сигма [26], которые были одними из первых в мире языков системного программирования, создавались поэтому в коллективах трансляторщиков, только что завершивших большие программные проекты и почувствовавших, каково сапожнику обходиться без сапог.

Язык Алмо имел в своей основе некоторую абстрактную машину, отражавшую особенность существовавшего тогда класса машин, и в этом отношении Алмо-подход предвосхищал появившиеся позже Р-код, М-код и прочие подобные подходы. Помимо того, что этот язык был языком реализации для системного программирования, он предназначался быть языком-посредником при трансляции с различных языков.

Идея была в том, чтобы заменить трансляцию с m входных языков в n машинных языков трансляцией “из m в один” и “из одного в n”.

Важно заметить, что в языке существовали средства определения многопроцессности (типа fork и joint). Машинная ориентированность явно прослеживалась в языке — регистровые объекты, постфиксная запись выражений, оперирование с битами машинных слов и т.п. Были созданы реализации языка для основных отечественных машин того времени (М-20, БЭСМ-6, Минск 2, Урал 11) и трансляторы с Алгола-60 и ФОРТРАНа в Алмо, причем все трансляторы также были написаны на Алмо и “раскручены” на всех этих машинах.

Язык Эпсилон трактовал машинную ориентированность иначе. В этом отношении его идеология совпадала с одновременно появившимся языком Н. Вирта ПЛ360, ставшим прототипом большого числа языков системного программирования того времени: средства высокого уровня необходимы для естественного (для программиста) одевания конструкций машинного языка. Семантика каждой конструкции языка определялась сопоставленным ей образом — последовательностью операций Любимский Э. З. и др. От ПП к системам программирования машинного языка. При этом, конечно, рекомендовалось, чтобы образы для разных машинных языков были бы в определенной мере аналогичны, однако переносимость не обеспечивалась, за ней надо было следить.

Типы данных языка тоже следовали за назначением языка и его машинной ориентированностью — допускались целые (но не вещественные), классы двоичных значений, слоги машинных слов или их последовательности. Эпсилон тоже был реализован для большого числа архитектур — М-20, БЭСМ-6, Минск-2. Существенно, что при создании многопроцессорной архитектуры АИСТ-0, Эпсилон играл такую же роль, как впоследствии Си для Юникса или Эль-76 для Эльбруса — был базовым системным языком, на котором писалось все многочисленное системное обеспечение, от ядра ОС до системных программ, ориентированных на пользователя.

Язык Сигма обладал двумя важными и в то время новыми особенностями. Синтаксически ограничиваемый макросами, он, как и более поздний Форт, допускал генеральную линию создания программ — подстановку описанных макросов. Язык содержал средства формального описания конкретной архитектуры: была разработана система параметров, в терминах которой фиксировалось представление языка для конкретной ЭВМ. Таким образом, общая Сигма-программа вместе с описанием архитектуры ЭВМ транслировалась на данную ЭВМ. Параметрами архитектуры были длина слова, представление значений типов в машинном слове и т.п., так и правила заполнения шаблонов машинных команд.

Таким образом, вспоминая славные дни становления у нас в стране трансляции как области исследований и разработок, авторы, как кажется, сумели показать, что российские коллективы всегда находились на высоком научном уровне. Подходы и системы, о которых здесь рассказывалось, были выбраны в качестве той линии, к которой авторы имели непосредственное отношение. Часть российских работ, лежащая вне этой линии, здесь не рассматривалась — более широкое рассмотрение всех работ тех лет можно найти в обзоре [28, 29], а языки системного программирования тех и более поздних лет рассматриваются более подробно в [30].

26 Становление новосибирской школы программирования 1. Rutishauser H. Automatishe Rechenplanfertigung bei programmgesteuerten Rechenmaschinen // Mi. Inst. fur Angew. Math. dec ETH Zurich. — 2. Ляпунов А. А. О логических схемах программ // Проблемы кибернетики. — Вып. 1. — М.: Физматгиз, 1958. — С. 46–74.

3. Камынин С. С., Любимский Э. З., Шура-Бура М. Р. Об автоматизации программирования с помощью программирующей программы // Проблемы кибернетики. — Вып. 1. — М.: Физматгиз, 1958. — С. 135– 4. Ершов А. П. Программирующая программа для БЭСМ АН СССР // Тр. конф. “Пути развития советского математического машиностроения и приборостроения”. — ч.3. — М.:ВИНИТИ, 1956. — С. 18–29.

5. Система автоматизации программирования // Под ред. Н. П. Трифонова и М. Р. Шуры-Буры. — М.: Физматгиз, 1961. — 187 с.

6. Бухтияров А. М., Войтишек Л. В., Левина А. А. и др. Программирующая программа ПП-С // Сб. научных трудов № 1. — МО СССР.

7. Великанова Т. В., Ершов А. П., Ким К. В. и др. Программирующая программа для машины “Стрела” // Тез. докл. сов. по вычисл.

матем. и прим. средств выч. техники. — Изд-во АН АзССР. — Баку, 8. Ершов А. П. О программировании арифметических операторов // Докл. АН СССР. — 1958. — Т. 118, № 3. — С. 427–430.

9. Ершов А. П. Программирующая программа для быстродействующей электронной счетной машины // Изд-во АН СССР. — М., 1958. — 116 с.

10. Ershov A. P. Programming program for the BESM computer / Pergamon 11. Янов Ю. И. О логических схемах алгоритмов // Проблемы кибернетики. — Вып. 1. — М.:Физматгиз, 1958. — С.75-127.

12. Ершов А. П. Об операторных алгорифмах // Докл. АН СССР. — 13. Backus J. W. The FORTRAN automatic coding system / WJCC. — 14. Камынин С. С., Любимский Э. З. Автоматизация программирования // Тр. конф. “Пути развития советского математического машиностроения и приборостроения”. — Ч. 3. — М., 1956. — С. 9–17.

15. Жоголев Е. А., Росляков Г. С., Трифонов Н. П., Шура-Бура М. Р. Система стандартных подпрограмм // М.:Физматгиз. — 16. Кожухин Г. И., Нагорный Н. М., Поттосин И. В. Принцип организации и использования библиотеки программ // Вычислительная математика. — Изд-во АН СССР. — М., 1961.

Любимский Э. З. и др. От ПП к системам программирования 17. Шура-Бура М. Р. Система интерпретации ИС-2 // Библиотека стандартных программ. — М.:Изд-во ЦБТИ, 1961.

18. Шура-Бура М. Р., Любимский Э. З. Транслятор АЛГОЛ 60 // ЖВМиМФ. — 1964. — Т. 4, № 1. — С. 96–112.

19. Попов В. Р., Степанов В. А., Стишева А. Г., Травникова Н. А.

Программирующая программа // ЖВМиМФ. — 1964. — Т. 4, № 1. — С. 78–95.

20. Бабецкий Г. И., Бежанова М. М., Волошин Ю. М. и др. Система автоматизации программирования АЛЬФА // ЖВМиМФ. — 1965. — Т. 5, № 2. — С. 317–325.

21. Irons E. T. A sintax directed compiler for ALGOL 60 // CACM. — Jan.

1961. — №4. — P. 51–55.

22. Naur P. The design of the GIER ALGOL compiler // BIT.— 1963. — № 3. — P. 124–140.

23. Dijkstra E. W. An ALGOL 60 translator for the X1 // Ann.R. — 1963.

24. Камынин C. С., Любимский Э. З. Алгоритмический машинно-ориентированный язык АЛМО // Алгоритмы и алгоритмические языки. — Изд-во ВЦ АН СССР. — 1967. — Вып.1.

25. Поттосин И. В., Рар А. Ф.,Катков В. Л. ЭПСИЛОН — система автоматизации программирования для задач символьной обработки // Тр. 1-ой Всесоюзной конф. по программированию. — Киев, 1968.

26. Ershov A. P., Rar A. F. SYGMA, a symbolic generator and macroassembler // Symbol manipulation languages and technique, North-Holland Publ.

Co., 1968.

27. Wirth N. PL 360, Programming Language for the 360 Computers // JACM. — 1968. — Vol. 15, № 1.

28. Ершов А. П., Шура-Бура М. Р. Становление программирования в СССР // Кибернетика. — 1976. — № 6. — С. 141–160.

29. Erschov A. P., Shura-Bura М. R. The Early Development of Programming in the USSR // A History of Computing in the Twentieth Century. — Academic Press, 1980. — P. 137–196.

30. Поттосин И. В. Языки реализации для системного программирования // Новосибирск, 1979. — 24 с. —(Препринт/Сиб. Отд-ние АН СССР. ВЦ; № 179)

А. П. ЕРШОВ И СТАНОВЛЕНИЕ НОВОСИБИРСКОЙ

ШКОЛЫ ПРОГРАММИРОВАНИЯ

Становление ведущих научных школ по информатике у нас в стране практически всегда было связано с именами ярких личностей. Если у истоков киевской школы стоял В. М. Глушков, а у истоков ИПМовской школы — А. А. Ляпунов и М. Р. Шура-Бура, то у истоков новосибирской школы стоял их более молодой соратник А. П. Ершов, ученик А. А. Ляпунова.

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

Первым большим проектом, с которого начиналась новосибирская школа, был трансляторный проект “Альфа”. В отличии от предыдущих проектов программирующих программ проект Альфа был хорошо, практически по современному специфицирован: было подготовлено формальное описание входного языка [1, 2], была создана развернутая функциональная спецификация системы [3].

Поттосин И. В. А. П. Ершов и становление новосибирской школы Отправной точкой проекта была публикация начальной версии нового суммировавшего накопившийся программистский опыт языка программирования, создаваемого международной рабочей группой — так называемого Алгола 58. Группа, руководимая А. П. Ершовым, стала готовить на основе Алгола 58 новый проект языка — параллельно с работавшей международной группой. Во многом направления развития языка оказались совпадающими, но в новосибирском проекте появился ряд существенно новых механизмов, поэтому в конце концов язык был сформулирован как правильное расширение окончательной версии международного языка — Алгола 60. В Альфа-языке впервые были разработаны средства, характерные для последующих за Алголом 60 языков. Было определено столь важное для вычислительных алгоритмов понятие многомерных значений, определены операции над ними, в том числе их конструирование. Были введены свойственные современным языкам концепции, такие как разнообразие видов циклов, задание начальных значений и т.п. В формальном определении языка впервые была сделана попытка выйти за пределы контекстно-свободных грамматик.

Сама работа над транслятором была в большой мере и исследовательской, и пионерской. Именно в этой работе начали складываться принципы современной оптимизирующей трансляции. Дело в том, что сам Алгол 60 был определенным вызовом для существовавших методов трансляции. Его существенно рекурсивная структура, мощность механизма процедур, возможная их вложенность и потенциальная рекурсивность, общность циклов и индексных выражений — все это требовало заметной модификации и развития техники трансляции, а самое главное — ставило вопрос о возможности получения эффективного кода.

По последнему поводу высказывались сомнения, и Альфа-транслятор стал действительно первым конструктивным доказательством того, что для языков, сопоставимых по мощности с Алголом, можно построить транслятор, дающий сравнимый с ручным программированием код.

Достижению поставленной цели послужил богатый набор оптимизаций, реализованный в Альфа-трансляторе [4, 5]. Была предложена смешанная стратегия программирования (то, что позднее на Западе было названо “casing”) таких конструкций, как процедуры, циклы, индексные выражения, когда на основании анализа контекста выбирался наиболее эффективный из допустимых способ генерации конструкций. Особенно изощренно программировались процедуры и подстановка параметров 30 Становление новосибирской школы программирования для них: выбор осуществлялся среди 11 способов. В результате алголовские процедуры при всей мощности механизма программировались оптимальным образом (что стимулировало программистов активно использовать это средство). Существовавшая ранее оптимизация экономии выражений была существенно развита — полностью учитывались свойства коммутативности и ассоциативности; если это преобразование не стало глобальным, то оно уже было квазилокальным. Впервые была реализована глобальная чистка циклов. Тщательной оптимизации подвергались операции над многомерными значениями — то, чего не было в стандартном Алголе, но активно использовалось вычислителями. Впервые была реализована глобальная экономия памяти, опирающаяся на теоретические работы А. П. Ершова и С. С. Лаврова.

Альфа-транслятор стал первым в мире транслятором с Алгола с большими оптимизирующими возможностями. Похожий английский проект Хоукинса и Хакстебла, который разрабатывался в это время, так и не был до конца завершен из-за сложности задачи. Конечно, успеху способствовало не только механическое соединение многих оптимизаций, но и существенное развитие существовавшей методологии оптимизации программ. Была выдвинута идея внутреннего языка, к программе на котором и применяются оптимизации, которая, хотя и не совсем в чистом виде, была реализована. Был также практически реализован глобальный анализ контекста, хотя и разрозненно для различных оптимизаций, учет которого существенно увеличил мощность оптимизаций — зародыш современного потокового анализа. Стремление практически всегда получать эффективный код привело к отказу от некоторых средств Алгола, важнейшим из которых была рекурсивность процедур.

Альфа-транслятор активно использовался во многих организациях страны. Хотя его интерфейсы с пользователем и простота эксплуатации оставляли желать много лучшего, но высокая эффективность получаемого кода обеспечила большой интерес пользователей к этой системе. Поэтому когда на смену М-20 пришла существенно более высокопроизводительная машина БЭСМ-6, организации, связанные с большими задачами, стимулировали создание версии Альфа-транслятора для БЭСМ-6. Самым быстрым решением была простая переделка Альфатранслятора, при которой та его часть, которая отвечала за генерацию кода, была заменена генератором кода для БЭСМ-6. Возник транслятор Алгибр (“Альфа гибридный”), который был одним из первых отечеПоттосин И. В. А. П. Ершов и становление новосибирской школы ственных кросс-трансляторов. Такое решение имело ряд недостатков, но зато оно было реализовано быстро, и транслятор Алгибр стал первым транслятором для новой машины БЭСМ-6. Решение существенно облегчалось тем, что в Альфе-трансляторе уже существовал внутренний язык, хотя и не до конца единый для всех оптимизирующих преобразований.

Основным затруднением при Алгибр-трансляции была передача оттранслированного кода с М-20 на БЭСМ-6. В ВЦ СО АН СССР был даже разработан специальный канал передачи информации между инструментальной и объектной ЭВМ, однако это не могло быть серийным решением при массовой трансляции. Возникла необходимость “родного” транслятора для БЭСМ-6.

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

Новый транслятор — транслятор Альфа-6 [6] — был улучшенной версией оптимизирующего транслятора с Алгола. Ряд предыдущих решений был приведен к более чистому и эффективному виду. Более четко был выделен внутренний язык и этап потокового анализа программ на внутреннем языке. Общая схема трансляции уже могла рассматриваться как типовая схема оптимизирующей трансляции (для одноязыкового транслятора), она насчитывала всего 10 просмотров. Лучше была решена проблема взаимного влияния различных оптимизирующих преобразований. Идентификация и визуализация ошибок пользователя была более совершенной, что облегчало эксплуатацию. В результате система Альфа-6 стала достаточно широко используемой системой у пользователей БЭСМ-6.

32 Становление новосибирской школы программирования В середине 60-х годов начало складываться новое направление системного программирования — операционные системы. Причины их возникновения связаны и с усложнением архитектур ЭВМ, и с совершенствованием методов взаимодействия “человек—машина”. В архитектурах появились параллельно работающие устройства, и возникла задача управления их совместной работой. Назрела необходимость автоматической смены задач, диалоговой связи с оператором ЭВМ и, что еще важнее, с пользователем. Появилось понятие режима разделения времени как средство обеспечения многозадачности. Как зарубежные, так и отечественные программисты ринулись в эту новую область, закладывая основы методологии современных операционных систем.

А. П. Ершов с его прекрасным чувством нового и перспективного стал инициатором и руководителем проекта “автоматической информационной станции” АИСТ-0 [7, 8]. Этот проект сочетал в себе создание как многопроцессорной архитектуры, так и развитого программного обеспечения, использующего те возможности, которые предоставляла эта архитектура.

АИСТ-0 стал одной из первых отечественных многопроцессорных систем. В системе существовал управляющий процессор и несколько рабочих. В качестве процессоров были взяты серийно производимые отечественные ЭВМ — управляющим процессором был взят Минск-2, а рабочим процессором — М-220. Внешняя и оперативная памяти рабочих процессоров были обобществлены и подключались через коммутатор.

Для фиксации событий и для программируемых прерываний существовала система прерываний. Архитектурными и программными средствами была сохранена полная совместимость с существующим программным обеспечением для М-220.

Программное обеспечение АИСТа-0 было богатым и разнообразным, его создатели хотели использовать все предоставившиеся им возможности. Существовал ряд специализированных операционных систем пакетного режима, которые могли образовывать несколько потоков задач, исполняемых по различным дисциплинам обслуживания, учитывающих важность, срочность и прочие пользовательские требования.

Были созданы многопользовательские системы диалоговой отладки и редактирования, системы диалогового программирования как для стандартных языков (Алгол 60), так и для специальных диалоговых языков (известный в то время ДЖОСС). Как пример применения диалога Поттосин И. В. А. П. Ершов и становление новосибирской школы в прикладных программах были разработаны система аналитических преобразований и интеллектуальный пакет для линейной алгебры. Было создано несколько информационно-поисковых систем. По-видимому, впервые в стране было разработано несколько диалоговых игровых программ.

Создание столь разнообразных систем облегчалось разработанной структурой программного обеспечения [9]. Как и другими разработчиками операционных систем разделения времени и реального времени решалась задача выделения ядра операционной системы. Такое ядро (в АИСТ-0 оно называлось диспетчер) обеспечивало создание и управление процессами, передачу сообщений между процессами, первичную обработку сигналов и прерываний, реализовывало некоторую универсальную дисциплину управления многопроцессностью, на базе которой за счет задания параметров можно было реализовать удобную для данного вида работы дисциплину обслуживания. Следующий слой программного обеспечения составляли так называемые системные программы, специализированные на способ обслуживания операционные системы.

Диспетчер работал на управляющей машине, все остальное программное обеспечение — на рабочих процессорах. Такая структура облегчала обеспечение множества режимов и видов обслуживания, каждый из которых реализовался своей системной программной с использованием базовых понятий и средств диспетчера. Конечно, можно было попытаться найти общность среди некоторых классов режимов и видов обслуживания, но отсутствие реального опыта разнообразной работы делало эти попытки умозрительными, и от них сознательно отказались, сосредоточив все общие модели в диспетчере, что, по-видимому, удалось сделать довольно удачно.

Достаточно успешная реализация АИСТа-0 вызвала к жизни проект серийного производства многопроцессорных комплексов, который прорабатывался Казанским заводом ЭВМ, однако общий поворот в идеологии отечественного производства ЭВМ не дал этому проекту осуществиться. Часть идей АИСТа-0, но далеко не полностью, была использована при создании ЭВМ М-222.

Заглядывая в более поздние времена, надо отметить, что опыт, накопленный при архитектурной и программной разработке АИСТа-0, сказался и в последующих новосибирских разработках — макете потокового суперкомпьютера МАРС, первой отечественной 32-битной рабочей станции Кронос, специализированной рабочей станции для редакционноСтановление новосибирской школы программирования издательской деятельности МРАМОР. Следует отметить и дух создания новосибирских архитектур — они проводились под сильным влиянием системных программистов. Так, архитектура МАРС разрабатывалась под влиянием языка асинхронного потокового программирования Барс, а в архитектуре Кроноса были заложены средства схемной реализации конструкций языка программирования высокого уровня, прежде всего — Модулы-2.

В качестве непосредственного продолжения проекта АИСТ-0 было начато создание системы коллективного пользования для новой тогда ЭВМ БЭСМ-6, руководителем разработки программного обеспечения в котором был Г.И.Кожухин. Проект этот пришлось прекратить ввиду организационных трудностей, связанных с требуемой проектом модификации БЭСМ-6, однако он повлиял на следующий реализованный проект ВЦКП (Вычислительного Центра Коллективного Пользования), прообраза гетерогенных локальных вычислительных сетей.

Работы по АИСТ-0 не исключали и продолжение исследований и в уже традиционном для новосибирской школы направлении языков программирования и трансляции. Параллельно с работами по АИСТ- новосибирцами были созданы одни из первых языков системного программирования — Эпсилон и Сигма. Естественным было взаимодействие между этими работами и проектом АИСТ-0 — так, все системное программное обеспечение АИСТа-0 было написано на Эпсилоне.

Языкотворчество осталось хорошей традицией новосибирской школы — позднее новосибирцами был реализован ряд интересных и оригинальных языковых проектов: язык системного программирования второго поколения Ярмо, язык программирования баз данных Бояз, язык параллельного потокового программирования Барс, язык описания и проектирования архитектуры Поляр.

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

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

Для создания подобной системы определяющим было решение трех проблем — разработка общего внутреннего языка как семантического базиса широкого класса входных языков, выработка универсальной схемы языково-независимой оптимизации программ, разработка технологии включения новых входных языков в единую транслирующую систему. Все эти проблемы носили весьма серьезный характер, поэтому проект планировался как комплекс длительных методологических и экспериментальных исследований. Он выполнялся более 10 лет, задание на систему было опубликовано в 1971 г. [10], а итоговая публикация появилась только в 1982 г. [11].

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

Окончательная версия внутреннего языка была создана как объединение абстракций общих понятий и конструкций широкого спектра входных языков с включением не полностью интерпретируемых языковозависимых конструкций. Версия эта была построена на анализе большого числа существовавших тогда языков программирования — Алгола 60, ПЛ/1, Симулы-67, Алгола 68, Паскаля (ФОРТРАН игнорировался изза наличия в нем рудиментарных конструкций, Кобол же по существу никогда не был в поле зрения отечественных программистов), на выделении общностей этих языков — в системе типов, в управляющих конструкциях, на построении абстракций, как отражающих эти общности, так и дающих простор для включения специфических средств данного языка. Вся эта работа была частью общемировых исследований по внутСтановление новосибирской школы программирования ренним языкам и помимо своей конструктивной роли для Бета-проекта обогатила понимание общей содержательной семантики существующих языков программирования.

Оптимизирующая трансляция в системе БЕТА реализуется специальным оптимизирующим процессором, осуществляющим глобальные оптимизирующие преобразования программы на внутреннем языке. Оптимизирующее преобразование понимается как пара — условие применимости преобразования и собственно схема трансформации в терминах внутреннего языка. Условия применимости большинства преобразований существенно используют управляющие и информационные зависимости между операторами программы, поэтому в оптимизирующем процессоре выделяется начальный этап потокового анализа. В результате его работы над операторами внутреннего языка надстраивается гамачно-цикловая иерархическая структура, а каждый оператор и компонента такой структуры снабжаются списками аргументов и результатов. Как условия применимости, так и трансформации определяются в терминах введенной иерархии, кроме того, иерархия используется для факторизации глобальных оптимизаций.

Собственно трансформирующая часть оптимизирующего процессора построена как открытый набор преобразований. Был выбран некоторый порядок их исполнения, дающий наибольший эффект их совместного применения с учетом их взаимозависимости. Ряд оптимизаций был существенно обобщен — чистка циклов реализовывалась не только за счет выноса перед циклом фрагментов выражений, но и за счет выноса как перед, так и после цикла операторов целиком, а также целых гамаков; максимально осуществлялось удаление несущественных операторов, обобщавшее так называемую ликвидацию “мертвого кода”.

Таким образом, в системе БЕТА были развиты в сторону кристаллизации те понятия оптимизирующей трансляции, которые были найдены в Альфа-проектах: внутренний язык стал действительно единым, потоковый анализ был выделен как отдельный фрагмент, да и само выполнение языково-независимых оптимизаций было выделено в отдельную компоненту транслирующей системы, которая могла привлекаться по желанию пользователей.

Технологической целью проекта была максимальная унификация трансляции с различных языков. Общая схема трансляции включала двухпроходную схему получения абстрактной программы на внутреннем языке (декомпозиции), охватывающую лексический, синтаксичеПоттосин И. В. А. П. Ершов и становление новосибирской школы ский и контекстный анализ (язык Ада внес сюда некоторые коррективы), многопроходную работу оптимизирующего процессора, включаемую лишь по специальному запросу, и двухпроходную схему генерации кода. Оптимизирующий процессор не зависит ни от входного, ни от выходного языка — языково-зависимые конструкции внутреннего языка снабжались нужными для оптимизации атрибутами и были в этом смысле частично интерпретируемы. Вначале предполагалось, что как получение абстрактной программы, так и генерация кода будут строиться специальными метапроцессорами по описанию входного и выходного языков соответственно, однако в окончательной версии победил модульный подход. Была сделана библиотека модулей декомпозиции, фактически вводящая обобщенные операции, в терминах которых строились лексический, синтаксический и контекстный анализ для конкретного языка. Точно также была создана библиотека генерации кода, включавшая модули общих для генерации действий — обхода программы на внутреннем языке, назначения регистров (с учетом конкретных параметров архитектуры) и пр. Как показал опыт, общая часть декомпозиции и генерации кода (оптимизация была универсальной) составляла в зависимости от языка от 40% (Ада) до 60% (Паскаль).

В целом этот проект был интересным экспериментом в трансляции программ, по своему размаху превосходящим другие опыты многоязыковой трансляции, существовавшие в мире. Были реализованы Симула 67, Паскаль, Ада и Модула-2, причем два последних языка, не участвовавшие в выработке схемы трансляции и внутреннего языка, достаточно хорошо вписались в систему, что свидетельствовало о надежности принятых в проекте решений. Выходными языками были столь разные языки БЭСМ-6 и СМ-4.

Область трансляции стала традиционной для новосибирцев. Было реализовано множество трансляторов для различных языков — от Сетла до Оберона, традиции многоязыковой трансляции были продолжены в биязыковой системе программирования XDS.

Наряду с исследованиями в различных направлениях системного программирования — и это очень важно отметить — в новосибирской школе велись исследования и по теоретическому программированию, основы которых были заложены А.П.Ершовым. Сознательная его позиция, заключавшаяся в том, что серьезные эксперименты по созданию 38 Становление новосибирской школы программирования систем должны подкрепляться разработкой теоретических моделей и стимулировать эту разработку, была весьма плодотворной.

Опыт в трансляторных проектах вызвал естественный интерес к теории схем программ — как последовательных, так и параллельных. Первыми работами новосибирской школы в этом направлении были работы А. П. Ершова по операторным алгоритмам, прообразам стандартных схем, и по аксиоматике схем Янова, когда предложенная Яновым аксиоматика преобразований была сведена к существенно меньшему числу аксиом. Работы по схемам программ концентрировались вокруг проблем эквивалентности и преобразований схем Янова. А. П. Ершовым и его учениками (В. Э. Иткиным, В. К. Сабельфельдом, Э. Л. Горель) был получен ряд интересных результатов [12]: был найден общий критерий локальности правил преобразований схем Янова, доказана логическая независимость правил преобразования, построена полная система преобразований с отношением тождества, доказана распознаваемость логико-термальной эквивалентности и пр.

Новосибирская школа одной из первых в мире занялась проблемами теории параллельного программирования. В. Е. Котовым и А. С. Нариньяни была предложена одна из первых моделей параллельных программ — недетерминированные асинхронные автоматы. Для этой модели получен ряд важных результатов, связанных с условиями отсутствия конфликтов параллелизма, с преобразованием последовательных программ в параллельные и преобразованиями, увеличивающими внутренний параллелизм — это определяющие проблемы теории параллелизма.

Для коллектива, активно работающего в области трансляции, естественным было обратить внимание на теорию оптимизации программ и на применение этой теории для создания оптимизирующих трансляторов. А.П.Ершовым (совместно с С.С.Лавровым) были заложены здесь основы современной теории экономии памяти [13]. Результаты, полученные при этом, были использованы при построении оптимизирующей части Альфа-транслятора. Был предложен ряд моделей программ, ориентированных на обоснование других оптимизирующих преобразований [14]. Модель линейных схем позволяла обосновывать преобразования, связанные с удалением и перестановкой операторов, что было использовано в системе БЕТА. Модель линейных программ позволила построить оптимальный алгоритм преобразования линейных участков.

Была предложена и более общая модель крупноблочных схем, объединяющая преимущества линейных схем и преобразований, связанных с Поттосин И. В. А. П. Ершов и становление новосибирской школы памятью.

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

А. П. Ершов стимулировал возникновение и еще одного направления работ новосибирской школы — искусственного интеллекта. Г. И. Кожухиным еще в 1959 г. была построена, по-видимому, одна из первых программ по искусственному интеллекту — она на основании знаний путем проб и ошибок строила алгоритм нахождения корней полинома.

Дальнейшие исследования по искусственному интеллекту возглавлялись А. С. Нариньяни, учеником А. П. Ершова. Вначале эти исследования концентрировались вокруг проблем понимания естественного языка и недетерминированного управления шагающим роботом. Решение задач, возникавших здесь, привело к созданию современных направлений исследований — недоопределенности как основе программирования в ограничениях и методологии создания инструментов построения интеллектуальных систем.

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

1. Ершов А. П., Кожухин Г. И.,Волошин Ю. М. Входной язык системы автоматического программирования: предварительное сообщение. — М.: ВЦ АН СССР, 1961. — 176 с.

2. Ershov A. P., Kozhuhin G. I., Voloshin Yu. M. Input language for automatic programming systems. — Acad. Press, London—New York, 40 Становление новосибирской школы программирования 3. Ершов А. П. Основные принципы построения программирующей программы Института математики Сибирского отделения Академии наук CCCP // Сиб.мат. журнал. — 1961. — Т. 2, № 6. — С. 835–852.

4. АЛЬФА-система автоматизации программирования / Под. ред.

А. П. Ершова). — РАН. Сиб.отд-ние. — Новосибирск: Наука, 1967. — 5. The Alpha automatic programming system / (Ed. by A.P.Ershov). — Acad. Press, London—New York, 1971. — 247 p.

6. Аникеева И. Н., Богданова С. Ф., Буда А. О. и др. Система автоматизации программирования АЛЬФА-6 // Системное программирование. — Ч. 1. — Новосибирск, ВЦ СО АН СССР, 1973. — С. 12–23.

7. Ershov A. P., Kozhuhin G. I., Makarov G. P., Nechepurenko M. I., Pottosin I. V. An experimental automatic information station AIST-0 // Proc. of AFIPS Conf.— Vol. 30.— Academic Press, Washington-London, 8. Вишневский Ю. Л., Ершов А. П., Кожухин Г. И. и др. Экспериментальная система коллективного пользования АИСТ-0 // Тр.

2-ой Всесоюзной конф. по программированию. Заседание Н. — Новосибирск, ВЦ СО АН СССР, 1970. — С. 3–14.

9. Поттосин И. В. Структура операционных систем коллективного пользования // Некоторые проблемы вычислительной и прикладной математики. — Новосибирск: Наука, 1975.

10. Ершов А. П. Универсальный программирующий процессор // Проблемы прикладной математики и механики. — М.: Наука, 1971.— С. 103– 11. Ершов А. П., Касьянов В. Н., Покровский С. Б., Поттосин И. В., Степанов Г. Г. Методика разработки многоязыковых трансляторов на примере системы БЕТА // Математическая теория и практика систем программного обеспечения. — Новосибирск, ВЦ СО АН СССР, 12. Ершов А. П. Современное состояние теории схем программ // Проблемы кибернетики. — Вып. 27. — M.: Наука, 1973. — С. 87–110.

13. Ershov A. P. Axiomatics for memory allocation // Acta Informatica. — 14. Поттосин И. В. О математических моделях программ, ориентированных на оптимизацию программ // Proc. YII Nation. School “Mathematical Methods in Informatics”. — Varna, 1981.

КАК А. П. ЕРШОВ СТАЛ ПРОГРАММИСТОМ

А. П. Ершов окончил механико-математический факультет МГУ по кафедре Вычислительной математики в 1954 году. Это был первый выпуск кафедры, для которого читался курс программирования. Лекции читал профессор А. А. Ляпунов.

Кафедра Вычислительной математики была создана на мехмате МГУ в 1949 году. В 1950 году на ней защитили дипломные работы два или три выпускника, а в 1951 году был выпуск этой кафедры по сокращенному учебному плану. Я был среди выпускников этой кафедры 1952 года, которые закончили ее по полному учебному плану. Но курса программирования нам еще не читали. Был у нас только курс по электронным схемам вычислительных машин.

В 1951 году, когда А. П. Ершов заканчивал 2-й курс, он должен был выбрать кафедру для продолжения обучения. И А. П. Ершов записался на кафедру Высшей алгебры. Но в это дело вмешался счастливый случай.

С 1949 года в МГУ регулярно проводилась традиционная легкоатлетическая эстафета на приз газеты “Московский университет”. Дистанция эстафеты проходила от Киевского вокзала до строительства нового здания университета на Ленинских горах и состояла из 14 этапов. Сначала эта эстафета проводилась в последнее воскресенье апреля (в частности, и в 1951 году, хотя в работе [1] ошибочно указана дата 5 мая), позже она стала проводиться в первое воскресенье мая. В 1951 году Андрей и я бежали за первую команду мехмата. После эстафеты мы вместе с ним пошли пешком к Киевскому вокзалу. Он стал расспрашивать меня о нашей кафедре. Зав. кафедрой Вычислительной математики в то время был профессор Б. М. Щиголев (в работе [1], опять-таки ошибочно, указан академик С. Л. Соболев — он стал зав. кафедрой только после переезда в новое здание). Я рассказал Андрею все, что знал об электронных вычислительных машинах (я в то время был уже на 4-м курсе). Особенно большое впечатление на Андрея произвела память на ртутных трубках. Потом мы долго фантазировали о возможностях этих машин. И так были увлечены разговором, что прошли мимо КиевскоСтановление новосибирской школы программирования го вокзала и дошли пешком аж до самого общежития университета на Стромынке (на берегу реки Яуза).

После этого разговора А. П. Ершов забрал свое заявление с кафедры Высшей алгебры и подал его на нашу кафедру. Много лет спустя, в году, даря мне сборник переводов под его редакцией [2], он назовет меня своим “крестным отцом”.

И еще я вспоминаю о его студенческой свадьбе в общежитии, для которой я написал четверостишие (см. ниже). Оно до Андрея так и не дошло (я редко отдавал свои стихи адресатам).

После окончания университета мы с А. П. Ершовым регулярно встречались на различных программистских форумах. Он стал признанным лидером программистов СССР. Но этот период его деятельности хорошо известен, многие об этом уже высказывались. И я вряд ли могу сказать лучше. Но хочу лишь отметить его неизменно доброжелательное отношение к моим выступлениям, далеко не всегда удачным.

1. Карл Левитин. Прощание с АЛГОЛом. — М.: Знание, 1989.

2. Как проектируются и создаются программные комплексы. Сб. переводов под ред. чл.-корр. АН СССР А.П. Ершова. — М.: ИТМ и ВТ АН В моей трудовой жизни были работа и ситуация, о которых я никогда не смогу забыть.

Все началось осенью 1959 года. Наш отдел программирования, возглавляемый Андреем Петровичем Ершовым, территориально размещался в Институте математики им. Стеклова АН СССР. Там нам было выделено несколько комнат, рядом с кабинетом С. Л. Соболева. В этом же здании на 1-ом этаже располагался Вычислительный центр, обслуживавший наряду с сотрудниками Стекловки и нас.

В отдел обратился заказчик, сейчас уж не помню кто, с просьбой найти обратную матрицу для заданной матрицы 436 порядка.

Выбор пал на меня и Вадима Янкова. Исходная матрица была “дырявой”, как сито: очень много нулевых элементов. В поиске алгоритма мы с Вадимом остановились на алгоритме обращения матриц, предложенном в свое время Андреем Петровичем.

Первый этап — написание программы и ее отладка — занял не слишком много времени. На этом этапе работу вели я и Вадим Янков.

Второй этап — подготовка данных — осуществляла уже я одна. Это была трудоемкая работа, долгая и нудная. Тогда я научилась и “читать”, и править информацию на перфоленте: на месте с ошибкой недостающую дырочку пробивать, лишнюю — заклеивать. Главное — точно локализовать то место, куда следовало приложить руку в прямом смысле этого слова.

Третий этап — собственно счет по отлаженной программе — начался где-то весной 1960 года.

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

Андрей Петрович в это время был в отъезде. С разрешения того, кто его замещал по Отделу (кажется, Гены Кожухина), я с чистой совестью уехала отдыхать. К тому времени было сделано несколько десятков “шагов” по пути приближения к желанной обратной матрице.

44 Становление новосибирской школы программирования В положенное время я появилась на работе. И тут грянул гром! Андрей Петрович узнав, что матрица все еще не обращена, что вместо того, чтобы в поте лица трудиться, я разъезжаю по гостям, он в первый (и слава Богу в последний!) раз в моей жизни, не повышая голоса (но металл в голосе был явно!), сделал строгий выговор за то, что личные интересы я поставила выше производственных! И это несмотря на симпатию, которую я всегда чувствовала по отношению к себе.

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

Счет шел на отечественной машине БЭСМ-2. Хотя она для того времени и была на высоте, но ее быстродействия и надежности для решения больших задач было, конечно же, недостаточно.

Времени просили много. Его давали, но как правило ночью. Благо, жили мы тогда уже в Черемушках, до работы пешком минут 15–20.

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

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

“Быстро сказка сказывается, да не скоро дело делается!” В октябре я поняла, что в июне 1961 года стану мамой. Все наши уезжали в Академгородок с намерением заняться транслятором с Алголаизучение которого началось еще в Москве на семинарах Отдела. А я и Софья Давыдовна Тартаковская, определенная мне в помощники, оставались в Москве — заканчивать обращение надоевшей матрицы.

Ничего нового и интересного в этой работе уже не осталось, надо было только добить, дожать до конца все 436 итераций.

В начале апреля 1961 года я ушла в декретный отпуск. К тому времени из 436 итераций были просчитаны более 410.

Но “чем дальше в лес, тем больше дров”! Каждая следующая итерация давалась с большим трудом — машина сбивалась, и опять надо было повторять просчет. Не была готова БЭСМ-2 ни по памяти, ни по быстродействию для решения таких громоздких задач. Важно было иметь длительный период стабильной работы, без сбоев.