Repetitie (informatica)
Van Wikipedia
Een repetitie in de zin van de informatica is een constructie in een programmeertaal waardoor een of meer statements een aantal keren uitgevoerd worden.
Inhoud |
[bewerk] Repetitiestatements
Alle universele programmeertalen beschikken over tenminste één repetitiestatement. Dit soort statement geeft aan dat een aantal andere statements steeds opnieuw uitgevoerd dienen te worden, totdat aan een bepaalde conditie voldaan is. Een dergelijk statement bestaat op zijn minst uit drie zaken:
- Een conditionele expressie die aangeeft hoe vaak de repetitie zich moet herhalen
- Een statement (of blok statements) die herhaald worden
- De sleutelwoorden die de repetitie-constructie aanduiden in de programmeertaal
[bewerk] De 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 nie nog een slag verder.
[bewerk] Statementvormen
Er zijn een aantal vormen van de repetitie die vaak voorkomen.
[bewerk] While
Ongetwijfeld de bekendste vorm van de repetitie is de while-vorm:
while B do S
De "normale" semantiek van dit statement is dat conditionele expressie B geëvalueerd wordt. Als B tot true evalueert, wordt het statementblok S uitgevoerd. Daarna wordt B weer geëvalueerd. Als daar weer true uitkomt, wordt S weer uitgevoerd. Enzovoorts, totdat B evalueert tot false. Daarna eindigt het statement.
In zijn meest voorkomende vorm is de while-constructie een statement dat niet gegarandeerd eindigt. Het herhaald uitvoeren van S moet er uiteindelijk voor zorgen dat B een keer de waardering false krijgt. Gebeurt dit niet, dan eindigt de repetitie niet.
Een uitgebreidere variatie hierop, bekend uit de programmeertaal GCL, is de do-constructie. 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 B0 -> S0 [] B1 -> S1 [] ... [] Bn -> Sn od
[bewerk] 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.
Meestal is de semantiek van een dergelijk statement dusdanig dat het blok tenminste een keer uitgevoerd wordt. Daarna wordt de conditionele expressie voor het eerst geëvalueerd.
repeat S until B
[bewerk] For
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.
for (each element in variabele) do S
[bewerk] 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:
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 tenminste net zo sterk is als P. P is namelijk de logische begintoestand van de volgende slag van de repetitie.
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.
Hieruit "volgt" het axioma van de repetitie:
Dit algemene schema kan uitgebreid worden voor de volledige do-constructie met meerdere, conditionele expressies.
[bewerk] De 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 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.
