stringtranslate.com

АЛГОЛ

АЛГОЛ ( / ˈ æ 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]

подпись
Генеалогическое древо династий языков программирования Algol, Fortran и COBOL

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

Питер Наур: «Как редактор ALGOL Bulletin я был вовлечён в международные дискуссии по языку и был выбран членом Европейской группы по разработке языка в ноябре 1959 года. В этом качестве я был редактором отчёта ALGOL 60, подготовленного в результате встречи ALGOL 60 в Париже в январе 1960 года». [12]

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

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

Наследие

Значительным вкладом отчета ALGOL 58 стало предоставление стандартных терминов для концепций программирования: оператор, объявление, тип, метка, первичный, блок и другие. [10]

ALGOL 60 вдохновил многие последующие языки. Тони Хоар заметил: «Вот язык, который настолько опередил свое время, что он был не только улучшением своих предшественников, но и почти всех своих последователей». [14] Язык программирования Scheme , вариант Lisp , который принял блочную структуру и лексическую область ALGOL, также принял формулировку «Пересмотренный отчет по алгоритмической схеме языка» для своих документов стандартов в знак уважения к ALGOL. [15]

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

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

ALGOL 60 допускал две стратегии оценки для передачи параметров : общий вызов по значению и вызов по имени . Вызов по имени имеет определенные эффекты в отличие от вызова по ссылке . Например, без указания параметров как значения или ссылки невозможно разработать процедуру, которая поменяет местами значения двух параметров, если фактические переданные параметры являются целочисленной переменной и массивом, индексированным этой же целочисленной переменной. [16] Представьте себе передачу указателя на 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; в частности, они способны выражать тип требований, которые во многих других стандартах языков программирования обозначены как «семантика» и должны быть выражены в прозе естественного языка, подверженной неоднозначности, а затем реализованы в компиляторах как специальный код, прикрепленный к формальному синтаксическому анализатору языка.

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

Сравнение образцов кода

АЛГОЛ 60

(То, как должен быть написан жирный текст, зависит от реализации, например, «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]); я := р; к := д конец конец Абсмакс

Вот пример того, как создать таблицу с использованием Elliott 803 ALGOL. [17]

ТЕСТ АЛГОЛА С ПЛАВАЮЩЕЙ ТОЧКОЙ НАЧАЛО РЕАЛЬНЫХ A,B,C,D' ЧИТАЙТЕ D' ДЛЯ A:= 0.0 ШАГ D ДО 6.3 ДО НАЧИНАТЬ ПЕЧАТЬ ПЕРФОРАТОРА(3) ,££L??' B := SIN(A)' С := COS(A)' ПЕЧАТЬ ПЕРФОРАТОРА(3), ОДНА ЛИНИЯ , ВЫРОВНЕННАЯ(1,6) ,A,B,C' КОНЕЦ КОНЕЦ'

АЛГОЛ 68

Следующие примеры кода представляют собой версии приведенных выше примеров кода 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 . [ требуется ссылка ]

АЛГОЛ 58 (IAL)

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

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

Поскольку в 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 серии ICT 1900 допускала ввод с бумажной ленты или перфокарты. Режим бумажной ленты «full» допускал строчные буквы. Вывод осуществлялся на строчный принтер. Символы открывающей и закрывающей кавычек представлялись с помощью '(' и ')' и пробелов %. [18]

 'НАЧИНАТЬ' НАПИШИТЕ ТЕКСТ('('ПРИВЕТ%МИР')'); 'КОНЕЦ'

АЛГОЛ 68

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

начинать printf(($gl$,"Привет, мир!"))конец

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

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

В этой статье содержатся символы Unicode 6.0 "Miscellaneous Technical". Без надлежащей поддержки рендеринга вы можете увидеть вопросительные знаки, квадраты или другие символы вместо чего-то вроде "₁₀" (десятичный экспоненциальный символ U+23E8 TTF).

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

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

1961 сентябрь: ASCII — набор символов ASCII , находившийся тогда на ранней стадии разработки, пополнился символом \ (обратная косая черта), добавленным для поддержки булевых операторов ALGOL /\ и \/ . [19]

1962: ALCOR – Этот набор символов включал необычный символ рунического креста «᛭» [20] для умножения и символ десятичной экспоненты «⏨» [21] для записи чисел с плавающей точкой. [22] [23] [24]

1964: ГОСТ – Советский стандарт ГОСТ 10859 1964 года допускал кодирование 4-битных, 5-битных, 6-битных и 7-битных символов в АЛГОЛЕ. [25]

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

2009 Октябрь: Unicode – ⏨(Символ десятичной экспоненты) для записи чисел с плавающей точкой был добавлен в Unicode 5.2 для обратной совместимости с историческим программным обеспечением ALGOL программы «Буран» . [26]

Реализации АЛГОЛа

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

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

Смотрите также

Ссылки

  1. ^ Название этой языковой семьи иногда приводится в смешанном регистре (Algol 60 Архивировано 25 июня 2007 года на Wayback Machine ), а иногда полностью в верхнем регистре (ALGOL68 Архивировано 13 сентября 2014 года на Wayback Machine ). Для простоты в этой статье используется ALGOL .
  2. ^ Собранные алгоритмы ACM Архивировано 17 октября 2011 г. в Wikiwix Сжатые архивы алгоритмов. ACM .
  3. ^ O'Hearn, PW; Tennent, RD (сентябрь 1996 г.). "Algol-like languages, Introduction". Архивировано из оригинала 14 ноября 2011 г.
  4. ^ "Язык программирования ALGOL" Архивировано 6 октября 2016 г. в Wayback Machine , Мичиганский университет в Дирборне
  5. ^ abc Backus, John Warner ; Bauer, Friedrich Ludwig ; Green, Julien; Katz, Charles ; McCarthy, John ; Naur, Peter ; Perlis, Alan Jay ; Rutishauser, Heinz ; Samelson, Klaus ; Vauquois, Bernard ; Wegstein, Joseph Henry ; van Wijngaarden, Adriaan ; Woodger, Michael (май 1960 г.). Naur, Peter (ред.). "Отчет об алгоритмическом языке ALGOL 60". Communications of the ACM . 3 (5). Копенгаген, Дания: 299–314. doi : 10.1145/367236.367262 . ISSN  0001-0782. S2CID  278290.
  6. ^ "Пересмотренный отчет об алгоритмическом языке Алгол 60". 1963. Архивировано из оригинала 25 июня 2007 года . Получено 8 июня 2007 года .
  7. ^ «Транслятор ALGOL 60 для X1» (PDF) . 1961. Архивировано (PDF) из оригинала 9 октября 2022 года . Проверено 7 января 2021 г.
  8. ^ "Пересмотренный отчет об алгоритмическом языке АЛГОЛ 68" (PDF) . 1973. Архивировано (PDF) из оригинала 13 сентября 2014 года . Получено 13 сентября 2014 года .
  9. ^ «История ALGOL — Software Preservation Group». www.softwarepreservation.org . Получено 14 марта 2024 г. .
  10. ^ abc Бемер, Боб. "Политико-социальная история Алгола" (PDF) . Музей компьютерной истории . Получено 9 августа 2024 г. .
  11. ^ Кнут, Дональд Э. (1964). «Нормальная форма Бэкуса против формы Бэкуса-Наура». Сообщения ACM . 7 (12): 735–736. doi : 10.1145/355588.365140 . S2CID  47537431.
  12. ↑ Цитата из премии ACM: Питер Наур. Архивировано 2 апреля 2012 г. в Archive-It , 2005 г.
  13. ^ Перлис, Алан Дж. (1978). «Американская сторона развития АЛГОЛа». История языков программирования. стр. 75–91. doi :10.1145/800025.1198352. ISBN 0-12-745040-8– через dl.acm.org.
  14. ^ «Советы по проектированию языков программирования». Архивировано 15 сентября 2009 г. в Wayback Machine , CAR Hoare, декабрь 1973 г. Страница 27. (Это утверждение иногда ошибочно приписывают Эдсгеру В. Дейкстре , также участвовавшему в реализации первого компилятора ALGOL 60. )
  15. ^ Dybvig, RK; et al. Rees, Jonathan; Clinger, William; Abelson, Hal (ред.). "Revised(3) Report on the Algorithmic Language Scheme, (Dedicated to the Memory of ALGOL 60)". Архивировано из оригинала 14 января 2010 года . Получено 20 октября 2009 года .
  16. ^ Ахо, Альфред В.; Сети , Рави ; Ульман, Джеффри Д. (1986). Компиляторы: принципы, методы и инструменты (1-е изд.). Addison-Wesley. ISBN 0-201-10194-7., Раздел 7.5 и ссылки в нем
  17. ^ "803 ALGOL" Архивировано 29 мая 2010 г. на Wayback Machine , руководство по Elliott 803 ALGOL
  18. ^ "ICL 1900 series: Algol Language". Техническая публикация ICL 3340. 1965.
  19. ^ Как ASCII получил свой обратный слеш Архивировано 11 июля 2014 г. на Wayback Machine , Боб Бемер
  20. ^ железный/рунический крест
  21. ^ Символ десятичного показателя степени
  22. ^ Бауманн, Р. (октябрь 1961 г.). «Руководство АЛГОЛ группы АЛКОР, Часть 1» [Руководство АЛГОЛ группы АЛКОР]. Elektronische Rechenanlagen (на немецком языке): 206–212.
  23. ^ Бауманн, Р. (декабрь 1961 г.). «Руководство АЛГОЛ группы АЛКОР, Часть 2» [Руководство АЛГОЛ группы АЛКОР]. Elektronische Rechenanlagen (на немецком языке). 6 : 259–265.
  24. ^ Бауманн, Р. (апрель 1962 г.). «Руководство по АЛГОЛу группы ALCOR, часть 3» [ALGOL Manual of the ALCOR Group]. Elektronische Rechenanlagen (на немецком языке). 2 .
  25. ^ "Стандарт ГОСТ 10859". Архивировано из оригинала 16 июня 2007 г. Получено 5 июня 2007 г.
  26. ^ Брухис, Леонид (22 января 2008 г.). "Пересмотренное предложение по кодированию символа десятичной экспоненты" (PDF) . www.unicode.org . ISO/IEC JTC 1/SC 2/WG 2. Архивировано (PDF) из оригинала 31 июля 2015 г. . Получено 24 января 2016 г. . Это означает, что потребность в перекодировании программного обеспечения и документации на основе ГОСТ все еще может возникнуть: устаревшие численные алгоритмы (некоторые из которых могут представлять интерес, например, для автоматической посадки шаттла "Буран" ...), оптимизированные для представления чисел с плавающей точкой, отличного от IEEE, БЭСМ-6, не могут быть просто перекомпилированы и, как ожидается, будут работать надежно, и может потребоваться некоторое вмешательство человека.
  27. ^ "Энциклопедия компьютерных языков". Архивировано из оригинала 27 сентября 2011 г. Получено 20 января 2012 г.
  28. ↑ История музея компьютеров. Архивировано 20 августа 2010 г. в Wayback Machine . Исторический компьютер Zuse-Computer Z23, восстановленный в Konrad Zuse Schule в Хюнфельде для Центра истории музея компьютеров в Маунтин-Вью (Калифорния), США.
  29. ^ Daylight, EG (2011). «Dijkstra's Rallying Cry for Generalization: the Advent of the Recursive Procedure, late 1950s – early 1960s». The Computer Journal . 54 (11): 1756–1772. CiteSeerX 10.1.1.366.3916 . doi :10.1093/comjnl/bxr002. Архивировано из оригинала 12 марта 2013 г. 
  30. ^ Kruseman Aretz, FEJ (30 июня 2003 г.). "Компилятор Dijkstra-Zonneveld ALGOL 60 для Electrologica X1". Software Engineering (PDF) . History of Computer Science. Amsterdam: Centrum Wiskunde & Informatica. Архивировано (PDF) из оригинала 4 марта 2016 г.
  31. ^ Хоар, Энтони (1980). «Старые одежды императора». Сообщения ACM . 24 (2): 75–83. doi : 10.1145/358549.358561 .
  32. ^ Коффман, Элиот. «Все, что мне действительно нужно знать, я узнал в CS1» (PDF) . Архивировано из оригинала (PDF) 12 октября 2012 г. . Получено 20 мая 2012 г. .
  33. ^ "GOGOL – PDP-1 Algol 60 (Computer Language)". Онлайновая историческая энциклопедия языков программирования. Архивировано из оригинала 2 февраля 2018 года . Получено 1 февраля 2018 года .
  34. ^ Mounier-Kuhn, Pierre (2014). «Algol во Франции: от универсального проекта к встроенной культуре». IEEE Annals of the History of Computing . 36 (4): 6–25. doi :10.1109/MAHC.2014.50. ISSN  1058-6180. S2CID  16684090.
  35. ^ Випперманн, Ханс-Вильм (1968) [15 июня 1967, 1966]. «Определение фон Шранкенцалена в Триплекс-АЛГОЛ». Вычисление (на немецком языке). 3 (2). Карлсруэ, Германия: Springer: 99–109. дои : 10.1007/BF02277452. ISSN  0010-485X. S2CID  36685400.

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

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