Андрій Петрович

Єршов

(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 р. він стає завідувачемвідділом автоматизації програмування у новоствореному Обчислювальномуцентрi АН СРСР. У зв'язку зі створенням Сибірського відділення АН СРСР на проханнядиректора Інституту математики СВ АН СРСР академіка 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). Реалізована набагатомашинної комплексі з вітчизняних ЕОМ, ця система була багато в чомупіонерської і внесла великий внесок в розвиток вітчизняних робіт зархітектурі ЕОМ і операційних систем, які, на жаль, були вНадалі загальмовані орієнтацією на копiювання закордонних розробок.
Ряд таких властивостей системи, як поділ в процесорах комплексууправління і обробки, ієрархічність будови програмного забезпечення,виділення ядра операційної системи, природне поєднання різнихрежимів спілкування і обробки, забезпечили гарну ефективність і гнучкістьсистеми.

Осмислюючи досвід проекту АІСТ та інших подібних робіт у нас в країні іза кордоном у своїй доповіді на Конгресі ІФІП-68, Єршов висуває кільканасущних тез: про спеціалізацію процесів в багатопроцесорних комплексахдля поділу часу, про універсальних і спеціалізованих системахрозділення часу, і сферах їх застосування, про відмінність вимогпрофесіоналів і непрофесіоналів в програмуванні до спілкування з системамирозділення часу, і про те аспекті систем, який згодом буденазваний дружній до користувача.

Досвід керівників?? ства такими великими проектами, як АЛЬФА і АІСТ, і роботив цих проектах дали Єршову усвідомлення спільних проблем програмування істворення програмного забезпечення. У 1973 р. - з'являється зробила великувплив на розвиток вітчизняних робіт стаття. У цій роботі проводивсяглибокий і розгорнутий аналіз як зовнішніх властивостей машин четвертогопокоління, так і різних видів програмних систем: операційних систем,систем програмування та їх вхідних мов, спеціалізованих системобробки інформації, у тому числі пакетів прикладних програм (у роботідається класифікація ППП, яка зберігає свою цінність і в наш час).
Виділено ряд характерних систем обробки інформації і визначено їх зовнішніі внутрішні властивості. Окреслена загальна модель операційної системи - такзвана базова операційна система з концентричних будовою.
Зазначена в роботі спільність у реалізації мов програмування, створенняпроцесорів діалогових мов і систем відображення хоча і не вилилася, якприпускав автор, у створення універсальних систем, але стимулювала роботипо знаходженню загальної методології створення таких систем (втім, деякаобмежена у своїй універсальності багатомовна транслює система націєї спільноти була побудована - це система БЕТА, про яку говорилосявище).

Технологічні проблеми

Істотним в цій роботі було також те, що в ній піднімалисятехнологічні проблеми розробки програмного забезпечення. Єршов буводним з перших в країні, хто поставив проблему створення технологіїпрограмування. Треба сказати, що прагнення Єршова провести аналогіюміж створенням програмного забезпечення та промисловим виробництвом,ввести дисципліну, організацію, інструментірованіе в такій здававсябагатьом старим програмістам нерегламентіруемий творчий процес, якпрограмування, зустрічало у багатьох наших колег кінця 60-х рр.. активнуопір і навіть різкий протест. Те, що зараз здається тривіальнимтвердженням, Єршову доводилося відстоювати в палких суперечках і дискусіях.

Єршов ще в 60-х рр.. відстоював точку зору, що програмування,незважаючи на інтелектуальність і творчий характер цього процесу,має потребу в організації та регламентації, наборі або системі угод іправил, не кажучи вже про інструментальному забезпеченні. Керуючи і активноберучи участь у великих програмних проектах, Єршов з його допитливий розум не мігне замислитися над питанням: "Як це робиться?" Ще в роботах по АЛЬФА і
АІСТ він пише про ряд організаційних принципів і регламентуючихугод. Першою його роботою, повністю присвяченій технологіїпрограмування, була стаття ( «Про одному виді контакту людини змашиною »). Автоматизація розумових процесів »матеріали науковихсемінарів з теоретичних і прикладних питань кібернетики, 1963.), вонаж була першою радянською роботою в цьому виникла в ті роки новомунапрямку, і сам російський термін - технологія програмування (softwareingineering) - був запропонований Єршовим. Відповідно