Пересмотренное сообщение об алголе 68
Обновлено: 30.06.2024
Вы можете добавить книгу в избранное после того, как авторизуетесь на портале. Если у вас еще нет учетной записи, то зарегистрируйтесь.
Ссылка скопирована в буфер обмена
Вы запросили доступ к охраняемому произведению.
Это издание охраняется авторским правом. Доступ к нему может быть предоставлен в помещении библиотек — участников НЭБ, имеющих электронный читальный зал НЭБ (ЭЧЗ).
Если вы являетесь правообладателем этого документа, сообщите нам об этом. Заполните форму.
Алгол 68 (англ. Algol 68 от англ. algorithmic — алгоритмический и англ. language — язык), усовершенствован в 1964–68 (Алгол-68). Алгол относится к языкам высокого уровня англ. high-level language и позволяет легко переводить алгебраические формулы в программные команды.
Алгол-68 обладает широким спектром возможностей, от свободы переопределения синтаксиса и операторов до матричных операций, операций со структурами, организации параллельных вычислений. Идеей языка Алгол-68 являлось достижение максимальной выразительности средств программирования и возможности запрограммирования максимально абстрактных алгоритмов.
Несмотря на схожесть названия с языком Алгол-60, Алгол-68 представляет собой существенно другой язык с другими принципами программирования и мало похожим синтаксисом.
Обилие возможностей вызвало критику многих ведущих учёных и программистов: в частности, Хоар отмечал, что, отойдя от простоты языка Алгол-60, этот язык совершенно не облегчает разработку программ. Критика Алгола-68 привела к тому, что НАТО предпочло другие принципы, и признало лучшим язык Ада ?. В СССР существовали рабочие группы по разработкам на Алголе-68 (например, новосибирская под руководством академика Андрея Петровича Ершова, ленинградская под руководством Андрея Николаевича Терехова, ростовская под руководством Александра Николаевича Маслова), но широкого распространения язык также не получил.
Причиной неудач являлась не столько сложность конструкций, сколько провокация разработчика к свободному неструктурному программированию с активным использованием собственных абстрактных категорий и обозначений. От этого код программы становился неудобочитаемым, что затрудняло разработки группы и сопровождения. Кроме того, обилие возможностей языка делало затруднительным полноценную реализацию компилятора.
Несмотря на неудачу, этот язык серьёзно повлиял на разработчиков более поздних объектно-ориентированных языков, и, в частности C++ ?, хотя многие возможности были отброшены, а многие — существенно переделаны.
Детально об этом языке можно почитать на английском языке здесь: Programming Algol 68 Made Easy.
Мы далеко не сразу осознали, какую мощную новую функцию имеет Алгол 68. Дело в том, что в этом языке впервые появилась возможность описывать новые типы данных и операции над ними. Идентификатор вида или операции надо было выделить жирным шрифтом или подчеркнуть.
mode точка = struct (real х, у);
- это описание точки, а описание прямой:
mode прямая = struct (точка а, b);
После того, как мы описали виды, ими можно пользоваться наравне с int, real и так далее. Более того, можно описать новые операции над ними. Например, операцию Пересечение, где операндами выступали бы прямые, а результатом - точка или исключительное значение в случае, когда прямые параллельны. Можно переписывать даже стандартные знаки операции, что очень удобно: +, -, *, /. Таким образом, можно спокойно описать сложение или умножение матриц - любые действия с любыми типами данных.
Одной из первых была работа моей дипломницы Наташи Витт из города Лыткарино, там находится огромный оптический завод, ориентированный в первую очередь на космос и на оборонку, но выпускает и гражданскую продукцию - линзы, зеркала, объективы. По их заказу мы разработали специализированный язык планиметрии, именно в этом языке были определены точки, прямые, окружности и другие геометрические фигуры и операции отражения и преломления. В результате, появилась возможность очень компактно и эффективно описывать сложные структуры, состоящие из многих зеркал и линз. Насколько я знаю, этот язык очень интенсивно использовался на заводе.
Внедрение в промышленность
Когда мы разработали транслятор с Алгола 68, естественно встал вопрос, как его внедрять в промышленность. Университетские люди (из разных университетов) использовали Алгол 68 очень охотно - новый язык, новые возможности. Но мы понимали, что очень важно внедрить его в реальную промышленность. И вновь так совпало, что в начале 80-ых годов (так же как и совпадение начала работ по реализации Алгола 68 с разработкой ЕС ЭВМ), нас почти силой заставили заниматься военными разработками. В начале 80-ых годов военные испытывали довольно много проблем при переходе к цифровой вычислительной технике (до этого использовались либо аналоговые машины, либо вообще не было никакой электроники). При разработке информационных систем, систем управления, основных военных приложений ЭВМ, оказалось, что никакими приказами, драконовскими порядками не заставить людей разработать и довести до промышленной эксплуатации и сопровождения систему, в которой, скажем, миллион строк кода.
Мы стали внедрять Алгол 68 как некую панацею, поскольку мы искренне думали, что этот язык очень хорошо защищен от ошибок, что если ты попробуешь сложить, грубо говоря, яблоки с коровами, то эта ошибка будет найдена или, если ты передашь неправильное число параметров в процедуру, это тоже будет обнаружено, или, если ты напишешь A[i], и i выйдет за границы массива, это также будет обнаружено и так далее.
Этот А68К стал активно использоваться не только нашим коллективом. Нам удалось внедрить это средство в самые разные организации (в основном, военного толка). Мы получили огромную пользу от этого, поскольку была широкая обратная связь: люди находили какие-то ошибки, делали предложения по улучшениям, в том числе, пользовательского интерфейса. Много нареканий вызывала система сигнализации об ошибках, мы потратили много сил, чтобы ее улучшить. В это самое время как раз появились первые персональные ЭВМ, и мы методами раскрутки перенесли А68ЛГУ на них. Чуть позже перенесли А68ЛГУ на DEC-овскую архитектуру (СМ3, СМ4). Мы уже привыкли работать на достаточно больших машинах, каковыми были ЕС ЭВМ, и, когда мы фактически сделали шаг назад и вернулись к работе на миниЭВМ, то оказалось, что то, что хорошо выглядит на ЕС ЭВМ, плохо выглядит на СМ4.
Приведу пример. Синтаксический анализ на СМ4 занимал для обычной программы 5 минут, а мы уже привыкли, что он занимает какие-то доли секунды. Мы стали исследовать этот вопрос. Оказалось, что когда-то мы применили автоматную модель для сравнения видов Алгола 68, а поскольку есть рекурсивные виды (цепные списки и юнионы), то структура видов довольно сложная. Когда мы нашли статью Ярослава Крала из Пражского Карпового университета, в которой говорилось, что можно вместо деревьев, где все алгоритмы экспоненциальны, использовать автоматные модели, где сложность сравнения автоматов или минимизации порядка n*log п, где п - количество состояний, мы обрадовались и перешли на автоматы. Но оказалось, что этот метод не очень-то и хороший - он требует сравнения всех описаний, какие только есть, включая и операции из стандартного вступления, в котором порядка тысячи описаний. Именно это и замедляло работу. Тогда мы сделали ужасный поступок: вернулись к алгоритмам, которые были реализованы еще в моей дипломной работе. Они были с экспоненциальной оценкой сложности, но эта экспонента реально возникала, только когда использовались сложные вложенные юнионы, что на практике очень редко, фактически никогда, не встречалось. Когда мы вернулись к потенциально экспоненциально сложному алгоритму, программы стали работать намного быстрее.
Об этом я часто рассказываю студентам, как о примере того, что не всегда асимптотическая оценка играет такую практически важную роль в реальной жизни. Кстати, с тех пор я встретился с еще несколькими примерами того же сорта. Но этот мне запомнился лучше всего - поскольку он был первым и, главное, казалось, что мы делаем абсурдную вещь: переходим от оценки сложности n*log п к экспоненциальной сложности, а все начинает работать быстрее. Понятно, что здесь никакого нарушения теории нет, просто эти оценки даются с точностью до некоторой константы, и когда эту константу удается, например, в сто раз уменьшить, то во многих практических случаях это оказывает решающую роль, даже большую, чем основная оценка.
Внедрение в промышленность шло болезненно, но все-таки шло. Очень помогала идея специализированных языков. Как только мы пытались объяснять людям с крупных промышленных предприятий Алгол 68 в оригинальном виде - мы встречали полное непонимание. Когда же мы забыли об Алголе 68 и стали рассказывать только о А68К, хотя всегда при этом мы пользовались нашим стандартным транслятором с полного Алгола 68, то это намного легче воспринималось. Эго дало мне пищу для размышлений, и я до сих пор считаю, что широкие массы программистов требуют выразительных, но относительно простых средств, а академические изыски им ни к чему.
Аппаратная реализация
Мы сделали больше десятка трансляторов и кросс-трансляторов для специализированных военных ЭВМ, каждая из которых была хуже другой. Дело в том, что для всех этих специализированных ЭВМ, которые проектировались инженерами и для инженеров, формулировались требования типа малого энергопотребления, надежности, возможности работы в кунге, едущем по бездорожью. При этом разработчики забывали такое простое требование, что для этих машин придется еще и программировать. В конце концов мы решили, что спасение утопающих - дело рук самих утопающих и решили сделать свою машину. Кое-что мы на эту тему уже знали: надо было разработать машину, ориентированную на языки высокого уровня - HLL-компьютер (high level language). Мы уже знали про не очень успешный опыт машины Мир с языком Аналитик, где аппаратная интерпретация стоила довольно дорого и препятствовала массовому использованию. Знали о разработке компании Intel - iAPX432, которая по тактовой частоте и другим технологическим возможностям должна была давать порядка 10 миллионов операций в секунду, а давала только 100 тысяч операций в секунду, поскольку там было 7 типов адресации, и при каждом действии динамически проверялись все эти типы адресации. Знали мы и о машине Эльбрус с ее аппаратной реализацией алгоритмических языков.
Когда мы решили, что нам хватит делать кросс-трансляторы для совершенно дурацких специализированых вычислительных машин, мы начали думать, что же надо предпринять, чтобы сделать HLL-компьютер, но не такой дорогой как Эльбрус (пусть и не такой быстрый), при этом более совершенный и эффективный чем Intel АРХ 432. Как и во многих других случаях, решение подсказал Алгол 68. После стольких лет работы над разными трансляторами с Алгола 68 для разных ЭВМ мы уже четко понимали, что главное преимущество Алгола 68 в его полном видовом контроле периода компиляции. В каждой точке программы компилятор точно знает виды обрабатываемых значений. Именно эту идею мы использовали при разработке своей вычислительной машины, которую мы назвали Самсон [13], разработали её, получили на нее три авторских свидетельства. Самсон при тактовой частоте 3.25 МГц выигрывал по скорости счета на реальных программах не менее чем в 3 раза(!) у IBM PC АТ с тактовой частотой 16 МГц. Таким образом, архитектурный выигрыш был не менее чем 15.
Главным ограничением УВК Самсон (Управляющий Вычислительный Комплекс, это была не универсальная машина, а ЭВМ для специальных применений, прежде всего для систем управления) было обязательное требование, что входные программы пишутся только на статических языках высокого уровня типа Алгол 68, Модула 2, Ада, Chill (был такой стандартный язык международного комитета по телеграфии и телефонии), но не на языках типа Фортрана, PL/1 или даже С, в котором в те времена соответствие параметров (не только их тип, но и даже количество) никак не проверялось.
На этой идее, что если абсолютное большинство проверок можно вынести на этап компиляции, а во время счета все, что проверил транслятор, уже не перепроверять, удалось сделать малогабаритную машину с высокой эффективностью. Позже наши военные заказчики потребовали сделать также и транслятор с языка С, чтобы обеспечить совместимость с теми программами, с которыми они работали раньше. Мы его, конечно, реализовали, но взяли подписку с заказчиков, что к нам претензий в случае аварийных ситуаций никто предъявлять не будет. Как говорится, кто предупрежден - тот вооружен. Наши заказчики это осознали и довольно часто проектирование программ велось на Алголе 68, а если какие-то подпрограммы использовались, ранее написанные на языке С, то при этом предпринимались все мыслимые методы и способы защиты: проверки аргументов, проверки результатов и так далее, чтобы уберечься от ненадежности языка С.
Первую реализацию УВК Самсон мы провели в основном за деньги наших болгарских друзей из города Пловдив, это готовилось как подарок к 70-летию советской власти. 5 ноября 1987 года состоялась демонстрация, на которой присутствовали члены Политбюро ЦК КПСС и Компартии Болгарии. За полчаса до начала визита высоких гостей еще ничего не работало, но как известно, я везунчик. К двум часам дня машина заработала. Фактически, она просто прошла несколько тестов, но члены Политбюро ничего другого и не спрашивали. Эго был запоминающийся момент, после этого мы стали массово гонять разнообразные тесты, улучшать архитектуру, изменять систему команд с целью ее оптимизации и так далее - это уже длинная и скучная история. Начальная же идея - опыт Алгола 68 помог нам сделать ЭВМ, отличающуюся, причем довольно сильно, от других своей архитектурой.
В 1992 году УВК Самсон была принята на вооружение. После этого я на долгий срок потерял эту машину из виду, тем более я и сам не хотел влезать в какие-то особо секретные работы. Иногда от моих бывших учеников или бывших сотрудников доходила какая-то информация об использовании Самсона. Совсем недавно я узнал, что Самсон до сих пор выпускается, причем в довольно большом количестве экземпляров.
Техники трансляции Алгола 68, используемые до сих пор
Не все из того, что мы тогда написали в этой монографии, выдержало проверку временем. Методы синтаксического анализа, которые там были предложены Мартыненко и Гиндышем, мы сейчас не используем. Сами эти методы хорошие, но там была довольно неудачно реализованная сигнализация об ошибках. В результате, после нареканий первых пользователей, мы довольно существенно переписали видонезависимый анализ, с тем, чтобы обеспечить более разумную сигнализацию об ошибках пользователей. А вот методы видозависимого анализа, идентификации мы применяем и до сих пор. В частности, именно потому, что ЭВМ того времени не были такими быстрыми и мощными, как сейчас, и их память была в тысячи раз меньше, чем сейчас, мы применяли различные оптимизации. Для того чтобы при поиске описания по применению не перебирать все строчки таблицы идентификаторов, мы ввели такую технику, что в таблице представлений у нас всегда была ссылка на текущее описание. Описание находилось буквально за одно обращение к памяти. В начале и конце блока все эти ссылки разом подменялись, что существенно ускоряло работу этого механизма (так как описаний во много раз меньше, чем применений) по сравнению с традиционным перебором.
Или, например, метод динамического распределения памяти. Моя дипломница Людмила Григорьева в своей дипломной работе сравнила различные методы динамического распределения памяти (первый подходящий, наиболее подходящий, метод граничных признаков, метод близнецов) и провела моделирование на датчике случайных чисел. Оказалось, что лучшим является метод с граничными признаками, поскольку в этом методе память не только дробится, но и укрупняется за счет склеивания рядом стоящих участков. При довольно разумных ограничениях этот метод работает практически бесконечно, не требуя сборки мусора. Теперь во всех разработках, которые мы делаем, мы используем именно этот метод, настолько удачным было это решение.
Конечно, инструменты раздельной трансляции с накоплением контекста в виде таблиц мы используем и сейчас во всех похожих случаях.
Для эффективной генерации кода Цейтин предложил разработать механизм работы с предсказателями (это стало темой моей диссертационной работы). Предположим, что у вас возникло некоторое анонимное, не имеющее идентификатора, рабочее значение на регистре. Если это значение долежит на регистре до момента использования - все хорошо, это самый эффективный случай, но если регистров не хватит, придется выгружать это значение в память. Но ведь обнаружиться нехватка регистров может в какой-нибудь внутренней конструкции, в том числе - во внутреннем цикле. Поэтому, если вы будете прямо там выгружать регистр в память, вы потеряете эффективность, поскольку в цикле эта выгрузка произойдет много раз. Лучше было бы выгрузить значение сразу во время возникновения, но кто знает - долежит оно или нет. Цейтин предложил мне использовать некую технику, которую он придумал для естественных языков еще в 50-е годы, но, разумеется, тогда на машинах типа УРАЛ-1 у него не началось даже сколько-нибудь серьезных экспериментов. Я разработал такую технику, и мы применили её в нашем трансляторе. Но тогда памяти ЭВМ были очень маленькие, а вся техника основывалась на том, что варианты перебирались не с помощью известного уже даже тогда бэктреккинга (экспоненциально сложного), а с помощью представления в виде очень сложных деревьев, где варианты использования переменных представлены в листьях этого дерева. Удалось разработать набор действий (сложение, сравнение деревьев, даже циклы по деревьям), были проведены эксперименты, но, к сожалению, эта техника в реальный транслятор не вошла - все-таки нужно много памяти. Но оказалось, что эту технику можно очень хорошо применять в другой задаче - задаче поиска методом-в-ширину.
Алгол 68 в образовании и научных исследованиях
Алгол 68 постепенно стал языком научных публикаций в нашей области. Хочется упомянуть хотя бы два примера. Профессор кафедры исследования операций нашего мат-меха Иосиф Владимирович Романовский написал книгу по исследованию операций [15], где все алгоритмы были написаны на Алголе 68, справедливо полагая, что так они выглядят наиболее компактно, ярко и выразительно.
Еще один замечательный пример. Мой близкий приятель Николай Непейвода, профессор из Удмуртского университета (г. Ижевск) около 20 лет назад опубликовал статью [16], как по доказательству в интуиционистской логике (то есть без закона исключенного третьего) можно сгенерировать алгоритм работы программы, т.е. сгенерировать действующую программу по доказательству ее корректности. В этой статье тоже органичным образом были вставлены алгоритмы на Алголе 68, так как структурами и юнионами этого языка было очень удобно описать логические преобразования.
Начитавшись статей Вирта про P-коды (виртуальные машины), которые он использовал для создания переносимых трансляторов с Паскаля, мы решили сделать что-нибудь в этом роде. Мы придумали свою виртуальную машину, она называлась Айвик - я даже уже и не помню почему. Наталья Волковская реализовала компактный анализатор с Алгола 68, и этот анализатор с помощью кросс-транслятора из Алгола 68 в коды Айвека мы поместили в дисплей 7063, в котором был однобайтовый процессор Intel8080. Там было всего 64 килобайта памяти, тем не менее, через компактную виртуальную машину нам удалось уместить анализатор с Алгола 68 в эту маленькую память, в результате студенты работали в дисплейных классах и, когда они запускали трансляцию, то незаметно для них запускался анализатор, который сидел прямо в этом дисплее. В случае ошибок именно этот анализатор выдавал ошибку, и на центральную ЭВМ программа даже не отправлялась. Если же ошибок не было, программа шла на центральную ЭВМ. В результате, нагрузка на последнюю упала в десятки раз. Жизнь студентов, работающих за дисплеями, стала более комфортная, так как время ожидания сократилось на порядок.
Читайте также: