АЛГОЛ

Эта статья о семействе языков программирования. Чтобы узнать о других значениях, см. Алгол (значения) .

АЛГОЛ

Руководство по Алголу-20 1965 года.
Парадигма	Процедурный , императивный , структурированный.
Семья	АЛГОЛ
Разработано	Бауэр , Боттенбрух , Рутисхаузер , Самельсон , Бэкус , Кац , Перлис , Вегштейн , Наур , Вокуа , ван Вейнгаарден , Вуджер , Грин , Маккарти
Впервые появился	1958 год ( 1958 )
Дисциплина набора текста	Статический , сильный
Объем	Лексический
Под влиянием
Большинство последующих императивных языков (включая так называемые АЛГОЛ-подобные языки) например PL/I , Simula , Pascal , C и Scheme

АЛГОЛ ( / ˈ æ l ɡ ɒ l , - ɡ ɔː l / ; сокращение от « Алгоритмический язык ») — это семейство императивных языков компьютерного программирования, первоначально разработанных в 1958 году. АЛГОЛ сильно повлиял на многие другие языки и был стандартным методом описания алгоритмов , используемым Ассоциацией вычислительной техники (ACM) в учебниках и академических источниках более тридцати лет.

В том смысле, что синтаксис большинства современных языков «алгольный», возможно, он оказал большее влияние, чем три других языка программирования высокого уровня, среди которых он был примерно современным: FORTRAN , Lisp и COBOL . в конечном итоге породил множество других языков программирования, включая PL/I , Simula , BCPL , B , Pascal , Ada и C. Он был разработан, чтобы избежать некоторых предполагаемых проблем с FORTRAN, и

АЛГОЛ представил блоки кода и begin... end пары для их разграничения. Это был также первый язык, реализовавший определения вложенных функций с лексической областью действия . Более того, это был первый язык программирования, в котором подробное внимание уделялось формальному определению языка, и в отчете об Алголе 60 была представлена ​​форма Бэкуса-Наура , основная формальная грамматическая запись для проектирования языка.

Существовало три основные спецификации, названные в честь года их первой публикации:

• АЛГОЛ 58 — первоначально предлагалось называть IAL , что означает «Международный алгебраический язык» .
• АЛГОЛ 60 - впервые реализован как X1 АЛГОЛ 60 в 1961 году. Пересмотрен в 1963 году.
• АЛГОЛ 68 – представлены новые элементы, включая гибкие массивы, срезы, параллелизм, идентификация операторов. Пересмотрено в 1973 году.

АЛГОЛ 68 существенно отличается от АЛГОЛа 60 и не был принят хорошо. поэтому под словом «Алгол» обычно понимают АЛГОЛ 60 и его диалекты.

История

АЛГОЛ был разработан совместно комитетом европейских и американских ученых-компьютерщиков на встрече в 1958 году в Швейцарском федеральном технологическом институте в Цюрихе (см. АЛГОЛ 58 ). Он определил три разных синтаксиса: ссылочный синтаксис, синтаксис публикации и синтаксис реализации, синтаксисы, которые позволяли использовать разные имена ключевых слов и соглашения для десятичных точек (запятые или точки) для разных языков.

АЛГОЛ использовался в основном учеными-компьютерщиками в США и Европе; коммерческим приложениям препятствовало отсутствие стандартных средств ввода/вывода в его описании, а также отсутствие интереса к языку со стороны крупных поставщиков компьютеров (кроме Burroughs Corporation ). Однако АЛГОЛ 60 стал стандартом для публикации алгоритмов и оказал глубокое влияние на будущее развитие языка.

Алгол, Фортран и КОБОЛ. Генеалогическое древо династии языков программирования

Джон Бэкус разработал метод нормальной формы Бэкуса для описания языков программирования специально для АЛГОЛА 58. Он был переработан и расширен Питером Науром для АЛГОЛА 60 и по Дональда Кнута предложению переименован в форму Бэкуса-Наура .

Питер Наур: «Как редактор бюллетеня АЛГОЛ, я был вовлечен в международные дискуссии по языку и в ноябре 1959 года был выбран членом европейской группы разработчиков языков. В этом качестве я был редактором отчета по АЛГОЛ 60, подготовленного в результате встречи АЛГОЛ-60 в Париже в январе 1960 года».

На встрече в Париже (с 1 по 16 января) присутствовали следующие люди:

• Фридрих Людвиг Бауэр , Петер Наур , Хайнц Рутисхаузер , Клаус Самельсон , Бернар Вокуа , Адриан ван Вейнгаарден и Михаэль Вуджер (из Европы)
• Джон Уорнер Бэкус , Жюльен Грин , Чарльз Кац , Джон Маккарти , Алан Джей Перлис и Джозеф Генри Вегштейн (из США).

Алан Перлис дал яркое описание встречи: «Встречи были утомительными, бесконечными и волнующими. Человек раздражался, когда хорошие идеи одного человека отбрасывались вместе с плохими идеями других. Тем не менее, усердие сохранялось в течение всего периода. 13-й был превосходен».

АЛГОЛ 60 вдохновил множество последовавших за ним языков. Тони Хоар заметил: «Это язык, настолько опередивший свое время, что он стал улучшением не только своих предшественников, но и почти всех своих преемников». Язык программирования Scheme , вариант Lisp , который принял блочную структуру и лексическую область ALGOL, также принял формулировку «Пересмотренный отчет об алгоритмической языковой схеме» для своих стандартных документов в честь ALGOL.

АЛГОЛ и исследование языка программирования

Как заметил Питер Ландин , АЛГОЛ был первым языком, в котором органично сочетались императивные эффекты с ( вызов по имени ) лямбда-исчислением . Возможно, самая элегантная формулировка языка принадлежит Джону К. Рейнольдсу , и она лучше всего демонстрирует свою синтаксическую и семантическую чистоту. Идеализированный АЛГОЛ Рейнольдса также представил убедительный методологический аргумент относительно пригодности локальных эффектов в контексте языков с вызовом по имени, в отличие от глобальных эффектов, используемых языками с вызовом по значению, такими как ML . Концептуальная целостность языка сделала его одним из основных объектов семантических исследований наряду с программированием вычислимых функций (PCF) и ML.

График внедрения IAL

На сегодняшний день существует не менее 70 дополнений, расширений, производных и подъязыков Алгола 60.

Имя	Год	Автор	Страна	Описание	Целевой процессор
ZMMD-реализация	1958	Фридрих Л. Бауэр , Хайнц Рутисхаузер, Клаус Самельсон, Герман Боттенбрух	Германия	реализация АЛГОЛА 58	Z22 (позже Zuse ​​от Z23 был поставлен с компилятором Algol 60)
X1 АЛГОЛ 60	1960 август	Эдсгер В. Дейкстра и Яап А. Зонневельд	Нидерланды	Первая реализация АЛГОЛА 60	Электрологика X1
Эллиотт Алгол	1960-е годы	АВТОМОБИЛЬ Хоар	Великобритания	Тема на Премии Тьюринга 1980 года. лекции	Эллиотт 803 , Эллиотт 503, Эллиотт 4100 серии
ВЕСЕЛЫЙ	1960	Жюль Шварц	НАС	DOD ​ HOL перед Адой	Разное (см. статью)
Берроуз Алгол (Несколько вариантов)	1961	Burroughs Corporation (при участии Хоара, Дейкстры и др.)	НАС	Основа компьютеров Burroughs (а теперь и Unisys MCP )	Компания Burroughs Large Systems , а также их устройства среднего класса.
Случай Алгола	1961	Технологический институт Кейса	НАС	Simula изначально задумывалась как расширение моделирования Case ALGOL.	УНИВАК 1107
ГОГОЛЬ	1961	Уильям М. Маккиман	НАС	Для системы разделения времени ODIN	ПДП-1
RegneCentralen АЛГОЛ	1961	Питер Наур , Йорн Йенсен	Дания	Внедрение полного Алгола 60	DASK в Регнецентралене
Дартмутский Алгол 30	1962	Томас Юджин Курц и др.	НАС		ЛГП-30
Военный корабль США 90 Алгол	1962	Л. Петроне	Италия
АЛГОЛ 60	1962	Бернар Вокуа , Луи Болье	Франция	Институт компьютерных наук и прикладной математики Гренобля (IMAG) и Compagnie des Machines Bull	Бык Гамма 60
Алголь переводчик	1962	Г. ван дер Мей и В.Л. ван дер Поэль	Нидерланды	Государственная почта, Телеграфная и телефонная компания	ЗЕБРА
Кидсгроув Алгол	1963	ФГ Дункан	Великобритания		Английская электрическая компания KDF9
ВАЛГОЛЬ	1963	Вэл Шорре	НАС	Тест META II компилятора компилятора
точильный камень	1964	Брайан Рэнделл и Эл Джей Рассел	Великобритания	Подразделение атомной энергетики английской электрической компании. Предшественник реализаций Ferranti Pegasus , National Physical Laboratories ACE и English Electric DEUCE .	Английская электрическая компания KDF9
НЕ АЛГОЛ	1965		Норвегия		УНИВАК
ВОДОРОСЛИ	1965		Советский Союз	АЛГЭК на базе АЛГОЛ-60 и КОБОЛа для экономических задач. поддержки	Минск-22
АЛГОЛ W	1966	Никлаус Вирт	НАС	Предлагаемый преемник АЛГОЛА 60.	IBM Система/360
МАЛГОЛ	1966	publ. A. Viil, M Kotli & M. Rakhendi,	Эстонская ССР		Минск-22
ЗАРПЛАТА	1967	GAMS group (ГАМС, группа автоматизации программирования для машин среднего класса), cooperation of Comecon Academies of Science	СЭВ		Минск-22 , позже ЕС ЭВМ , БЭСМ
ALGOL/ZAM	1967		Польша		Польский ZAM компьютер
С 67 лет	1967	Оле-Йохан Даль и Кристен Нигаард	Норвегия	Алгол 60 с классами	УНИВАК 1107
Триплекс-АЛГОЛ Карлсруэ	1967/1968		Карлсруэ , Германия	АЛГОЛ 60 (1963) с триплексными числами для интервальной арифметики
Китайский Алгол	1972		Китай	Китайские иероглифы, выраженные через систему символов.
ГД/Л	1972		НАС		DG Eclipse Семейство компьютеров
S-алгол	1979	Рон Моррисон	Великобритания	Добавление ортогональных типов данных с предполагаемым использованием в качестве языка обучения.	PDP-11 с последующей реализацией на Java VM

Диалекты Берроуза включали специальные диалекты начальной загрузки, такие как ESPOL и NEWP . Последний до сих пор используется для системного программного обеспечения Unisys MCP.

Характеристики

Алгол 60 в официальном определении не имел средств ввода-вывода ; реализации определяли свои собственные способами, которые редко были совместимы друг с другом. Напротив, АЛГОЛ 68 предлагал обширную библиотеку средств передачи (ввода/вывода).

АЛГОЛ 60 допускал две стратегии оценки передачи параметров : общий вызов по значению и вызов по имени . Вызов по имени имеет определенные эффекты в отличие от вызова по ссылке . Например, без указания параметров как value или reference невозможно разработать процедуру, которая будет менять местами значения двух параметров, если фактические передаваемые параметры представляют собой целочисленную переменную и массив, индексированный той же целочисленной переменной. . Подумайте о передаче указателя на swap(i, A[i]) в функцию. Теперь, когда каждый раз обращаются к свопу, он пересчитывается. Скажем, i := 1 и A[i] := 2, поэтому при каждом обращении к swap он будет возвращать другую комбинацию значений ([1,2], [2,1], [1,2] и т. д. ). Аналогичная ситуация возникает со случайной функцией, переданной в качестве фактического аргумента.

Функция Call-by-name известна многим разработчикам компиляторов благодаря интересным « thunks », которые используются для ее реализации. Дональд Кнут разработал « тест мужчины или мальчика » для разделения компиляторов, которые правильно реализовали « рекурсию и нелокальные ссылки». Этот тест содержит пример вызова по имени.

Алгол 68 был определен с использованием двухуровневого грамматического формализма, изобретенного Адрианом ван Вейнгаарденом и носящего его имя. Грамматики Ван Вейнгаардена используют контекстно-свободную грамматику для создания бесконечного набора продуктов, которые распознают конкретную программу ALGOL 68; в частности, они способны выражать требования, которые во многих других стандартах языков программирования называются «семантикой» и должны быть выражены в склонной к неоднозначности прозе естественного языка, а затем реализованы в компиляторах в виде специального кода, прикрепленного к формальному языку. парсер.

Примеры и переносимость

Сравнение примеров кода

АЛГОЛ 60

(Способ написания жирного текста зависит от реализации, например, «ЦЕЛОЕ» (включая кавычки) для целого числа. Это называется обрезкой .)

procedure Absmax(a) Size:(n, m) Result:(y) Subscripts:(i, k);
    value n, m; array a; integer n, m, i, k; real y;
comment The absolute greatest element of the matrix a, of size n by m,
    is copied to y, and the subscripts of this element to i and k;
begin
    integer p, q;
    y := 0; i := k := 1;
    for p := 1 step 1 until n do
        for q := 1 step 1 until m do
            if abs(a[p, q]) > y then
                begin y := abs(a[p, q]);
                    i := p; k := q
                end
end Absmax

Вот пример того, как создать таблицу с помощью Elliott 803 ALGOL.

 FLOATING POINT ALGOL TEST'
 BEGIN REAL A,B,C,D'
 READ D'
 FOR A:= 0.0 STEP D UNTIL 6.3 DO
 BEGIN
   PRINT PUNCH(3),££L??'
   B := SIN(A)'
   C := COS(A)'
   PRINT PUNCH(3),SAMELINE,ALIGNED(1,6),A,B,C'
 END
 END'

АЛГОЛ 68

Следующие примеры кода представляют собой версии ALGOL 68 приведенных выше примеров кода ALGOL 60.

Реализации ALGOL 68 использовали подходы ALGOL 60 к ограничению . В случае Алгола 68 токены, выделенные жирным шрифтом, представляют собой зарезервированные слова, типы (режимы) или операторы.

proc abs max = ([,]real a, ref real y, ref int i, k)real:
comment The absolute greatest element of the matrix a, of size ⌈a by 2⌈a
is transferred to y, and the subscripts of this element to i and k; comment
begin
   real y := 0; i := ⌊a; k := 2⌊a;
   for p from ⌊a to ⌈a do
     for q from 2⌊a to 2⌈a do
       if abs a[p, q] > y then
           y := abs a[p, q];
           i := p; k := q
       fi
     od
   od;
   y
end # abs max #

Примечание. Нижняя (⌊) и верхняя (⌈) границы массива, а также срез массива доступны непосредственно программисту.

floating point algol68 test:
(
  real a,b,c,d;
   
  # printf – sends output to the file stand out. #
  # printf($p$); – selects a new page #
  printf(($pg$,"Enter d:"));  
  read(d);
   
  for step from 0 while a:=step*d; a <= 2*pi do
    printf($l$);  # $l$ - selects a new line. #
    b := sin(a);
    c := cos(a);
    printf(($z-d.6d$,a,b,c))  # formats output with 1 digit before and 6 after the decimal point. #
  od
)

Таймлайн: Привет, мир!

Вариации и отсутствие переносимости программ из одной реализации в другую легко демонстрируется на примере классической программы hello world .

АЛГОЛ 58 (ИАЛ)

Основная статья: АЛГОЛ 58

Алгол 58 не имел средств ввода-вывода.

Семейство АЛГОЛ 60

Основная статья: АЛГОЛ 60

Поскольку в АЛГОЛе 60 не было средств ввода-вывода, в АЛГОЛе нет переносимой программы hello world . Следующие три примера находятся в расширенном алгоритме Берроуза. Первые два напрямую выводятся на интерактивный терминал, на котором они запущены. Первый использует массив символов, аналогичный C. Язык позволяет использовать идентификатор массива в качестве указателя на массив и, следовательно, в инструкции REPLACE.

BEGIN
   FILE F(KIND=REMOTE);
   EBCDIC ARRAY E[0:11];
   REPLACE E BY "HELLO WORLD!";
   WRITE(F, *, E);
 END.

Более простая программа, использующая встроенный формат:

BEGIN
   FILE F(KIND=REMOTE);
   WRITE(F, <"HELLO WORLD!">);
 END.

Еще более простая программа, использующая оператор Display. Обратите внимание, что его выходные данные попадут на системную консоль («SPO»):

BEGIN DISPLAY("HELLO WORLD!") END.

Альтернативный пример использования ввода-вывода Elliott Algol выглядит следующим образом. Эллиот Алгол использовал разные символы для «цитат открытой строки» и «кавычек закрытой строки», представленных здесь как  '   и  ’  .

program HiFolks;
 begin
    print ‘Hello world’
 end;

Ниже представлена ​​версия от Elliott 803 Algol (A104). В стандартном Elliott 803 использовалась бумажная лента с пятью отверстиями, поэтому в нем были только заглавные буквы. В коде отсутствовали символы кавычек, поэтому для открытой кавычки использовался £ (знак британского фунта), а ? (Знак вопроса) для закрытия цитаты. Специальные последовательности заключались в двойные кавычки (например, ££L?? выводил на телетайпе новую строку).

  HIFOLKS'
  BEGIN
     PRINT £HELLO WORLD£L??'
  END'

Версия ввода-вывода Algol серии ICT 1900 позволяла вводить данные с бумажной ленты или перфокарты. В режиме «заполнения» бумажной ленты разрешен нижний регистр. Вывод осуществлялся на построчный принтер. Символы открывающей и закрывающей кавычек были представлены с помощью символов «(» и «)» и пробелов через %.

  'BEGIN'
     WRITE TEXT('('HELLO%WORLD')');
  'END'

АЛГОЛ 68

Основная статья: АЛГОЛ 68

Код ALGOL 68 был опубликован с зарезервированными словами, обычно написанными строчными буквами, но выделенными жирным шрифтом или подчеркнутыми.

begin
  printf(($gl$,"Hello, world!"))
end

На языке «Отчета об Алголе 68» средства ввода/вывода назывались «Транспут».

Хронология специальных символов АЛГОЛА

Алголы были задуманы в то время, когда наборы символов были разнообразны и быстро развивались; кроме того, АЛГОЛы были определены так, что только заглавные требовались буквы.

1960: ИФИП . Язык и отчет Алгол 60 включали несколько математических символов, которые доступны на современных компьютерах и операционных системах, но, к сожалению, в то время не поддерживались большинством вычислительных систем. Например: ×, ÷, ≤, ≥, ≠, ¬, ∨, ∧, ⊂, ≡, ␣ и ⏨.

Сентябрь 1961 года: ASCII. В набор символов ASCII , находившийся тогда на ранней стадии разработки, был добавлен символ \ (обратная косая черта) для поддержки логических операторов АЛГОЛА /\ и \/ .

1962: ALCOR - этот набор символов включал необычный рунический крест «᛭». символ умножения и символ десятичной экспоненты «⏨». для записи с плавающей запятой.

1964: ГОСТ . Советский стандарт ГОСТ 10859 1964 года разрешал кодирование 4-битных, 5-битных, 6-битных и 7-битных символов в АЛГОЛе.

1968: «Отчет об Алголе 68» - использовались существующие символы ALGOL и в дальнейшем приняты символы →, ↓, ↑, □, ⌊, ⌈, ⎩, ⎧, ○, ⊥ и ¢, которые можно найти на клавиатуре IBM 2741 с помощью печатного мяча (или мяча для гольфа ) вставлены печатающие головки (например, мяча для гольфа APL ). Они стали доступны в середине 1960-х годов, когда разрабатывался Алгол 68. Отчет был переведен на русский, немецкий, французский и болгарский языки и позволял программировать на языках с более широким набором символов, например, на кириллице советского БЭСМ -4. Все символы АЛГОЛА также являются частью стандарта Unicode , и большинство из них доступны в нескольких популярных шрифтах .

Октябрь 2009 г.: Юникод – The ⏨ (Символ десятичной экспоненты) для записи с плавающей запятой был добавлен в Unicode 5.2 для обратной совместимости с историческим программным обеспечением ALGOL программы Buran .

См. также

• Адрес (язык программирования)
• Атлас Автокод
• Коралл 66
• Эдинбургский ИМП
• Устройство Дженсена
• ИСВИМ
• ВЕСЕЛЫЙ
• Трон (видеоигра)
• НЕЛИАК
• начало
• S-алгол
• Схема (язык программирования)

Дальнейшее чтение

• О'Хирн, Питер; Теннент, Роберт Д., ред. (1997). Алголоподобные языки . Том. 1. Кембридж, Массачусетс: Биркхаузер. дои : 10.1007/978-1-4612-4118-8 . ISBN  9780817638801 . S2CID   6273486 . Первый том двухтомного набора, который включает введение Питера У. О'Хирна и Роберта Д. Теннента, отчет об Алголе 60 Питера Наура и его коллег, четыре главы Джона К. Рейнольдса и другие главы Кристофера. Стрейчи , Матиас Феллисен , Стивен Уикс , Альберт Р. Мейер , Курт Зибер, Випин Сваруп, Удай С. Редди и Эван Айрлэнд.
• Бауманн, Рихард [на немецком языке] ; Фелисиано, Мануэль; Бауэр, Фридрих Людвиг ; Самельсон, Клаус (1964). Введение в АЛГОЛ – учебник для неспециалистов, подчеркивающий практическое использование алгоритмического языка . Автоматический расчет. Энглвуд Клиффс, Нью-Джерси: Prentice-Hall, Inc. ISBN  0134778286 . LCCN   64-10740 . ковчег:/13960/t6qz35p37 . Проверено 23 октября 2022 г.
• Рэнделл, Брайан и Л. Дж. Рассел (1964). Реализация ALGOL 60: перевод и использование программ ALGOL 60 на компьютере . Академическая пресса. CiteSeerX   10.1.1.737.475 . . О конструкции компилятора Whetstone и одном из ранних опубликованных описаний реализации компилятора. Соответствующую статью см. в « Брайана Рэнделла , Возвращение к точильному камню Алгола» заархивированному 27 февраля 2008 года в Wayback Machine , и в «Переводчике Алгола Whetstone KDF9» .
• Дейкстра, Э.В. (1961), Перевод АЛГОЛа 60: транслятор АЛГОЛа 60 для X1 и создание транслятора для АЛГОЛА 60 (PDF) , отчет MR 35/61, Амстердам: Mathematisch Centrum, в архиве (PDF) с оригинала 9 октября
• Круземан Арец, Франс Э.Дж., Компилятор ALGOL 60 Дейкстры-Зонневельда для Electrologica X1 (PDF) , Историческая справка SEN, 2, Амстердам: Centrum voor Wiskunde en Informatica, заархивировано (PDF) из оригинала 9 октября 2022 г.
• Гус, Герхард [на немецком языке] (7 августа 2017 г.). История немецкоязычной информатики - Языки программирования и проектирование компиляторов [ История информатики в немецкоязычных странах - Языки программирования и проектирование компиляторов ] (PDF) (на немецком языке). Карлсруэ, Германия: Факультет компьютерных наук Технологического института Карлсруэ . Архивировано (PDF) из оригинала 19 мая 2022 г. Проверено 14 ноября 2022 г.

Внешние ссылки

• Пересмотренный отчет об алгоритмическом языке Algol 60 Питера Наура и др.
• Европейская сторона последней фазы разработки Алгола 60, Питер Наур
• История Алгола из Музея истории компьютеров.
• Компилятор ALGOL-F с поддержкой Интернета, позволяющий проводить небольшие эксперименты.
• Онлайн-компилятор АЛГОЛА
• Компилятор ALGOL60 или Ян ван Катвейк (GitHub)