АЛГОЛ ( / ˈ æ l ɡ ɒ l , - ɡ ɔː l / ; сокращение от « Алгоритмический язык ») [1] — семейство императивных языков программирования, первоначально разработанное в 1958 году. АЛГОЛ оказал сильное влияние на многие другие языки и был стандартным методом описания алгоритмов, используемым Ассоциацией вычислительной техники (ACM) в учебниках и академических источниках на протяжении более тридцати лет. [2]
В том смысле, что синтаксис большинства современных языков «похож на Algol», [3] он, возможно, оказал большее влияние, чем три других языка программирования высокого уровня, среди которых он был примерно современником: FORTRAN , Lisp и COBOL . [4] Он был разработан, чтобы избежать некоторых предполагаемых проблем с FORTRAN, и в конечном итоге дал начало многим другим языкам программирования, включая PL /I , Simula , BCPL , B , Pascal , Ada и C.
ALGOL ввел блоки кода и пары begin... endдля их разграничения. Это был также первый язык, реализующий вложенные определения функций с лексической областью действия . Более того, это был первый язык программирования, который уделил пристальное внимание формальному определению языка и через отчет Algol 60 ввел форму Бэкуса–Наура , основную формальную грамматическую нотацию для проектирования языка.
Существовало три основных спецификации, названные по годам их первой публикации:
ALGOL 68 существенно отличается от ALGOL 60 и не был хорошо принят, [ по мнению кого? ] поэтому ссылка на «Algol» обычно подразумевает ALGOL 60 и его диалекты. [ необходима ссылка ]
ALGOL был разработан совместно комитетом европейских и американских специалистов по информатике на встрече в 1958 году в Швейцарском федеральном технологическом институте в Цюрихе (см. ALGOL 58 ). [9] Он определил три различных синтаксиса: синтаксис ссылок, синтаксис публикации и синтаксис реализации, синтаксисы, которые позволяли использовать различные ключевые слова и соглашения для десятичных точек (запятые и точки) для разных языков. [5]
ALGOL использовался в основном исследователями-компьютерщиками в Соединенных Штатах и Европе; коммерческое применение было затруднено отсутствием стандартных средств ввода/вывода в его описании и отсутствием интереса к языку со стороны крупных поставщиков компьютеров (кроме Burroughs Corporation ). [10] ALGOL 60, однако, стал стандартом для публикации алгоритмов и оказал глубокое влияние на будущее развитие языка. [10]
Джон Бэкус разработал метод нормальной формы Бэкуса для описания языков программирования специально для АЛГОЛа 58. Он был пересмотрен и расширен Питером Науром для АЛГОЛа 60 и по предложению Дональда Кнута переименован в форму Бэкуса–Наура . [11]
Питер Наур: «Как редактор ALGOL Bulletin я был вовлечён в международные дискуссии по языку и был выбран членом Европейской группы по разработке языка в ноябре 1959 года. В этом качестве я был редактором отчёта ALGOL 60, подготовленного в результате встречи ALGOL 60 в Париже в январе 1960 года». [12]
На встрече в Париже (с 11 по 16 января) присутствовали следующие лица: [5]
Алан Перлис дал яркое описание встречи: «Встречи были изнурительными, бесконечными и воодушевляющими. Человек раздражался, когда его хорошие идеи отбрасывались вместе с плохими идеями других. Тем не менее, усердие сохранялось в течение всего периода. Химия 13 была превосходной». [13]
ALGOL 60 вдохновил многие последующие языки. Тони Хоар заметил: «Вот язык, который настолько опередил свое время, что он был не только улучшением своих предшественников, но и почти всех своих последователей». [14] Язык программирования Scheme , вариант Lisp , который принял блочную структуру и лексическую область ALGOL, также принял формулировку «Пересмотренный отчет по алгоритмической схеме языка» для своих документов стандартов в знак уважения к ALGOL. [15]
Как отметил Питер Ландин , [ требуется ссылка ] АЛГОЛ был первым языком, который органично объединил императивные эффекты с лямбда-исчислением ( вызов по имени ) . [ требуется ссылка ] Возможно, самая элегантная формулировка языка принадлежит Джону К. Рейнольдсу , и она лучше всего демонстрирует его синтаксическую и семантическую чистоту. [ согласно кому? ] Идеализированный Рейнольдсом АЛГОЛ также представил убедительный методологический аргумент относительно пригодности локальных эффектов в контексте языков вызова по имени, в отличие от глобальных эффектов, используемых языками вызова по значению, такими как ML . [ требуется ссылка ] Концептуальная целостность языка сделала его одним из главных объектов семантических исследований, наряду с программированием вычислимых функций (PCF) и ML. [ требуется ссылка ]
На сегодняшний день существует не менее 70 дополнений, расширений, производных и подъязыков Алгола 60. [16]
Диалекты Burroughs включали специальные диалекты Bootstrapping, такие как ESPOL и NEWP . Последний до сих пор используется для системного программного обеспечения Unisys MCP.
ALGOL 60, как официально определено, не имел средств ввода/вывода ; реализации определяли свои собственные способами, которые редко были совместимы друг с другом. Напротив, ALGOL 68 предлагал обширную библиотеку средств переноса (ввода/вывода).
ALGOL 60 допускал две стратегии оценки для передачи параметров : общий вызов по значению и вызов по имени . Вызов по имени имеет определенные эффекты в отличие от вызова по ссылке . Например, без указания параметров как значения или ссылки невозможно разработать процедуру, которая поменяет местами значения двух параметров, если фактические переданные параметры являются целочисленной переменной и массивом, индексированным этой же целочисленной переменной. [25] Подумайте о передаче указателя на swap(i, A[i]) в функцию. Теперь, когда каждый раз, когда ссылаются на swap, он переоценивается. Скажем, i := 1 и A[i] := 2, поэтому каждый раз, когда ссылаются на swap, он будет возвращать другую комбинацию значений ([1,2], [2,1], [1,2] и т. д.). Похожая ситуация возникает со случайной функцией, переданной в качестве фактического аргумента.
Call-by-name известен многим разработчикам компиляторов по интересным " thunks ", которые используются для его реализации. Дональд Кнут разработал " тест man or boy ", чтобы отделить компиляторы, которые правильно реализовали " рекурсию и нелокальные ссылки". Этот тест содержит пример call-by-name.
ALGOL 68 был определен с использованием двухуровневого грамматического формализма, изобретенного Адрианом ван Вейнгарденом и носящего его имя. Грамматики ван Вейнгардена используют контекстно-свободную грамматику для генерации бесконечного набора производных, которые распознают конкретную программу ALGOL 68; в частности, они способны выражать тип требований, которые во многих других стандартах языков программирования обозначены как «семантика» и должны быть выражены в прозе естественного языка, подверженной неоднозначности, а затем реализованы в компиляторах как специальный код, прикрепленный к формальному синтаксическому анализатору языка.
(То, как должен быть написан жирный текст, зависит от реализации, например, «INTEGER» — включая кавычки — для целых чисел. Это известно как стропинг .)
процедура Absmax(a) Размер:(n, m) Результат:(y) Индексы:(i, k); значение n, m; массив a; целое число n, m, i, k; действительное число y; комментарий Абсолютный наибольший элемент матрицы a, размером n на m, копируется в y, а индексы этого элемента — в i и k;начало целого числа p, q; у := 0; я := к := 1; для p := 1 шаг 1 до тех пор, пока n не выполнить для q := 1 шаг 1 до тех пор , пока m не выполнить if abs(a[p, q]) > y then begin y := abs(a[p, q]); я := р; к := д конец конец Абсмакс
Вот пример того, как создать таблицу с использованием Эллиотта 803 АЛГОЛ. [26]
ТЕСТ АЛГОЛА С ПЛАВАЮЩЕЙ ТОЧКОЙ НАЧАЛО РЕАЛЬНЫХ A,B,C,D' ЧИТАЙТЕ D' ДЛЯ A:= 0.0 ШАГ D ДО 6.3 ДО НАЧИНАТЬ ПЕЧАТЬ ПЕРФОРАТОРА(3) ,££L??' B := SIN(A)' С := COS(A)' ПЕЧАТЬ ПЕРФОРАТОРА(3), ОДНА ЛИНИЯ , ВЫРОВНЕННАЯ(1,6) ,A,B,C' КОНЕЦ КОНЕЦ'
Следующие примеры кода представляют собой версии приведенных выше примеров кода ALGOL 60 на языке ALGOL 68.
Реализации ALGOL 68 использовали подходы к правке ALGOL 60. В случае ALGOL 68 лексемы с жирным шрифтом представляют собой зарезервированные слова, типы (режимы) или операторы.
proc abs max = ([,] real a, ref real y, ref int i, k) real : comment Абсолютный наибольший элемент матрицы a, размером ⌈a на 2⌈aпереносится в y, а индексы этого элемента на i и 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]; я := р; к := д фи од од ; уконец # абс макс #
Примечание: нижняя (⌊) и верхняя (⌈) границы массива, а также срез массива доступны программисту напрямую.
Тест algol68 с плавающей точкой:( действительные a,b,c,d; # printf – отправляет вывод в файл stand out . # # printf($p$); – выбирает новую страницу # printf(($pg$,"Введите d:")); читать(д); for step from 0 while a:=step*d; a <= 2*pi do printf($l$); # $l$ - выбирает новую строку . # б := sin(а); с := cos(a); printf(($zd.6d$,a,b,c)) # форматирует вывод с 1 цифрой до и 6 после десятичной точки. # од)
Различия и отсутствие переносимости программ из одной реализации в другую легко продемонстрировать на примере классической программы Hello World . [ требуется ссылка ]
ALGOL 58 не имел средств ввода-вывода.
Поскольку в ALGOL 60 не было средств ввода-вывода, в ALGOL нет переносимой программы hello world . Следующие три примера приведены в Burroughs Extended Algol. Первые два напрямую выводятся на интерактивный терминал, на котором они запущены. Первый использует массив символов, похожий на C. Язык позволяет использовать идентификатор массива в качестве указателя на массив и, следовательно, в операторе REPLACE.
НАЧАТЬ ФАЙЛ F ( ТИП = УДАЛЕННЫЙ ); МАССИВ EBCDIC E [ 0 : 11 ]; ЗАМЕНИТЬ E НА "HELLO WORLD!" ; ЗАПИСЬ ( F , * , E ); КОНЕЦ . Более простая программа, использующая встроенный формат:
НАЧАЛО ФАЙЛА F ( ТИП = УДАЛЕННЫЙ ); ЗАПИСЬ ( F , < "ПРИВЕТ, МИР!" > ); КОНЕЦ .Еще более простая программа, использующая оператор Display. Обратите внимание, что ее вывод в конечном итоге окажется на системной консоли ('SPO'):
НАЧАЛО ОТОБРАЖЕНИЯ ( "ПРИВЕТ, МИР!" ) КОНЕЦ .Альтернативный пример, использующий ввод-вывод Эллиотта Алгола, выглядит следующим образом. Эллиотт Алгол использовал разные символы для "open-string-quote" и "close-string-quote", представленные здесь как ' и ' .
программа HiFolks ; начало печати ' Привет, мир ' конец ; Ниже приведена версия из Elliott 803 Algol (A104). Стандартный Elliott 803 использовал бумажную ленту с пятью отверстиями и, таким образом, имел только верхний регистр. В коде отсутствовали символы кавычек, поэтому £ (знак фунта стерлингов Великобритании) использовался для открытия кавычек, а ? (знак вопроса) для закрытия кавычек. Специальные последовательности заключались в двойные кавычки (например, ££L?? создавал новую строку на телетайпе).
HIFOLKS' НАЧИНАТЬ ПЕЧАТЬ £ПРИВЕТ, МИР£L??' КОНЕЦ'
Версия Algol I/O серии ICT 1900 допускала ввод с бумажной ленты или перфокарты. Режим бумажной ленты «full» допускал строчные буквы. Вывод осуществлялся на строчный принтер. Символы открывающей и закрывающей кавычек представлялись с помощью '(' и ')' и пробелов %. [27]
'НАЧИНАТЬ' НАПИШИТЕ ТЕКСТ('('ПРИВЕТ%МИР')'); 'КОНЕЦ'Код ALGOL 68 был опубликован с зарезервированными словами, обычно написанными строчными буквами, но выделенными жирным шрифтом или подчеркнутыми.
начинать printf(($gl$,"Привет, мир!"))конец
На языке «Отчета по Алголу 68» средства ввода/вывода в совокупности назывались «Транспут».
Алгол был задуман в то время, когда наборы символов были разнообразны и быстро развивались; кроме того, Алгол был определен таким образом, что требовались только заглавные буквы.
1960: IFIP – Язык и отчет Algol 60 включали несколько математических символов, которые доступны на современных компьютерах и операционных системах, но, к сожалению, не поддерживались большинством вычислительных систем того времени. Например: ×, ÷, ≤, ≥, ≠, ¬, ∨, ∧, ⊂, ≡, ␣ и ⏨.
1961 сентябрь: ASCII — в набор символов ASCII , находившийся тогда на ранней стадии разработки, был добавлен символ \ (обратная косая черта) для поддержки булевых операторов ALGOL /\ и \/ . [28]
1962: ALCOR – Этот набор символов включал необычный символ рунического креста «᛭» [29] для умножения и символ десятичной экспоненты «⏨» [30] для записи чисел с плавающей точкой. [31] [32] [33]
1964: ГОСТ – Советский стандарт ГОСТ 10859 1964 года допускал кодирование 4-битных, 5-битных, 6-битных и 7-битных символов в АЛГОЛЕ. [34]
1968: «Отчет по Алголу 68» — использовались существующие символы Алгола, а также дополнительно принятые символы →, ↓, ↑, □, ⌊, ⌈, ⎩, ⎧, ○, ⊥ и ¢, которые можно найти на клавиатуре IBM 2741 со вставленными печатающими головками типа «пишбол» (или «мяч для гольфа» ) (например, « мяч для гольфа APL» ). Они стали доступны в середине 1960-х годов, когда разрабатывался Алгол 68. Отчет был переведен на русский, немецкий, французский и болгарский языки и позволил программировать на языках с более крупными наборами символов, например, кириллический алфавит советской БЭСМ -4. Все символы Алгола также являются частью стандарта Unicode , и большинство из них доступны в нескольких популярных шрифтах .
2009 Октябрь: Unicode – ⏨(Символ десятичной экспоненты) для записи чисел с плавающей точкой был добавлен в Unicode 5.2 для обратной совместимости с историческим программным обеспечением ALGOL программы «Буран» . [35]
Значительным вкладом отчета ALGOL 58 стало предоставление стандартных терминов для концепций программирования: оператор, объявление, тип, метка, первичный, блок и другие. [10]
Это означает, что потребность в перекодировании программного обеспечения и документации на основе ГОСТ все еще может возникнуть: устаревшие численные алгоритмы (некоторые из которых могут представлять интерес, например, для автоматической посадки шаттла "Буран" ...), оптимизированные для представления чисел с плавающей точкой, отличного от IEEE, БЭСМ-6, не могут быть просто перекомпилированы и, как ожидается, будут работать надежно, и может потребоваться некоторое вмешательство человека.