Raport Algol-60

Raport Algol-60 został napisany w latach 1959-1960 przez zespół ekspertów od języków programowania, w skład którego wchodził redaktor Peter Naur oraz kilku pedagogów i praktyków z Europy i Stanów Zjednoczonych. Celem raportu było opracowanie kompletnego opisu międzynarodowego języka algorytmicznego do wyrażania procesów numerycznych w formie nadającej się do tłumaczenia na języki programowania komputerów. Nie miał to być język programowania, chociaż został później zaimplementowany jako język i stał się popularny w Europie.

Wiele wersji języka programowania Algol zostało zaimplementowanych w latach 60-tych i wczesnych 70-tych. Doprowadziło to również do rozwoju kilku innych języków programowania, takich jak Pascal, zaimplementowany przez Niklausa Wirtha na początku lat 70-tych, oraz C.

Raport wprowadził pojęcia języka referencyjnego, języka publikacji i reprezentacji sprzętowej. Język referencyjny był standardem dla raportu, autorów kompilatorów i implementacji sprzętowej. Dyktował on formę języka i jego składnię. Język publikacji wykorzystywał język referencyjny z drobnymi poprawkami dotyczącymi różnic w publikacjach w różnych krajach oraz różnic w druku i piśmie, takich jak obsługa indeksów dolnych, górnych i innych notacji. Reprezentacja sprzętowa brała pod uwagę charakterystykę maszyny. Język referencyjny był językiem definiującym, a język publikacji i reprezentacja sprzętowa musiały być na niego przetłumaczalne.

Celem raportu i języka było jednoznaczne przedstawienie różnych koncepcji komputerowych – w szczególności projektowania algorytmów, czyli ALGOrithmic Language 1960. Kolejna wersja, Algol68, nie była tak popularna lub szeroko zaimplementowana jak Algol-60, chociaż była bardziej potężna.

Algol jest językiem strukturalnym, zawierającym instrukcje while, if-then-else-statements i inne konstrukcje, które implementują selekcję, iterację, podstawowe stwierdzenia, strukturę blokową i rekurencję. Chociaż został opracowany zaledwie kilka lat po FORTRANIE (FORmula TRANslator), wydanym w 1957 roku przez IBM, zawierał cechy brakujące w FORTRANIE – mianowicie rekurencję i język strukturalny – i stanowił duży postęp na arenie programowania.

Jednym z potomków Algolu i FORTRANu był język BASIC (Beginner’s All-purpose Symbolic Instruction Code), opracowany przez Johna Kemeny’ego i Thomasa Kurtza z Uniwersytetu Dartmouth. BASIC był rodzajem pozbawionej formatu deklaracji wersji FORTRAN-a, przeznaczonej do interaktywnych i początkujących obliczeń. BASIC cieszył się długim panowaniem od lat 70. do 80. i został ostatnio zaimplementowany w całkiem innej formie, Visual Basic.

Potomkiem Algolu był Pascal, który również cieszył się długim panowaniem jako popularny język do implementacji struktur danych i badania kompilatorów. Nie był to język produkcyjny, lecz narzędzie dydaktyczne. C był językiem systemu i doprowadził do rozwoju C, języka obiektowego, który nadal jest popularny.

Język Algol został opisany w notacji zwanej Backus normal lub Backus-Naur form (BNF). Notacja ta została zaproponowana przez Johna Backusa, który oparł ją na notacji E. L. Posta, słynnego logika z lat 30-tych XX wieku. Była ona podobna do notacji opracowanej przez Noama Chomsky’ego w 1957 roku dla lingwistyki, która była używana do implementacji gramatyk. Gramatyka jest zwięzłym, jednoznacznym sposobem opisywania języków. Użycie formalnej notacji w teorii języka było dużym postępem.

Ewolucja języków programowania była uderzająca, ale nie tak oszałamiająca jak ewolucja teorii kompilatorów. Wkrótce po raporcie Algol-60, kilku teoretyków kompilatorów użyło notacji gramatycznej do zaimplementowania kompilatorów w sposób „automatyczny”. Kompilatory te znane były jako kompilatory-kompilatory. Podobnymi wysiłkami było opracowanie Lex, analizatora leksykalnego, oraz Yacc („Yet another compiler-compiler”) w Bell Laboratories w połowie lat 70.

Understanding Programming Language

Gramatyka angielska ma pewne konstrukcje, takie jak fraza rzeczownikowa, która składa się z innych konstrukcji, takich jak rzeczownik i modyfikator. Języki programowania mają konstrukcje takie jak instrukcje while i wyrażenia arytmetyczne. Konstrukcje te są wskazywane przez specjalne symbole zwane symbolami nieterminalnymi lub meta symbolami języka.

Symbole, które faktycznie występują w języku nazywane są symbolami terminalnymi. Terminologia pochodzi od struktur danych, lub drzew parsowania, używanych do implementacji języka.

Przykładem jest:

Gramatyka ta wskazuje, że wyrażenie arytmetyczne, E, składa się z innych wyrażeń arytmetycznych i terminów, T, dodanych razem (E–>E T). Wyrażenie, T, składa się z wyrażenia razy czynnik, F, tak że T–>T*F. Wreszcie, czynnik, F, jest najbardziej podstawowym wyrażeniem, składającym się z wyrażeń nawiasowych (nawias E), identyfikatorów (identyfikatorów zdefiniowanych przez użytkownika lub zmiennych), id, i stałych numerycznych (num). Gramatyka podaje postać wyrażeń arytmetycznych.

Przykład daje smak notacji. Elementy po lewej stronie strzałki są złożone z elementów po prawej stronie. W tym przypadku, E, T i F są metasymbolami. Pozostałe symbole, *, (, ), oraz, w tym przypadku, id i num, występują w języku. Są one słowami języka. W tym przypadku E jest symbolem początkowym lub pierwszym symbolem nieterminalnym. Jest to najbardziej ogólne wyrażenie, które jest definiowane. Chociaż notacja może wydawać się niezręczna na początku, jest przydatna w projektowaniu języka, teorii kompilatorów i implementacji.

Rozwój gramatyk w informatyce dał wielki impuls do projektowania i implementacji języków programowania.

see also Algorithms; Procedural Languages; Programming.

Roger R. Flynn

Bibliografia

Naur, Peter, ed. „Revised Report on the Algorithmic Language Algol-60.” Communications ACM 6, no. 1 (1963): 1-17.

Wexelblat, Richard L., ed. History of Programming Languages. New York: Academic Press, 1981.

.