Větvení (programování)

Větvení v programování je operace používaná v případech, kdy provedení či neprovedení určité množiny příkazů musí záviset na splnění či nesplnění určité podmínky. Větvení je jednou ze tří (spolu se sekvenčním prováděním příkazů a smyčkou ) základních struktur strukturovaného programování .

Hlavními formami implementace větvení v imperativních programovacích jazycích jsou podmíněný operátor (operátor if) a operátor s více hodnotami (switch, case, switch). V raných jazycích nízké úrovně je větvení implementováno prostřednictvím operátoru podmíněné větve .

Podmíněný operátor

Podmíněný operátor implementuje provádění určitých příkazů za předpokladu, že nějaký logický výraz (podmínka) nabývá hodnoty "true" true. Ve většině programovacích jazyků začíná podmíněný příkaz klíčovým slovem if(přeloženo z  angličtiny  -  „if“). Existují následující formy podmíněného operátoru -- s jednou větví a dvěma.

Při provádění podmíněného příkazu s jednou větví if <условие> then <команды> endse vyhodnotí podmínka, a pokud je pravdivá, provedou se příkazy až po klíčové slovo end, jinak provádění programu pokračuje příkazem následujícím za podmíněným příkazem. V jazycích nižší úrovně ( assemblery ) je to jediná dostupná forma podmíněného příkazu. V některých jazycích se pro podmíněný operátor s jednou větví používá speciální klíčové slovo (obvykle toto then, přeloženo z  angličtiny  -  „že“).

Při provádění podmíněného operátoru se dvěma větvemi if <условие> then <команды1> else <команды2> end , pokud je podmínka pravdivá, jsou provedeny příkazy za klíčovým slovem , pokud je podmínka thennepravda, provedou se příkazy za klíčovým slovem else. Pokud je nutné zkontrolovat několik podmínek za sebou, je možné kaskádovat podmíněné příkazy:

if podmínka 1 then příkazy 1 else if podmínka 2 then příkazy 2 else if podmínka 3 then příkazy 3 ... else if podmínka N + 1 then příkazy N + 1 else příkazy end ;

V tomto případě budou podmínky zkontrolovány postupně, a jakmile bude splněna hodnota true, provede se odpovídající sada příkazů a vykoná se příkaz následující po podmíněném příkazu. Pokud není splněna žádná z podmínek, provedou se příkazy z větve else.

Řada programovacích jazyků obsahuje speciální konstrukci pro kaskádové podmíněné příkazy, která umožňuje psát vícenásobné větvení poněkud kompaktněji a méně náchylné k chybám při psaní:

if podmínka1 then příkazy1 elsif podmínka2 then příkazy2 elsif podmínka3 then příkazy3 ... else příkazy end ; pořadí provádění tohoto příkazu přesně odpovídá výše uvedené kaskádě jednoduchých příkazů if-then-else a rozdíl je čistě formální: namísto vnořených několika podmíněných příkazů je tato konstrukce jediným celkem a obsahuje další klíčové slovo elsif, které vyžaduje další stav po sobě.

Implementace

Pascal zdědil syntaxi z Algolu -60, podle které lze do větví podmíněného operátoru umístit pouze jeden příkaz. Proto, aby se tam vešlo více příkazů, jsou seskupeny do složeného příkazu pomocí klíčového slova beginand end. Větev else je volitelná. begina endjsou nutné pouze v případě, že existuje několik operátorů (například z důvodu jednotnosti kódu ). V příkladu operátor volby v Pascalu:

If podmínka then begin příkazy ; end else begin příkazy ; konec ;

Potřeba podmíněného operátoru v Algolu a Pascalu byla kritizována již od jeho počátku. Kritici uvedli, že mnoho složených příkazů zahlcuje program, narušuje normální odsazení a vyvolává chyby (pokud zapomenete složený příkaz tam, kde je potřeba v poslední větvi příkazu if, kompilátor si ničeho nevšimne, ale při spuštění programu ze skupiny příkazů, které by se měly v této větvi provést, se podle podmínky provede pouze první, všechny ostatní - vždy). Další generace jazyků - potomci Algolu se pokusili tohoto nedostatku zbavit. Mezi nimi jsou tři široce známé jazyky: Algol-68 , Modula-2 a Ada . Konstrukce příkazu if v nich je téměř stejná, až na jednotlivá klíčová slova:

  • Algol-68:
if podmínka ... fi ;
  • Modul-2
IF podmínka 1 THEN příkaz 1 ELSE IF podmínka 2 THEN příkaz 2 ... ELSE příkaz N END ;
  • Ada
if podmínka1 then příkazy1 else if podmínka2 then příkazy2 ... else příkazyN end if ;

Ve všech případech je "commandX" libovolný počet příkazů oddělených středníky. Ve všech případech jsou všechny větve podmíněného příkazu, kromě první (větve "pak"), volitelné a lze je přeskočit. Pokud neexistuje žádná „jiná“ větev a není splněna žádná z podmínek, pak se řízení přenese na příkaz za klíčovým slovem podmíněné dokončení (END, FI nebo END IF).

Jazyky C a C++ (a po nich Java , C# , PHP a mnoho dalších jazyků) mají podmíněný operátor, který je strukturálně podobný Pascalu. beginRozdíl je v tom, že podmínka musí být zapsána v závorkách a místo klíčových slov endse používají složené závorky {}:

if ( < podmínka > ) { < operátoři > } jiný { < operátoři > }

V Nemerle , na rozdíl od většiny jazyků, kde operátor ifmůže mít jednu nebo dvě větve, musí mít operátor if(syntaxe je zcela podobná jazyku C) dvě větve. Podmíněný operátor s jednou větví začíná klíčovým slovem when, navíc má jazyk další podmíněný operátor - unless, což je "reverse when" - v něm se provádějí příkazy podmíněné větve, pokud je podmínka nepravdivá.

když ( podmínka ){ příkazy } ledaže ( podmínka ) { příkazy }

Ve Forth má podmíněný operátor jinou formu než v jiných jazycích, a to kvůli příponové notaci a organizaci zásobníku. Podmínkový operátor se skládá ze tří slov IF ELSE THEN[1] .

< podmínka > IF < výraz _1_ pokud _ podmínka _ je pravdivá > ELSE < výraz _2_ pokud _ podmínka _ je nepravdivá > POTOM

Zde <условие>pouze přesune hodnotu na vrchol zásobníku, IFanalyzuje příznak a pokud:

  • nerovná se nule, pak se provedou výrazy až ELSEnebo THEN;
  • pokud se rovná nule, pak se provedou výrazy mezi ELSEa THEN.

Pokud chybí ELSE, získá se selektor s jednou větví: výrazy mezi IFa THENjsou provedeny pouze tehdy, je-li příznak nenulový.

Fortran měl zpočátku jen aritmetický IF , ve kterém, v závislosti na znaménku výrazu, byl proveden přechod na jeden ze tří štítků. Například část kódu rutiny pro řešení kvadratických rovnic:

DN = B * B - 4 * A * C IF ( DN ) 90 , 10 , 10 10 D = SQRT ( DN ) X1 = ( - B + D ) / ( 2 * A ) X2 = ( - B - D ) / ( 2 * A )

Poté byly přidány logické (booleovské) výrazy a logický IF s jedním příkazem, vyhodnocený GOTO, později - strukturální IF (s několika podmínkami), například:

DN = B * B - 4 * A * C _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 2 * A ) ELSE ! (žádný kód pro záporný diskriminant) END IF

Perl podporuje vícepodmínkovou strukturu if a také modifikátory příkazů, které se zapisují za část příkazu, která se provádí. Například následující dva příklady jsou z hlediska funkčnosti totožné:

if ( $a == 0 ) { ++ $nula_pocet ; } ++ $nula_count if $a == 0 ;

Místo if můžete napsat if, což způsobí, že hodnota podmíněného výrazu bude před kontrolou invertována. Stejná akce, pokud:

++ $nula_count, pokud $a != 0 ;

U složeného příkazu (bloku) je povolena pouze strukturní forma, nikoli modifikátor. Například:

if ( $a == 0 ) { ... } else if ( $a > 0 ) { ... } else { ... }

Poslední klíčové slovo není potřeba kvůli požadavku, aby příkazy za podmínek byly formátovány do bloků {…}.

Neexistuje žádný ekvivalent if pro větve elsif.

Erlang používá dva podmíněné příkazy – if a case. Oba mají výslednou hodnotu, která se rovná hodnotě posledního příkazu ve vykonávané větvi a lze je použít (přiřadit ke jménu, předat funkci...), takže v nich není žádný samostatný ternární podmíněný příkaz . V příkazu case se provádí Pattern Matching s možností dalších podmínek na hodnotách v porovnávaných a v příkazu if pouze testování podmínek. Ochranné testy umožňují omezenou sadu operací a vestavěných funkcí.

Příklad případu (smazání záznamu události ze stromu časů):

{ NewEBW , NewEBN } = case dict : find ( EBN , Node ) of error -> { EBW , EBN }; { ok , Expiry } -> { gb_trees : delete_any ({ Expiry , Node }, EBW ), dict : erase ( Node , EBN )} end ,

Příklady, pokud:

if NeedLater -> erlang : send_after ( trunc ( 1000 * ( 1 + Elapsed )), self (), i_apply_nodes_portion ); pravda -> konec ne , After2 = if %% Pokud to bylo příliš dávno, naplánujte časový limit okamžitě. Po1 =< ? EXPIRY_STEP_MIN -> ? EXPIRY_STEP_MIN ; Po 1 >= ? EXPIRY_STEP_MAX -> ? EXPIRY_STEP_MAX ; true -> After1 end ,

Operátor s více volbami

Konstrukce přepínače má několik (dvě nebo více) větví. Přepínač provede jednu danou větev v závislosti na hodnotě vyhodnocovaného klíčového výrazu. Základní rozdíl mezi touto instrukcí a podmíněným operátorem je v tom, že výraz, který určuje volbu spustitelné větve, nevrací logickou, ale celočíselnou hodnotu nebo hodnotu, jejíž typ lze přetypovat na celé číslo. Některé jazyky umožňují použití některých výrazů neceločíselného typu (například textových řetězců) v přepínači.

Prototypem moderní syntaktické konstrukce byla instrukce skoku používaná ve starých programovacích jazycích. Tento příkaz určil selektorový výraz, který vrátil celočíselnou hodnotu a sadu štítků. Po provedení příkazu byl výraz vyhodnocen a jeho hodnota byla použita jako číslo štítku (v seznamu příkazů), na který byl přechod proveden. Takové konstrukce byly například v programovacích jazycích Fortran („počítaný GOTO“) a BASIC . Atraktivní stránkou návrhu je jeho poměrně vysoká účinnost: pro určení požadované větve (značky skoku) není nutné sekvenční porovnání výsledku selektorového výrazu s mnoha hodnotami, stačí uložit pole nepodmíněných instrukcí skoku s potřebnými adresami v paměti tak, aby při provedení příkazu byl požadovaný prvek vypočítán přímo z hodnot výrazu. V tomto případě rychlost provádění příkazu nezávisí na počtu štítků. V moderních jazycích je implementace příkazu switch také často implementována jako skoková tabulka, sestávající z nepodmíněných příkazů skoku na odpovídající fragmenty kódu. Výraz, který má být vyhodnocen, je převeden na hodnotu posunu tabulky skoků, která určuje příkaz, který se má provést. V jazycích, kde výraz selektoru může mít neceločíselnou hodnotu, není zdaleka vždy možné přímo vyhodnotit požadovanou větev konstrukce přepínače, takže pro optimalizaci provádění používají jiné metody.

V moderních programovacích jazycích na vysoké úrovni má příkaz switch obvykle název switch(přeloženo z  angličtiny  -  "přepnout") nebo case(přeloženo z  angličtiny  -  "případ"). Vypočítaný výběr štítků však může být zachován v moderních nízkoúrovňových programovacích jazycích, jako je instrukce JL programovacího jazyka STL pro programovatelné logické automaty S7-300 a S7-400 vyráběné společností Siemens .

Například v C je syntaxe příkazu:

přepínač ( i ) { případ 0 : case 1 : // sekvence příkazů break ; case 2 : // sekvence příkazů break ; výchozí : ; }

Zde i je selektorový výraz, který musí být typu integer castable, každá větev provádění začíná klíčovým slovem case, za kterým následuje hodnota výrazu, pod kterým se má tato větev provést. Zajímavostí jazyka C je, že v něm je přepínač interpretován přesně jako příkaz ke skoku na vypočítaný štítek a hlavičky větví ( case значение :) hrají roli štítků. K ukončení příkazu switch po dokončení kódu větve se používá speciální příkaz break. Pokud ve větvi žádný takový příkaz není, po provedení kódu vybrané větve se spustí provádění kódu následujícího za ním. Tuto vlastnost lze využít pro optimalizaci, i když může způsobit těžko dohledatelné chyby (pokud programátor náhodou vynechá přestávku, kompilátor nevyhodí chybu, ale program poběží špatně). Výchozí větev se provede, když žádná z ostatních větví není vhodná.

Syntaxe příkazu C switch je zděděna mnoha jazyky, ale jeho sémantika není vždy zcela podobná C. Například C# umožňuje použít výraz pro výběr typu řetězce a příslušné štítky.

Vlastnosti výpočtu logických výrazů

Pořadí provádění programu s podmíněnými příkazy může být významně ovlivněno logikou vyhodnocování podmíněných výrazů přijatých v jazyce. Je-li podmínkou komplexní booleovský výraz, například „f(x) > 0 AND g(y) > 0“, existují dvě strategie pro vyhodnocení jeho výsledku:

  • Úplný výpočet: vypočítejte f(x), g(y), porovnejte výsledky s nulou a poté proveďte s výsledky operaci AND. Stejně tak například Visual Basic.
  • Neúplný výpočet: vypočítat f(x), porovnat hodnotu s nulou. Pokud je výsledek porovnání "pravda", vyhodnoťte zbytek výrazu. Pokud je první podmínka nepravdivá, přeskočte druhou podmínku, včetně výpočtu g(y), které jsou v ní obsaženy, protože pro operaci „AND“, pokud je jeden z operandů nepravdivý, je celý výraz zjevně nepravdivý.

Druhá možnost je nejběžnější pro průmyslové jazyky (zejména pro Algol, Fortran, C++, C, Java, JavaScript, ECMAScript, JScript, C#, Python). Tyto jazyky mají přísné pravidlo: "Logický výraz se vždy vyhodnocuje zleva doprava a jeho vyhodnocování se zastaví, jakmile je definován výsledek celého výrazu." To znamená, že pokud se výraz skládá z několika dílčích podmínek kombinovaných s operátorem AND (AND), pak se vyhodnocení výrazu zastaví, jakmile se ukáže, že jedna z dílčích podmínek je nepravdivá (protože „false AND libovolná hodnota“ má vždy za následek „false“) a naopak, pokud je několik dílčích podmínek zkombinováno s operátorem OR (OR), vyhodnocení se zastaví po první pravdivé dílčí podmínce, protože v tomto případě je pravdivý celý výraz bez ohledu na další vyhodnocení. Ale výraz obsahující operátor Exclusive OR (XOR) nelze plně vyhodnotit, protože jedna z hodnot v něm nemůže určit výsledek výpočtu celého výrazu.

Jazyky Ada a Erlang používají pro tyto varianty různá klíčová slova: slova a a nebo znamenají úplné hodnocení a a pak, nebo jinak (Ada), a také orelse (Erlang) – neúplné. V Erlangu mají andalso a orelse nižší prioritu než operátory porovnání, což se vyhýbá závorkám kolem elementárních termínů. Jazyk Visual Basic .NET má podobná klíčová slova: AndAlso a OrElse.

Pevné pořadí vyhodnocování dílčích podmínek (logický výraz se vždy vyhodnocuje zleva doprava) je zavedeno proto, aby bylo možné řídit pořadí vyhodnocování výrazu a vkládat do něj jako první ty podmínky, které mají být vyhodnoceny jako první. Mimochodem, takto se liší logické výrazy od aritmetických, u kterých ve většině jazyků není pořadí vyhodnocování podvýrazů (pokud není určeno prioritou a asociativitou operací) jazykem specifikováno a může se lišit v různé případy.

Volba této konkrétní logiky provádění je způsobena skutečností, že vám umožňuje zjednodušit logické výrazy, které používají závislé prvky. Klasickým příkladem je lineární vyhledávání v poli:

// Hledání v poli celých čísel v jazyce Pascal // Parametry - požadovaná hodnota a otevřené pole celých čísel // Výsledek - index nalezeného prvku nebo -1 pokud prvek nebyl nalezen funkce Najít ( e : integer ; var a : pole integer ) : integer ; _ var i : celé číslo ; začít i := 0 ; while ( i <= High ( a )) AND ( a [ i ] <> e ) do inc ( i ) ; //!!! if i <= High ( a ) then Find := i else Find := - 1 ; konec ;

Algoritmus implementovaný programem je zcela zřejmý, ale implementace má jednu jemnost (viz řádek označený vykřičníky): podmínka smyčky se skládá ze dvou částí spojených operátorem AND. První dílčí podmínka kontroluje, zda index i přesáhl pole, druhá kontroluje, zda se aktuální prvek pole nerovná požadované hodnotě. Pokud pole neobsahuje požadovanou hodnotu, tak po kontrole posledního prvku se hodnota proměnné i zvýší o jedničku; při další iteraci bude první dílčí podmínka nepravdivá a smyčka skončí bez kontroly druhé dílčí podmínky. Pokud by byly logické výrazy plně vyhodnoceny, pak pokud by v poli po poslední iteraci nebyl žádný prvek, došlo by k chybě: pokus o určení a[i] by způsobil nesprávný přístup do paměti.

Nutno podotknout, že kromě neúplného vyhodnocení hodnoty výrazu zde hraje významnou roli i pevné pořadí vyhodnocení dílčích podmínek: jelikož se jako první zapisuje kontrola na pole out-of-bounds, bude vždy provedené před kontrolou dosažení požadované hodnoty. Pokud by nebylo definováno pořadí, ve kterém byly podvýrazy vyhodnocovány, nebylo by možné zaručit správnost daného fragmentu programu.

Při úplném výpočtu logických výrazů by výše uvedený algoritmus musel být napsán přibližně v následujícím tvaru:

// Vyhledávání v poli celých čísel v jazyce Pascal // Hypotetická varianta s plným vyhodnocením logických výrazů // Parametry - požadovaná hodnota a otevřené pole celých čísel // Výsledek - index nalezeného prvku nebo -1, pokud prvek nebyla nalezena funkce Find ( e : integer var a : array of integer ) : integer ; _ var i : celé číslo ; f : boolean ; // další proměnná - příznak ukončení smyčky begin i := 0 ; f := false ; zatímco ne f do if i > High ( a ) then f := true else if a [ i ] = e then f := true else inc ( i ) ; if i <= High ( a ) then Find := i else Find := - 1 ; konec ;

Jak vidíte, museli jsme uměle nastavit pořadí, ve kterém byly výstupní podmínky počítány, a zavést další proměnnou. Právě proto, aby se předešlo podobným trikům, je zavedeno neúplné hodnocení logických výrazů.

Poznámka: Výše ​​uvedený kód je příkladem použití příkazu IF, ale nic víc. Tento kód nelze použít jako pravidlo pro zápis algoritmů v Pascalu.

Optimální algoritmus pro nalezení čísla v poli je:

function Find ( e : integer ; var a : array of integer ) : integer ; var i : celé číslo ; begin Vysledek := - 1 ; for i := Low ( a ) to High ( a ) do begin if a [ i ] = e then begin Výsledek := i ; zlomit ; konec ; konec ; konec ;

Poznámky

  1. Forth má operátor <условие> ?DUP <выражение>, který duplikuje výraz, pokud je podmínka pravdivá