Nekonečná smyčka - Infinite loop

V počítačovém programování je nekonečná smyčka (nebo nekonečná smyčka ) posloupnost instrukcí, které, jak jsou napsány, budou pokračovat donekonečna, pokud nedojde k vnějšímu zásahu („vytáhnout zástrčku“). Může to být záměrné.

Přehled

To se liší od:

• "typ počítačového programu, který nepřetržitě spouští stejné instrukce, dokud není zastaven nebo přerušen."

Zvažte následující pseudokód :

how_many = 0
while is_there_more_data() do
    how_many = how_many + 1
end
display "the number of items counted = " how_many

Stejné pokyny probíhaly nepřetržitě, dokud nebyly zastaveny nebo přerušeny . . . pomocí FALSE vrácené v určitém okamžiku funkcí is_there_more_data .

Následující smyčka naopak sama o sobě nekončí:

birds = 1
fish = 2
while birds + fish > 1 do
    birds = 3 - birds
    fish = 3 - fish
end

ptáci budou střídat 1 nebo 2, zatímco ryby budou střídat 2 nebo 1. Smyčka se nezastaví, pokud nedojde k vnějšímu zásahu („vytáhněte zástrčku“).

Podrobnosti

Nekonečné smyčky je posloupnost instrukcí v počítačovém programu , který smyček donekonečna, a to buď v důsledku smyčky , který nemá stav zakončovacího, které mají jeden, že nikdy nemůže být splněna, nebo ten, který způsobí, že smyčka začít znovu. Ve starších operačních systémech s kooperativním multitaskingem nekonečné smyčky normálně způsobily, že celý systém přestal reagovat. U nyní převládajícího preemptivního víceúlohového modelu obvykle nekonečné smyčky způsobují, že program spotřebuje veškerý dostupný čas procesoru, ale obvykle ho může uživatel ukončit. Rušné čekací smyčky se také někdy nazývají „nekonečné smyčky“. Nekonečné smyčky jsou jednou z možných příčin „ zamrznutí “ počítače ; další zahrnují mlácení , zablokování a narušení přístupu .

Zamýšlené vs neúmyslné smyčky

Smyčkování je opakování sady pokynů, dokud není splněna konkrétní podmínka. Nekonečná smyčka nastane, když podmínka nebude nikdy splněna, kvůli nějaké inherentní charakteristice smyčky.

Úmyslné smyčky

Existuje několik situací, kdy je toto požadované chování. Například hry na herních konzolách založených na kazetách obvykle nemají ve své hlavní smyčce žádnou podmínku ukončení, protože neexistuje žádný operační systém, do kterého by program mohl ukončit; smyčka běží, dokud není konzola vypnuta.

Moderní interaktivní počítače vyžadují, aby počítač neustále monitoroval vstup uživatele nebo aktivitu zařízení, takže na určité základní úrovni existuje nekonečná smyčka nečinnosti zpracování, která musí pokračovat, dokud se zařízení nevypne nebo nevynuluje. Například v naváděcím počítači Apollo byla tato vnější smyčka obsažena v programu Exec, a pokud by počítač neměl absolutně žádnou jinou práci, provedl by smyčku figuríny, která by jednoduše zhasla kontrolku „aktivity počítače“.

Moderní počítače také obvykle nezastaví hodiny procesoru nebo základní desky, když se zhroutí. Místo toho se vrátí k chybovému stavu zobrazujícímu zprávy operátorovi a zadají nekonečnou smyčku čekající na to, zda uživatel buď odpoví na výzvu k pokračování, nebo resetuje zařízení.

Vícevláknové

V programech s více vlákny se některá vlákna mohou spouštět uvnitř nekonečných smyček, aniž by celý program uvízl v nekonečné smyčce. Pokud hlavní podproces ukončí všechna vlákna procesu, jsou násilně zastavena, tím skončí všechny provádění a proces/program skončí. Vlákna uvnitř nekonečných smyček mohou provádět úkoly „úklidu“ nebo mohou být v zablokovaném stavu a čekat na vstup (ze soketu/fronty) a pokračovat v provádění pokaždé, když je přijat vstup.

Neúmyslné smyčky

Termín se nejčastěji používá pro situace, kdy to není zamýšlený výsledek; to znamená, když je to chyba . Takové chyby jsou nejčastější mezi začínajícími programátory, ale mohou je dělat i zkušení programátoři, protože jejich příčiny mohou být docela jemné.

Jednou z běžných příčin je například to, že programátor zamýšlí iterovat sekvenci uzlů v datové struktuře , jako je propojený seznam nebo strom , přičemž pro každý uzel provede kód smyčky jednou. Nesprávně vytvořené odkazy mohou vytvořit referenční smyčku v datové struktuře, kde jeden uzel odkazuje na jiný, ke kterému dochází dříve v sekvenci. Tím se část datové struktury stane prstencem , což způsobí, že se naivní kód bude navždy opakovat.

Zatímco většinu nekonečných smyček lze nalézt podrobnou kontrolou kódu, neexistuje obecná metoda, která by určovala, zda se daný program někdy zastaví nebo poběží navždy; To je nerozhodnutelnost o váhavý problém .

Přerušení

Dokud systém reaguje, nekonečné smyčky lze často přerušit odesláním signálu do procesu (například SIGINT v Unixu) nebo přerušením procesoru, což způsobí přerušení aktuálního procesu. To lze provést ve správci úloh , v terminálu pomocí příkazu Control-C nebo pomocí příkazu kill nebo systémového volání . To však nefunguje vždy, protože proces nemusí reagovat na signály nebo procesor může být v nepřerušitelném stavu, například v chybě komatu Cyrix (způsobené překrýváním nepřerušitelných pokynů v kanálu instrukcí ). V některých případech mohou fungovat i jiné signály, jako je SIGKILL , protože nevyžadují odezvu procesu, zatímco v jiných případech nelze smyčku ukončit po vypnutí systému.

Jazyková podpora

Nekonečné smyčky lze implementovat pomocí různých konstrukcí toku řízení . Nejčastěji je to u nestrukturovaného programování skok zpět ( goto ), zatímco u strukturovaného programování jde o neurčitou smyčku (while loop) nastavenou tak, aby nikdy nekončila, a to buď vynecháním podmínky, nebo explicitním nastavením na true, jako while (true) ....

Některé jazyky mají speciální konstrukce pro nekonečné smyčky, obvykle vynecháním podmínky z neurčité smyčky. Mezi příklady patří Ada ( loop ... end loop), Fortran ( DO ... END DO), Go ( for { ... }), Ruby ( loop do ... end) a Rust ( loop { ... }).

Příklady záměrných nekonečných smyček

Jednoduchý příklad (v C ):

#include <stdio.h>

int main()
{
  for (;;) // or equivalently, while (1)
    ;  
  return 0;
}

Forma for (;;)pro nekonečnou smyčku je tradiční, objevuje se ve standardním referenčním programovacím jazyce C a často se trestuhodně vyslovuje „navždy“.

Toto je smyčka, která bez zastavení vytiskne „Nekonečnou smyčku“.

Podobný příklad v roce 1980 éry BASIC :

10 PRINT "INFINITE LOOP"
20 GOTO 10

Podobný příklad v dávkových souborech DOS :

:A
echo Infinite Loop
goto :A

Zde je smyčka zcela zřejmá, protože poslední řádek bezpodmínečně posílá provedení zpět na první.

Příklad v Javě

while (true) {
    System.out.println("Infinite Loop");
}

Příklad v Bourne Again Shell

for ((;;)); do
	echo "Infinite Loop"
done

Příklad v Rust

loop {
    println!("Infinite loop");
}

Příklady neúmyslných nekonečných smyček

Matematické chyby

Zde je jeden příklad nekonečné smyčky v jazyce Visual Basic :

dim x as integer
do while x < 5
  x = 1
  x = x + 1
loop

To vytváří situaci, kde xnikdy nebude větší než 5, protože na začátku kódu smyčky xje dána hodnota 1, takže smyčka vždy skončí 2 a smyčka se nikdy nepřeruší. To lze opravit přesunutím x = 1instrukce mimo smyčku. V podstatě to, co tato nekonečná smyčka dělá, je instruovat počítač, aby stále přidával 1 k 1, dokud není dosaženo 5. Protože 1+1 se vždy rovná 2, nikdy se to nestane.

V některých jazycích může zmatek programátorů ohledně matematických symbolů vést k neúmyslné nekonečné smyčce. Zde je například úryvek v jazyce C :

#include <stdio.h>

int main(void)
{
   int a = 0;
   while (a < 10) {
      printf("%d\n", a);
      if (a = 5)
         printf("a equals 5!\n");
      a++;
   }
   return 0;
}

Očekávaný výstup jsou čísla 0 až 9 s vloženým „a se rovná 5!“ mezi 5 a 6. V řádku " if (a = 5)" výše však programátor zaměnil operátor = (přiřazení) s operátorem == (test rovnosti). Místo toho se av tomto bodě programu přiřadí hodnota 5 až . aNikdy tedy nebude možné postoupit na 10 a tato smyčka nemůže být ukončena.

Chyby zaokrouhlení

Tento problém může také způsobit neočekávané chování při vyhodnocování podmínky ukončení. Zde je příklad v C :

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

Na některých systémech se tato smyčka spustí desetkrát podle očekávání, ale na jiných systémech nikdy neskončí. Problém je v tom, že podmínka ukončení smyčky (x! = 1,1) testuje přesnou rovnost dvou hodnot s plovoucí desetinnou čárkou a způsob, jakým jsou hodnoty s plovoucí desetinnou čárkou reprezentovány v mnoha počítačích, způsobí, že tento test se nezdaří, protože nemohou přesně reprezentovat hodnotu 0,1, tedy zavádění chyb zaokrouhlování při každém přírůstku (srov. rámeček).

Totéž se může stát v Pythonu :

x = 0.1
while x != 1:
    print(x)
    x += 0.1

Z důvodu pravděpodobnosti neočekávaného selhání testů rovnosti nebo nerovnosti je bezpečnější používat při práci s hodnotami s plovoucí desetinnou čárkou testy větší než nebo menší než. Například místo testování, zda se xrovná 1,1, je možné otestovat, zda (x <= 1,0) nebo (x <1,1) , z nichž by bylo jisté, že se po konečném počtu iterací ukončí. Dalším způsobem, jak tento konkrétní příklad opravit, by bylo použít celé číslo jako smyčkový index a spočítat počet provedených iterací.

Podobný problém se často vyskytuje v numerické analýze : Aby bylo možné vypočítat určitý výsledek, má se iterace provádět, dokud není chyba menší než zvolená tolerance. Kvůli chybám zaokrouhlení během iterace však nelze nikdy dosáhnout zadanou toleranci, což má za následek nekonečnou smyčku.

Smyčky pro více účastníků

Nekonečná smyčka může být způsobena interakcí několika entit. Zvažte server, který vždy odpoví chybovou zprávou, pokud nerozumí požadavku. I když na samotném serveru neexistuje možnost nekonečné smyčky, systém obsahující dva z nich ( A a B ) se může smyčkovat donekonečna: pokud A přijme zprávu neznámého typu od B , pak A odpoví chybovou zprávou na B ; pokud B nerozumí chybové zprávě, odpoví na A vlastní chybovou zprávou; pokud A nerozumí chybové zprávě z B , odešle další chybovou zprávu atd.

Běžným příkladem takové situace je smyčka e -mailu . Příklad smyčky e-mailu je, pokud někdo přijímá poštu z doručené pošty bez odpovědi, ale jeho automatická odpověď je zapnutá. Budou odpovídat na doručenou poštu bez odpovědi a spustí odpověď „toto je doručená pošta bez odpovědi“. To bude odesláno uživateli, který poté odešle automatickou odpověď do doručené pošty bez odpovědi atd. A tak dále.

Pseudo-nekonečné smyčky

Pseudo-nekonečná smyčka je smyčka, která se jeví jako nekonečná, ale ve skutečnosti je to jen velmi dlouhá smyčka.

Velmi velká čísla

Příklad v bash :

for x in $(seq 1000000000); do
#loop code
done

Nemožná podmínka ukončení

Příklad pro smyčku v C :

unsigned int i;
for (i = 1; i != 0; i++) {
  /* loop code */
}

Zdá se, že to bude pokračovat donekonečna, ale ve skutečnosti hodnota inakonec dosáhne maximální hodnoty, kterou lze uložit, unsigned inta přidání 1 k tomuto číslu se zalomí na 0, čímž se přeruší smyčka. Skutečný limit izávisí na podrobnostech systému a použitém kompilátoru . S aritmetikou libovolné přesnosti by tato smyčka pokračovala, dokud by paměť počítače již nemohla vydržet i. Pokud by to ibylo celé číslo se znaménkem, nikoli celé číslo bez znaménka, přetečení by bylo nedefinováno. V tomto případě by kompilátor mohl optimalizovat kód do nekonečné smyčky.

Nekonečná rekurze

Nekonečná rekurze je speciální případ nekonečné smyčky, která je způsobena rekurzí .

Následující příklad ve VBA vrací chybu přetečení zásobníku :

Sub Test1()
    Call Test1
End Sub

Prohlášení o přestávce

while (true)Smyčka " " vypadá na první pohled nekonečně, ale může existovat způsob, jak smyčce uniknout příkazem break nebo return . Příklad v PHP :

while (true) {
    if ($foo->bar()) {
        return;
    }
}

Aldersonova smyčka

Aldersonova smyčka je vzácný slangový nebo žargónový výraz pro nekonečnou smyčku, kde je k dispozici výstupní podmínka, ale v aktuální implementaci kódu je nepřístupná, obvykle kvůli chybě programátora. Ty jsou nejběžnější a viditelné při ladění kódu uživatelského rozhraní .

Příklad pseudokódu podobný C ve smyčce Alderson, kde má program sčítat čísla daná uživatelem, dokud není zadána nula, ale kde programátor použil nesprávný operátor:

int sum = 0;
int i;
while (true) {
   printf("Input a number to add to the sum or 0 to quit");
   i = getUserInput();
   if (i * 0) { // if i times 0 is true, add i to the sum. Note: ZERO means FALSE, Non-Zero means TRUE. "i * 0" is ZERO (FALSE)!
      sum += i; // sum never changes because (i * 0) is 0 for any i; it would change if we had != in the condition instead of *
   }
   if (sum > 100) {
      break;    // terminate the loop; exit condition exists but is never reached because sum is never added to
   }
}

Termín údajně dostal své jméno od programátora (příjmení Alderson), který v roce 1996 kódoval modální dialogové okno v aplikaci Microsoft Access bez tlačítka OK nebo Storno, čímž deaktivoval celý program, kdykoli se pole objevilo.

Viz také

• Detekce cyklu
• Zablokování
• Divergence (počítačová věda)
• Vidlicová bomba (nekonečná smyčka je jednou ze dvou klíčových součástí)
• Jít do
• Nekonečná regrese
• Rekurze (počítačová věda)

Reference

externí odkazy

• Vytvořte nekonečnou smyčku v několika jazycích na programování-idioms.org .