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ů — procedury a funkce. 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 |
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, B: Byte a dvojice deklarací var A: Byte; var B: Byte 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).
{======================================================================} 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 |
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ě } ...
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í:
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á).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ý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:
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…function Funkce (X: Real): Real; begin Funkce := X; Funkce := Funkce + 1 end;
{======================================================================} 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 |
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ů |
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 |
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:
>
1 je n! = n . (n – 1)!
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:
Při výpočtu výrazu Nfunction Faktorial (N: Byte): LongInt; {------------------------------------} begin { Faktorial } if N < 2 then Faktorial := 1 else Faktorial := N * Faktorial(N - 1) end; { Faktorial }
*
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).
Rekurzivní algoritmus řešení spočívá v těchto krocích:
>
1):
{======================================================================} 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}