Андрій Петрович
Єршов
(1931 - 1988) рр..
Введення
Академік Андрій Петрович Єршов (1931-1988) - один із зачинателів теоретичного й системного програмування, творець Сибірської школи інформатики. Його істотний внесок у становлення інформатики як нової галузі науки і нового феномену суспільного життя широко визнаний у нашій країні і за кордоном.
Він проводив фундаментальні дослідження в області схем програм та теорії компіляції. Книга А. П. Єршова "Программирующая програма для електронної обчислювальної машини БЕСМ" була однією з перших у світі монографій з автоматизації програмування.
Роботи Єршова по технології програмування заклали основи цього наукового напряму в нашій країні.
Мова програмування АЛЬФА та оптимізуючий Альфа-транслятор, перша радянська система поділу часу АІСТ-0, система навчальної інформатики Школярка, система підготовки друкованих видань Рубін, багатопроцесорна робоча станція МАРМУР - всі ці проекти були ініційовані А. П. Єршовим і виконувалися під його керівництвом.
Він одним перших у нашій країні усвідомив ключову роль обчислювальної техніки в прогресі науки й суспільства. Його блискучі ідеї заклали основу для розвитку в Росії таких наукових напрямків, як паралельне програмування та штучний інтелект. Більше 20 років тому він почав експерименти з викладання програмування в середній школі, які призвели до введення курсу інформатики та обчислювальної техніки в середні школи країни і збагатили нас тезою "програмування - друга грамотність".
Єршов брав активну участь у підготовці безлічі міжнародних конференцій та конгресів, був редактором або членом редколегії як російських журналів "Мікропроцесорні засоби та системи", "Кібернетика", "Програмування", так і міжнародних - Acta Informatica, Information Processing Letters, Theoretical Computer Science.
Академік А. П. Єршов дуже багато уваги приділяв проблемам інформаційного забезпечення вчених. Свою наукову бібліотеку він збирав усе життя. На час передчасної кончини А. П. Єршова в його особистій бібліотеці зберігалося понад 30 тисяч книг, журналів, праць конференцій, препринтів і окремих відбитків статей практично на всіх європейських мовах. Після смерті академіка А. П. Єршова його спадкоємці передали бібліотеку в Інститут систем інформатики, який до того часу виділився з Обчислювального центру. Тепер це Меморіальна бібліотека ім. А. П. Єршова.
У 1988 році був створений благодійний Фонд імені А. П. Єршова, основною метою якого було розвиток інформатики як винахідництва, творчості, мистецтва та освітньої активності.
Андрій Петрович Єршов був не лише талановитим ученим, учителем і борцем за свої ідеї, але й видатної, різнобічно обдарованою особистістю. Він писав вірші, перекладав на російську мову вірші Р. Кіплінга та інших англійських поетів, прекрасно грав на гітарі і співав.
Шлях в програмування
Андрій Петрович Єршов, видатний програміст і математик, лідер радянського програмування, народився 19 квітня 1931 р. у Москві. Помер після важкої хвороби в Москві 8 грудня 1988
Походив він з родини потомствених інтелігентів. Батько був інженером-хіміком, мати - бібліотекарем.
З 1943 р. батьки А. П. Єршова живуть у Сибіру, в Кемерові, де в 1949 р. він закінчив середню школу. У тому ж році він вступає на фізико-технічний факультет Московського університету, збираючись стати фізиком. Однак через заборону вчитися на фізика йому не дали, а дозволили перевестися на механіко-математичний факультет того ж університету. Там він став спеціалізуватися на кафедрі обчислювальної математики, якою керував академік С. Л. Соболєв, а на останніх курсах під впливом А. А. Ляпунова захопився програмуванням. Ще будучи студентом, у 1953р., Він поступив на роботу в Інститут точної механіки та обчислювальної техніки - організацію, в якій складався один з перших радянських колективів програмістів.
Таким був його, не зовсім добровільний, шлях до програмування. Вибір галузі діяльності, зроблений А. П. Єршовим, виявився щасливим як для нього, так і для програмування. Дійсно, А. П. Єршов був різноманітне талановитий, він міг би досягти великих результатів і в якій-небудь іншій області діяльності, зокрема у фізиці, яка спочатку була їм обрана, тому не можна сказати, що програмування - єдиний напрям, де він міг б проводити свої дослідження. Однак саме в такій зароджується науці, як програмування, дивно до місця припали такі грані його таланту, як уміння нетрадиційно мислити, знаходити ясні основи інтуїтивно складається знання, бачити перспективні точки росту. Інша, більш визначилася наукова дисципліна, напевно, дала б йому менші можливості застосування свого інтелектуального потенціалу - і в цьому було щастя його вибору. Але, з іншого боку, і програмування в той потребувало вчених з характером першовідкривачів - подібних А. П. Єршову - для формування з різнорідної практики початкового наукового та методичного фундаменту. Діяльність Єршова, про яку піде мова далі, виявилася дуже співзвучною цим потреб програмування, так що вибір, зроблений ним, - удача для програмування.
Вплив на науку
У 1954 р. А. П. Єршов закінчив університет - це був перший у радянських вузах масовий випуск за фахом "програмування". З 1954 по 1957 р. він аспірант А. А. Ляпунова в Московському університеті. Кандидатську дисертацію, присвячену поняттю операторного алгорифма (існує багато визначень цього терміна. Наприклад, акад. А. Н. Колмогоров дає таке визначення: алгоритм або алгорифми - це будь-яка система обчислень, що виконуються за строго визначеними правилами, яка після якого-небудь числа кроків завідомо призводить до вирішення поставленого завдання. Тьюринг - англійська програміст-теоретик створив так звану машину Тюринга, за допомогою якої можна реалізувати будь-який алгоритм, а те, що не можна на ній реалізувати, алгоритмом не є. Машина Тьюрінга - це стрічка, на якій записані деякі символи . По ній «бігає» каретка, яка читає поточний символ, і у відповідності з поточним символом і поточним станом може переходити до наступного або попереднього символу, або залишатися на місці і змінювати стан, а також змінювати поточний символ на стрічці.), він підготував до 1958 р., проте у зв'язку з настороженим відношенням математиків до нової науки захистити її йому вдається тільки в 1962 р. Докторська дисертація по методам побудови трансляторів захищається їм в 1968 р. В 1970 р. він стає членом-кореспондентом, а в 1984 р . - академіком АН СРСР.
Таке швидке просування пов'язано з тим, що вже наприкінці 50-х рр.. він стає одним з провідних радянських програмістів - не тільки завдяки своїм блискучим індивідуальним робіт, але і як керівник плідно працюють програмістських колективів. У 1957 р. він стає завідувачем відділом автоматизації програмування у новоствореному Обчислювальному центрі АН СРСР. У зв'язку зі створенням Сибірського відділення АН СРСР на прохання директора Інституту математики СВ АН СРСР академіка C. Л. Соболєва він бере на себе обов'язок організатора й фактичного керівника відділу програмування цього інституту.
У 1960 р. він стає й формальним керівником цього відділу й остаточно переїжджає в Сибір. Сибірське відділення приваблювало молодих активних вчених великими можливостями організації нових масштабних досліджень, і Єршов був одним з тих молодих вчених, які наприкінці 50-х і початку 60-х рр.. разом з академіками-засновниками створювали інститути нового наукового центру в Академмістечку. Надалі відділ Єршова став однією з основ створеного в 1964 р. Г. І. Марчуком Обчислювального центру СВ АН СРСР. Завдяки Єршову Академмістечко стає одним з провідних центрів з програмування. Єршов створив відому Новосибірської школи системного й теоретичного програмування, дослідження якої складалися з робіт його учнів і послідовників у різних новосибірських інститутах. Сам Єршов, будучи тільки завідувачем відділом і відділенням Обчислювального центру, став ідейним керівником і неформальним главою великої й активно працюючої співдружності новосибірських програмістів.
Великий вплив Єршова і на розвиток програмістської науки і практики в країні в цілому. Цей вплив далеко не обмежувався тим, що він був головою однієї з провідних радянських наукових шкіл, або тим науковим внеском, про який мова піде нижче. З кінця 60-х рр.. він стає в центрі програмістської життя в СРСР. Він був одним з основних організаторів перших національних конференцій з програмування, великої кількості національних конференцій, семінарів і шкіл з різних проблем системного й теоретичного програмування, членом редколегій основних радянських програмістських журналів, редактором (з моменту його утворення) журналу "Мікропроцесорні засоби та системи", головою ряду національних комісій та робочих груп. У 1987 р. він стає головою Ради з кібернетики, який координує всі вітчизняні академічні дослідження з інформатики та програмування.
Єршов приділяв велику увагу навчально-організаційної роботи, в тому числі у світовому масштабі. Він був членом ряду комітетів і робочих груп IFIP (International Federation on Information Processing), активним учасником низки конгресів, у тому числі віце-головою програмного комітету IFIP-68, запрошеним доповідачем IFIP-71, організатором робочих конференцій IFIP. У 1980 р. нагороджений "Срібним сердечником" (Silver Core). Також був членом редколегії таких міжнародних видань, як "Information Processing Letters", "Theoretical Computer Science" і ін Його міжнародні творчі і дружні зв'язки були великі. Він виступав із запрошеними доповідями у великому числі організацій Європи, Японії та США. З 1965 р. він - член Association for Computing Machinery (АСМ), в 1974 р. став почесним членом Британського Комп'ютерного суспільства. В останні роки життя А. П. Єршов приділяє багато уваги міжнародної роботи з інформатики в освіті.
Теоретичне та системне програмування
А. П. Єршов - один з тих провідних світових вчених, завдяки діяльності яких виділилися і оформилися такі наукові напрямки сучасного програмування, як теоретичне й системне програмування. Його творча спадщина широко, воно включає більше 200 книг, статей, препринтів, не рахуючи великої кількості передмов, редакційних статей, відгуків тощо, а також газетних публікацій, віршів (і хороших віршів!) Та ін Обсяг цієї статті не дозволяє дати досить докладний огляд всіх робіт Єршова, і тут ми обмежимося викладом основних ідей і провідних публікацій.
А. П. Єршов був одним з перших радянських програмістів, які зробили визначальний внесок у вітчизняне програмування, тому природно, що становлення і розвиток його наукових інтересів більшою мірою відповідає становленню та розвитку як радянського, так і світового програмування.
Як і більшість програмістів 50-х рр.., А. П. Єршов починав зі створення алгоритмів чисельних методів і стандартних програм. Перша його робота («Про один метод звернення матриць» - доповідь АН СРСР, 1955) була присвячена розробленому ним методу обернення матриць, що належить до класу методів поповнення. Хороша алгорітмічность методу - компактність алгоритму, зручні рекурентні співвідношення - дозволила цим методом бути основою для стандартних програм для ряду перших радянських ЕОМ (для однієї з них - БЕСМ - така програма була розроблена Єршовим). Середина 50-х рр.. була часом становлення теоретичного й системного програмування. Системне програмування починалося з напряму, названого тоді автоматизацій програмування і пов'язаного з розробкою мов програмування та методів їх трансляції. Початковий поштовх цьому напрямку дали роботи Рутісхаузера і Ляпунова. Перші радянські мов програмування були пов'язані з операторними схемами, запропонованими А. А. Ляпуновим. Ці схеми задавали структуру програми в термінах операторів деяких фіксованих класів з наступним завданням подання цих операторів. А. П. Єршов був керівником і творцем одних із перших радянських програмуючих програм для ЕОМ БЕСМ і "Стріла" (програмуючими програмами тоді називалися інтегральні розробки мови та системи програмування). На основі даних робіт їм була написана монографія («Про поняття обчислювального алгорифма» - теза доповіді наради з обчислювальної математики і застосування засобів обчислювальної техніки, 1958), перша у світовій літературі монографія з автоматизації програмування, практично негайно перекладена і видана за кордоном, а також ряд робіт про обчислювальної техніки та реалізації алгоритмів на ній у 1956-1958 рр.. У монографії і цих роботах А. П. Єршовим був вперше запропонований ряд понять, підходів і методів, які увійшли в класичний багаж мов і систем програмування. Тут і поняття циклу як фундаментальної конструкції мов програмування, і тріадні внутрішнє представлення виразів, і метод функції розстановки для пошуку співпадаючих фрагментів (імен), та алгоритм оптимального розподілу робочих осередків (регістрів), і початкові ідеї потокового аналізу, і пр.
АЛЬФА-і БЕТА-мови
Першим великим проектом, з якого починалася новосибірська школа, був трансляторний проект "Альфа". На відміну від попередніх проектів програмуючих програм проект Альфа був добре, практично по-сучасному специфікований: було підготовлено формальний опис вхідної мови, була створена розгорнута функціональна специфікація системи.
Відправною точкою проекту була публікація початковій версії нової мови програмування, підсумованого накопичився програмістський досвід і створюваного міжнародною робочою групою - так званого Алгола 58. Група, керована А. П. Єршовим, стала готувати на основі Алгола 58 новий проект мови - паралельно з працювала міжнародною групою. Багато в чому напрямки розвитку мови виявилися однаковими, але в новосибірському проекті з'явився ряд істотно нових механізмів, тому, в кінці кінців, мова був сформульований як правильне розширення остаточної версії міжнародної мови - Алгола 60. В Альфа-мові вперше були розроблена кошти, характерні для подальших за Алголом 60 мов. Було визначено таке важливе для обчислювальних алгоритмів поняття багатовимірних значень, визначені операції над ними, в тому числі, їх конструювання. Були введені властиві сучасним мовам концепції, такі, як різноманітність видів циклів, завдання початкових значень і тому подібне У формальному визначенні мови вперше була зроблена спроба вийти за межі контекстно-вільних граматик.
Сама робота над транслятором була великою мірою й дослідницькою та піонерської. Саме в цій роботі почалися складатися принципи сучасної оптимизирующей трансляції. Справа в тому, що сам Алгол 60 був певним викликом для існуючих методів трансляції. Його істотно рекурсивна структура, потужність механізму процедур, можлива їх вкладеність і потенційна рекурсивность, спільність циклів та індексних виразів - все це вимагало помітною модифікації і розвитку техніки трансляції, а найголовніше - ставило питання про можливість отримання ефективного коду. По останньому приводу висловлювалася ряд сумнівів, і Альфа-транслятор став справді першим конструктивним доказом того, що для мов, порівнянних за потужністю з Алголом, можна побудувати транслятор, що дає порівнянний з ручним програмуванням код.
Досягненню поставленої мети послужив багатий набір оптимізацій, реалізований в Альфа-транслятор. Була запропонована змішана стратегія програмування (те, що згодом на Заході було названо "casing") таких конструкцій, як процедури, цикли, індексні вирази, коли на підставі аналізу контексту вибирався найбільш ефективний з допустимих способів генерації конструкцій. Особливо витончено програмувались процедури і підстановка параметрів для них: вибір здійснювався серед 11 способів. У результаті алголовскіе процедури при всій потужності механізму програмувались оптимальним чином (що стимулювало програмістів активно використовувати цей засіб). Існуюча раніше оптимізація економії виразів була істотно розвинена - повністю враховувалися властивості комутативності та асоціативності; якщо це перетворення не стало глобальним, то воно вже було квазілокальним. Вперше була реалізована глобальна чистка циклів. Ретельної оптимізації піддавалися операції над багатовимірними значеннями - те, що не було в стандартному Алголь, але активно використовувалося обчислювачами. Вперше була реалізована глобальна економія пам'яті, яка спирається на теоретичні праці О. П. Єршова і С. С. Лаврова.
Альфа-транслятор став першим у світі транслятором з Алгола з великими оптимізують можливостями. Схожий англійський проект Хоукінса і Хакстебла, який розроблявся в цей час, так і не був до кінця завершено через складність завдання. Звичайно, успіху сприяло не тільки механічне з'єднання багатьох оптимізацій, а й суттєве розвиток існуючої методології оптимізації програм. Була висунута ідея внутрішнього мови, до програми на якому і застосовуються оптимізації, яка, хоча і не зовсім в чистому вигляді, була реалізована. Був реалізований практично глобальний аналіз контексту, хоча і розрізнено для різних оптимізацій, облік якого істотно збільшив потужність оптимізацій - зародок сучасного потокового аналізу. Прагнення практично завжди отримувати ефективний код призвело до відмови від деяких засобів Алгола, найважливішим з яких була рекурсивность процедур.
Альфа-транслятор активно використовувався у великому числі організацій країни. Хоча його інтерфейси з користувачем і простота експлуатації бажали багато кращого, але висока ефективність одержуваного коду забезпечила гарний інтерес користувачів до цієї системи. Тому коли на зміну М-20 прийшла істотно більш високопродуктивна машина БЕСМ-6, організації, пов'язані з великими завданнями, стимулювали створення версії Альфа-транслятора для БЕСМ-6. Найшвидшим рішенням була проста переробка Альфа-транслятора, при якій та його частина, яка відповідала за генерацію коду, була замінена генератором коду для БЕСМ-6. Виник транслятор Алгібр ("Альфа гібридний"), який був одним з перших вітчизняних крос-трансляторів. Таке рішення мало ряд недоліків, але зате воно було реалізовано швидко, і транслятор Алгібр став першим транслятором для нової машини БЕСМ-6. Рішення істотно полегшувалося тим, що в Альфі-транслятор вже існував внутрішній мову, хоча і не до кінця єдиний для всіх оптимізують перетворень.
Основним ускладненням при Алгібр-трансляції була передача відтранслювати коду з М-20 на БЕСМ-6. У ВЦ СВ АН СРСР був навіть розроблений спеціальний канал передачі інформації між інструментальної та об'єктної ЕОМ, проте це не могло бути серійним рішенням при масової трансляції. Виникла необхідність "рідного" транслятора для БЕСМ-6.
У розробників Альфа-транслятора виникала і внутрішня потреба модифіковані та поліпшити як схему трансляції, так і нестандартні властивості транслятора, в першу чергу, його інтерфейс з користувачем. Альфа-транслятор, незважаючи на його досить широку використовуванність, носив риси експерименту і пошуку - хоча ідейні рішення були знайдені вірно, але реалізаційні рішення були характерні скоріше для експериментального, ніж виробничого транслятора (велика кількість переглядів програми - 24, деяке дублювання аналізу контексту, не завжди виправдане ускладнення оптимізують перетворень). Не потрібно забувати, що цей транслятор був першим оптимизирующим транслятором з Алгола. Додатковий досвід - транслятор Алгібр, незавершений проект Альфа-транслятора для ЕОМ Урал-14 (проект ТАУ) - давав основу для нових рішень.
Новий транслювати - транслятор Альфа-6 - був покращеною версією оптимизирующего транслятора з Алгола. Ряд попередніх рішень був приведений до більш чистому та ефективному увазі. Більш чітко був виділений внутрішній мову і етап потокового аналізу програм на внутрішньому мовою. Загальна схема трансляції вже могла розглядатися як типова схема оптимизирующей трансляції (для одноязикового транслятора), вона налічувала всього 10 переглядів. Краще була вирішена проблема взаємного впливу різних оптимізують перетворень. Ідентифікація та візуалізація помилок користувача була більш досконалою, що полегшувало експлуатацію. У результаті система Альфа-6 стала досить широко використовуваною системою у користувачів БЕСМ-6.
Лексикон
У певному сенсі з аналізу загальних понять мов програмування і усвідомлення їх певну обмеженість виросла запропонована Єршовим у статті «Математичне забезпечення четвертого покоління» («Кібернетика», 1973, № 1) фундаментальна і багатообіцяюча ідея лексикону програмування як загальної середовища для розробки і обгрунтування програм. Він визначає лексикон як "лінгвістичну систему з фразовой структурою, яка містить в собі формальну нотацію для вираження всіх загальнозначущих конструкцій, вживаних при формулюванні умов завдань, при синтезі і перетворенні програм". Лексикон, говорить Єршов, "виражає не тільки і не стільки програми, скільки їх властивості і наші судження про них. Мова програмування кодує об'єкти предметної області завдання, а наше знання про ці об'єкти залишається за межами програмного тексту. Лексикон ж є засобом опису об'єктів предметних областей і містить нотацію для побудови баз знання про предметні областях. Програма, виражена засобами лексикону, в певному сенсі містить у своєму тексті опис своєї семантики у вигляді сукупності нетривіальних фактів про обчислюється нею функції - на відміну від "чистих" програм, які не говорять нічого про свої функціональні властивості. Лексикон, на відміну від конкретної мови програмування, є відкритою системою. Для нього в цілому не ставиться завдання трансляції будь-якого його тексту в машинну програму, хоча будь-яка машинна програма у випадку необхідності може бути виражена в лексиконі. Аналогічно природної мови лексикон має здатність опису однієї своєї частини засобами іншій своїй же частині. Не треба думати, що лексикон - це все і назавжди. Це ретельно відібрана, але розвивається система вдалих позначень. Ступінь його успіху визначається ступенем общезначимости і общепонятном його нотації ".
Змішаний обчислення і
трансформаційна машина
Змішаний обчислення є певний універсальний процес, який визначається над парами (програма, дані) і приводить в загальному випадку до отримання залишкової програми і часткових результатів. Математичним аналогом змішаного обчислення є функціонал, який для певного класу функцій з кількома аргументами будує (при завданні деяких аргументів) функції з меншим числом аргументів. Процес змішаного обчислення може бути, у свою чергу, заданий у виді програми (змішаного обчислювача), що дозволяє ставити питання про самопріменімості змішаних обчислень, а сам змішаний обчислювач уподібнити snm - функції Кліні.
Поняття змішаного обчислення (і змішаного обчислювача) в застосуванні до процесорів обробки програм, для яких програми та їх атрибути є дані, дозволяє із загальної точки зору дослідити і визначити різні види обробки програм: від трансляції і інтерпретації до аналізу програм, їх перетворення і генерації самих мовних процесорів. У ряді робіт зі змішаних обчислень і трансформаційний підхід Єршов методологічно досліджує цю концептуальну сторону змішаних обчислень.
Саме визначення принципу змішаних обчислень як загальної основи великого числа процесів роботи над програмами відрізняє роботу Єршова від ряду попередніх робіт і здогадок Ломбарді, Футамури, Турчина та ін Це і стало причиною того, що роботи Єршова лягли в основу нового і активно розвивається напряму в програмуванні , пов'язаного з теоретичними дослідженнями і практичними додатками змішаних обчислень. Застосування змішаних обчислень виявилося вельми корисним методологічно для розуміння і трактування різних понять і сутностей програмування.
Поняття змішаних обчислень, введене Єршовим як загальна модель для різних видів обробки програм, з необхідністю вимагало широкого кола досліджень, як за властивостями самої моделі, так і за її трактування в різних областях можливого застосування. Було введено поняття коректності змішаних обчислень і визначено моделі змішаних обчислень і отримання залишкової програми, для яких можна було доводити коректність. Однією з таких моделей, на яких фокусувалася увагу, стала трансформаційна модель, для якої змішане обчислення задавалося набором базових трансформацій. Сама модель змішаних обчислень та їх коректність розглядалися як для імперативних мов, так і для рекурсивних програм. Було отримано ряд важливих результатів щодо визначення механізму затримки (заморожування) обчислень і даних, за описом процесу змішаних обчислень для різних мов представлення програм, щодо формулювання набору базових трансформацій, по надійності (незацікліванію) процесу змішаних обчислень і пр.
Для реальних додатків змішаних обчислень крім, зрозуміло, необхідних властивостей коректності та надійності важливими виявляються їх гнучкість і глибина. І тут Єршову і його учням вдалося істотно просунутися в дослідженнях. Гнучкість змішаних обчислень може бути помітно збільшена, якщо змішаний обчислювач буде при отриманні залишкової програми враховувати не тільки властивості даних мати конкретне значення, а й більш тонкі властивості, зумовлені відомими співвідношеннями між даними (предикати над даними). У цьому випадку змішаний обчислювач оперує з деякою визначеною на даних обстановкою. Глибина змішаних обчислень визначається схемою змішаних обчислень. Поряд з суворою схемою змішаних обчислень, введеної спочатку, була визначена поліваріантну схема, пов'язана з просуванням змішаних обчислень в альтернативи, навіть якщо вибір альтернатив не може бути визначений при такому обчисленні.
Спільно з Островським Єршов досліджував застосування змішаних обчислень у такій традиційно важливій галузі, як трансляція, а саме побудова трансляторів для заданого опису вхідної мови. Істотно відзначити, що тут були отримані не тільки результати, які демонструють практичну застосовність принципу змішаних обчислень (вдавалося будувати транслятори істотно більш ефективні, ніж це досягається при звичайному автоматичному побудові), але і ряд фактів і спостережень, важливих для зіставлення методів трансляції та розуміння сутності трансляції і показують методологічну важливість принципу змішаних обчислень.
Таким чином, в області змішаних обчислень Єршову належить не тільки визначення основних понять і моделей, але і визначальний внесок у теорію і методологію цієї області. Він по праву вважається засновником і лідером цього напрямку, активно розвивається зараз у різних колективах і країнах.
Відштовхуючись від трансформаційної моделі змішаних обчислень і від своїх робіт в області трансляції і оптимізації програм, Єршов визначає концепцію трансформаційної машини. Трансформаційна машина є абстрактне обчислювальний пристрій, що виконує програми в деякому "сверхязике", діями якого є трансформації пар (програма, дані). Дії ці підтримують збереження деякого інваріанту, що забезпечує коректність трансформацій. Концепція трансформаційної машини представляється досить багатообіцяючою - і як теоретична модель для опису та обгрунтування процесів обробки програм, і як методологічна основа побудови різних інструментальних процесів.
Концепція трансформаційної машини є тим важливим внеском у трансформаційний підхід до побудови програм, ентузіастом і пропагандистом якого був А. П. Єршов, і різні аспекти якого досліджуються в ряді його робіт 80-х рр.. Трансформаційний підхід розвивається зараз у ряді колективів у нас і за кордоном і є досить перспективним, оскільки він дає можливість отримувати програми з хорошими показниками таких якостей, як надійність і ефективність, а також підвищує ступінь перевикористання програмного забезпечення. Роботи Єршова по трансформаційний підхід дають природну точку росту для подальших досліджень.
Слід зауважити, що поряд з роботами по мовах і методам трансляції роботи зі змішаних обчислень і трансформаційний підхід були джерелом вже згадуваної ідеї Єршова про лексиконі програмування.
Укладають роботи Єршова з теорії програмування його публікації, присвячені поняттю обчислюваності. Сам він визначає ці роботи як спробу синтезу поглядів на обчислюваності, сформованих як в математичній логіці, так і в теоретичному програмуванні. Оскільки поняття обчислюваності є одним з головних як в тій, так і в іншій області і має фундаментальне значення для інших програмістських понять, очевидно, що визначення поняття обчислюваності, абстрагованого від несуттєвих синтаксичних або модельних понять і разом з тим вбирає необхідні для теорії і численною практики суті, є однією з головних завдань, що визначають подальший взаємовплив математики та програмування. У фундаментальній роботі «Проблеми програмування: Всесоюзна конференція в Новосибірську» (Вісник АН СРСР, 1970, № 6) проводиться глибокий аналіз великого числа визначень обчислюваності, що склалися в зазначених областях, їх співставлення та оцінка вкладу в загальну теорію. На підставі даного аналізу Єршов намацує ідею визначення обчислюваності: звести визначення обчислюваної функції до поняття детермінанта, тобто того, що є інваріантні до різних способів завдання обчислень. Мабуть, ці роботи Єршова будуть мати таке ж стимулююче значення для досліджень в даній області, як і його роботи початку 70-х рр.. для теорії схем програм.
Проект АІСТ
Однією з важливих заслуг Єршова перед вітчизняним і світовим програмуванням є те, що він умів оцінити поточний стан науки і практики і намітити ті реальні точки зростання і перспективи досліджень, які будуть визначати розвиток програмування. Так, у другій половині 60-х рр.. він одним з перших у країні усвідомив ті нові можливості спілкування з ЕОМ, які створюють системи поділу часу. У 1966 р. він організовує роботи з автоматичним інформаційним станціям (проект АІСТ). Проект АІСТ, творцем і керівником якого був О. П. Єршов, об'єднував широке коло досліджень з архітектури обчислювальних комплексів, їх програмного забезпечення та моделювання обчислювальних систем. У рамках цього проекту була створена перша в країні розвинена система поділу часу АІСТ-0, проект якої був предметом доповіді на Конгресі AFIPS 1967 р. («Вхідна мова системи автоматичного програмування» попереднє повідомлення - М.: ВЦ АН СРСР, 1961), а підсумковий доповідь було зроблено на 2-й Всесоюзній конференції з програмування в 1970 р. («Программирующая програма для машини» Третє Всесоюзна нарада з обчислювальної математики і застосування засобів обчислювальної техніки, 1961). Реалізована на багатомашинної комплексі з вітчизняних ЕОМ, ця система була багато в чому піонерської і внесла великий внесок у розвиток вітчизняних робіт з архітектури ЕОМ і операційних систем, які, на жаль, були в подальшому загальмовані орієнтацією на копіювання зарубіжних розробок. Ряд таких властивостей системи, як поділ в процесорах комплексу управління та обробки, ієрархічність будови програмного забезпечення, виділення ядра операційної системи, природне поєднання різних режимів спілкування і обробки, забезпечили гарну ефективність і гнучкість системи.
Осмислюючи досвід проекту АІСТ та інших подібних робіт у нас в країні і за кордоном у своїй доповіді на Конгресі ІФІП-68, Єршов висуває кілька нагальних тез: про спеціалізацію процесів в многопроцессорном комплексі для поділу часу, про універсальні і спеціалізованих системах поділу часу та областях їх застосовності, про розходження вимог професіоналів і непрофесіоналів у програмуванні до спілкування з системами поділу часу і про той аспект систем, який згодом буде названий дружністю до користувача.
Досвід керівництва такими великими проектами, як АЛЬФА і АІСТ, і роботи в цих проектах дали Єршову усвідомлення загальних проблем програмування та створення програмного забезпечення. У 1973 р. - з'являється зробила великий вплив на розвиток вітчизняних робіт стаття. У цій роботі проводився глибокий і розгорнутий аналіз як зовнішніх властивостей машин четвертого покоління, так і різних видів програмних систем: операційних систем, систем програмування та їх вхідних мов, спеціалізованих систем обробки інформації, в тому числі пакетів прикладних програм (у роботі дається класифікація ППП, зберігає свою цінність і в наш час). Виділено ряд характерних систем обробки інформації та визначено їх зовнішні і внутрішні властивості. Окреслена загальна модель операційної системи - так звана базова операційна система з концентричним будовою. Зазначена у роботі спільність у реалізації мов програмування, створення процесорів діалогових мов і систем відображення хоча і не вилилася, як припускав автор, у створення універсальних систем, але стимулювала роботи по знаходженню загальної методології створення таких систем (втім, деяка обмежена у своїй універсальності багатомовна транслює система на даній спільності була побудована - це система БЕТА, про яку говорилося вище).
Технологічні проблеми
Істотним у цій роботі було також те, що в ній піднімалися технологічні проблеми розробки програмного забезпечення. Єршов був одним з перших в країні, хто поставив проблему створення технології програмування. Треба сказати, що прагнення Єршова провести аналогію між створенням програмного забезпечення та промисловим виробництвом, ввести дисципліну, організацію, інструментірованіе в такій здавався багатьом старим програмістам нерегламентіруемий творчий процес, як програмування, зустрічало у багатьох наших колег кінця 60-х рр.. активний опір і навіть різкий протест. Те, що зараз здається тривіальним твердженням, Єршову доводилося відстоювати в палких суперечках і дискусіях.
Єршов ще в 60-х рр.. відстоював точку зору, що програмування, незважаючи на інтелектуальність і творчий характер цього процесу, має потребу в організації та регламентації, наборі або системі угод і правил, не кажучи вже про інструментальному забезпеченні. Керуючи і активно беручи участь у великих програмних проектах, Єршов з його допитливим розумом не міг не замислитися над питанням: "Як це робиться?" Ще в роботах по АЛЬФА і лелеки він пише про ряд організаційних принципів і регламентуючих угод. Першою його роботою, повністю присвяченої технології програмування, була стаття («Про одному виді контакту людини з машиною»). Автоматизація розумових процесів »матеріали наукових семінарів з теоретичних і прикладних питань кібернетики, 1963.), Вона ж була першою радянською роботою в цьому виникла в ті роки новому напрямку, і сам російський термін - технологія програмування (software ingineering) - був запропонований Єршовим. Відповідно до назви велика частина роботи була присвячена власне технології трансляції. У ній розглядалися загальні питання проектування трансляторів: їх структури, системи технічних процедур та ін, питання вибору методів реалізації, питання організації налагодження й документування. Окремо розглядалися проблеми автоматизації побудови трансляторів та автоматизованого побудови документації. Важливою стороною роботи було те, що проблеми технології трансляції розглядалися в загальному контексті технології створення великих програмних систем.
У ряді інших робіт Єршов досліджує і розвиває ідеї технології програмування. Їм була запропонована матрична організація колективу розробників, внесений вклад у специфікацію етапів розробки, в тому числі стосовно до розробки трансляторів, проведений аналіз реальної розробки (АЛЬФА-6) з точки зору її технологічності. У роботі «Алгоритмічні мови програмування» (Вісник АН СРСР. -1968. - № 3), написаної спільно з Г. Д. Чініним, визначається, як повинен бути організований колектив, провідний розробку промислових трансляторів, як повинна вирішуватися така важлива проблема, як наступність і перевикористання розробленого програмного забезпечення, як повинен проходити і інформаційно забезпечуватися процес розробки. Орієнтована на технологію трансляції, ця робота дає ряд хороших ідей за технологіями промислової розробки інших видів програмного забезпечення.
З загальнометодологічною точки зору для розвитку технологій програмування, їх обгрунтування та формування концептуального фундаменту вкрай важливою є робота, що представляє текст доповіді Єршова на засіданні Президії Академії наук СРСР. Для програмістської громадськості ця робота мені здається не менш важливою, ніж для членів Президії АН, яким зроблено цей доповідь.
Вже давно ведуться спроби побудувати процес програмування як доказовий, при якому правильність програми обеспечіваема або проверяєма на кожному етапі її побудови. Для реальних технологій програмування з їх безсумнівним вимогою забезпечення надійності (високого ступеня правильності) програми ці спроби при їх вдалому просуванні мали б неоціненне значення. Відомий, наприклад, підхід Е. В. Дейкстри, який заснований на ідеальній тенденції будувати програму як точний висновок з математичної постановки завдання. Незважаючи на свою ідеальність і "навязиваемость" жорсткої дисципліни, цей підхід є ідейною основою (може бути, не до кінця чисто реалізованої) низки сучасних технологій. Однак підхід Єршова, пов'язаний з оцінкою реального досвіду програмування і диференціацією різних його видів, - не нав'язування дисципліни, а її вилучення з практики - здається і більш практичним, і більш широким.
Єршов виділяє й аналізує три види програмування, які забезпечують його доказовість: синтезирующее, складальне і конкретизують. Синтезирующее програмування (одним з типів якого є те, яке здійснюється за методом Дейкстри) пов'язане з автоматичним, автоматизуються або ручним маніпулюванням знанням про завдання, сфери застосування і общематематических способах доказового міркування. Складальне програмування здійснює побудову програми з уже існуючих (перевірених на правильність) фрагментів. Конкретизують програмування засноване на систематичному побудові спеціалізованих програм з універсальної заготівлі (одним із способів такого програмування є застосування змішаних обчислень). Єршов, з одного боку, розглядає специфіку кожного виду і відзначає їх відмінності, які повинні виражатися в різних технологічних прийомах і інструментах, з іншого боку, говорить про те, що при побудові реального програмного забезпечення ці види можуть і нерідко повинні комбінуватися. Все це дає основу для створення розвиненого методологічного фундаменту майбутніх технологій програмування.
Міні-та мікро-ЕОМ
Робота "An Experimental Automatic Information Station AIST-O» (AFIPS Conf. Proc., Atlantic City, April 18-20, 1967. - Washington; London: Acad. Press., 1966) оцінює з точки зору застосування засобів обчислювальної техніки новий тоді феномен - поява міні - і мікроЕОМ, прогнозує ті необмежені можливості, які вони створюють, виділяє ті нові риси, які характерні для програмного забезпечення мікроЕОМ: інтегральність підходи до спільного проектування обладнання і софтвера, спеціалізованість програмного забезпечення (ПЗ), його орієнтація на використання непрофесіоналами в програмуванні. Тут же роблять виправданий згодом висновок про крайню важливість для ПО цих ЕОМ проблем переносу та сумісності, а також намічені можливі шляхи вирішення цих проблем. В одній зі своїх робіт він справедливо заперечує висувався деякими фахівцями тезу про стабілізацію становища в програмуванні і викладають активні точки зростання - нові концепції в мовах програмування, кристалізація і фундаменталізація понять трансляції, перехід від баз даних до баз знань (в роботі вони називаються "складними" базами даних), поява інструментальних комплексів (що згодом з легкої руки "АДІСТ" стало називатися "оточенням програмування"). Треба сказати, що прогноз Єршова повністю виправдався. Тут же оцінюється стан теорії програмування та її співвідношення з практикою, що відчутно для визначення шляхів розвитку теорії. Багато в роботі йдеться про навчання програмуванню, про підготовку кадрів - але про цю її боці скажімо пізніше.
Програмування - друга грамотність
Єршов виявив і прояснив ряд суттєвих рис, властивих програмування як науці і людської діяльності. Зауваження та судження Єршова з цього приводу розкидані у багатьох його роботах, але є декілька широко відомих його статей, багаторазово перекладених і виданих, які цілком присвячені не науковим або технічних проблем програмування, а питань, що є програмування як наука і діяльність, що є програміст як фахівець специфічного інтелектуальної праці. Це такі роботи, як "Про людське і естетичному факторах в програмуванні", "Програмування - друга грамотність", "Два вигляду програмування" та ін У роботі, присвяченій пам'яті рано померлого талановитого програміста Г. І. Кожухіна, міститься конструктивний аналіз протиріч, виникають між творчою природою програміста праці та необхідної для будь-яких масових професій виробничої його організацією. Головна теза статті: "Програмування володіє багатою, глибокої і своєрідною естетикою, яка лежить в основі внутрішнього ставлення програміста до своєї професії, будучи джерелом інтелектуальної сили, яскравих переживань і глибокого задоволення. Коріння цієї естетики лежать у творчій природі програмування, його труднощі й суспільну значимість ". Стаття сповнена глибоких суджень і зауважень, що пояснюють цю тезу. У статті наголошується елітарність програмістів і в той же час говориться про необхідність зробити мистецтво програмування загальним надбанням.
Єршов відзначає, що програмування необхідно сучасній людині не тільки в силу того, що ЕОМ в найближчому майбутньому прониже всі сторони життя, але й тому, що сучасне життя вимагає повсякденного планування і передбачення. Він говорить: "Друга грамотність - це не тільки вміння писати команди, а й виховання людини, рішучого і завбачливого разом". Програмування, укладає Єршов, є суттєвою компонентою сучасного навчання і виховання.
Єршов чітко формулює інтуїтивно усвідомлювали положення про те, що не можна програмування розглядати одноманітно. Він поділяє програмування на два види: програмування для себе та програмування для замовника і точно описує корінні відмінності цих видів, образів програмування. Відповідно він вводить терміни "програміст-слуга" і "програміст-господар" і показує, як глибоко різняться їхні манери, стилі і навіть критерії. Така конструктивна диференціація програмування вкрай важлива при створенні реальних технологій програмування, та й для низки більш загальних речей, що виражаються навіть в етиці і естетиці програмування. У суто науковому плані ця робота містить модель програмної обстановки для програміста-господаря, засновану на вже згадуваній трансформаційної машині.
Помітною лінією робіт Єршова є роботи, присвячені спілкуванню з ЕОМ на природній мові. Початковим підходом до конструктівізаціі цих проблем була робота "Про одному виді контакту людини з машиною". Вперше у вітчизняній і, мабуть, світовій літературі Єршов спробував сформулювати ряд точно поставлених завдань реалізації такого спілкування. Роздуми з цього приводу, об'єднані з дослідженнями лінгвістів (І. А. Мельчук) і системних програмістів (А. С. Наріньяні), призвели до появи проекту РІТА. Проект РІТА в такому вигляді, як описувався, не був реалізований, але можна чітко простежити, як ряд суттєвих ідей цього проекту перейшов у за реалізовані лінгвістичні процесори і системи штучного інтелекту: виділення проміжного рівня семантичного представлення, співвідношення лінгвістичних та програмних складових діалогової системи, наявність інтерфейсних блоків для інших (класичних) програмних систем, множинність значень інтерпретує функцій (що пізніше було узагальнено А. С. Наріньяні в понятті недовизначених множин) і т.д.
У подальшому Єршов проводить подальшу конструктівізацію проблем спілкування на природній мові, виділяючи з природної мови дуже важливе підмножина мови ділової прози. Також А. П. Єршов дає загальне визначення ділової прозі як мовною носію виробничих відносин людини і зазначає, що вона фактично виділяється в особливу лінгвістичну категорію. Ряд властивостей ділової прози - внутрішня формалізованість, чіткість функцій повідомлення - говорить про актуальність не тільки необхідності, але і можливості навчити машину повністю (Єршов це підкреслює) розуміти і сприймати цю мову. Далі Єршов розглядає деякі суттєві риси глобальної моделі повного сприйняття мови стосовно ділової прозі.
Тут у своїх дослідженнях і міркуваннях Єршов виходить за межі власне програмування і формулює фундаментальну проблему створення машинного фонду російської мови. Відзначаючи зв'язок цієї проблеми з вирішенням завдання спілкування з ЕОМ природною мовою, він підкреслює дуже важливу наукову, загальнокультурну і прикладну значимість цієї проблеми.
Інші проекти
Єршов був ініціатором та ідейним керівником і ряду інших проектів, не згаданих вище. Наведемо як приклад такі проекти, як система програмування СЕТЛ для мови надвисокого рівня (мови специфікацій), професійна робоча станція МАРМУР чи шкільна система програмування школярки. Хоча Єршов не був розробником в таких проектах і не брав участь в публікаціях з них, ці проекти харчувалися його ідеями та обговореннями з ним.
Наукові напрямки діяльності Єршова різноманітні. У принципі це властиво багатьом програмістам 50-х і початку 60-х рр.. - Можна навести чимало прикладів радянських і зарубіжних програмістів, які мають хороші результати в трьох - чотирьох розрізняються наукових напрямах. Такий характер діяльності природний для вчених, що стоять біля витоків нової наукової дисципліни (і, на жаль, мало доступний тим, хто вступає у вже сформовану, з великим спектром оформились напрямків науку). Але навіть і на тлі перших програмістів Єршов виділяється воістину "Ломоносовський" широтою своїх інтересів і результатів.
Висновок
Андрій Петрович Єршов визначив розвиток радянського і світового програмування на десятки років вперед: він проводив фундаментальні дослідження в області обчислювальної техніки, схем програм, теорії компіляції та ін Саме завдяки йому з'явилася так звана логічна ЕОМ, яка не залежить від конкретної реалізації. Це був принципово новий крок: раннє кожна програма писалася тільки для однієї конкретної машини і сильно залежала від конкретних фізичних схем і не могла застосовуватися на інших ЕОМ, що сильно ускладнювало поширення програмування.
Можливо, ідея лексикону є однією з основних, залишених нам Єршовим. Вона може служити джерелом створення наукових і методичних основ програмування на десятки років вперед. Багатовимірні значення - масиви та списки, що містять подібні дані, були також придумані і вперше реалізовані науковою групою Єршова. Їм створені такі мови програмування, як АЛЬФА, АЛЬФА-6 і БЕТА, він брав активну участь у створенні Алгола та його варіацій. Не можна не помітити, що найбільш поширений навчальний мову програмування - Паскаль і найбільш популярна мова серед професіоналів - Сі і його модифікації є алголоподобнимі, тобто за основу взяті принципи, використовувані в Алголь.
Творча спадщина академіка А. П. Єршова, одного з видатних учених у галузі інформатики, внесло визначальний внесок у становлення і сучасний стан світового програмування. Воно містить як підходи і методи, вже міцно ввійшли в теорію, методологію та практику сучасного програмування та упредметнені в них, так і ряд ідей та концепцій, які дають основу для майбутніх досліджень. Саме останні потребують живому продовженні і розвитку. Це - концепція змішаних обчислень, поняття абстрактної обчислюваності, трансформаційний підхід, положення про наукові основи доказового програмування, нарешті, об'єднує їх ідея лексикону програмування як джерело визначення та інтеграції досліджень по створенню майбутнього вигляду програмування. Також він проводив дослідження в області штучного інтелекту. Вплив на поширення програмування в масах теж багато в чому його заслуга - Єршов багато часу приділяв розвитку цієї дисципліни в школах і вузах.
Таким чином, його можна сміливо назвати одним з основоположників програмування. Однак не можна забувати, що своїми роботами він наклав деякі рамки, що стали вже шаблонами, що, зрозуміло, гальмує фундаментальні дослідження, хоча і сильно допомагає при конкретній реалізації програм.
Використана література:
1) http://thl.narod.ru/a/3.htm, без назви - близько 10 грудня 2003р ..
2) Архів академіка Єршова, електронна версія http://ershov.iis.nsk.su/archive - близько 10 грудня 2003р.:
А) «Про один метод звернення матриць» - доповідь АН СРСР, 1955р.
Б) «АЛЬФА-народження, або як створювалася система автоматичного програмування» - «За науку в Сибіру», 1965.
В) стаття Поттосіна про Єршов
Г) «Операторні алгоритми. Про операторних схемах Янова »-« Проблеми кібернетики », 1968.
3) «Наука в Сибіру», http://www.sbras.ru/HBC/2001/n25/f09.html, близько 10 грудня 2003р.
4) «Радянська Сибір», http://www.sovsibir.ru/show.shtml?tp=day&nart=4718, близько 10 грудня 2003р.