А.А.ЛЯПУНОВ И СТАНОВЛЕНИЕ ТЕОРЕТИЧЕСКОГО ПРОГРАММИРОВАНИЯ В РОССИИПодловченко Р.И. Московский государственный университет, Москва, Россия Алексей Андреевич Ляпунов вошёл в историю естество знания XX века как исследователь с богатым творческим на следием и как гражданин, чьё нравственное наследие заслу живает пристального внимания и самостоятельного изучения. Значительность вклада А.А.Ляпунова в компьютеризацию науки давно признана в нашем отечестве. Первым шагом в ме ждународном признании заслуг А.А. Ляпунова в этой области было присуждение ему в 1996 году медали “Computer Pioneers”, одной из самых авторитетных профессиональных организаций в сфере высоких технологий - IEEE Computer-Society. Напомним, что IEEE (The Institute of Electrical and Electronics Engineers) как международное сообщество существует более ста лет. В 1946 году в нём было основано структурное подразделение Computer Society, объединяющее сотни тысяч профессионалов, работающих в области информатики, программирования, вычислительной техники и компьютерного бизнеса. Медаль “Computer Pioneers” является самой престижной наградой Computer Society. Она была учреждена в 1981 году. В число лауреатов этой почётной награды вместе с А.А. Ляпуновым во шли Виктор Михайлович Глушков и Сергей Алексеевич Лебедев. На лицевой стороне медали изображён Чарльз Бэббидж. Оборотную сторону медали, присуждённой А.А. Ляпунову, украшает надпись: "Компьютерное общество признало А.А. Ляпунова основателем советской кибернетики и программирования". Мы надеемся, что обсуждение вклада европейцев в развитие компьютерных технологий явится следующим шагом в международном признании заслуг А.А. Ляпунова в данной области. Прежде всего - небольшая биографическая справка. А.А. Ляпунов родился в I911 году в Москве. Проучился полтора года на физико-математическом факультете МГУ и был отчислен как "лицо дворянского происхождения". Математическое образование получил под непосредственным руководством Н.Н. Лузина. Экзамен по университетским курсам сдал экстерном. Кандидатскую и докторскую диссертации защитил в области теории множеств. В Великую Отечественную войну, отказавшись от брони, добровольцем ушел на фронт и с марта 1942 года по апрель 1945 года находился в артиллерийских частях. Из армии отозван в Артиллерийскую Академию для преподавания математики. С 1951 года работал в Институте математики им. Стеклова и во вновь образованном его Отделении прикладной математики, куда перешёл по приглашению М.В. Келдыша и где возглавил отдел программирования. С 1952 года профессор кафедры вычислительной математики МГУ. В 1962 году переехал в Новосибирский академгородок. Работал там в отделе кибернетики Института математики СО АН, в последние годы руководил лабораторией кибернетики в Институте гидродинамики СО АН. В 1964 году избран членом-корреспондентом АН СССР по отделению математики. Скончался на 62-ом году жизни в Москве. Алексей Андреевич был не только большим учёным, но и редким явлением духовной культуры. В духовном же мире ни что не возникает из ничего. Алексей Андреевич принадлежит к древнему роду, берущему начало от князя Константина Галицкого, брата Александра Невского. Этот род вписал немало славных страниц в отечественную историю. А с начала прошлого века он прочно вошёл в мир созидателей духовной культуры. Упомянем два имени из этого мира: академика А.М. Ляпунова - известного математика и академика А.Н. Крылова -знаменитого кораблестроителя. Для первого из них Алексей Андреевич - внучатный племянник, для второго - племянник. Родственными отношениями, которые подкреплялись глубокой духовной близостью, род Ляпуновых связан с Сеченовыми, Филатовыми, Намёткиными, Капицами, Сперанскими, Фигнерами... Широта научных интересов Алексея Андреевича в значительной мере обусловлена средой, в которой он рос. К настоящему времени мы располагаем доступными публикациями основных трудов Алексея Андреевича. В их числе труды по теории множеств, общим вопросам кибернетики, программированию и его теории, машинному переводу и математической лингвистике, кибернетическим вопросам биологии, философским и методологическим проблемам науки. За пределами этого перечня остаются многочисленные работы по приме нению математических методов в различных областях естествознания - математической статистике, теории стрельбы, то пографии, геофизике, биологии и других. Математизация науки - это постоянное стремление Алексея Андреевича. Вместо с тем феномен Алексея Андреевича не раскрывается его опубликованными работами. Алексей Андреевич был учёным - проповедником, он любил живое общение с людьми, мало заботился о публикации своих научных идей. Их впитали его ученики и современники, воплотив в конкретные результаты. Трудно оценить, сколь много учёных обязаны Алексею Андреевичу своими научными интересами. От научной деятельности Алексея Андреевича неотделима его деятельность гражданина, пробивающего дорогу новым научным направлениям. В первом ряду таких направлений находится кибернетика. Непосредственно кибернетикой Алексей Андреевич стал заниматься в начале пятидесятых годов. К этому времени, он был сложившимся учёным, известным своими работами и имеющим опыт применения математического аппарата в недостаточно формализованных областях науки. Кибернетика была провозглашена Н. Винером как наука об управлении. Н. Винер ввёл и само понятие "управление" как самостоятельную категорию. Однако для всех, ознакомившихся с работой Н. Винера, было ясно, что кибернетику как науку ещё предстоит создавать: сформулировать предмет исследования, описать проблематику, выработать терминологию. Значительная часть этой работы проделана Алексеем Андреевичем. Его называют отцом отечественной кибернетики и с полным на то правом можно назвать одним из основоположников кибернетики вообще. Работы в области кибернетики начались борьбой Алексея Андреевича за её существование. Дело в том, что в те годы малоизвестная в нашей стране кибернетика носила ярлык "буржуазной науки", и чтобы создать условия для развития кибернетики, надо было его снять. Алексей Андреевич проводит большую разъяснительную работу: он убеждает людей разного научного и служебного ранга в неверности официального суждения о кибернетике, проводит многочисленные лекции и беседы об истинном содержании кибернетики, наконец, совместно с С.Л. Соболевым и А.И. Китовым публикует в "Вопросах философии" обстоятельную статью о том, что составляет предмет кибернетики, и сколь важным является её развитие для прогресса науки и укрепления государства. Алексей Андреевич организует кибернетический семинар в МГУ, добивается издания "Кибернетических сборников", в которых помещаются переводы наиболее значительных работ в теоретической кибернетике (сборники выходят под редакцией А.А. Ляпунова и О.Б. Лупанова), добивается перевода книги Н.Винера, договаривается об издании "Проблем кибернетики", сборников, где публиковались бы отечественные работы (под редакцией Алексея Андреевича вышли 29 сборников). При Президиуме АН СССР создаётся Совет по кибернетике под руководством А.И. Берга, и Алексей Андреевич становится его заместителем. К задаче изучения вычислительной машины и процесса программирования на ней Алексей Андреевич приходит, отталкиваясь от задач кибернетики в целом. Он говорит: "основным вопросом, в связи с которым формируется кибернетика, является вопрос о взаимоотношении возможностей вычислительной машины и мышления. Это - тот вопрос, вокруг которого группируется тематика кибернетики и на почве которого возникают её различные задачи". Научная деятельность Алексея Андреевича в кибернетике началась с создания операторного метода программирования. Так был назван метод, сочетавший в себе определение языка программирования - языка логических схем и описание на нём приёмов программирования. Операторный метод вырастал на глазах студентов молодой кафедры вычислительной математики, незадолго до того организованной на механико-математическом факультете МГУ. Это происходило в курсе восьми лекций под названием "Принципы программирования", прочитанном Алексеем Андреевичем в 1952/53 учебном году. Курс был новаторским во всём. В основе операторного метода лежал принципиально но вый подход к описанию алгоритма. Отмечалось, что традиционные языки теории алгоритмов, такие, как машины Тьюринга, продукции Поста, нормальные алгоритмы Маркова, рекурсивные функции и т.п., хороши для исследования природы вычислимости, но непригодны для описания алгоритма в форме, удобной для решения практических задач. В операторном методе нашла реализацию идея "крупноблочного" описания алгоритма, открывающая путь к новым формализациям понятия ал горитм. Задачу строгого описания новой формализации, которое бы сопровождалось доказательством её адекватности традиционным языкам теории алгоритмов, Алексей Андреевич по ставил перед своим аспирантом А.П. Ершовым, и она была решена в его кандидатской диссертации. В новом подходе к описанию алгоритма выразился вклад Алексея Андреевича в теорию алгоритмов. Язык логических схем вырос из бытующего в то время блок схемного описания программы. Такое описание предписывало перед программированием алгоритма деление его на части блоки с установлением связи между ними. Однако понятие самого блока было расплывчатым, а поэтому не могли быть чётко описаны ни правила выделения блоков, ни правила их сочленения. Язык логических схем был нацелен на устранение этих недостатков. В нём выделение частей алгоритма осуществляется по признаку функциональной нагрузки, несомой в алгоритме той или иной его частью. Так появились понятие оператора, осуществляющего акт переработки информации, и понятие логического условия, которое воплощает акт проверки информации, чтобы определить порядок выполнения опера торов. Логическая схема, описывающая алгоритм, представляет собой строку из операторов и логических условий, снабжённых стрелками перехода. Выполнение логической схемы осуществляется применением к ней универсальной процедуры и демонстрирует фактическое использование всех средств композиции операторов. Язык логических схем стал первым языком, позволившим говорить об общих приёмах программирования. При изложении их сразу выявилась задача перехода от описания алгоритма на этом языке к построению программы. В рамках операторного метода были предусмотрены следующие этапы перехода: от схемы счёта - к схеме программы, от схемы программы - к самой программе. С позиции современных языков программирования этот процесс можно трактовать следующим образом. Первоначально программируемый алгоритм описывается схемой счёта, которая синтезируется из фрагментов, фактически являющихся операторами циклов. Схема программы строится по схеме счёта путём замены операторов цикла эквивалентными им композициями простых операторов, таким образом появляются операторы и логические условия, "управляющие" счётом. Трансляция схемы программы в программу следует необходимости линеаризовать массивы, используемые в алгоритме. По твёрдому убеждению Алексея Андреевича, трансляция схемы счёта в машинную программу - это акт, который может и должна выполнять сама ЭВМ. Так появилась задача построения программирующей программы, призванной реализовать этот акт. Над отдельными её блоками трудились первые дипломники Алексея Андреевича, слушатели его легендарного курса "Принципы программирования". Как развивалась эта деятельность - тема отдельного доклада на данном симпозиуме. Задача трансляции с языка высокого уровня на машинный язык была стержневой в операторном методе - вокруг неё складывалась проблематика программирования. В неё во шли такие задачи, как оптимизация схемы счета и функциональная корректность перехода от неё к схеме программы, а от последней - к самой программе. Они потребовали введения отношений эквивалентности как между схемами одного, -так и между схемами разных типов, разработки эквивалентных преобразований схем, построения применяющих их алгоритмов и так далее: одни задачи порождали другие. С момента появления операторного метода на нём базировались как обучение, так и исследовательские работы в программировании. Этому способствовали открытые для широкой общественности семинары, которые Алексей Андреевич проводил в МГУ: по программированию /с 1953 года/ и по исследованию проблем расширения области применения вычислительных машин /с 1954 года/. Они собирали слушателей из различных и не только московских организаций. Операторный метод лёг ив основу первых отечественных учебников по программированию. Его роль в становлении программирования как науки, имеющей свои объекты исследований и проблематику, трудно переоценить. В лоне операторного метода зародилась теория схем программ, возвестившая начало нового научного направления - теоретического программирования. Логические схемы Ляпунова использовались двояко - для описания одной конкретной программы и для описания целого класса программ, имеющих общую структуру. Вторая трактовка логических схем возникла в связи с трудностями следующего рода. С введением понятия программы одной из основных становится задача разработки их эквивалентных преобразований. Но поскольку формализация программы уравнивает её с другими формализациями алгоритма, проблема распознавания того, выполняют ли две программы одну и ту же функцию или нет, приобретает статус неразрешимой. Отсюда возникает задача моделирования программ объектами с разрешимой эквивалентностью. В качестве таковых и были взяты те же логические схемы, но каждая из них теперь трактовалась как класс про грамм с одинаковой структурой. Эквивалентность двух схем вводилась требованием: какой бы ни была допустимая совместная интерпретация схем как программ, она приводит к функционально эквивалентным программам. Значит, эквивалентные преобразования схем остаются эквивалентными и для программ представимых схемами. Использование схем во втором смысле закрепило за ними название схем Янова. Ю.И. Янов был в те годы аспирантом Алексея Андреевича и перед ним были поставлены задачи: перейти от программ к их схемам, сохраняя структуру первых и вводя эквивалентность схем таким образом, чтобы из неё следовала эквивалентность программ, описываемых схемами; для каждой эквивалентности разработать полную систему эквивалентных преобразований схем. Под полнотой системы в классе схем понимается следующее её свойство: какими бы ни были две эквивалентные схемы из данного класса, существует цепочка преобразований, принадлежащих системе и переводящих одну схему в другую. Интерес к построению полной системы вызван тем, что она даёт самый богатый набор эквивалентных преобразований программ, который можно получить на схемах, заменивших программы, при выбранной эквивалентности схем. Ю.И. Яновым в его кандидатской диссертации было введено множество эквивалентностей, удовлетворяющих, на интуитивном уровне, требованию первой задачи; формальное доказательство этого факта произошло значительно, позже. Для каждой введённой эквивалентности была решена вторая зада ча, правда, не во всём множестве схем, а в некотором его подмножестве. Полнота системы устанавливалась алгоритмом, который, получив на свой вход две схемы из данного подмножества, приводил их к общему виду, если схемы оказывались эквивалентными, и обрывал процесс их преобразований в противном случае. Таким образом, была положительно решена и проблема эквивалентности в данном подмножестве. Схемы программ, отличающиеся от исследованных Яновым, рассматривались в работах Н.А. Криницкого и Р.И. Подловченко, тоже выполняемых под руководством Алексея Андреевича. Если в первых память программы, ассоциируемая с множеством используемых в ней переменных, выступала в неявном виде, то во вторых схемах она фигурировала явно. Впоследствии эти схемы стали именовать стандартными. Н.А. Криницкий исследовал функциональную эквивалентность схем без циклов. Р.И. Подловченко занималась построением эквивалентных преобразований схем, вызванных линеаризацией массивов данных. Работы по моделированию программ схемами для изучения на схемах свойств программ были подхвачены сразу, но раз вернулись широким фронтом после того, как А.П. Ершов переизложил результаты Ю.И. Янова на общедоступном языке граф схем. В отечестве и за рубежом строились различные модели программ, исследовалась в них эквивалентность схем, заменивших программы, отыскивались случаи её разрешимости и неразрешимости, проводились сравнения различных моделей по признаку реализуемых схемами функций и т.д. Самым близким в идейном плане развитием работы Ю.И. Янова является теория моделей программ, построенная Р.И. Подловченко. Деятельность по моделированию программ схемами продолжается и в наши дни. Алексею Андреевичу принадлежит постановка ещё одной задачи, прочно вошедшей в проблематику программирования. Эта задача рассматривалась в кандидатской диссертации его аспиранта Р.Н. Тонояна. В ней логическая схема обобщалась следующим образом: порядок выполнения операторов в схеме брался не полным, а частичным. Всякое его доведение до полного порядка превращало схему в программу. Требовалось строить такие частичные порядки, которые при любом доведении их до полного давали бы функционально эквивалентные программы. Фактически данной задачей открываются исследования по параллельному программированию. На этом мы завершим краткий обзор деятельности Алексея Андреевича в программировании. Заложенные им направления исследований успешно развиваются, и с годами всё отчётливее вырисовывается основной вклад Алексея Андреевича в программирование - превращение его из кустарного ремесла в область знания. Подловченко Р.И. Размышления о феномене Алексея Андреевича Ляпунова // Программирование, 1991, 5. Подловченко Р.И. О вкладе А.А. Ляпунова в кибернетику // В сб.: Очерки истории информатики в России, Научно-издат. центр Объединённого института биологии, геофизики и минералогии СО РАН, Новосибирск, 1998.