НАКОПЛЕНИЕ ОПЫТА И РАЗВИТИЕ ЗНАНИЙ (1956-1959 гг.)

Итак, практикующие программисты и студенты имели в 1956 г. в своем распоряжении пять методов программирования конкретных задач:

1) операторный метод с использованием программирующих программ [28]; 2) метод библиотечных программ [27]; 3) символическое кодирование (изложенное впервые А.И. Китовым [33] со ссылкой на работы, выполненные для ИБМ-701 [37]); 4) крупноблочное программирование по Л.В. Канторовичу [28]; 5) "ручное" программирование с 8- или 16-ричным кодированием машинных программ и с использованием блок-схем или операторных логических схем в качестве неформального подспорья.

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

С этой точки зрения было важно расширить фронт работ и, в частности, пережить опыт разработки и использования библиотеки стандартных подпрограмм. Последнее направление получило особое развитие в Вычислительном центре МГУ, где в итоге интенсивной двухлетней работы была создана развитая библиотека подпрограмм, основная часть которой была опубликована в 1958 г. в монографии [38]. Вот как авторы объяснили свои цели: " Одним из путей автоматизации программирования является путь использования библиотеки стандартных подпрограмм. Сущность этого метода заключается в том, что для наиболее часто встречающихся алгоритмов раз и навсегда тщательно составляются подпрограммы, которые затем могут быть использованы в качестве готовых частей программы при решении любой конкретной задачи, где требуется реализация соответствующих алгоритмов. Это дает существенную экономию труда программиста.

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

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

1958 год вообще был урожайным на публикации по программированию. В издательстве АН СССР вышло описание транслятора ЦП БЭСМ [39], которое содержало изложение операторного метода, описание входного языка и основных алгоритмов трансляции, а также подробные блок-схемы транслятора.

В этом же году вышел первый выпуск известной "красной серии", основанной А.А. Ляпуновым, под названием "Проблемы кибернетики". В этой серии были опубликованы, в частности, статьи, содержащие полное описание транслятора ПП-2 ([42]. п. 2-6),а также изложение работы А.А. Ляпунова, приведшей к операторному методу. Эта работа была выполнена А.А. Ляпуновым в 1952-1953 гг. ([42], п. 1).

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

Группа сотрудников Вычислительного центра разработала транслятор ППС для ЭВМ "Стрела-З" [40], [41], более совершенный, чем транслятор ПП БЭСМ (см. табл. 2. п. VIII). В этом трансляторе, в частности, были введены более естественные обозначения для операторов циклов и для условий в логических операторах. Имелась возможность в весьма суженных пределах задавать описания процедур-функций при условии, что телом процедуры являлось выражение или машинная программа.

Когда в 1956 г. ЭВМ "Стрела-4" появилась в Вычислительном центре МГУ. там уже сложилась методика программирования на М-2 (обсуждавшаяся авторами в начале этого раздела). Ее естественным развитием стала концепция интегрированной системы автоматизации программирования, в которой транслятор был бы лишь одной из компонент. Таким образом, кроме транслятора, разработанного под руководством Н.П. Трифонова, система содержала библиотеку стандартных подпрограмм, разработанную Е.А. Жоголевым "составляющую программу", представляющую собой комбинацию простого ассемблера с загрузчиком, и серию отладочных программ. Система автоматизации программирования была подробно описана в сборнике, вышедшем в 1961 г. [43].

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

Выходом транслятора был стандартный модуль загрузки. Входной язык транслятора во многом следовал стилю ПП-2, хотя уже не требовал строгого разделения на схему программы и на спецификацию операторов. В трансляторе был реализован в некотором объеме аппарат макроопределений, в котором тело макроса обозначило некоторую "подсхему" задачи, подставляемую предпроцессором на место сокращенного обозначения подсхемы. Таким аппаратом в трансляторе реализовывались операторы цикла, которые во входном языке трактовались как "обобщенные операторы", т. е. сводимые к базисным.

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

Элементы символического кодирования можно усмотреть уже в первых трансляторах ПП-2 и ПП БЭСМ. Текст программы на входном языке мог содержать так называемые "нестандартные операторы", представляющие собой фрагменты машинных программ, где в адресных частях могли находиться имена величин. Однако система символического кодирования, так сказать, в чистом виде появилась сравнительно поздно -- в 1957 г. для ЭВМ "Стрела" и в 1959 г. для М-20 ([44]. п. 4, [46]).

Начиная с 1955 года, сотрудниками Института математики АН УССР (Киев) В.С. Королюком и Е.Л. Ющенко был осуществлен важный цикл исследований, связанных с понятием адресного программирования. Введение в рассмотрение функции именования [47] и обратной функции разыменования позволило использовать на уровне абстрактных алгоритмов операции взятия значения по адресу, рассмотрения значения как адреса другого значения (косвенная адресация) и засылки значения по вычисленному адресу. Указанные функции были названы адресными. С их помощью точно вписываются такие аспекты управляющих действий в программах, как настройка программы на место в памяти, вычисляемый переход, индексная арифметика, переадресация и формирование адресов, например при вызове параметра подпрограммы по адресу [48], [49]. В результате получился своеобразный язык программирования с операторами присваивания, с выражениями, содержащими только скалярные величины, и условиями перехода по предикатам и значениям адресных функций. С некоторыми расширениями этот язык был положен в основу целого семейства трансляторов, разрабатывавшихся в течение ряда лет в Киеве под руководством заведующей отделом программирования сначала Вычислительного центра, а затем Института кибернетики АН УССР Е.Л. Ющенко [49]. В одной из первых версий такого транслятора, сделанного для ЭВМ "Киев" (первая крупная ЭВМ, спроектированная вслед за МЭСМ сотрудниками Вычислительного центра АН УССР в 1956-1958 гг.), впервые в качестве достоинства отмечалась однопроходная схема трансляции, а для записи выражений использовалась обратная польская запись [51].

В рамках крупноблочного программирования была создана серия экспериментальных прикладных программ, главным образом в лаборатории приближенных вычислений ЛОМИ. В этих системах получили определенное развитие принципы оперирования со структурными объектами: использование вырезок в работе с массивами ([52], п. 1), "геометрические операции" композиции массивов и теоретико-множественные операции над ними ([52], п. 2), а также были реализованы правила аналитических выкладок над некоторыми объектами анализа, в частности весьма развитая система для работы с полиномами ([52], п. 5).

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

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

В 1953 г. ШБ предложил метод прокрутки, реализованный тогда же для "Стрелы" Э.З. Любимским.

В ПП-2 В.С. Штаркман реализовал применяемый и сейчас метод экономии рабочих ячеек на линейном участке программы, основанный на возвратном просмотре команд этого участка ([42], п. 6).

В ПП-2 был также реализован метод вычисления логических выражений в виде последовательности логических проверок с передачей управления сразу, как только становится ясным значение еще недовычисленного выражения ([42], п. 3).

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

В ЦП БЭСМ была реализована универсальная система построения операторов цикла с рядом оптимизаций (контроль числа повторений по переменной команде, совмещение восстановления по внутреннему параметру с переадресацией по внешнему и т. д.) [39].

При программировании циклов в ПП БЭСМ применялся метод, получивший впоследствии название метода решающих таблиц. Имелось 12 способов реализации зависимости переменного адреса от параметра, -- выбор их проводился по таблице решений, входом в которую были значения четырех двоичных признаков [39], [49], [50].

В ПП-2 осуществлялась экономия совпадающих выражений в пределах выражения, а в ЦП БЭСМ-в пределах линейного участка.

В трансляторе МГУ был реализован алгоритм экономии совпадающих выражений в пределах линейного участка с учетом альтернативных ветвей в условных выражениях (допускавшихся в этом трансляторе), ассоциативности операций и перемены знака выражений [43].

В трансляторе ЛИС был реализован частичный синтаксический контроль с использованием матрицы попарной сочетаемости элементарных символов входной программы [40].

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

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

ШБ в 1952 г. предложил универсальный способ манипулирования с множествами, являющимися подмножествами некоторого генерального занумерованного множества . Любое такое множество изображается двоичным вектором , где , а остальные равны нулю. Такой вектор получил название логической шкалы. Пересчет и теоретикомножественные операции над множествами в таком представлении удобно сводились к машинным операциям сдвига нормализации и поразрядным логическим операциям [33].

В ЦП БЭСМ АЕ выдвинул в качестве общего правила принцип "адресной кодировки" различных объектов, с которыми приходится иметь дело при трансляции. При такой кодировке всюду, где это имеет смысл, объект кодируется адресом ячейки, содержащей информацию об этом объекте. Такая кодировка существенно сокращает время поиска информации и хорошо соответствует структуре оперативной памяти с произвольным доступом ([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, то ему было суждено сыграть в развитии программирования в СССР весьма важную роль. Он явился своего рода центром кристаллизации новой ситуации в программировании, которая созревала в Советском Союзе в преддверии второго поколения ЭВМ.