V.  

PODPROGRAMY


Podprogramy jsou základním nástrojem hierarchického členění programu. Tvoří do jisté míry samostatné, na hlavním programu nezávislé celky. Je-li třeba nějakou činnost provádět vícenásobně na různých místech programu, lze ji zapsat jako podprogram a na příslušná místa programu uvést již pouze jeho volání. Tímto způsobem lze snížit rozsah zdrojového textu i cílového kódu a zlepšit srozumitelnost programu. Při volání podprogramu a návratu z něj jsou sice prováděny jisté nezbytné akce, které jsou však z hlediska zpomalení výpočtu zanedbatelné, pokud není frekvence volání podprogramu velmi vysoká.

Činnost, kterou má podprogram vykonávat, způsob komunikace (předávání dat) a mechanismus volání jsou předepsány v jeho deklaraci. V tomto smyslu Turbo Pascal implementuje dvě třídy podprogramů — proceduryfunkce. Zatímco procedury komunikují výhradně pomocí svých parametrů (případně globálních proměnných), funkce přímo vracejí jistou hodnotu. Volání procedury je proto ze syntaktického hlediska příkazem, kdežto volání funkce výrazem.

Struktura deklarace podpogramu je do značné míry podobná struktuře celého programu — podprogram je tvořen hlavičkou a blokem. V deklarační části vlastního bloku mohou podprogramy deklarovat soukromé — lokální — objekty, tedy lokální návěští, konstanty, typy a proměnné, ale i vnořené procedury a funkce.

Deklarace podprogramu smí být umístěna kdekoliv v deklarační části bloku (ovšem až za deklaracemi veškerých vnějších objektů, které jsou v ní použity), zpravidla se však deklarace všech podprogramů daného bloku umisťují až na konec jeho deklarační části.

V.1. 

Procedury

Deklarace procedury je tvořena hlavičkou procedurytělem. Hlavička je uvozena rezervovaným slovem procedure, následuje identifikátor procedury a případně seznam formálních parametrů, pokud procedura nějaké parametry má. Tělo může obsahovat direktivu modelu volání podprogramu near nebo far, následuje blok nebo direktiva forward či external.

Obrázek 25: Deklarace procedury



Model volání souvisí s problematikou modulárního programování (kapitola XV). Podprogramy s dalekým modelem volání (far) lze volat ze všech modulů programu, kdežto podprogramy s blízkým modelem volání (near) pouze z toho modulu, v němž jsou deklarovány. Implicitní výběr modelu volání je řízen direktivou kompilátoru {$F+} (vzdálený) resp. {$F–} (blízký).

Direktiva forward odkládá deklaraci chybějícího bloku. Je používána v deklaracích vzájemně rekurzivních podprogramů (viz Rekurzivní procedury a funkce níže).

Direktiva external avizuje ve spojení s direktivou kompilátoru {$L soubor} (kapitola XXI), že přeložený kód podprogramu je připraven v souboru soubor. Jeho montáž do kódu programu zajistí po ukončení překladu automaticky spojovací program. Používá se pro začlenění assemblerských podprogramů, překládaných externím překladačem.

Seznam formálních parametrů je ohraničen kulatými závorkami a obsahuje deklarace parametrů podprogramu, vzájemně oddělené středníky:

Formální parametry   Deklarace parametru specifikuje jeho typ a model volání (nezaměňovat s modelem volání podprogramu). Parametr může být volán odkazem nebo hodnotou. S parametrem volaným hodnotou je nakládáno jako s lokální proměnnou (existuje pouze po dobu aktivity podprogramu), kdežto k parametru volanému odkazem je přistupováno jako k vnější nelokální proměnné. (Význam modelu volání je podrobněji popsán níže, v oddílu Skutečné parametry.)

Obrázek 26: Deklarace formálního parametru


Deklarace parametru volaného odkazem je uvozena rezervovaným slovem var, následuje identifikátor, dvojtečka a nepovinný typ parametru (viz Netypové parametry podprogramů). Pokud je deklarováno více parametrů stejného typu, lze uvést seznam jejich identifikátorů (například deklarace var A, BByte a dvojice deklarací var AByte; var BByte jsou navzájem rovnocenné).

V deklaraci parametru volaného hodnotou rezervované slovo var chybí a typ musí být uveden vždy.

Jako typ parametru může být uveden identifikátor typu, rezervované slovo string (řetězcový parametr) nebo rezervované slovo file (netypový soubor). Identifikátorem může být identifikátor jakéhokoliv typu s jediným omezením — soubory lze předávat pouze odkazem. V deklaraci hodnotového parametru nesmí být tedy uveden typ file ani identifikátor žádného typu soubor.

Volání procedury   Volání procedury je příkaz, jehož zápis je tvořen identifikátorem procedury a případným seznamem skutečných parametrů. Počet skutečných parametrů musí odpovídat počtu deklarovaných formálních parametrů, přičemž formálnímu parametru odpovídá skutečný parametr stejného pořadí v seznamu. Mechanismus přiřazení skutečného parametru formálnímu závisí na modelu jeho volání.

Obrázek 27: Volání procedury

Skutečné parametry   Skutečný parametr volaný odkazem musí být proměnná typu uvedeného v deklaraci parametru formálního. Proceduře je předána její adresa. Veškeré akce, které procedura deklaruje pro formální parametr, jsou potom prováděny přímo s touto proměnnou. Je-li tedy například uvnitř procedury deklarováno přiřazení nějaké hodnoty formálnímu parametru, přiřadí se tato hodnota proměnné skutečného parametru.

Pro parametr volaný hodnotou je při aktivaci procedury vytvořena lokální proměnná příslušného typu (uvedeného v deklaraci parametru) a do ní je vložena hodnota skutečného parametru. Dále nemá tato lokální proměnná ke skutečnému parametru žádný vztah — žádná z akcí, provedená procedurou nad formálním parametrem, nemá vliv na parametr skutečný. Skutečným parametrem nemusí být v tomto případě nutně proměnná — je dovoleno uvést libovolný výraz, jehož typ je kompatibilní vzhledem k přiřazení s typem formálního parametru.

Parametry volané hodnotou lze z uvedených důvodů použít pouze pro předávání dat proceduře (vstupní parametry procedury), kdežto parametry volané odkazem lze použít pro předávání dat oběma směry, tedy i pro vývoz výsledků výpočtu (vstupně-výstupní parametry procedury).


POZNÁMKA: Odkazem volaný parametr je vhodné použít i v případech, kdy má být proceduře předána hodnota proměnné, která je velmi rozsáhlá (například pole). Při volání odkazem je totiž proceduře předána pouze adresa skutečného parametru, odpadá vytvoření jeho kopie. Potom je však nutno zajistit, aby procedura nezpůsobila nechtěnou změnu hodnoty parametru.


PŘÍKLAD: V následující ukázce programu je pro výpočet přirozené mocniny reálného čísla deklarována procedura Mocnina. Vstupní data jsou jí předávána v parametrech Zaklad (umocňované číslo) a Exponent (mocnitel), výsledek výpočtu je vyvážen parametrem Vysledek. V algoritmu výpočtu je využito platnosti vztahu x2n = (x2)n.

{======================================================================}
program VypocetMocniny;
{======================================================================}

 var X: Real;                         { vstupní data programu - základ }
     N: Word;                         { a exponent mocniny             }

 procedure Mocnina (Zaklad: Real; Exponent: Word; var Vysledek: Real);
 {---------------------------------------------------------------------}
 begin { Mocnina }
  Vysledek := 1;                      { inicializace proměnné Vysledek }
  while Exponent > 0 do
   begin
    while not Odd(Exponent) do        { úprava podle x^(2*n) = (x^2)^n }
     begin
      Zaklad := Sqr(Zaklad);
      Exponent := Exponent div 2
     end;
    Vysledek := Vysledek * Zaklad;    { aktualizace mezivýsledku       }
    Exponent := Exponent - 1          { a exponentu                    }
   end
 end; { Mocnina }

begin { program }
 Writeln;                             { tisk titulku                   }
 Writeln('Výpočet mocniny');
 Writeln;
 Write('základ: ');                   { načtení základu a exponentu    }
 Readln(X);
 Write('exponent: ');
 Readln(N);
 Mocnina(X, N, X);                    { volání procedury               }
 Writeln('výsledek: ', X)             { tisk výsledku                  }
end. { program }

V.2. 

Funkce

Na rozdíl od procedur poskytují funkce svým voláním přímo nějakou hodnotu. Tato hodnota je vyvážena z funkce přes její identifikátor. V deklaraci hlavičky funkce je proto uveden typ hodnoty funkce. Přípustnými typy funkcí jsou všechny typy vyjma strukturovaných. Seznam formálních parametrůtělo mají v deklaraci funkce stejný tvar a význam, jako v deklaraci procedury.

Obrázek 28: Deklarace funkce


Volání funkce   Volání funkce je tvořeno jejím identifikátorem a případným seznamem skutečných parametrů. Ze syntaktického hlediska je výrazem, nikoliv příkazem. Může se tedy ve zdrojovém textu vyskytovat pouze tam, kde je výskyt výrazu přípustný.

Obrázek 29: Volání funkce

var X, Y: Real;

function Funkce (A: Real): Real;
...

Y := Funkce(X);                        { správně }
Y := 5 * Funkce(X) - 1;                { správně }
if Funkce(X) > Funkce(Y) then ...;     { správně }
Writeln(Funkce(X));                    { správně }
Funkce(X);                             { chybně  }
...

POZNÁMKA: Zákaz volání funkce příkazem lze eliminovat direktivou {$X+}. Viz rozšířená syntax volání funkcí.

Definice výstupní hodnoty funkce   Hodnotu, kterou má funkce vracet, je nutno v jejím těle definovat přiřazovacím příkazem, na jehož levé straně je uveden identifikátor funkce a na straně pravé požadovaná hodnota. Tento příkaz smí být uveden kdekoliv v příkazové části bloku funkce. Pokud chybí, vrací funkce hodnotu nedefinovanou, pokud je naopak proveden vícekrát, platí definice poslední:

function F1 (X: Real): Real;
begin
 if X = 0 then F1 := 1
          else F1 := Sin(X)/X
end;

function F2 (X: Real): Real;
begin
 F2 := 10 * X;
 F2 := 20 * X
end;
V těle funkce F1 je podle hodnoty parametru vždy provedena jediná z uvedených definic. V těle funkce F2 jsou naopak nezávisle na hodnotě parametru provedeny definice obě, prvá je však vždy předefinována druhou (je tedy zbytečná).

Výskyt identifikátoru funkce jinde než na levé straně přiřazovacího příkazu v jejím těle je překladačem chápán jako volání této funkce. Není tedy možné zacházet s identifikátorem funkce zcela jako s proměnnou:

function Funkce (X: Real): Real;
begin
 Funkce := X;
 Funkce := Funkce + 1
end;
Při překladu posledního příkazu v příkazové části uvedené funkce dojde k chybě — výskyt identifikátoru Funkce na pravé straně přiřazení bude chápán jako volání funkce, za nímž je očekávána oblá závorka se skutečným parametrem…


PŘÍKLAD: Program pro výpočet mocniny z přechozího příkladu upravíme změnou koncepce podprogramu — Mocnina bude funkcí:

{======================================================================}
program VypocetMocniny;
{======================================================================}

 var X: Real;                         { vstupní data programu - základ }
     N: Word;                         { a exponent mocniny             }

 function Mocnina (Zaklad: Real; Exponent: Word): Real;
 {---------------------------------------------------------------------}

  var Vysledek: Real;

 begin { Mocnina }
  Vysledek := 1;                      { inicializace proměnné Vysledek }
  while Exponent > 0 do
   begin
    while not Odd(Exponent) do        { úprava podle x^(2*n) = (x^2)^n }
     begin
      Zaklad := Sqr(Zaklad);
      Exponent := Exponent div 2
     end;
    Vysledek := Vysledek * Zaklad;    { aktualizace mezivýsledku       }
    Exponent := Exponent - 1          { a exponentu                    }
   end;
  Mocnina := Vysledek                 { definice výst. hodnoty funkce  }
 end; { Mocnina }

begin { program }
 Writeln;                             { tisk titulku                   }
 Writeln('Výpočet mocniny');
 Writeln;
 Write('základ : ');                  { načtení základu a exponentu    }
 Readln(X);
 Write('exponent : ');
 Readln(N);
 Writeln('výsledek : ', Mocnina(X, N)){ tisk výsledku                  }
end. { program }

V.3. 

Bloková struktura programu

Syntax jazyka umožňuje deklarace vnořených podprogramů. Úroveň vnoření přitom není syntaxí omezena, přesně je však vymezen rozsah platnosti deklarací. V bloku jsou vždy přístupné všechny objekty deklarované v něm — lokální objekty — a potenciálně přístupné i všechny objekty deklarované ve všech blocích vyšších, v nichž je daný blok vnořen — nelokální objekty.

Identifikátory všech objektů, deklarovaných v rámci jediného bloku, se musí vzájemně lišit, avšak objekty z navzájem různých bloků stejný identifikátor mít mohou. Redeklarací identifikátoru je jeho nelokální význam zastíněn významem lokálním. Následkem zastínění je nepřístupnost příslušného nelokálního objektu v uvažovaném bloku i všech blocích v něm vnořených (přesněji v té části programu, jejíž zdrojový text je vymezen výskytem redeklarace a koncem bloku tohoto výskytu).

Deklarace identifikátoru podprogramu náleží do toho bloku, v němž je uvedena jeho hlavička, kdežto deklarace identifikátorů jeho formálních parametrů až do jeho vlastního bloku. Proto mohou mít stejně označené formální parametry i podprogramy ve stejných blocích.

V.4. 

Mechanismus volání a komunikace podprogramů

Lokální proměnné podprogramů existují pouze po dobu aktivity bloku, ve kterém jsou deklarovány. Jsou alokovány ve speciálním úseku programu přidělené operační paměti, nazývaném zásobník. Při volání podprogramu jsou na zásobníku vytvořeny veškeré jeho lokální proměnné, včetně proměnných odpovídajících formálním parametrům volaným hodnotou. Hodnota formálních parametrů je inicializována hodnotou skutečných parametrů, hodnoty ostatních lokálních proměnných jsou nedefinované. Na zásobník jsou také ukládány adresy skutečných parametrů volaných odkazem a návratová adresa z podprogramu. Po ukončení výpočtu podprogramu je uvolněna jím použitá část zásobníku a řízení je předáno zpět na návratovou adresu.

Pokud je během aktivity podprogramu volán (z  jeho těla) další podprogram, jsou opět na zásobníku vytvořeny potřebné lokální proměnné a použitá velikost zásobníku roste. Počet současně aktivních podprogramů je tak omezen přidělenou velikostí zásobníkového segmentu programu. Požadavek na velikost přiděleného zásobníku lze ve zdrojovém textu uvést formou direktivy kompilátoru (viz požadavek na přidělení paměti), maximální velikost je zhruba 64 KB.

Vzhledem k tomu, že parametry volané hodnotou jsou lokálními proměnnými podprogramu, lze je použít pouze k předávání vstupních dat podprogramu, nikoli k vývozu dat z podprogramu. Výsledky výpočtu jsou standardně předávány prostřednictvím parametrů volaných odkazem, jen výjímečně pak pomocí nelokálních proměnných. Změna hodnoty nelokální proměnné uvnitř podprogramu je totiž poměrně nebezpečnou akcí, neboť není patrná ze zápisu jeho volání, takže se stává zdrojem obtížně odhalitelných chyb.

V.5. 

Rekurzivní procedury a funkce

Rekurzivní volání podprogramu je takové volání, které je uskutečněno v době, kdy je daný podprogram aktivní (předchozí volání ještě nebylo ukončeno). Je umožněno způsobem práce překladače, který dokáže přeložit volání jakéhokoliv podprogramu již v okamžiku, kdy je dokončen překlad jeho hlavičky (tedy nikoliv až po překladu kompletní deklarace podprogramu). K rekurzivnímu volání podprogramu může dojít v zásadě dvěma způsoby, označovanými jako rekurze přímárekurze vzájemná.

Přímá rekurze nastane v případech, kdy podprogram obsahuje ve svém těle volání sebe sama. Při deklaraci a překladu takového podprogramu se nevyskytují žádné problémy, neboť k překladu těla podprogramu — a tím i příkazu jeho rekurzivního volání — dochází vždy až po překladu jeho hlavičky.

Vzájemná rekurze nastane například tehdy, když z podprogramu P1 je volán podprogram P2 a z podprogramu P2 je volán podprogram P1 (nebo z P1 je volán P2, z P2 je volán P3, přičemž z P3 je volán P1 a pod.). Při deklaraci a překladu vzájemně rekurzivních podprogramů vyvstává problém pořadí deklarací. V uvedeném příkladu je P2 volán z P1, proto musí deklarace (hlavičky) P2 předcházet deklaraci (těla) P1. Zároveň však je z P2 volán P1, proto musí deklarace (hlavičky) P1 předcházet deklaraci (těla) P2

Problém řeší dopředná deklarace alespoň jednoho z podprogramů, v níž je jeho blok nahrazen direktivou forward. Úplná dodatečná deklarace tohoto podprogramu (obsahující již i blok) musí následovat nejpozději do konce deklarační části bloku, v němž je uvedena deklarace dopředná. V dodatečné deklaraci musí být hlavička buď zcela totožná s hlavičkou v deklaraci dopředné nebo musí obsahovat za rezervovaným slovem procedure resp. function již jen identifikátor podprogramu a středník. Direktiva modelu volání podprogramu (near či far) již v dodatečné deklaraci být uvedena nesmí.

Použití rekurze   Rekurzivními algoritmy lze řešit problémy, jejichž rozkladem vzniká podobný, ale v nějakém smyslu jednodušší problém. Jako pracovní příklad vezměme výpočet faktoriálu. Ten lze pro přirozené číslo n rekurzivně definovat takto:

Pro n rovno 0 nebo 1 je tedy faktoriál roven jedné a pro n > 1 je výpočet triviální, pokud je známa hodnota výrazu (n – 1)!, jejíž výpočet (týmž způsobem) je jednodušší než výpočet hodnoty n!. Deklarace funkce pro výpočet faktoriálu podle uvedené definice vypadá takto:

function Faktorial (N: Byte): LongInt;
{------------------------------------}
begin { Faktorial }
 if N < 2 then Faktorial := 1
          else Faktorial := N * Faktorial(N - 1)
end; { Faktorial }
Při výpočtu výrazu N * Faktorial (N – 1) se nejdříve musí vyhodnotit oba operandy operace násobení. Tak dochází k rekurzivnímu volání funkce Faktorial pro každý argument větší než 1. Celkový počet volání funkce Faktorial pro argument N > 1 je tedy právě N.

Z hlediska efektivity algoritmu je rekurze nevýhodná. Každé vyvolání podprogramu je totiž provázeno nezbytnými pomocnými akcemi (vytvoření lokálních proměnných na zásobníku, předání parametrů a návratové adresy, skok do podprogramu, uvolnění lokálních proměnných ze zásobníku, návrat z podprogramu), které zpomalují výpočet a zvětšují nároky na velikost zásobníku. To se negativně projeví především u takových algoritmů, ve kterých počet rekurzivních volání roste rychleji než lineárně. Rekurze je tedy ospravedlnitelná především v případech, kdy na efektivitě výpočtu příliš nezáleží a kdy je zápis rekurzivního algoritmu proti algoritmu nerekurzivnímu výrazně jednodušší (nebo kdy nerekurzivní algoritmus není znám).


PŘÍKLAD: Klasický problém hanojských věží je použitím rekurze řešitelný velmi elegantně a názorně: Jsou dány tři jehly, označené čísly 1, 2 a 3. Na jehle 1 je navléknuto n plochých disků, opatřených uprostřed otvorem. Průměry disků se směrem k vrcholu jehly postupně zmenšují. Úkolem je přenést všechny disky (věž) z jehly 1 na jehlu 3, přičemž

Rekurzivní algoritmus řešení spočívá v těchto krocích:

je-li n = 1:
přenes tento jediný disk ze zdrojové na cílovou jehlu
jinak (n > 1):
použitím tohoto algoritmu postupně přenes n – 1 horních disků ze zdrojové na pomocnou jehlu, cílová jehla přitom slouží jako pomocná
pak přenes jediný zbylý disk ze zdrojové na cílovou jehlu
a nakonec použitím tohoto algoritmu postupně přenes n – 1 odložených disků z pomocné na cílovou jehlu, jako pomocná přitom slouží jehla zdrojová

{======================================================================}
program HanojskeVeze;
{======================================================================}

 var N: Byte;                            { počet disků - výška věže    }

 procedure Vez (Zdroj, Cil, Pocet: Byte);{ číslo zdrojové a cílové     }
 {--------------------------------------}{ jehly, počet přenášených    }
                                         { disků                       }
  var Pomocna: Byte;                     { číslo pomocné jehly         }

 begin { Vez }
  if Pocet = 1 then                      { přenos jediného disku       }
   Writeln(Zdroj, '-', Cil)
  else                                   { přenos více disků           }
   begin
    Pomocna := 6 - Zdroj - Cil;          { výpočet čísla pomocné jehly }
    Dec(Pocet);                          { počet disků odkládaných na  }
                                         { pomocnou jehlu              }
    Vez(Zdroj, Pomocna, Pocet);          { odložení na pomocnou jehlu  }
    Writeln(Zdroj, '-', Cil);            { přenos zbývajícího disku    }
    Vez(Pomocna, Cil, Pocet)             { přenos odložených disků     }
   end
 end; { Vez }

begin { program }
 Writeln;                                { výpis titulku               }
 Writeln('HANOJSKÉ VĚŽE');
 Writeln;
 repeat                                  { načtení výšky věže          }
  Write('Počet disků (> 0): ');
  Readln(N)
 until N > 0;
 Writeln;
 Vez(1, 3, N);                           { přenos celé věže z jehly 1  }
                                         { na jehlu 3                  }
 Writeln
end. {program}