Добавлен: 22.04.2023
Просмотров: 169
Скачиваний: 1
В ЦП БЭСМ АЕ выдвинул в качестве общего правила принцип "адресной кодировки" различных объектов, с которыми приходится иметь дело при трансляции. При такой кодировке всюду, где это имеет смысл, объект кодируется адресом ячейки, содержащей информацию об этом объекте. Такая кодировка существенно сокращает время поиска информации и хорошо соответствует структуре оперативной памяти с произвольным доступом ([28], п. 3).
Мы уже упоминали о введенной Л.В. Канторовичем концепции дескриптора (справки) как объекта фиксированного формата, концентрирующего в себе описание способов доступа к компонентам динамического структурного объекта (величины) ([28], п. 4).
В 1957 г. АЕ независимо, хотя и позже сотрудников ИБМ, придумал функцию расстановки как способ беспереборного поиска информации по ключу, исследовал экспериментально ее статистические свойства и применил для алгоритма экономии команд, работающего за линейное время [53].
В 1957 г. Л.Н. Королев в рамках экспериментов по машинному переводу, выполнявшихся в ИТМиВТ, разработал метод ускорения ассоциативного поиска в файлах словарного типа, а также способы сжатия ключевых слов без потери однозначности [54], [55].
В конце 50-х годов группа московских математиков занялась вопросом программирования шахматной игры. Через 16 лет эти исследования завершились выигрышем 1 Всемирного чемпионата шахматных программ, происходившего в Стокгольме в 1974 г. во время Конгресса ИФИП. Одной из важных компонент последовавшего успеха были глубокое изучение вопросов организации информации в памяти ЭВМ и разработка эвристик поиска, требующего перебора. Г.М. Адельсон-Вольский и Е.М. Ландис изобрели двоичное дерево поиска (дихотомическая справочная) [56], а А.Л. Брудно независимо от Дж. Маккарти придумал -эвристику для сокращения перебора на дереве игры [57].
В обсуждаемый период времени в Советском Союзе были выполнены работы, развитие которых привело к созданию теории схем программ [31], [32].
В 1958 г. состоялись первые личные контакты советских программистов с американскими и английскими коллегами. В июне 1958 г. по приглашению проф. Дж.В. Карра III в США для участия в летней школе Мичиганского университета прибыла делегация из СССР, возглавляемая академиком А.А. Дородницыным. Л.Н. Королев, бывший членом делегации, выступил с лекцией, в которой дал краткий обзор советских работ по трансляторам [61].
В ноябре 1958 года АЕ в составе советской делегации по автоматизации выступил на известной конференции по механизации процессов мышления в НФЛ в Теддингтоне. Там он встретился с Джоном Бэкусом и Грэйс М. Хоппер. Темой доклада АЕ были обзор трансляторов, разработанных в Вычислительном центре АН СССР 1621, а так же изложение некоторых результатов по теоретическому программированию. Сокращенное изложение доклада позднее появилось в журнале "Дейтамейшин" [63].
В августе 1958 года в Советский Союз с ответным визитом прибыла американская делегация из четырех человек, возглавляемая проф. Дж.В. Карром. Проф. Карр выступил с докладом о новой американской машине СТРЕТЧ, а проф. Алан Перлис привез "свежеиспеченное" предварительное сообщение о продукции совместного Германа американского комитета: проекте алгоритмического языка АЛГОЛ [64], получившего позднее название АЛГОЛ 58.
В результате этих контактов советские программисты познакомились с серией первых американских систем программирования, описание которых было издано в русском переводе в 1961 г. [65].
Что же касается АЛГОЛА 58, то ему было суждено сыграть в развитии программирования в СССР весьма важную роль. Он явился своего рода центром кристаллизации новой ситуации в программировании, которая созревала в Советском Союзе в преддверии второго поколения ЭВМ.
НОВЫЕ РУБЕЖИ (1959-1963 гг.)
В течение шестой пятилетки в пределах доступных ресурсов проходила интенсивная работа по конструированию ЭВМ. В дополнение к первым ЭВМ (табл. 1) появилось еще по крайней мере восемь типов ЭВМ, не считая воспроизведений по документации (см. табл. 2). За исключением ЭВМ "Урал-2" и М-20, роль остальных разработок была промежуточной. Одни были индивидуальными разработками типа "сделай сам" (ГИФТИ, ЦЭМ-1), другие -- промежуточным этапом в поисках основного направления разработок ("Киев"), третьи носили экспериментальный характер ("Сетуй"). В основном же, если не считать попутного освоения ферритовой памяти, эти модели стали своего рода ламповыми прототипами поколения полупроводниковых машин.
В ноябре 1959 года в МГУ состоялось Всесоюзное совещание по вычислительной математике и вычислительной технике. Несмотря на скромное название, это было грандиозное научное собрание, на котором присутствовало почти 2000 участников и на четырех секциях [44] было прочитано 217 докладов. К сожалению, организаторам не удалось собрать доклады и издать труды совещания.
На пленарном заседании ШБ и АЕ было поручено выступить с обзорным докладом "Современное состояние автоматизации программирования". Доклад был сделан, однако справедливости ради следует признать, что единого взгляда на проблематику в этот момент выработать не удалось.
К концу 50-х годов у каждого из авторов сложилась своего рода программа деятельности на будущее. Их взгляды нашли свое частичное выражение в ряде работ (в том числе и в представленных на этом совещании [45], [66]). Дело, однако, не столько в самих работах, сколько в контексте, определявшем подход авторов.
ШБ довелось принять участие в проектировании логической структуры ЭВМ М-20. Нужно отметить, что это была одна из немногих моделей ЭВМ, при создании которой объединились проектанты, конструкторы и математики, представленные ИТМиВТ, конструкторским бюро, создавшим машину "Стрела", и МИАНом. Эта солидная основа возлагала большую ответственность на разработчиков, поскольку машине (точнее, ее архитектуре) предстояло воплотиться в нескольких крупных сериях (М-20, БЭСМ-ЗМ, БЭСМ-4, М-220, М-220М. М-222). В частности, масштабы использования средств программирования возрастали не измеримо и сложившиеся прецеденты накопления натурального программного хозяйства, еще кое-как приемлемые для уникальных научных вычислительных центров, уже совершенно не годились для будущей машины. По степенно складывалась концепция "математического обеспечения" -- интегрированной и удобной в работе системы различных средств программирования (библиотеки, трансляторы, средства отладки), сопряженной с определенной дисциплиной прохождения задач на машине. Для ШБ важными предпосылками для формирования такой философии были экспериментальные системные, проекты в Вычислительном центре МГУ [38], [43], а также повседневный опыт организации производственных вычислений в МИАНе, требовавших большой четкости и высокой надежности работы как оборудования, так и программ.
На пути к полному пониманию проблемы математического обеспечения ЭВМ, не говоря уже о ее решении в сколько-нибудь полном объеме, было много препятствий как научно-технического, так и организационного характера, в частности слабая разработанность концепции программного продукта. Опыт работы с машинами "Стрела" отчетливо показал, что дивергенция средств программирования в целом неизбежна, если не будет единой и нерушимой основы, сооружаемой непосредственно на "голой" машине. Для М-20 в то время такой основой была библиотека стандартных подпрограмм. Идея превращения библиотеки в переносимый и общий программный продукт стала для ШБ главной задачей, на решении которой со временем сформировались более общие взгляды на программное обеспечение. ИС-2 стала своего рода мини-ОС, обеспечивающей "в последней инстанции" определенную однородность строения исполняемых программ.
Что же касается второго соавтора пленарного доклада, то следует отметить, что АЕ интересовали в то время совершенно другие проблемы. Продолжая работать над трансляторами и их входными языками [65], он стремился увлечь своих новых сотрудников довольно амбициозным проектом "Сибирского языка программирования" [66].
Нетрудно понять, что эти два взгляда, хотя и объективно обусловленные, находились, так сказать, в разных плоскостях, что, кстати, и проявилось во время дискуссий на совещании. Необходимо было найти некоторый объект конструирования и научной работы, который бы одновременно решал задачу унификации математического обеспечения, мог быть эффективным средством программирования и выдвигал новую научную проблематику. Таким объектом стал Алгол 60.
Как уже упоминалось, первое знакомство с проектом западногерманских и американских специалистов состоялось в августе 1958 года, когда А. Перлис привез предварительную версию публикации [64] в СССР. Первыми ее читателями были сотрудники Вычислительного центра АН СССР, работавшие в то время над транслятором ЛИС [41], и начальная группа сотрудников будущего Вычислительного центра Сибирского отделения АН СССР. Общая схема языка была положена в основу проекта "Сибирского языка" -- системы программирования для М-20. В то же время стала совершенно очевидной общенаучная ценность документа [64], что требовало его широкого распространения. Не дожидаясь публикации сборника переводов [65], описание АЛГОЛА в переводе АЕ было издано Вычислительным центром и распространено на ноябрьском совещании 1959 г. [67].
Тем временем усилия международного коллектива ученых завершились выработкой законченной спецификации нового алгоритмического языка. Редактор "Сообщения об алгоритмическом языке АЛГОЛ 60" [68] Потер Наур поддерживал контакт с советскими коллегами, что позволило уже в марте 1960 года подготовить для публикации перевод сообщения, выполненный Г.И. Кожухиным. Этот перевод был опубликован в мае 1960 года в издательстве Вычислительного центра АН СССР, а через год -- в новом "Журнале вычислительной математики и математической физики" [69].
Ситуация весной 1960 года оказалась весьма благоприятной для принятия АЛГОЛА 60 в качестве единого языка программирования научных и инженерных применений ЭВМ. Авторы уже говорили об общих предпосылках к унификации языка. АЛГОЛ 60 не только обладал очевидными достоинствами, выдвигая в то же время интересную научную проблематику, но и, будучи международным "комитетским" языком, ставил в равную позицию любую индивидуальную оценку языка, отодвигая тем самым на второй план субъективные или "вкусовые" точки зрения. Другим благоприятным моментом было отсутствие инерции, поскольку количество "Стрел" и БЭСМ не шло ни в какое сравнение с потоком выпускаемых машин типа М-20.
В июне 1960 года в Вычислительном центре АН СССР состоялось координационное совещание по вопросам реализации АЛГОЛА 60. На фоне общей и во многом разнонаправленной активности выделились три проекта реализации языка для М-20, руководимые С.С. Лавровым, ШБ и АЕ и получившие соответственно названия ТА-1, ТА-2 и Альфа. Начавшись как три независимые и подчас конкурирующие разработки, эти проекты в процессе своего развития приобрели взаимодополняющие свойства, решив в целом удовлетворительно проблему снабжения М-20 трансляторами с АЛГОЛА 60.
ШБ попытался решить проблему унификации конкретного представления с тем, чтобы достичь совместимости трансляторов по входу. К сожалению, технические различия во взглядах возобладали и в полном объеме решить проблему не удалось. Серьезным препятствием на этом пути стало отсутствие у М-20 стандартного буквенно-цифрового оборудования для ввода и вывода, что побудило разработчиков и пользователей временно решать эту проблему каждый по-своему. Кроме того, разгон, взятый АЕ в разработке "Сибирского языка", оказался слишком велик, чтобы остаться в рамках АЛГОЛА 60. Проект был адаптирован таким образом, чтобы стать расширением АЛГОЛА 60, и в таковом качестве он получил название "Входного языка" [70], а в его конкретном представлении -- Альфа-языка. Наиболее существенным расширением было введение комплексных и многомерных величин в качестве аргументов и результатов основных операций, а также операций формирования и членения таких величин.
В то же время все три транслятора базировались на системе ИС-2 для обращений к стандартным подпрограммам.
22-24 декабря 1960 года в МГУ состоялась рабочая конференция "Построение программирующих программ на основе языка АЛГОЛ". К этому времени у разработчиков уже сложились общие подходы к реализации языка и выбору схем трансляции. В ТА-1, благодаря отказу от возможной рекурсивности процедур и ряду других ограничений, была выбрана компактная и быстрая схема трансляции без оптимизации. Главной задачей ТА-2 стала реализация практически полного языка без существенной потери в качестве реализации. В разработке системы Альфа было поставлено в качестве главной цели обеспечение высокого качества рабочих программ с сохранением приемлемой скорости трансляции ([79], стр. 264). В докладе разработчиков системы Альфа был создан, можно сказать, классический прецедент просчета в определении плановых показателей больших программных работ с универсальным коэффициентом недооценки 2-3, подтвержденным впоследствии многими проектами: авторы отводили разработке системы 15 человеко-лет для построения 15000 команд, затратив на самом деле свыше 30 человеко-лет и соорудив систему в 45000 команд ([79], стр. 64).
В дальнейшем на технические решения разработчиков оказали существенное влияние материалы проходившей почти одновременно в США конференции по методам трансляции с АЛГОЛА 60, многие доклады которой были опубликованы в одном из самых известных среди программистов выпусков журнала Эй-Си-Эм Коммьюникейшенз [71]. Общественное признание АЛГОЛА 60 нашло свое выражение в обзорном докладе ШБ и АЕ "Машинные языки и автоматическое программирование", с которым они выступили на пленарном заседании IV Всесоюзного математического съезда, состоявшемся в Ленинграде в июле 1961 года [72].
Параллельно работам по АЛГОЛУ 60 развивались события, приведшие к организации ассоциации пользователей ЭВМ М-20. Уже на июньское совещание по АЛГОЛУ 60 были приглашены представители организаций, использующих М-20, чтобы решать вопросы реализации с учетом общественного мнения пользователей. На декабрьской конференции 1960 года по реализации АЛГОЛА 60 среди участников была распространена информация о предстоящем учредительном собрании членов ассоциации, которое состоялось в начале 1961 года. ШБ был избран председателем совета ассоциации.
В июле 1961 года ассоциация решением Президиума Академии наук СССР получила статус юридического лица и официальное название "Комиссия по эксплуатации вычислительных машин М-20".
Деятельность Комиссии была важна не только созданием прецедента, за которым последовало создание аналогичных ассоциаций для БЭСМ-2, серии "Урал", а чуть позже -- для серии "Минск", но и ускорением разработки концепции математического обеспечения -- термина, вошедшего в употребление в 1963 г. Несколько забегая вперед, заметим, что библиотека программ ИС-2, трансляторы ТА-1 и ТА-2 стали первыми образцами программного продукта, которые поставлялись вместе с оборудованием заводом-изготовителем, образуя интегрированную систему программирования.
Тем временем приближалась к концу разработка трансляторов с АЛГОЛА. Отчетные публикации появились для ТА-1 и ТА-2 в начале 1964 года [73], [74], для системы Альфа -- годом позже [75], [76].
Охарактеризуем кратко технические результаты по методам трансляции, полученные при выполнении этих работ.
В трансляторе ТА-1 была реализована разработанная Г.М. Заикиной и С.С. Лавровым общая схема программирования выражений с помощью стека, использующая трактовку знака операций как обобщенных парных ограничителей и разделителей [73].
В трансляторе ТА-2, как уже отмечалось, был реализован практически полный АЛГОЛ 60, впервые был систематически применен метод таблично-управляемой генерации машинных конструкций операторов языка, реализован новый алгоритм реализации рекурсивных процедур, не требующий размножения "санков" [77]; в пределах, допустимых оборудованием М-20, было реализовано поле "математической памяти" со сплошной адресацией, включая как оперативную, так и внешнюю памяти [78].