Algol-60 Report

Algol-60-rapporten skrevs mellan 1959 och 1960 av en grupp experter på programmeringsspråk bestående av redaktör Peter Naur och flera utbildare och praktiker från Europa och USA. Syftet med rapporten var att utveckla en fullständig beskrivning av ett internationellt algoritmiskt språk för att uttrycka numeriska processer i en form som lämpar sig för översättning till datorprogrammeringsspråk. Det var inte avsett att vara ett programmeringsspråk, även om det senare implementerades som ett språk och blev populärt i Europa.

Många versioner av programmeringsspråket Algol implementerades under 1960-talet och början av 1970-talet. Det ledde också till utvecklingen av flera andra programmeringsspråk, t.ex. Pascal, som implementerades av Niklaus Wirth i början av 1970-talet, och C.

I rapporten introducerades begreppen referensspråk, publikationsspråk och maskinvarurepresentation. Referensspråket var standarden för rapporten, kompilatorförfattare och hårdvaruimplementering. Det dikterade språkets form och dess syntax . Publikationsspråket använde referensspråket med mindre justeringar för publikationsvariationer mellan olika länder och tryck- och skrivvariationer, t.ex. hantering av subscripts, superscripts och annan notation. Hårdvarurepresentationen tog hänsyn till maskinens egenskaper. Referensspråket var det definierande språket, och publikationsspråket och maskinvarurepresentationen måste kunna översättas till det.

Syftet med rapporten och språket var att ge en otvetydig representation av olika datorkoncept – i synnerhet algoritmkonstruktion, eller ALGOrithmic Language 1960. En senare version, Algol68, var inte lika populär eller allmänt implementerad som Algol-60, även om den var mer kraftfull.

Algol är ett strukturerat språk som innehåller while-utsagor, if-then-else-utsagor och andra konstruktioner som implementerar urval, iteration, grundläggande uttalanden, blockstruktur och rekursion. Även om det utvecklades bara några år efter FORTRAN (FORmula TRANslator), som lanserades 1957 av IBM, innehöll det funktioner som saknades i FORTRAN – nämligen rekursion och det strukturerade språket – och var ett stort framsteg på programmeringsområdet.

En av ättlingarna till Algol och FORTRAN var BASIC-språket (Beginner’s All-purpose Symbolic Instruction Code), som utvecklades av John Kemeny och Thomas Kurtz vid Dartmouth University. BASIC var ett slags formatstationsfri version av FORTRAN för interaktiv databehandling och databehandling för nybörjare. BASIC hade ett långt regeringsinnehav från 1970-talet till 1980-talet och har nyligen implementerats i en helt annan form, Visual Basic.

En ättling till Algol var Pascal, som också hade ett långt regeringsinnehav som ett populärt språk för att implementera datastrukturer och studera kompilatorer. Det var inte ett produktionsspråk, utan ett undervisningsverktyg. C var ett systemspråk och ledde till utvecklingen av C, ett objektorienterat språk som fortfarande är populärt.

Algolspråket beskrevs i en notation som kallas Backus normal eller Backus-Naur form (BNF). Notationen föreslogs av John Backus, som baserade den på en notation av E. L. Post, en berömd logiker på 1930-talet. Den liknade den notation som Noam Chomsky utvecklade 1957 för lingvistik och som användes för att implementera grammatiker. En grammatik är ett kortfattat, entydigt sätt att beskriva språk. Användningen av en formell notation i språkteori var ett stort framsteg.

Evolutionen av programmeringsspråk var slående, men inte lika häpnadsväckande som utvecklingen av kompilatorteori. Kort efter Algol-60-rapporten använde flera kompilatorteoretiker grammatiknotationen för att implementera kompilatorer på ett ”automatiskt” sätt. Dessa kompilatorer var kända som kompilatorkompilatorer. Liknande insatser var utvecklingen av Lex, en lexikalisk analysator, och Yacc (”Yet another compiler-compiler”) vid Bell Laboratories i mitten av 1970-talet.

Förståelse av programmeringsspråk

Den engelska grammatiken har vissa konstruktioner, t.ex. en substantivfras, som består av andra konstruktioner, t.ex. ett substantiv och en modifierare. Programmeringsspråk har konstruktioner som while-satser och aritmetiska uttryck. Dessa konstruktioner anges med särskilda symboler som kallas språkets icke-terminalsymboler eller metasymboler.

De symboler som faktiskt förekommer i språket kallas terminalsymboler. Terminologin kommer från de datastrukturer, eller parse trees, som används för att implementera språket.

Ett exempel är:

Denna grammatik anger att ett aritmetiskt uttryck, E, består av andra aritmetiska uttryck och termer, T, som adderas tillsammans (E–>E T). En term, T, består av en term gånger en faktor, F, så att T–>T*F. Slutligen är en faktor, F, det mest grundläggande uttrycket som består av parentesuttryck (E), identifierare (användardefinierade identifierare eller variabler), id, och numeriska konstanter (num). Grammatiken ger formen för de aritmetiska uttrycken.

Exemplet ger en smak av notationen. Elementen till vänster om pilen är sammansatta av elementen till höger. I det här fallet är E, T och F meta-symbolerna. De andra symbolerna,, *, (, ) och, i det här fallet, id och num, förekommer i språket. De är språkets ord. I det här fallet är E startsymbolen eller den första icke-terminala symbolen. Det är det mest allmänna uttrycket som definieras. Även om notationen kan verka besvärlig till en början är den användbar vid utformning av språk, kompilatorteori och implementering.

Utvecklingen av grammatiker inom datavetenskapen gav en stor stimulans till utformning och implementering av programmeringsspråk.

Se även Algoritmer; Procedurella språk; Programmering.

Roger R. Flynn

Bibliografi

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.