# Podprogramy Programy mají dvě fundamentální složky: 1. pasivní datovou (hodnoty, na kterých je výpočet prováděn) a 2. aktivní řídící (kód, který výpočet řídí – určuje jaké operace, nad kterými hodnotami a v jakém pořadí se provedou). Základní jednotkou organizace aktivní části programu – řízení výpočtu – je «podprogram». ## Podprogramy abstraktně Nejprve se budeme zabývat podprogramem na abstraktní úrovni – jejich «významem» (sémantikou). To, jak se výpočet podprogramu realizuje na výpočetním stroji, si pak přiblížíme v další sekci. ### Účel │ • podprogram popisuje výpočet │ • parametrizace → různé výpočty │ • použití (volání) je výraz │ • lze používat opakovaně (i staticky) Podprogram je funkční celek, který popisuje nějaký výpočet – podobně jako samotný program. Tento výpočet je obvykle «parametrizován» – je možné podprogram používat (vykonávat, spouštět) opakovaně pro různé hodnoty «parametrů» a výsledek se může v závislosti na těchto parametrech měnit. Výsledkem podprogramu jsou pak opět nějaké hodnoty – v nejjednodušším případě je pouze jediná a říkáme jí «návratová hodnota». Díky této hodnotě je typicky použití (volání, spuštění, vykonání) podprogramu na syntaktické úrovni «výrazem». Později (ve čtvrté kapitole) si ukážeme i jiné možnosti, zejména «výstupní parametry». Hlavní charakteristikou podprogramu je možnost jej používat opakovaně, a to zejména „staticky“ – stejný podprogram je možné použít v mnoha různých (nezávislých) výrazech.¹ ¹ Toto se může jevit jako naprostá samozřejmost, ale uvážíme-li, jak pracuje výpočetní stroj – zejména instrukce řízení toku – není na první pohled jasné, jak něčeho takového dosáhnout a zároveň mít strojový kód podprogramu v jediné kopii. ### Zápis │ • definice │ ◦ návratový typ │ ◦ jméno │ ◦ formální parametry │ • použití (volání) │ ◦ jméno │ ◦ skutečné parametry Abychom mohli o podprogramech mluvit, musíme být nejprve schopni je zapsat, a také zapsat jejich použití. Definice podprogramu (v jazyce C) sestává z: 1. hlavičky, která deklaruje a. typ návratové hodnoty, b. jméno podprogramu (musí být v celém programu¹ unikátní), c. typy a jména formálních parametrů, 2. těla složeného z příkazů, které realizují výpočet podprogramu. Chceme-li již definovaný podprogram «použít» (zavolat, vykonat), použijeme k tomu jeho jméno následované seznamem «skutečných parametrů» uzavřeným v kulatých závorkách. ¹ V programech složených z více překladových jednotek umožňuje jazyk C pojmenovávat podprogramy buď na úrovni programu (implicitně), nebo překladové jednotky (klíčovým slovem ‹static›). Ty druhé pak ale není možné přímo používat mimo tuto překladovou jednotku. V tomto předmětu nic z toho ale potřebovat nebudeme. ### Vstupy a výstupy Nyní nastala ta chvíle, kdy budeme nuceni konfrontovat otázku vstupů a výstupů. Protože podprogramy zavádíme na úrovni jazyka C, budeme se pro tuto chvíli bavit o vstupech pouze na této úrovni. Protože náš jazyk je v tuto chvíli velice omezený, vstupy a výstupy budou mít velmi jednoduchou formu: 1. «parametry» podprogramu jsou hodnoty, které v místě použití podprogramu explicitně uvádíme, 2. «návratová hodnota» je výsledek, který se při vyhodnocení výrazu „dosadí“ místo (již ukončeného) provedení podprogramu. Krom explicitně uvedených parametrů je ale podprogram stále „uzavřený“ v tom smyslu, že jeho výsledek (návratová hodnota) nebude záviset na ničem dalším. Tento pohled se nám ovšem značně zamotá již příští týden. Z výše uvedeného můžeme udělat možná poněkud překvapivý závěr – náš jazyk prozatím neumožňuje zapsat jiné podprogramy, než «čisté funkce». K otázce vstupů, výstupů a čistoty funkcí se ale vrátíme hned v další kapitole. ### Sémantika │ • čistá │ ◦ nahrazení volání výsledkem │ • obecně │ ◦ nahrazení tělem? │ ◦ výsledek + efekt Omezíme-li se na čisté funkce, sémantika volání podprogramu je velmi jednoduchá – stačí ve výrazu celý podvýraz volání nahradit jeho výsledkem. V očekávání nových prvků jazyka ale takovýto denotační pohled není příliš uspokojivý a zvážíme tedy i jiný (operační), který blíže odpovídá tomu, jak se skutečně podprogramy chovají. Předpokládejme (bez újmy na obecnosti), že program je zadán jako sbírka vzájemně se volajících podprogramů a jeden z nich je vyznačen jako „hlavní“ – jeho výpočet odpovídá výpočtu celého programu.¹ Pak můžeme „výpočet programu“ ztotožnit s „výpočtem hlavního podprogramu“, od této ekvivalence se odrazit, a zavést pojem „výpočet podprogramu“ (od výpočtu programu se liší pouze tím, že se musíme vypořádat s parametry – vstupem). Nyní již můžeme přistoupit k popisu sémantiky volání (použití) podprogramu. Je-li během výpočtu potřeba získat výsledek takového volání: 1. hlavní výpočet v tomto místě «pozastavíme», 2. poznačíme si hodnoty skutečných parametrů (které v tomto bodě již musí být známy), 3. spustíme «nový výpočet» zadaný «volaným podprogramem» (nad zadanými vstupy - skutečnými parametry), 4. poznačíme si výsledek tohoto vedlejšího výpočtu, 5. pokračujeme v hlavním výpočtu, přitom jako výsledek volání použijeme hodnotu z bodu 4. Velice jednoduchým (i když ne zcela praktickým) způsobem, jak tohoto dosáhnout, je bod 3 realizovat na zcela novém výpočetním stroji (kterému jako program zadáme volaný podprogram). Jak později uvidíme, skutečné volání podprogramu se ale tomuto přístupu až podezřele podobá. ¹ Tento podprogram také jistě dobře znáte ze sbírky cvičení. Jmenuje se ‹main›. V našem zjednodušeném světě tento podprogram nebude mít žádné parametry – to odpovídá uzavřenosti programu jako celku. ### Parametry │ • formální parametr ~ proměnná │ ◦ má «vlastní objekt» │ • předání parametru │ ◦ jako «inicializace» proměnné │ ◦ předání «hodnotou» Velmi důležitým aspektem podprogramů (a zejména jejich vzájemné interakce) je předávání parametrů. Smyslem parametrů je možnost opakovaně spouštět tentýž podprogram pro různé vstupní hodnoty – máme-li algoritmus pro sčítání, můžeme ho použít k výpočtu ⟦13 + 7⟧ ale stejně tak třeba k výpočtu ⟦120 + 11⟧. Prozatím se budeme držet představy, že výpočet podprogramu spouštíme na nezávislém výpočetním stroji, a tedy velmi úzce koresponduje s výpočtem programu, jak jsme ho definovali v první kapitole. Jediný rozdíl je právě v roli parametrů. Vzpomeňte si na definici programu – jedná se o počáteční stav výpočetního stroje. Tento pomyslný program (počáteční stav) bude tedy různý pro různé hodnoty parametrů. Důležité ale je, že to je zároveň to jediné, v čem se bude lišit. To je důležité zejména proto, že pouhým přepisem několika málo paměťových buněk (těch, které odpovídají parametrům) dostaneme nový užitečný výpočet. Parametrické podprogramy nám tedy umožňují „jedním tahem“ popsat celou rodinu výpočtů. Na úrovni jazyka C jsou formální parametry velmi podobné lokálním proměnným. Mají jména, která jsou platná v celém těle podprogramu, a tato jména jsou svázána s objekty, které existují až do konce vykonávání podprogramu. Tyto objekty «vznikají voláním», tzn. ve chvíli, kdy je předáno řízení tělu, už všechny existují, a všechny mají přiřazenou hodnotu (tzn. jsou inicializované). Této metodě předávání parametrů se obecně (tzn. nejen v jazyce C) říká „volání hodnotou“. Jazyk C žádnou jinou metodu předávání parametrů nemá.¹ ¹ Na sémantické úrovni budeme příští týden mluvit o výstupních parametrech – něco, co by při předávání hodnotou nemělo být možné. Mechanicky ale skutečně půjde i v tomto případě o předání hodnotou. ### Typy │ • návratový typ │ ◦ patří «výrazu volání» │ • typy parametrů │ ◦ výrazy «skutečných» parametrů │ • kontrola použití bez těla Protože volání (použití) podprogramu je výrazem, podléhá stejně jako všechny ostatní výrazy «typové kontrole». Jak víme z předchozí kapitoly, typová kontrola ověřuje, že výraz je správně typově utvořený – tedy každý podvýraz je správného typu. Podprogramy interagují s typovou kontrolou dvěma způsoby: 1. je-li samotné volání správně utvořeno: pro každý podvýraz (tzn. pro každý skutečný parametr) je potřeba ověřit, že je typově kompatibilní s typem odpovídajícího «formálního parametru» (které tedy musíme znát), 2. je-li volání podprogramu podvýrazem, je potřeba ověřit, že typ tohoto podvýrazu je na daném místě přípustný – a k tomu potřebujeme znát «typ návratové hodnoty», který je zároveň typem celého výrazu. Protože předání parametru má «sémantiku inicializace» (formální parametr je skutečným objektem), typová kontrola parametrů probíhá stejně, jako by tomu bylo u inicializace proměnné stejného typu. Zároveň, známe-li typy parametrů, nejsou potřeba pro typovou kontrolu voláni žádné další informace – zejména není potřeba mít k dispozici tělo podprogramu. Díky tomu je možné typovou kontrolu provést i v situaci, kdy je viditelná pouze deklarace, ale nikoliv definice, volaného podprogramu. ## Operační sémantika V této sekci se budeme zabývat tím, jak se volání podprogramu realizuje na úrovni výpočetního stroje. Jako příklad standardně poslouží stroj ‹tiny› a překladač ‹tinycc›, ale všechny zde zmíněné principy jsou v produkčních překladačích velmi podobné. ### Hardwarový zásobník │ • oblast v paměti │ • speciální registr ‹sp› = adresa │ • souvisí s datovou strukturou │ ◦ last in, first out │ ◦ operace ‹push›, ‹pop› │ ◦ ‹sp› ~ top Hardwarový zásobník je oblast paměti, která je organizovaná automaticky – součinností překladače a procesoru (výpočetního stroje). Zejména tedy programátor (ve vyšším programovacím jazyce) nemusí správě této paměti věnovat přímou pozornost. Hardwarový zásobník (zásobník volání) v tomto smyslu volně odpovídá abstraktní datové struktuře zásobník, kterou znáte z předchozího studia – zejména se řídí principem „last in, first out“ – odebrání položky odstraní tu, která byla vložená nejpozději. Zásobník je realizován velice jednoduše – jediným celočíselným registrem, který obsahuje adresu «vrcholu» zásobníku. Pro správu zásobníku poskytuje procesor operace ‹push› a ‹pop›, které kombinují ‹st› resp. ‹ld› s posuvem adresy ‹sp›. Protože podobně jako v odpovídající ADT je vstupní podmínkou ‹pop› (resp. obecně odebrání položky) to, že tato musela být na zásobník vložena, znamená to, že není potřeba pamatovat si adresu dna zásobníku. ### Sémantika ‹push›, ‹pop› │ • ‹push reg› │ ◦ ‹sub sp, 2 → sp› │ ◦ ‹st reg → sp› │ • ‹pop reg› │ ◦ ‹ld sp → reg› │ ◦ ‹add sp, 2 → sp› Operace ‹push› a ‹pop› jsou základním mechanismem pro práci se zásobníkem a odpovídají intuici. Protože obě operace je velmi jednoduché nahradit jinými, nehrají pro vyjadřovací sílu výpočetního stroje nijak významnou roli, a překladače tyto operace (jak uvidíme za chvíli) používají spíše sporadicky. Za povšimnutí ale stojí směr, kterým tyto instrukce posouvají adresu vrcholu zásobníku (uloženou v registru ‹sp›). Instrukce ‹push reg› odpovídá sekvenci ‹sub sp, 2 → sp; st reg → sp›, a tedy adresu vrcholu zásobníku «snižuje». To mimo jiné znamená, že zásobník „roste“ směrem k nižším adresám.¹ Také je důležité, že pořadí přístupu do paměti a změny ‹sp› je pro ‹push› a ‹pop› opačné; které to bude je určeno právě směrem růstu zásobníku (rozmyslete si proč). ¹ To ve skutečnosti není samo o sobě důležité a jedná se spíše o historický artefakt. Podstatné je, že se všichni na tomto směru shodnou – zejména překladač, který často generuje kód, který registrem ‹sp› manipuluje přímo, bez použití ‹push› a ‹pop›. ### Předání řízení │ • vstup: ‹call› │ ◦ vstup do podprogramu │ ◦ «neřeší» parametry │ • konec: ‹ret› │ ◦ ukončení podprogramu │ ◦ «neřeší» návratovou hodnotu Mnohem důležitějšími operacemi, které pracují přímo se zásobníkem, je dvojice ‹call› a ‹ret› (které v nějakém smyslu odpovídají operacím ‹push› a ‹pop›). Tyto operace realizují «volání podprogramu» a «návrat řízení» do podprogramu volajícího. Pozor, ani operace ‹call›, ani operace ‹ret›, přímo neinteraguje s parametry ani návratovou hodnotou. Z pohledu výpočetního stroje žádné předávání parametrů do podprogramů neexistuje – vše potřebné musí zařídit překladač za pomoci běžných instrukcí. ### Sémantika ‹call›, ‹ret› │ • ‹call fn› (jeden krok!) │ ◦ ‹push pc› │ ◦ ‹jmp fn› │ • ‹ret› ~ ‹pop pc› │ ◦ nebo: ‹pop X›, ‹jmp X› │ ◦ «nepřímý» skok Z definice podprogramu a popisu operace ‹call› se již snadno nahlédne, že tato musí v nějakém smyslu pozastavit provádění současného podprogramu, a to způsobem, který umožní později v jeho vykonávání pokračovat. Zároveň lze říct, že provede pouze «nutné minimum» – sama o sobě operace ‹call› neprovede uložení stavu stroje. To zejména znamená, že sama o sobě operace ‹call› nerealizuje naši předchozí představu, že podprogram spustíme ve zcela novém výpočetním stroji. Jediná část stavu výpočtu, kterou není snadné uložit nijak jinak, je hodnota ‹pc›, a právě tuto hodnotu musí operace ‹call› zachovat. A protože není předem známo, kolik takových hodnot bude potřeba uchovat (odpovídá hloubce zanoření podprogramů), bude k tomu využívat «paměť», které je typicky k dispozici relativně velké množství. Zároveň také víme, že je-li nějaký podprogram ukončen, je to právě ten, který byl zavolán (aktivován) jako poslední – platí tedy opět princip LIFO – „last in, first out“. Tyto dvě skutečnosti dohromady přirozeně vedou na standardní řešení, totiž ukládat hodnotu ‹pc› na hardwarový zásobník (který je uložený v paměti a pracuje na principu LIFO). ### Lokální proměnné │ • hodnota se musí zachovat │ • „zálohování“ registrů │ ◦ na zásobník (‹push›, ‹pop›) │ ◦ do rámce │ • caller save vs callee save Podobná úvaha pak vede také k tomu, že na hardwarový zásobník budeme ukládat další části stavu stroje, které je potřeba uchovat, aby bylo možno v přerušeném výpočtu volajícího pokračovat. Na úrovni jazyka C se zejména jedna o «hodnoty lokálních proměnných», které jsou typicky uloženy v registrech. Uvažme prvně zjednodušenou situaci, kdy máme registrů k dispozici libovolně (nekonečně) mnoho. Na první pohled by se mohlo zdát, že bude-li každý podprogram využívat jinou podmnožinu těchto registrů, není potřeba nic dalšího řešit – výpočty podprogramů budou nezávislé automaticky. To ale přestane platit, jakmile dojde k aktivaci (volání) podprogramu, který už v té chvíli aktivní je. To je samozřejmě přípustné (tento jev jistě dobře znáte – říká se mu rekurze). Dohromady tyto dva problémy (konečný počet registrů a rekurzivní aktivace podprogramů) znamenají, že hodnoty registrů budeme považovat za součást stavu podprogramu, a bude tedy nutné je při volání nového podprogramu zachovat. Jednoduchá strategie, která tento problém řeší, je během vstupu do podprogramu uložit hodnoty registrů na zásobník, např. sekvencí operací ‹push›, a během návratu z něj jejich hodnoty obnovit, např. zrcadlovou sekvencí operací ‹pop›. Alternativně je možné registry ukládat do předem vymezeného prostoru – rámce (uvidíme později). V obou případech ovšem vyvstává otázka, na které „straně“ instrukce ‹call› (a instrukce ‹ret›) toto ukládání (obnovení) provádět. Provede-li uložení a obnovení stavu volající, mluvíme o „caller save“; provede-li jej naopak volaný, mluvíme o „callee save“. Každá metoda přináší nějaké výhody a nějaké nevýhody a typické překladače volí pro různé registry různou strategii (tzn. část registrů může být caller save a jiná část callee save).¹ ¹ Metoda callee save je výhodná v situaci, kdy je šance, že volající daný registr vůbec nepotřebuje použít, a jeho hodnota se tedy zachová přirozeně – není potřeba ji ukládat na zásobník. Metoda caller save je naopak výhodná v situaci, kdy je šance, že hodnota je v době volání „mrtvá“ – volající už ji nebude potřebovat a tedy ji není nutné uložit z tohoto důvodu. ### Předávání parametrů │ • přednostně v registrech │ ◦ ‹l1›, ‹l2›, … │ ◦ další na zásobník │ • podobně návratová hodnota (‹rv›) │ • složitější typy později Tím jsme sestavili mechanismus, který nám umožní bezpečně přerušit výpočet podprogramu a později se k němu vrátit. Zbývá vyřešit druhý důležitý aspekt podprogramů – parametrizaci. K tomu nám ale stačí najít vhodné místo, kam může volající parametry uložit a volaný je na tomto místě vyzvednout. Přirozeně se nabízí registry – je ovšem potřeba vyřešit interakci mezi využitím registrů pro lokální proměnné volajícího vs parametry předané do podprogramu. Návratová hodnota je jednodušší v tom, že je vždy pouze jedna – překladač ‹tinycc› pro její předání používá registr ‹rv›. ### Volací sekvence │ • ‹f( e₁, e₂, …, eₙ )› │ ◦ vyhodnoť ‹e₁› do ‹l1› │ ◦ vyhodnoť ‹e₂› do ‹l2› │ ◦ atd. až po ‹eₙ› │ ◦ ‹call f› ### Rekurze │ • použití v těle (definici) │ • neznámá hloubka zanoření │ • koncová vs obecná Podprogramy je typicky možné používat (volat) i uvnitř jejich vlastní definice.¹ Takto použitý podprogram se chová podobně jako cyklus – vede k opakovanému spuštění téhož úseku kódu. Je zde ale jeden podstatný rozdíl: nová aktivace podprogramu vytvoří nové instance lokálních proměnných (a tedy odpovídajících objektů), kdežto cyklus pracuje stále s těmi stejnými. Protože objekty svázané s lokálními proměnnými musí existovat až do ukončení podprogramu, musí se nutně tyto objekty během rekurze hromadit, a rekurzivní podprogram musí mít nutně paměťovou složitost přinejmenším lineární vůči hloubce zanoření. Protože tyto objekty jsou uloženy na zásobníku, a velikost zásobníku je typicky striktně omezená (to s týká i reálných programů, nejen stroje ‹tiny›), u běžné rekurze je nutné pečlivě sledovat maximální hloubku zanoření.² Je-li hloubka zanoření logaritmická (např. pro samo-vyvažovací vyhledávací stromy), nepředstavuje toto omezení žádný problém. Je-li ale zanoření lineární vůči nějakému externímu parametru (např. při zpracování obecného stromu), musíme být při použití rekurze opatrní. Existuje ovšem speciální případ, kdy hloubku rekurze není nutné omezovat, a totiž ten, kdy je možné všechny lokální objekty zničit ještě předtím, než je řízení odevzdáno rekurzivnímu volání. Tato situace nastane, je-li rekurzivní volání poslední akcí podprogramu – v takovém případě totiž nezbývá žádný kód, který by mohl k těmto objektům přistoupit. Taková rekurze se nazývá «koncovou».³ ¹ Platí to jak pro Python, tak pro jazyk C, a také pro většinu běžných programovacích jazyků. ² Jedním z důležitých důvodů pro tuto zvýšenou opatrnost je skutečnost, že běžné operační systémy program, jemuž dojde místo na zásobníku, ihned násilně ukončí. ³ Žel většina jazyků nezaručuje, že při koncové rekurzi se provede úklid mrtvých objektů (odstranění rámce ze zásobníku) dříve, než se provede rekurzivní volání. Mnoho překladačů sice tuto optimalizaci nezávazně provádí, ale spoléhat na to je poněkud riskantní. ## Rámec Pro uložení stavu podprogramu se v praxi využívá struktury známé jako „rámec“ nebo také „aktivační záznam“. Jedná se o flexibilnější a výkonnější mechanismus než naivní využití operací ‹push› a ‹pop›. Rámce jsou ale stále uloženy na hardwarovém zásobníku (v pořadí LIFO). ### Přelití registru │ • potřebujeme volný registr │ • co když jsou všechny „živé“ │ • přesuneme hodnotu na zásobník │ ◦ stejně jako při „zálohování“ Hlavní motivací pro rámce je skutečnost, že registrů je k dispozici konečné (a často velmi omezené) množství – zejména může lehce nastat situace, kdy používá podprogram více lokálních proměnných a/nebo potřebuje uložit více mezivýsledků, než kolik je k dispozici registrů. Potřebuje-li překladač uložit hodnotu, pro kterou není k dispozici registr, může tuto hodnotu místo toho uložit do rámce, kde si na ni přichystá místo. Objevuje se zde ale komplikace – s hodnotami uloženými v paměti není možné přímo počítat (nelze je použít jako operand většiny instrukcí). Proto je nutné hodnoty vhodně stěhovat mezi registry a pamětí. ### Lokální proměnné │ • lokálních proměnných může být „moc“ │ • uložíme je na zásobník │ • načtení do „dočasných“ registrů │ • příště: adresa proměnné (je-li jich víc než registrů) ### Vyhodnocení proměnné │ • vyhodnocujeme do ‹tmp› │ • „žije“ v registru: │ ◦ ‹copy reg → tmp› │ • „žije“ na zásobníku: │ ◦ ‹ld bp, offset → tmp› │ ◦ offset = vlastnost proměnné ### Rámec │ • privátní paměť podprogramu │ • alokuje se na zásobníku │ • různé aktivace → různé rámce │ • pevná velikost ### Správa rámců │ • při vstupu do podprogram: │ ◦ ‹push bp› │ ◦ ‹copy sp → bp› │ ◦ ‹sub sp, N → sp› │ • při výstupu: │ ◦ ‹copy bp → sp› │ ◦ ‹pop bp›