ALGOL. Co po nim odziedziczyliśmy?

Zabieram Was dziś w podróż do przeszłości. Do końcówki lat 50., kiedy tworzyły się podstawy informatyki, kiedy programowanie było zajęciem zupełnie elitarnym, kiedy o komputerze mówiło się, że tak wygląda przyszłość. Z tego okresu najczęściej słyszymy o Fortranie, Lispie czy COBOL-u. A tymczasem gdzieś z boku jest ALGOL, który był bardzo ważnym językiem w historii informatyki.

Jak wtedy wyglądał świat programowania?

Był to świat zupełnie inny od teraźniejszego przede wszystkim dlatego, że większość kodowania odbywało się w asemblerze. Jeżeli ktoś z Was programował w asemblerze to wie, że jest to dość żmudny proces. I tak właśnie było w latach 50. W tym okresie powstawały dopiero pierwsze języki programowania, które miały ułatwić pisanie programów. Większość z nich miała konkretne zastosowania, często były powiązane bezpośrednio z architekturą (komputerem), na którym były uruchamiane. Dodatkowo wzorowano je na językach naturalnych. To wszystko oznaczało, że ciężko było przenieść powstały kod między platformami.

W 1955 roku na sympozjum w Darmstadt pojawiły się postulaty stworzenia zunifikowanego języka algorytmicznego, niezależnego od platformy. Chcąc sprostać temu wyzwaniu, Stowarzyszenie Gesellschaft fur Angewandte Mathematik und Mechanik (GAMM) sformowało subkomitet i zaprosiło do współpracy amerykańskie stowarzyszenie Association of Computing Machinery (ACM). Wydaje się, że GAMM chciało skorzystać z doświadczeń zza oceanu, gdzie informatyka była dużo bardziej zaawansowana. Kiedy tam IBM sprzedawał komercyjnie komputery, w Europie poszczególne ośrodki badawcze podejmowały dopiero próby konstruowania własnych maszyn. Dodatkowo IBM właśnie wypuścił FORTRAN-a, który wprowadził do programowania nową jakość.

ALGOL wchodzi na scenę

ALGOL to skrót od Algorythmic Language. Początkowo miał się nazywać IAL (International Algebraic Language), ale w porę zauważono, że niezbyt wygodnie wymawia się ten skrót. Pierwsza wersja powstała na spotkaniu międzynarodowego komitetu naukowców z Europy i Stanów Zjednoczonych w Zurychu w 1958 roku - stąd ALGOL 58. Nie był to do końca język programowania w dzisiejszym rozumieniu. Jak napisał John Backus, jeden z twórców ALGOLA:

Konferencja ACM-GAMM w Zurychu miała dwa główne motywy w stworzeniu IAL:

(a) zapewnić sposób komunikacji metod numerycznych i innych procedur między ludźmi  
(b) zapewnić sposób na wykonanie ustalonego procesu na różnorodnych maszynach.

W 1958 roku chodziło o stworzenie standardu opisu dla tego, co się dzieje na komputerach. Co prawda ALGOL 58 miał kilka implementacji, jednak nie zdobył dużego uznania. Wprowadził pojęcie instrukcji złożonej, ale użycie było ograniczone tylko do przepływu sterowania. Szybko okazało się, że efekt prac nie jest zadowalający. W czerwcu 1959 stało się jasne, że konieczne są dalsze prace i ogłoszono szerokie konsultacje, żeby zebrać materiał do kolejnego spotkania, na którym powstanie nowa wersja języka. Amerykanie skupiali się na praktycznych walorach języka - głównie dlatego, że w USA programowanie powoli stawało się profesją i walory użytkowe ALGOL-a 58 nie były zbyt wielkie. Natomiast Europejczycy zgłaszali więcej propozycji dotyczących fundamentów języka. Takie początki miał ALGOL 60.

Tak, zgadliście. ALGOL 60, bo został zaproponowany w 1960 roku - jak widać, nie było wtedy jeszcze SemVer. Spotkanie tym razem odbyło się w Paryżu, z udziałem trzynastu naukowców. Przedstawię ich szybko - by pokazać, jaki był to kaliber ludzi:

• Friedrich L. Bauer - twórca terminu „inżynieria oprogramowania”
• Peter Naur - edytor raportu ALGOL 60, współautor notacji Backusa-Naura (chociaż sam się tego mocno wypierał)
• Heinz Rutishauser - matematyk, pionier współczesnej analizy numerycznej i informatyki
• Klaus Samelson - pionier w dziedzinie kompilatorów i algorytmów stosu
• Bernard Vauquois - pionier w tłumaczeniu maszynowym
• Adriaan van Wijngaarden - ojciec holenderskiej informatyki
• Michael Woodger - współtwórca Pilot ACE, jednego z pierwszych komputerów brytyjskich, współtwórca języka Ada
• John W. Backus - twórca Fortrana (kierował zespołem), twórca notacji Backusa-Naura oraz twórca paradygmatu programowania na poziomie funkcji (function-level programming - nie mylić z programowaniem funkcyjnym. Mega ciekawy koncept, o którym nigdy nie słyszałem)
• Julien Green - brał również udział przy ustalaniu specyfikacji 58
• Charles Katz - pracował przy kompilatorach do pierwszych komputerów
• John McCarthy - twórca terminu „sztuczna inteligencja” i badacz tej dziedziny, za co dostał nagrodę Turinga; twórca Lispa
• Alan Perlis - pierwszy laureat nagrody Turinga, którą dostał za wkład w zaawansowane techniki programistyczne i w konstrukcję kompilatorów
• Joseph Henry Wegstein - pracował nad automatycznym przetwarzaniem danych i rozpoznawaniem linii papilarnych, uczestniczył w pracach nad COBOL-em

Alan Perlis tak opisywał paryskie spotkania:

Spotkania były wyczerpujące, niekończące się i porywające. Niektórzy denerwowali się, że zaproponowane przez nich dobre pomysły odrzucano razem ze złymi pomysłami innych osób. (...) Jednak gorliwość przetrwała przez cały okres. Chemia między całą trzynastką była wspaniała. (...) Postęp był stały, a rezultat - ALGOL 60 - to raczej koń wyścigowy, niż wielbłąd.

Zdjęcie przedstawia szóstkę uczestników paryskiej konferencji w 1960 roku, poświęconej ALGOL-owi. W górnym rzędzie: John McCarthy, Friedrich Bauer, Joseph Wegstein. W rzędzie dolnym: John Backus, Peter Naur, Alan Perlis.

Wyobraźcie sobie trzynastu naukowców, inżynierów, badaczy z kilku krajów. Każdy rzuca swoje pomysły na to, jak powinien wyglądać język (ok, wstępne propozycje były wcześniej wybrane). W 1960 mieliśmy do czynienia z czymś, co po angielsku nazwiemy greenfield - nie było ograniczeń wynikających z historii, bo dziedzina była nowa. Chociaż była już poprzednia wersja ALGOL-a i Fortrana oraz skromne języki lat 50-tych, wszystkim z nich sporo brakowało, jeżeli chodzi o możliwość opisu algorytmów czy ekspresywność. Stąd pole do popisu było ogromne. Z tego wszystkiego trzeba było wykrystalizować spójny, czysty język, który będzie podstawowym narzędziem używanym przez informatyków* w codziennej pracy. Co wymyślił komitet?

Właściwości języka

Z pewnością jedną z bardziej spektakularnych nowości było wprowadzenie bloków. Bloki ograniczały słowa kluczowe, bardzo dobrze znane nam dzisiaj “begin” i “end”. Dodatkowo blok miał już swój własny zasięg (scope). Było to rozwinięcie instrukcji złożonej znanej już z wersji 58.

ALGOL był pierwszym językiem pozwalającym na definicję zagnieżdżonych funkcji, które miały swój zasięg leksykalny.

Autorzy raportu zalecili zaimplementowanie 9 funkcji standardowych: abs, sign, sqrt, sin, cos, arctan, ln, exp i entier. To bardzo niedużo, gdy weźmiemy pod uwagę biblioteki standardowe współczesnych języków. To pokazuje jak czysty był ALGOL.

Kolejnym ważnym narzędziem była rekurencja. Zaproponował ją John McCarthy, który dopiero co ukończył prace na Lispem, gdzie umieścił taką możliwość. Propozycja ta spotkała się jednak ze sporymi obawami komitetu i obradujący odrzucili wprowadzenie słowa kluczowego recursive. Ostatecznie rekurencja trafiła do standardu implicite - specyfikacja ALGOL-a nie zabrania rekurencyjnych wywołań.

Inną ciekawostką były dwie strategie przekazywania parametrów. Pierwsza to znane wszystkim przekazanie przez wartość. Druga natomiast to przekazanie przez nazwę. W tej strategii argumenty nie są wywoływane aż do czasu gdy pojawią się w ciele procedury. Teoretycznie może to zapewnić przewagę wydajnościową, jednak tworzy pewne wyzwania dla kompilatorów.

ALGOL idzie na „produkcję”

Raport powstały w 1960 roku był wspaniałą rzeczą, jednak nie możemy zapominać o tym, że był to tylko kilkunastostronicowy opis języka. Nie było referencyjnej implementacji. Co więcej, ALGOL 60 w ogóle nie specyfikował operacji wejścia i wyjścia! Dlatego też ciężko mówić o programie „Hello world” napisanym w ALGOL-u 60. Sam raport był niezwykle zwięzły, zawierał bardzo niewiele zbędnych słów i - jak to powiedział Alan Perlis: 

Tak jak Biblia - jest nie tylko do czytania, ale także do interpretowania.

Tak więc jednym z wyzwań czekających na twórców poszczególnych implementacji było zinterpretowanie operacji wejścia i wyjścia w duchu specyfikacji.

Pierwszą implementacją był X1 ALGOL 60 opracowany przez Dijkstrę (tak, ten sam, co w wykładach z algortymów) i Zonnevelda - na holenderski komputer Electrologica X1.

Electrologica X1, ok. 1960 roku

Do 1963 roku pojawiły się kompilatory na kilkanaście z ówczesnych komputerów, w tym na UNIVAC czy Elliot (twórcą kompilatora był Tony Hoare). W drugiej połowie lat 60. powstały również implementacje ALGOL-a na komputery z bloku sowieckiego. Od 1965 można było programować w ALGOL-u na komputerze Minsk, a od 1967 na polskim komputerze ZAM.

Największym problemem ALGOL-a był brak wsparcia. Fortran opracowany pod skrzydłami IBM nie był tak zaawansowany, ale miał pełne wsparcie firmy matki. IBM własnymi siłami pisało referencyjne implementacje na kolejne platformy, przez co dla komercyjnych zastosowań wydawał się bardziej bezpieczny - był ustandaryzowany.

Tak o nowym języku mówił Robert Bemer na sympozjum RAND w 1961 roku:

Nie istnieje rozsądny mechanizm wsparcia. Nikt nie jest w stanie odpowiedzieć na podstawowe pytanie „Czym jest ALGOL?”. Przewiduję ciężkie czasy dla ALGOL-a, chyba że powstaną przemyślane procedury wsparcia. Język jest zbyt ogólny i ma zbyt wiele niedopowiedzeń.

Bemer miał rację o tyle, że w raporcie rzeczywiście było kilka niedopowiedzeń i brakowało mechanizmu do ich poprawienia. Ostatecznie twórcy czy osoby zainteresowane ALGOL-em nie ustanowiły ani mechanizmu wsparcia, ani mechanizmu rozwoju, co doprowadziło do fiaska ALGOL-a 68, który został odrzucony przez środowisko.

O ile na polu komercyjnym ALGOL nie odniósł spektakularnego sukcesu, to naukowcy przyjęli go bardzo entuzjastycznie. Stąd stał się głównym językiem do opisu algorytmów na kolejne 20-30 lat. Jego czysta i ekspresywna składnia ułatwiała komunikację między ludźmi. Brak referencyjnych implementacji utrudniał natomiast używanie języka przy komunikacji człowiek-maszyna. Ponieważ w Ameryce przemysł informatyczny był o wiele bardziej rozwinięty niż w Europie, tam liczyły się przede wszystkim względy praktyczne. Problem wsparcia i kompatybilności był kluczowy. W Europie natomiast informatyka była domeną niemal wyłącznie ośrodków naukowych. Naukowcy mieli inne priorytety, a nowy język bardzo dobrze nadawał się do badań nad algorytmami. Dlatego na Starym Kontynencie ALGOL przyjął się o wiele lepiej.

Co odzieczyliśmy?

Wpływ ALGOL-a na późniejsze języki był ogromny. Zainspirował większość imperatywnych języków programowania. Z tych bardziej znaczących Pascal, Simula (pierwszy język obiektowy), C.

W zasadzie wszystkie kolejne języki programowania zawierają bloki i rekurencję. Prace nad ALGOL-em 68 przyniosły jeszcze wyrażenia case i koncept rekordu wraz z referencją, a także przekazanie przez referencję.

Bardzo ważne było opracowanie i wykorzystanie BNF, czyli Backus-Neur Form. W zasadzie chodzi o budowanie języka z już zdefiniowanych pojęć - przy minimalnych odwołaniach do języka naturalnego.

Ogólna forma to:

<zmienna metajęzyka> ::= <forma>

Przykład prosty:

<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Przykład bardziej skomplikowany:

<if clause> ::= if <Boolean expression> then

<unconditional statement> ::= <basic statement> |
       <compound statement> | <block>

<if statement> ::= <if clause> <unconditional statement>

<conditional statement> ::= <if statement> |
       <if statement> else <statement> |
       <if clause> <for statement> |
       <label>: <conditional statement>

Pierwszy przykład nie wygląda zbyt imponująco, ale drugi daje lepsze zrozumienie możliwości. Dzięki temu zapisowi można skutecznie opisywać język programowania bez zewnętrznego kontekstu. Od tej pory ta notacja i jej rozwinięcia stały się standardem opisu języków programowania.

ALGOL stał się katalizatorem w procesie rozwoju kompilatorów. Pierwsze kompilatory były prostymi translatorami formuł na kod maszynowy, ale ALGOL potrzebował czegoś więcej - procedury, tablice o zmiennej wielkości czy rekurencja nie pasowały do techniki sekwencyjnej translacji. By poprawnie i wydajnie je zaimplementować, trzeba było opracować nowe, dużo bardziej zaawansowane techniki kompilacji.

To wszystko sprawia, że choć całkowicie wypadł z użycia, był to język niezwykły. Wysiłek, jaki włożono w jego opracowanie i implementację, przeniósł informatykę jako dziedzinę na inny poziom. Można sobie wyobrazić, że rozwój był nieunikniony. Wydaje mi się jednak, że dzięki jakości ALGOL-a był on nieco szybszy. Bezboleśnie można było przenieść wiele konceptów do innych języków programowania lub je rozwinąć - i właśnie z tego korzystamy dzisiaj. Chylę czoła przed twórcami i inicjatorami przedsięwzięcia.

* Słowo „informatyk” w tym tekście należy rozumieć jako „computer scientist”, czyli naukowca od komputerów, a nie jako osobę, która instaluje Windowsa w urzędzie gminy. Niestety słowo to straciło na blasku w naszym języku.

Źródła:

• The History of the ALGOL Effort, HT de Beer
• Revised Report on the Algorithmic Language Algol 60, J.W. Backus, F.L. Bauer, J. Green, C. Katz, J. McCarthy, P. Naur, A.J. Perlis, H. Rutishauser, K. Samuelson, B. Vauquois, J.H. Wegstein, A. van Wijngaarden, M. Woodger
• Wikipediowe artykuły o ALGOL-u i wszystkim, co powiązane