Oneindige lus

Een oneindige lus is een reeks instructies in een computerprogramma die in een oneindige herhaling ('lus', in het Engels: loop) uitgevoerd worden. Dit kan komen doordat de lus onder geen enkele voorwaarde eindigt of omdat de lus alleen eindigt onder bepaalde voorwaarden die nooit bereikt kunnen worden. In oudere besturingssystemen met coöperatieve multitasking kon dit ervoor zorgen dat het gehele systeem niet meer reageerde. Met het nu veelgebruikte preëmptieve multitasking zorgt een oneindige lus ervoor dat het systeem wel alle processortijd gebruikt maar dat dit meestal wel beëindigd kan worden door de gebruiker.

Lus

Een lus is een controlestructuur in programmeertalen waarmee een aantal instructies herhaald uitgevoerd kunnen worden totdat aan een bepaalde voorwaarde(n) is voldaan. Een oneindige lus doet zich voor wanneer die voorwaarde(n) nooit bereikt worden, bijvoorbeeld door inherente eigenschappen van de lus.

Voorbeeld

Een voorbeeld in BASIC:

10 PRINT "Hello, world"
20 GOTO 10

In het voorbeeld hierboven is de oneindige lus duidelijk aangezien de laatste regel altijd verwijst naar de eerste regel waar de executie voortgezet wordt. Onverwacht gedrag in de terminatievoorwaarde kan ook voor een oneindige lus zorgen. Een voorbeeld hiervan in de programmeertaal C:

float x = 0.1;
while (x != 1.1) {
  printf("x = %f\n", x);
  x = x + 0.1;
}

Op de bepaalde computers zal deze lus, zoals verwacht, tienmaal uitgevoerd worden maar op andere zal de lus nooit eindigen. Dit heeft te maken met de manier waarop zwevendekommagetallen worden voorgesteld op systemen. Het probleem is dat de conditie while (x != 1.1) een exacte gelijkheid tussen twee zwevendekommagetallen vereist. Op sommige systemen kan het getal 1.1 niet exact voorgesteld worden waardoor de test nooit zal slagen. De lus zal hierdoor nooit eindigen en een oneindige herhaling veroorzaken.

Aangezien de mogelijkheid bestaat dat gelijkheid tussen zwevendekommagetallen niet exact uitgevoerd kan worden, is het beter om bij zwevendekommagetallen te kijken of de getallen groter dan of kleiner dan elkaar zijn, zoals x >= 1.1 (hier wordt zowel op gelijkheid als groter dan gecontroleerd) of x < 1.2. De uitvoering zal hierdoor na enige tijd zeker eindigen , ongeacht de representatie van de getallen op het systeem. Een andere manier om dit probleem op te lossen is om gebruik te maken van integers (gehele getallen).

Een vergelijkbaar probleem doet zich voor bij het uitvoeren van numerieke wiskunde; om een bepaald resultaat te berekenen, worden berekeningen iteratief uitgevoerd totdat het verschil tussen het berekende antwoord en het werkelijke antwoord kleiner is dan een bepaalde waarde. Door afrondingsfouten tijdens het itereren kan het zijn dat aan deze voorwaarde nooit voldaan wordt.

Door de broncode van een computerprogramma te bestuderen is het vaak wel mogelijk oneindige lussen op te sporen. Er is echter geen algemene methode om te bepalen of een computerprogramma zal eindigen of oneindig zal blijven doorgaan. Dit wordt het stopprobleem genoemd.

Pseudo-oneindige lussen

Onmogelijke terminatievoorwaarde

Sommige lussen lijken op een oneindige lus maar blijken dit in de praktijk niet te zijn. Een voorbeeld (in C):

unsigned int i;
for (i = 1; i > 0; i++) {
  /* code in de lus */
}

De index in de for-lus begint op waarde 1 en de lus wordt pas beëindigd wanneer i <= 0 (aangezien de lus doorgaat zolang i > 0). Op het eerste gezicht zal deze lus oneindig uitgevoerd worden maar in de praktijk zal deze na enige tijd wel termineren. Na verloop van tijd zal i de maximale waarde hebben bereikt die in een unsigned int opgeslagen kan worden waarna er 1 bij opgeteld wordt waardoor de variable op 0 wordt gezet. De lus zal dan wel termineren.

Oneindige recursie

Een andere techniek is recursie: het aanroepen van dezelfde functie/methode om een resultaat te berekenen. In het volgende voorbeeld, in Haskell, wordt een functie incorrect gedefinieerd om de faculteit van een getal uit te rekenen:

fac_fout :: Int -> Int
fac_fout n = n * fac_fout (n-1)

Het probleem is dat de recursie niet termineert. Om de faculteit voor n uit te rekenen wordt n vermenigvuldigd met de faculteit van n-1.. en hetzelfde geldt voor n-1, n-2, ad infinitum. In dit soort situaties zal de executie eindigen als de stack volledig gebruikt wordt. Om dit op te lossen dient een basisgeval toegevoegd te worden, in dit geval voor n = 0:

fac :: Int -> Int
fac 0 = 1
fac n = n * fac (n-1)

De bovenstaande functie zal voor getallen n >= 0 eindigen. Voor negatieve getallen is de functie niet gedefinieerd.