Algol-60

Uit Wikipedia, de vrije encyclopedie

Ga naar: navigatie, zoeken

Algol-60 is een programmeertaal die nog steeds van belang is door haar invloed op latere programmeertalen. Na een eerste versie uit 1958 verscheen de definitieve versie in 1960. De naam Algol is een afkorting voor Algorithmic Language.

Inhoud

[bewerk] Geschiedenis

Algol is voortgekomen uit de wens om een machine-onafhankelijke programmeertaal te maken die zoveel mogelijk moest lijken op gebruikelijke wiskundige notatie. Algol was evenals de toen al bestaande programmeertaal Fortran bestemd voor wetenschappelijke doeleinden. In tegenstelling tot de in dezelfde tijd actieve ontwikkelaars van de programmeertaal Cobol hadden de ontwerpers van Algol geen speciale voorzieningen voor de bewerking van bestanden of het werken met niet-numerieke gegevens of grote geldbedragen.

De eerste versie, Algol-58 werd in 1958 ontworpen. Deze programmeertaal was meer een verzameling van goede ideeën, maar was nooit bedoeld als volledig afgemaakt product. In 1960 kwam Algol-60 uit, als resultaat van werk van John Backus, Peter Naur en Edsger Dijkstra. De Amerikaanse beroepsvereniging ACM besloot dat deze taal de standaardtaal zou worden voor het weergeven van algoritmes in haar blad Communications of the ACM. Desondanks is Algol-60 in Noord-Amerika nooit zo populair geworden als in Europa, mogelijk omdat men daar al gewend was aan het gebruik van Fortran.

Algol-60 is gespecificeerd in het Revised Report on the Algorithmic Language Algol 60 met een gedefinieerde grammatica, het Backus-Naur-formalisme zodat het mogelijk werd om op een formele manier vast te stellen of een programma syntactisch correct was. De implementatie van de taal was van later zorg. In korte tijd werd echter een flink aantal compilers voor de primitieve machines uit die tijd, zoals de X-1, geschreven. Daarbij moesten natuurlijk beperkingen worden vastgelegd, bijvoorbeeld met betrekking tot de lengte van namen of de omvang en nauwkeurigheid van getallen, die in het revised report niet gedefinieerd zijn. Er is nog steeds een compiler voor de PC beschikbaar, maar hierin gelden een aantal uitbreidingen en beperkingen op de oorspronkelijke versie, waardoor deze niet alle specifieke eigenschappen van Algol-60 kan laten zien.

[bewerk] Kenmerken van Algol-60

Deze beschrijving is bedoeld voor mensen die een nieuwere programmeertaal, zoals Pascal, C, Java of Visual Basic, kennen. Het is geen volledige beschrijving van of inleidende cursus in Algol-60.

[bewerk] Vorm van het programma

Een Algol-60 programma is een reeks van symbolen. Veel van die symbolen zijn tekens die op de meeste toetsenborden te vinden zijn, maar er zijn ook symbolen die in het Algol-60-report worden aangeduid met een vetgedrukt woord, zoals begin en if. Andere lastige tekens zijn 10, dat wordt gebruikt in een drijvende-kommagetal, en de tekens ‘ en ’ die het begin en einde van een string aangeven. Wordt Algol-60 op een computer geïmplementeerd, dan zijn er verschillende manieren om deze symbolen weer te geven. Zo is er een implementatie waarbij alle vette symbolen tussen aanhalingstekens worden gezet: 'BEGIN' 'IF'. Hierdoor verschillen ze wan de identifiers BEGIN en IF. Er is ook een implementatie van Algol-60 die de dubbele punt en de puntkomma niet kent en die tekens wordt er .. en ., geschreven. Inderdaad kan dat zonder dat er een syntactisch conflict ontstaat.

[bewerk] Structuur van het programma

Een noviteit in Algol-60 is de blokstructuur en sindsdien wordt iedere taal met een blokstructuur, zoals C en Pascal een taal met een Algolstructuur genoemd. De blokstructuur houdt in dat een aantal statements gegroepeerd kan worden door ze tussen de symbolen begin en end te zetten. Zo'n groep is zelf weer een statement en heet een compound-statement of (als er declaraties in voorkomen) een blok.

[bewerk] Dynamische arraydeclaratie

De grootte van een array kan dynamisch worden bepaald. Omdat een arraydeclaratie zich altijd aan het begin van een blok begint, moet de grootte van de array bekend zijn als de uitvoering van het blok begint. Bijvoorbeeld:

begin
  integer n;
  n := .....;
  begin
    integer array  list[1:n];
    integer i;
    for i:=1 step 1 until n do
        list[i]=i;
    .....
  end
end

[bewerk] Datatypen

In Algol-60 moeten alle variabelen gedeclareerd worden. Daardoor wordt de programmeur gedwongen van te voren na te denken over de vraag welke variabelen nodig zijn en welk type deze variabelen hebben. Algol-60 kent drie datatypen:

  • integer: gehele getallen
  • real: getallen met vaste relatieve nauwkeurigheid
  • boolean: logische waarden

De standaardvorm van Algol-60 kent geen variabele strings, karakters, records en door de programmeur gedefinieerde datatypen. Het is echter wel mogelijk strings in de uitvoer op te nemen. Latere implementaties van Algol kennen het type char.

Een boolean kan alleen true of false zijn.

De definitie van een real is (zie Backus-Naur-formalisme):

<real> ::= <integer>.<integer> | <real>10<integer> | <integer>10<integer>

Hieruit blijkt dat er aan weerszijden van de decimale punt minstens één cijfer moet staan.

Arrays bevatten data van één type. Het aantal dimensies is in principe onbeperkt. De onder- en bovengrens worden apart opgegeven. Dit zijn positieve of negatieve gehele getallen, waarvan de waarde bekend moet zijn op het moment van de declaratie.

[bewerk] Blok-structuur

Variabelen die aan het begin van het programma worden gedeclareerd heten globaal: zij kunnen overal in het programma gebruikt worden. Na iedere begin kunnen opnieuw variabelen gedeclareerd worden. Deze noemen we lokaal. Zij kunnen alleen in het blok zelf, met inbegrip van de binnenblokken daarvan, gebruikt worden, tenzij er in een binnenblok weer een idenitifier met dezelfde naam is gedeclareerd. Een globale array heeft altijd vaste grenzen. Een lokale array kan variabele grenzen hebben. Behalve gewone lokale variabelen kunnen ook own-variabelen worden gedeclareerd. Deze krijgen hun oude waarde bij een nieuwe aanroep van het blok. De own-variabele is lastig in het gebruik doordat hij niet automatisch een beginwaarde krijgt en een own-array met variabele grenzen is moeilijk te implementeren. De blokstructuur is in nieuwere talen alleen voor procedures blijven bestaan. Als een programma wordt opgedeeld in blokken met aparte variabelen kan het immers beter in procedures worden opgedeeld.

[bewerk] Opdrachten

Algol-60 kent een beperkt aantal statements:

De syntaxis is (in een niet geheel correcte versie van BNF):

<assignment> ::= <variabele>:=<expressie>
<if-statement> ::= if <boolean-expressie> {then <statement>} 
<for-statement> ::= for <variable>:=<beginwaarde> step <stapgrootte> until  <eindwaarde> {while<boolean-expressie>} do <statement>
<goto-statement> ::= goto <label>
<procedure-aanroep> ::= <procedurenaam> | <procedurenaam> (<parameterlijst>)

Opmerkelijk is dat in een expressie een if-then-else kan voorkomen. Als voorbeeld geven we twee manieren om het grootste van twee getallen te berekenen. In het eerste geval wordt de if-statement opdracht gebruikt, in het tweede de assignment met if-then-else.

if a>b then max:=a else max:=b
max:= if a>b then a else b;

In het tweede geval is de else-clausule verplicht.

[bewerk] Voorbeeld

Het volgende programma gebruikt beide vormen om een aantal getallen, afgesloten met 0, in te lezen en op het scherm te tonen. Aangezien de waarde van de for-variabele bij het verlaten van de lus volgens de definitie ongedefinieerd is wordt het aantal ingelezen getallen apart bijgehouden.

begin comment gebruik van for statement;
  integer maxn;
  text(1,"Maximaal aantal getallen=");maxn:=read(1);
  begin integer n,i;
    integer array a[1:maxn];
    n:=0;
    fori:=1,i+1 while a[i-1]>0 do
    comment Het aantal gelezen getallen wordt in n bijgehouden;
    begin 
      text(1,"Getal ");
      write(1,i);
      text(1,"=");
      a[i]:=read(1);
      if a[i]>0 then n:=i 
    end;
    for i:=1 step 1 until n do
    begin
      write(1,i);
      text(1," ");
      write(1,a[i]);
      skip(1)
    end
  end
end

Het goto-statement was in de tijd waarin Algol-60 ontworpen werd de meest gebruikte opdracht om de loop van het programma te besturen. Totdat Edsger Dijkstra in 1968 zijn beroemde ingezonden brief ‘’Goto statement considered harmful’’ in de Communications of the ACM publiceerde vond men het gebruik van goto' dan ook even gewoon als het opsteken van een pijp in een zaal vol collega’s. Behalve de gewone label kent Algol-60 ook de switch, een van te voren met labels gevuld array. Tegenwoodig wordt het gebruik van goto in iedere Algol-achtige taal afgekeurd.

[bewerk] Procedures en functies

De declaratie en het gebruik van procedures en functie in Algol-60 lijken sterk op die in nieuwere talen, maar hebben een iets andere vorm. Het type en de wijze van aanroep van de parameters worden niet in, maar na de parameterlijst gedefinieerd en functies worden aangeduid met de naam van het type gevolgd door het basissymbool procedure. Algol-60 introduceerde de recursieve procedure, de procedure die zichzelf aanroept. Een veel gebruikt voorbeeld is het oplossen van het probleem van de Torens van Hanoi. De procedure om aantal schijven van stokje van via stokje via naar stokje naar te brengen luidt in Algol-60:

procedure hanoi(van,naar,via,aantal);
value van,naar,via,aantal;
integer van,naar,via,aantal;
begin
  if aantal>1 then 
     hanoi(van,via,naar,aantal-1);
  text(1,‘van ’);
  write(1,van);
  text(1,‘ naar ’);
  write(1,naar);
  skip(1);
  if aantal>1 then
     hanoi(via,naar,van,aantal-1)
end

Dit programma is vaak gebruikt om de superioriteit van Algol-60 boven programmeertalen zonder recursie zoals Fortran en Cobol aan te tonen.

Een ander voorbeeld van een recursieve aanroep is de volgende functie om het n-de getal uit de rij van Fibonacci te bepalen:

integer procedure fibonacci(n);
value n;
integer n;
begin
if n<=2 then 
  fibonacci:=1 
else
  fibonacci:=fibonacci(n-1)+fibonacci(n-2)
end

Op enkele punten wijkt de procedure in Algol-60 werkelijk af van de procedure in latere programmeertalen. Behalve numerieke en logische variabelen kunnen ook procedures als parameter dienen en voor de formele parameters wordt naast de call-by-value niet de call-by-reference maar de call-by-name gebruikt waardoor Jensen device kan worden toegepast.

De merkwaardige manier waarop de returnwaarde van de functie wordt opgegeven, door een assignment naar de naam van de procedure, is overgenomen uit Fortran.

[bewerk] Een compleet programma

Als voorbeeld volgt hier een programma waarin het gemiddelde en de standaarddeviatie van een van te voren opgegeven aantal in te voeren getallen wordt berekend. In 1965 was dat een nuttig programma voor studenten omdat er nog geen spreadsheets bestonden waarmee ze de berekening met een formule als STDEVP(A1:A10) konden uitvoeren. Uiteraard is het aantal een geheel getal en zijn de in te voeren getallen, het gemiddelde en de standaarddeviatie reële getallen. Verder specificeren we dat de standaarddeviatie berekend wordt met de formule \sigma=\sqrt{\frac{\sum_{i=1}^n(x_i-\bar{x})^2}{n}}. Deze mag niet worden vereenvoudigd tot \sigma=\sqrt{\frac{\sum_{i=1}^n{x_i}^2}{n}-\bar{x}^2} omdat dat een te onnauwkeurig resultaat geeft als de afwijkingen van het gemiddelde relatief klein zijn. Dit betekent dat de ingelezen variabelen in een array opgeslagen moeten worden. In Algol-60 kan een array worden gedeclareerd die precies plaats biedt aan het aantal in te lezen getallen. Bij het beperkte geheugen van de computers uit 1960 was dat een zeer nuttige functie.

Het programma ziet er als volgt uit, waarbij de toelichtingen zo veel mogelijk in het commentaar staan:

begin comment Bereken standaarddeviatie;
  integer n;
  text(1,"aantal getallen:"); 
  n:=read(1);
  begin comment De variabelen worden pas in het binnenblok
                      gedeclareerd want ze zijn niet eerder nodig;
    real array a[1:n];
    integer i;
    real gem,stdev;
    gem:=0;
    comment Tijdens het inlezen wordt het gemiddelde berekend.
                  voor de som wordt de variabele gem gebruikt;
    for i:=1 step 1 until n do
    begin 
      text(1,‘getal ’);
      write(1,i);
      text(1,‘:’);
      a[i]:=read(1);
      gem:=gem+a[i]
    end;
    gem:=gem/n;
    comment Voor de berekeningn van de standaarddeviatie 
                  worden de opgeslagen waarden gebruikt;
    stdev:=0;
    for i:=1 step 1 until n do
       stdev:=stdev+(a[i]-gem)^2;
    stdev:=sqrt(stdev/n);
    comment Nu komt de output;
    text(1,‘gemiddelde=’); 
    rwrite(1,gem,10,6);
    text(1,‘ standaarddeviatie=’);
    rwrite(1,stdev,10,6)
  end
end


Op een DOS-scherm zien input en output er als volgt uit

aantal getallen:4
getal 1 :100001
getal 2 :100002
getal 3 :100003
getal 4 :100004
gemiddelde= 100002.48 standaarddeviatie= 1.118034

[bewerk] Gebruik

Algol-60 werd onder andere gedoceerd aan de Technische Hogeschool Eindhoven waar een van de grondleggers van Algol-60, Edsger Dijkstra, de eerste hoogleraar informatica was. Aanvankelijk werd hiervoor de X-8 gebruikt, waarvoor Dijkstra en zijn medewerkers zelf een besturingssysteem en een algolcompiler schreven. Later werd een Burroughs computer aangeschaft, vandaar dat de implementatie van Algol-60 op het Burroughs mainframe BEATHE werd genoemd, Burroughs Extended Algol TH Eindhoven. Ook op de TH Delft, de TH Twente en verschillende universiteiten was Algol-60 de taal waarin studenten hun eerste programmeerlessen kregen.

[bewerk] Opvolgers

Uit Algol-60 zijn een groot aantal talen voorgekomen. Tot de Algol-familie behoren onder andere

Bovendien hebben programmeertalen als Fortran, Basic en Cobol veel elementen uit Algol-60 overgenomen

[bewerk] Externe links

 
Persoonlijke instellingen
in andere talen