Repetitie (informatica)

Een repetitie in de zin van de informatica, meestal loop (spreek uit loep) en soms lus genoemd, is een constructie in een programmeertaal waarmee een of meer statements herhaald uitgevoerd worden.

Repetitiestatements

Bijna alle imperatieve programmertalen beschikken over ten minste één soort repetitieconstructie. Zo'n constructie heeft als onderdelen:

de sleutelwoorden of tekens van de constructie zelf
(bijna altijd:) de broncode die herhaald uitgevoerd moet worden
(meestal:) de voorwaarde waaronder herhaling door moet gaan
(soms:) het aantal malen dat herhaald moet worden

Conditionele expressie

Iedere repetitie kan zich natuurlijk eindeloos herhalen. De meeste, nuttige repetities in computerprogramma's eindigen echter in eindige tijd.

Om aan te geven wanneer een repetitie al dan niet moet eindigen, beschikken repetitieve constructies meestal over een of andere, conditionele expressie. Een dergelijke expressie is een uitspraak in de zin van de specifieke programmeertaal die evalueert tot een waarde van de verzameling $\{true,false\}$ . Deze verzameling is de verzameling van waarheidswaarderingen van George Boole.

De semantiek van de meeste repetities is dat de conditionele expressie geëvalueerd wordt tot true of false. Afhankelijk van de waarde die uit deze evaluatie volgt, gaat de repetitie wel of niet nog een slag verder.

Soorten repetitieconstructies

Vaak voorkomende soorten herhaling zijn:

While

Algemene vorm:

  while V
  do S
  end

maar hierop zijn nogal wat variaties.

De semantiek van deze constructie is als volgt: ze wordt uitgevoerd door V (een voorwaarde) te evalueren, en alleen als de voorwaarde geldt (true oplevert) S (een reeks statements en constructies) uit te voeren, en dit te herhalen tot V niet meer geldt.

Enkele voorbeelden:

WHILE < 5 DO j +:=i; i +:= 1 OD    # Algol 68 #

while (j < 5 ) do begin j +:= i; i+:=1 end  // Pascal

while [ i < 5 ]; do j=`expr "$j" + 1; i=`expr "$i" + 1`; done  # Bourne shell

while (j < 5) { j += i; ++i }      /* C, C++, C#, Java, JavaScript, ... */

while ($j < 5) { $j += i; ++$i }   /* Perl, PHP */

While j < 5 :  j = j + i :  i = i + 1 :  End While   -- Visual Basic .NET

In het algemeen is de while-constructie een statement dat niet gegarandeerd eindigt. Meestal test V de voorwaarde, zonder de geldigheid ervan te beïnvloeden, terwijl het uitvoeren van S de geldigheid juist wel beïnvloedt. Het herhaald uitvoeren van S moet er dan uiteindelijk voor zorgen dat B een keer de waardering false krijgt. Gebeurt dit niet, dan komt het programma in een oneindige loop.

Maar hier wordt vaak van afgeweken:

met een break- of goto-statement in S kan een lus direct verlaten worden; daarom kan V ontbreken, bv.

  do { j += i; ++i; if (j < 5) break; }  /* C */

V kan de voorwaarde zelf beïnvloeden; daarom kan ook S ontbreken, bv.

  while ((j += i++) < 5);               /* C */

Een andere variatie hierop met vooral theoretisch belang is de do-constructie in Guarded Command Language. Deze constructie staat toe dat er nog een keuze gemaakt wordt tussen uit te voeren blokken. Zijn er meerdere conditionele expressies die tot true evalueren, dan wordt er uit alle mogelijkheden non-deterministisch een blok gekozen. De repetitie eindigt als er een conditionele expressie meer tot true evalueert. De vorm is als volgt:

  do B<sub>0</sub> -> S<sub>0</sub>
  [] B<sub>1</sub> -> S<sub>1</sub>
  [] ...
  [] B<sub>n</sub> -> S<sub>n</sub>
  od

Repeat

Een andere bekende vorm van repetitie is de repeat-constructie. Deze lijkt op de while, maar is eigenlijk net andersom. Het blok statements wordt uitgevoerd totdat de conditionele expressie tot true evalueert in plaats van zolang.

 repeat S
 until V

De verschillen met while zijn dus:

de waarde van V wordt andersom gebruikt;
S wordt een keer uitgevoerd voordat V voor het eerst wordt berekend.

Voorbeelden:

  repeat 
     j +:= i; 
     i+:=1 
  until j >= 5  // Pascal

  do { 
     j += i; 
     ++i 
  } while (j < 5)  /* C, ... */

For en foreach

Een laatste, bekende serie repetities is die van de for-achtige repetities. Deze repetities zijn bijzonder omdat ze vaak geen oneindige repetities toestaan (hoewel er talen zijn waar dat weer wel kan, zoals Java).

Ook de conditionele expressie is anders en geeft vaak een boven- en ondergrens aan voor een of andere soort teller. Deze expressie dient gelezen te worden als "bevindt teller X zich tussen waarden A en B?" In veel talen is de ondergrens een vaste waarde, zoals 0. De meeste talen laten de teller automatisch aanpassen, zodat de repetitie altijd eindig is. Sommige talen staan toe dat de stap waarmee de teller in waarde toeneemt ook gespecificeerd wordt.

 for (teller = onder to boven) repeat S

Een ander gebruik van for kan worden toegepast op objecten of variabelen met een eindig aantal elementen, bijvoorbeeld een array. Elke iteratie (toepassing van de bewerking) wordt dan toegepast op het het volgende element.

 foreach (element in variabele) do S

Axioma van de repetitie

Binnen de Hoare logica is uitgebreid gekeken naar de semantiek van repetities en naar axioma's waaruit de correctheid van repetities geconcludeerd kan worden.

In logische zin blijkt een repetitie niet eens zo ingewikkeld te zijn. Het komt erop neer dat een repetitie correct is als het interne blok statements correct is. Het uiteindelijke axioma van de repetitie kan zelfs beredeneerd worden.

Iedere repetitie heeft een preconditie, zoals alle statements:

\{P\}do\ B\rightarrow S\ od

Een repetitie kan leiden tot herhaling van de repetitie -- dit gebeurt als conditie B tot true evalueert. Een noodzakelijke conditie voor de correctheid van de repetitie is dus dat als S uitgevoerd wordt, dit resulteert in een postconditie die ten minste net zo sterk is als P. P is namelijk de logische begintoestand van de volgende slag van de repetitie.

\{P\wedge B\}S\{P\}

Daarnaast is het mogelijk dat de repetitie eindigt -- de volgende slag wordt niet meer uitgevoerd. Om dit correct te laten zijn, moet de postconditie van de repetitie volgen uit de preconditie en het feit dat de conditionele expressie niet tot true evalueert.

P\wedge \neg B\Rightarrow Q

Hieruit "volgt" het axioma van de repetitie:

{\frac {\{P\wedge B\}S\{P\}\ \ \ \ \ P\wedge \neg B\Rightarrow Q}{\{P\}do\ B\rightarrow S\ od\{Q\}}}

Dit algemene schema kan uitgebreid worden voor de volledige do-constructie met meerdere, conditionele expressies.

Rol van de repetitie in de informatica

De repetitie is een essentiële constructie in de informatica. Een repetitie die oneindig kan zijn, is een absolute noodzaak voor iedere, universele programmeertaal. Dit volgt direct uit het turingmachine berekeningsmodel. Iedere berekening is namelijk een (mogelijk oneindige) herhaling van stappen. Die herhaling kan niet gesimuleerd worden in een taal zonder repetitie. Iedere stap is overigens een keuze uit een eindig aantal mogelijkheden, waaruit volgt dat de selectie evenzeer essentieel is als de repetitie.

De turingmachine is volledig equivalent met de lambdacalculus, die gebaseerd is op recursie en niet op repetitie. Het is dan ook niet verbazend dat recursie en repetitie elkaar wederzijds kunnen implementeren en fundamenteel verbonden concepten zijn.

Zie ook

Oneindige lus