Введение

Язык программирования ALGOL 68 (сокращение от Algorithmic Language 1968) — это императивный язык программирования, задуманный как преемник языка программирования ALGOL 60, разработанный с целью значительно более широкого спектра применения и более строго определенного синтаксиса и семантики. Сложность определения языка, насчитывающая несколько сотен страниц, заполненных нестандартной терминологией, затрудняла реализацию компиляторов, и говорили, что у него «нет реализаций и нет пользователей». Это было лишь отчасти правдой: ALGOL 68 нашёл применение в нескольких нишевых областях, особенно в Великобритании, где он был популярен на машинах International Computers Limited (ICL), а также в учебных целях. За пределами этих областей его использование было относительно ограничено. Тем не менее, вклад ALGOL 68 в область компьютерных наук был глубоким, широким и долговечным, хотя многие из этих вкладов были публично признаны только тогда, когда они вновь появились в языках программирования, разработанных позднее. Многие языки были разработаны специально как реакция на кажущуюся сложность ALGOL 68, наиболее известным из которых является Pascal, или были повторными реализациями для конкретных задач, например, Ada. Многие языки 1970-х годов напрямую выводят свой дизайн из ALGOL 68, выбирая некоторые функции и отказываясь от других, которые считались слишком сложными или не подходящими для определенных задач. Среди них — язык C, на который ALGOL 68 оказал непосредственное влияние, особенно в части строгой типизации и структур данных. Большинство современных языков прослеживают хотя бы часть своего синтаксиса к C или Pascal, а следовательно, прямо или косвенно к ALGOL 68.

Происхождение

ALGOL 68, как следует из названия, является развитием языка ALGOL, который был впервые формализован в 1960 году. В том же году была образована Международная федерация по обработке информации (IFIP) и начала работу Рабочая группа по ALGOL, или WG2.1. Эта группа опубликовала обновлённую спецификацию ALGOL 60 в Риме в апреле 1962 года. На последующей встрече в марте 1964 года было решено, что группа должна приступить к разработке двух новых стандартов: ALGOL X, который представлял собой переопределение языка с некоторыми дополнениями, и ALGOL Y, который должен был обладать возможностью модифицировать собственные программы в стиле языка LISP.

Процесс определения

Первое собрание группы ALGOL X состоялось в Принстонском университете в мае 1965 года. В отчете о встрече были отмечены две широко поддерживаемые темы: введение строгой типизации и интерес к концепциям Эйлера о «деревьях» или «списках» для обработки коллекций данных. На втором заседании в октябре во Франции были представлены три официальных предложения: ALGOL W Никлауса Вирта с комментариями К. А. Р. (Тони) Хоара о структурах записей, аналогичный язык Герхарда Зегмюллера и статья Адриаана ван Вейнгаардена «Ортогональное проектирование и описание формального языка». Последняя, написанная почти неразборчивой «Грамматикой W», оказалась решающим сдвигом в эволюции языка. Встреча завершилась соглашением о том, что ван Вейнгаарден перепишет предложение Вирта/Хоара, используя его грамматику W. Эта, казалось бы, простая задача в итоге оказалась сложнее, чем ожидалось, и следующее совещание пришлось отложить на шесть месяцев. Когда оно состоялось в апреле 1966 года в Кутвике, проект ван Вейнгаардена оставался незавершенным, и Вирт и Хоар представили версию, использующую более традиционные описания. В целом было признано, что их работа была «правильным языком в неверном формализме». По мере изучения этих подходов стало ясно, что существует разница в способе описания параметров, которая повлечет за собой реальные последствия, и, хотя Вирт и Хоар протестовали против того, что дальнейшие задержки могут стать бесконечными, комитет решил дождаться версии ван Вейнгаардена. Затем Вирт реализовал их текущее определение как ALGOL W.

На следующей встрече в Варшаве в октябре 1966 года был представлен предварительный доклад подкомитета по вводу/выводу, который встречался в Национальной лаборатории Оук-Ридж и Университете Иллинойса, но пока не достиг значительного прогресса. Два предложения с предыдущего заседания были вновь рассмотрены, и на этот раз возникла новая дискуссия об использовании указателей: ALGOL W использовал их только для ссылок на записи, в то время как версия ван Вейнгаардена могла указывать на любой объект. Чтобы добавить путаницы, Джон Маккарти представил новое предложение о перегрузке операторов и возможности объединять конструкции «и» или «или», а Клаус Сэмэльсон хотел разрешить анонимные функции. В результате возникшей неразберихи некоторые участники обсуждали возможность отказа от всего проекта. Смущение продолжалось на встрече, которая должна была стать встречей ALGOL Y в Зандворте в мае 1967 года.

Публикация

Проект доклада был наконец опубликован в феврале 1968 года. Это вызвало "шок, ужас и протест", главным образом из-за сотен страниц нечитаемой грамматики и странной терминологии. Чарльз Линдси попытался понять, "какой язык скрывался внутри", что потребовало шести человеко-недель усилий. Результатом стала работа "ALGOL 68 с меньшим количеством огорчений", которая получила широкое распространение. На более широкой конференции по обработке информации в Цюрихе в мае 1968 года участники жаловались, что язык им навязывают, и что IFIP является "истинным виновником этой нелепой ситуации", поскольку заседания проходили преимущественно в закрытом режиме и не было формального механизма обратной связи. Вирт и Питер Наур в то время официально сложили с себя полномочия в WG2.1. Следующее заседание WG2.1 состоялось в Тиррении в июне 1968 года. Предполагалось обсудить выпуск компиляторов и другие вопросы, но вместо этого дискуссия свелась к обсуждению самого языка. Ван Вийнгарден ответил (или пригрозил), что выпустит только еще одну версию доклада. К этому моменту Наур, Хоар и Вирт покинули проект, а еще несколько человек угрожали последовать их примеру. За этим последовали другие встречи: в Норт-Бервике в августе 1968 года и в Мюнхене в декабре, которые привели к выпуску официального доклада в январе 1969 года, а также к написанию спорного доклада меньшинства. Наконец, в Банфе, провинция Альберта, в сентябре 1969 года проект был в целом признан завершенным, и обсуждение касалось в основном опечаток и значительно расширенного введения к докладу. Работа заняла пять лет, истощила многих выдающихся ученых в области информатики и несколько раз зашла в тупик из-за разногласий как в определении языка, так и внутри самой группы. Хоар почти сразу же опубликовал "Критику ALGOL 68", на которую широко ссылаются в многочисленных работах. Вирт продолжил развивать концепцию ALGOL W и выпустил ее как Pascal в 1970 году.

ALGOL 68-R

Первая реализация стандарта, основанная на проекте отчета конца 1968 года, была представлена Королевским радиолокационным заведением в Великобритании как ALGOL 68 R в июле 1970 года. Однако это было лишь подмножество полного языка, и Барри Мейлу, последний редактор отчета, пошутил: "Это вопрос морали. У нас есть Библия, а вы грешите!". Эта версия, тем не менее, стала очень популярной на машинах ICL и широко использовалась в военном программировании, особенно в Великобритании. Среди изменений в 68 R было требование объявлять все переменные перед их первым использованием. Это давало значительное преимущество, позволяя компилятору выполнять однопроходную компиляцию, поскольку место для переменных в записи активации резервировалось до их использования. Однако это изменение также привело к тому, что процедуры PROC требовалось объявлять дважды: сначала как объявление типов, а затем – как тело кода. Другим изменением было исключение неявного режима VOID, выражения, не возвращающего значения (называемого оператором в других языках), и требование явно указывать слово VOID там, где оно подразумевалось. Кроме того, в 68 R были устранены явные команды параллельной обработки на основе PAR. a68g, GPLv3, написан Марселем ван дер Виром. algol68toc, порт с открытым исходным кодом ALGOL 68RS. Экспериментальный фронтенд Algol68 для GCC, написан Хосе Э. Маркези.

Единицы: выражения

Основная конструкция языка — это единица. Единицей может быть формула, заключенный блок, текст подпрограммы или одна из нескольких технически необходимых конструкций (присваивание, переход, пропуск, нигиль). Технический термин "заключенный блок" объединяет некоторые из по своей природе заключающие конструкции, известные как блок, оператор do, оператор switch в других современных языках. Когда используются ключевые слова, для завершения заключения обычно используется обратная последовательность символов вводящего ключевого слова, например (IF ~ THEN ~ ELSE ~ FI, CASE ~ IN ~ OUT ~ ESAC, FOR ~ WHILE ~ DO ~ OD). Этот синтаксис команд с защитой был повторно использован Стивеном Борном в стандартной оболочке Unix Bourne shell. Выражение также может возвращать множественное значение, которое формируется из других значений с помощью сопутствующего блока. Эта конструкция выглядит как набор параметров вызова процедуры.

Специальные символы

Большинство "специальных" символов Algol (⊂, ≡, ␣, ×, ÷, ≤, ≥, ≠, ¬, ⊃, ≡, ∨, ∧, →, ↓, ↑, ⌊, ⌈, ⎩, ⎧, ⊥, ⏨, ¢, ○ и □) можно найти на клавиатуре IBM 2741 с установленной печатной головкой APL "гольф-шарик"; они стали доступны в середине 1960-х годов, в период разработки ALGOL 68. Эти символы также входят в стандарт Unicode, и большинство из них доступны в нескольких популярных шрифтах.

Операционные системы, написанные на ALGOL 68

Компьютер Cambridge CAP – Все процедуры, составляющие операционную систему, были написаны на ALGOL 68C, хотя несколько других тесно связанных защищенных процедур, таких как paginator, написаны на BCPL. Eldon 3 – Разработан в Лидском университете для ICL 1900 и был написан на ALGOL 68 R. Flex machine – Аппаратное обеспечение было специализированным и микропрограммируемым, с операционной системой, (модульным) компилятором, редактором, сборщиком мусора и системой файлов, все написанные на ALGOL 68RS. Командная оболочка Curt была разработана для доступа к типизированным данным, аналогичным режимам Algol 68. VME – S3 был языком реализации операционной системы VME. S3 был основан на ALGOL 68, но с типами данных и операторами, соответствующими тем, что предлагались серией ICL 2900. Примечание: Советские компьютеры Эльбрус 1 и Эльбрус 2 были созданы с использованием языка высокого уровня Эль 76 (AL 76), а не традиционной ассемблерной разработки. Эль 76 похож на Algol 68, основное отличие заключается в динамической привязке типов в Эль 76, поддерживаемой на аппаратном уровне. Эль 76 использовался для прикладного, управляющего и системного программирования.

Приложения

И ALGOL 68C, и ALGOL 68 R написаны на ALGOL 68, что фактически делает ALGOL 68 приложением к самому себе. Другие приложения включают:

ELLA – язык описания аппаратуры и инструментарий поддержки. Разработан Королевским учреждением сигналов и радиолокации в 1980-х и 1990-х годах. Система управления ударными силами ВВС – "400 КБ безошибочного кода ALGOL 68 RT было создано за три человеко-года работы".

Библиотеки и API

NAG Numerical Libraries – программная библиотека подпрограмм численного анализа. Поставлялась на языке ALGOL 68 в 1980-х годах. TORRIX – система программирования для выполнения операций над векторами и матрицами над произвольными полями переменного размера, разработанная С. Г. ван дер Мюленом и М. Велдхорстом.

Переработки

За исключением случаев, когда это отмечено (с использованием сноски), язык, описанный выше, соответствует языку "Пересмотренного отчета" (r1).

Спецификация и график реализации True ALGOL 68s

Название Год Цель Страна Описание Целевой CPU Лицензирование Язык реализации
Generalized ALGOL 1962 Научный ALGOL для обобщенных грамматик
ALGOL YY 1966 Проект предложения Intl Первая версия Algol 68 Спецификация
ACM ALGOL 68DR 1968 Проект предложения Intl IFIP WG 2.1 Проект отчета Спецификация – Март
ACM ALGOL 68r0 1968 Стандарт Intl IFIP WG 2.1 Окончательный отчет Спецификация – Август
ACM ALGOL 68 RR 1970 Военный ICL 1900 ALGOL 60
EPOS ALGOLE 1971 Научный ALGOL 68
RSRS 1972 Военный Портативная компиляторная система ICL 2900/Series 39, Multics, VMS & C generator (1993) Crown Copyright
ALGOL 68RS 1972 Экспериментальные и другие Добавление областей к Algol 68
Mini ALGOL 68 1973 Исследование "Интерпретатор для простых программ Algol 68" Портативный интерпретатор Mathematisch Centrum
ALGOL 60 1973 Исследование OREGANO "Важность моделей реализации." UCLA ALGOL 68CC 1975 Научный Cambridge Algol 68 ICL, IBM 360, PDP 10 & Unix, Telefunken, Tesla & Z80 (1980) Cambridge
ALGOL 68C 1975 Стандарт Intl IFIP WG 2.1 Revised Report Спецификация ACM Algol HH 1975 Экспериментальные и другие Предлагаемые расширения системы режимов Algol 68 Спецификация
ALGOL WOdra 1976 Практическое применение / Odra 1204/IL Советский ALGOL 60
Oklahoma ALGOL 68 1976 Обучение программированию Реализация Oklahoma State University IBM 1130 и System/370/158 ANSI Fortran 66.
Berlin ALGOL 68 1977 Исследование "Реализация Berlin ALGOL 68" & Абстрактная машина ALGOL 68 – компилятор, не зависящий от машины Technical University of Berlin
CDL 2FLACCF 1977 Многоцелевой Полная реализация с функциями отладки System/370 lease, Chion Corporation Assembler
ALGOL 68 RTRT 1979 Научный Параллельный ALGOL 68 R
RS Algolrs 1979 Научный ALGOL 68+ 1980 Научный Предлагаемый суперязык ALGOL 68
M 220 ALGOL 68 1980 Советский EPSILON
Leningrad ALGOL 68L 1980 Телекоммуникации Полный язык + модули IBM, DEC, CAMCOH, PS 1001 & PC Советский
Interactive ALGOL 68I 1983 Инкрементная компиляция PC Noncommercial shareware
ALGOL 68SS 1985 Научный Intl Sun версия ALGOL 68 Sun 3, Sun SPARC (под SunOS 4.1 & Solaris 2), Atari ST (под GEMDOS), Acorn Archimedes (под RISC OS), VAX 11 под Ultrix 32
Algol68toC (ctrans) 1985 Электроника ctrans из ELLA ALGOL 68RS Портативный C-генератор
1995 ALGOL 68RSMK2 Interactive ALGOL 68 1992 Инкрементная компиляция PC Noncommercial shareware
Algol 68 GenieG 2001 Полный язык Включает стандартное оговорку о залоге Портативный интерпретатор C
Algol 68 Genie version 2.0.0 2010 Полный язык Портативный интерпретатор; опциональная компиляция выбранных модулей C

Язык S3, использовавшийся для написания операционной системы ICL VME и многих других системных программ для ICL 2900 Series, был прямым производным от Algol 68. Однако он опускал многие из более сложных функций и заменял основные режимы набором типов данных, которые напрямую соответствовали аппаратной архитектуре серии 2900.

Специфические расширения для реализации

ALGOL 68R(R) от RRE была первой реализацией подмножества ALGOL 68, работавшей на ICL 1900. Основанными на исходном языке, основными ограничениями подмножества были определение перед использованием и отсутствие параллельной обработки. Этот компилятор был популярен в университетах Великобритании в 1970-х годах, где многие студенты, изучающие компьютерные науки, осваивали ALGOL 68 как свой первый язык программирования; компилятор славился информативными сообщениями об ошибках. ALGOL 68RS(RS) от RSRE представляла собой переносимую компиляторную систему, написанную на ALGOL 68RS (собранную из ALGOL 68R) и реализованную на различных системах, включая ICL 2900/Series 39, Multics и DEC VAX/VMS. Язык основывался на Revised Report, но с аналогичными ограничениями подмножеств, как в ALGOL 68R. Этот компилятор сохранился в виде компилятора Algol68 to C. В ALGOL 68S(S) от Университета Карнеги-Меллона возможности параллельной обработки были расширены за счет добавления ортогонального расширения – событий. Любое объявление переменной, содержащее ключевое слово EVENT, делало присваивания этой переменной доступными для параллельного вычисления, то есть правая часть преобразовывалась в процедуру, которая перемещалась на один из процессоров многопроцессорной системы C. mmp. Доступ к таким переменным задерживался до завершения присваивания. Cambridge ALGOL 68C(C) был переносимым компилятором, реализующим подмножество ALGOL 68, ограничивающим определения операторов и исключающим сборку мусора, гибкие строки и форматированный вывод. Algol 68 Genie(G) от М. ван дер Вера – это реализация ALGOL 68 для современных компьютеров и операционных систем. "Несмотря на благие намерения, программист может нарушить переносимость, непреднамеренно используя локальное расширение. Чтобы предотвратить это, каждая реализация должна предоставлять прагматическую опцию PORTCHECK. Пока эта опция активна, компилятор выводит сообщение для каждой конструкции, которую он распознает как нарушающую какое-либо ограничение переносимости."

Цитируемые работы

Брайлсфорд, Д. Ф. и Уокер, А. Н., Введение в программирование на ALGOL 68, Эллис Хорвуд/Уайли, 1979
Линдси, Ч. Х. и ван дер Мюлен, С. Г., Неформальное введение в ALGOL 68, Норт-Холланд, 1971
МакГеттрик, А. Д., ALGOL 68: первый и второй курс, Издательство Кембриджского университета, 1978
Пек, Дж. Е. Л., An ALGOL 68 Companion, Университет Британской Колумбии, октябрь 1971
Таненбаум, А. С., Учебное пособие по ALGOL 68, Computing Surveys, 8, 155–190, июнь 1976 и 9, 255–256, сентябрь 1977
Вудворд, П. М. и Бонд, С. Г., Руководство пользователя ALGOL 68 R, Лондон, Издательство Ее Величества, 1972