: title : PB111 Nízkoúrovňové programování (shrnutí jazyka C) : authors : P. Ročkai : doctype : workbook : typing : plain : lang : cs : toc : yes # Výpočetní stroj Tato kapitola jazyk C nepoužívá. # Lokální proměnné, řízení toku Počínaje touto kapitolou budeme většinu programů psát ve zjednodušené verzi jazyka C. V tomto kurzu budeme psát programy do jednoho souboru, který bude sestávat z definic typů (uvidíme později) a podprogramů. Na diskusi o sémantice podprogramů zatím nejsme připraveni, proto je budeme chápat jako syntaktickou obálku pro kód, který budeme psát. Program bude typicky vypadat takto: int podprogram( int parametr₁, int parametr₂ ) /* C */ { … } int main() { assert( podprogram( 1, 2 ) == 3 ); … } Podprogram s názvem ‹main› bude v tomto kurzu vždy obsahovat testy, které ověřují základní funkcionalitu ostatních podprogramů. Můžete si do něj vždy přidat svoje vlastní testy. Zápis ‹podprogram( 1, 2 )› je volání (použití) podprogramu – prozatím jej nebudeme mimo testy potřebovat, protože jediné podprogramy, které budeme moct v tomto předmětu použít, jsou ty, které si sami napíšeme. ### Hodnoty, objekty a proměnné Proměnné znáte již z kurzu IB111 – proměnné v jazyce C mají s těmi v Pythonu mnoho společného, ale mají také důležité odlišnosti. Prvním, v zásadě syntaktickým, rozdílem je, že v jazyce C musíme každou proměnnou «deklarovat» – to provedeme zápisem ‹typ jméno;› případně ‹typ jméno = výraz;›. První forma proměnnou pouze deklaruje, ale její počáteční hodnotu ponechá neurčenu – tuto hodnotu «není dovoleno použít». Typ proměnné určuje, jakých hodnot může nabývat – k dispozici máme prozatím tyto zabudované typy: • ‹unsigned› – celé číslo v rozsahu 0 až 65535,¹ • ‹int› – celé číslo v rozsahu -32768 do 32767,² • ‹bool› – celé číslo, 0 nebo 1, které typicky reprezentuje pravdivostní hodnotu – 0 pro ‹false›, 1 pro ‹true›, • ‹signed char› – celé číslo v rozsahu -128 až 127, • ‹unsigned char› – celé číslo v rozsahu 0 až 255, • ‹char› – typ se stejným rozsahem jako jeden z předchozích dvou (který z nich je určeno implementací), ale přesto z pohledu kontroly typů od obou odlišný. Proměnná je v jazyce C pevně svázaná³ s «objektem». Objekt je «abstrakce paměti» – reprezentuje entitu, která je schopna pamatovat si «hodnotu», již můžeme z objektu «přečíst» nebo do objektu «uložit» novou (a tím tu předchozí přepsat). Objekt tak můžeme chápat jako dvojí zobecnění paměťové buňky: • místo jednoho bajtu si pamatuje «hodnotu» (která může mít potenciálně složitou vnitřní strukturu, i když takové zatím neumíme v jazyce C sestrojit), • místo adresy má «identitu» – objekt můžeme „uchopit“ a pracovat s ním – obvykle tak, že tento objekt svážeme s proměnnou. Realizace objektů je důležitým prvkem implementace programovacího jazyka a může se případ od případu lišit. Zejména není pravda, že by byl objekt pevně svázán s nějakou adresou nebo registrem – překladač může objekt transparentně přesouvat dle potřeby výpočtu.⁴ ¹ Pro typy ‹int› a ‹unsigned› je konkrétní rozsah přípustných hodnot daný implementací – na mnoha systémech jsou tyto typy 32bitové. ² Starší standardy jazyka C neurčují, jaké kódování se použije pro znaménkové typy, novější již požadují dvojkový doplňkový kód (viz také předchozí kapitola). ³ Na rozdíl od jazyka Python, kde je možné vazbu proměnné na objekt změnit přiřazením. To v jazyce C možné není. ⁴ Překladače jazyka C například běžně přesouvají objekty mezi registry a zásobníkem podle aktuální situace. Tentýž objekt může být tedy v různých fázích výpočtu fyzicky uložen na různých místech. ### Živost a rozsah platnosti Objekt, který je s proměnnou svázaný, vznikne právě deklarací, a zanikne opuštěním rozsahu platnosti této proměnné. Čtení objektu je implicitní – provede se kdykoliv proměnnou použijeme jako hodnotu ve výrazu, zápis do objektu pak provedeme operátorem přiřazení (viz také další sekce). Podobně jméno proměnné je platné počínaje deklarací, a konče pravou složenou závorkou, která ukončuje nejbližší uzavírající blok (složený příkaz nebo tělo funkce – podrobněji rozebereme dále). Například: { // zde x ještě není deklarováno int x; { int y; … // zde můžeme použít jak x tak y } // zde končí rozsah platnosti y … // zde již y není lze použít } // zde končí rozsah platnosti x U proměnných je tak syntakticky zaručeno, že jsou svázány s živým objektem – kdykoliv můžeme jméno proměnné použít, objekt, který tato proměnná pojmenovává, existuje. ### Výrazy Na úrovni jazyka C je základní jednotkou výpočtu «výraz» – podobně jako v jazyce Python můžeme výrazy tvořit induktivně. Jsou-li: • ‹e₁›, ‹e₂› … ‹eₙ› výrazy, • ‹var› jméno proměnné, • ‹lit› číselný literál (konstanta), existují také výrazy tvaru:¹ 1. ‹lit› (konstanta) je výraz, 2. ‹var› (jméno proměnné) je výraz, 3. použití aritmetického operátoru (binární v infixovém zápisu, unární v prefixovém): ◦ ‹e₁ + e₂›, ‹e₁ - e₂›, ◦ ‹e₁ * e₂›, ‹e₁ / e₂›, ‹e₁ % e₂› (modulo) ◦ unární mínus ‹-e₁›, 4. relační operátory: ◦ ‹e₁ == e₂› (rovnost), ‹e₁ != e₂› (nerovnost) ◦ ‹e₁ <= e₂›, ‹e₁ >= e₂›, ‹e₁ < e₂›, ‹e₁ > e₂› 5. bitové logické operace a posuvy: ◦ binární ‹e₁ & e₂› (and), ‹e₁ | e₂› (or), ‹e₁ ^ e₂› (xor), ◦ unární ‹~e₁› – bitová negace, ◦ bitové posuvy zapisujeme ‹e₁ >> e₂›, ‹e₁ << e₂›, 6. «operátory» přiřazení (pozor na změnu oproti jazyku Python – v jazyce C je přiřazení výraz, nikoliv příkaz): ◦ jednoduché ‹var = e₁›, ◦ složené ‹var += e₁›, ‹var -= e₁›, ◦ dále ‹var *= e₁›, ‹var /= e₁›, ‹var %= e₁›, ◦ s bitovým posuvem ‹var <<= e₁›, ‹var >>= e₂›, ◦ s bitovou operací ‹var &= e₁›, ‹var ^= e₁›, ‹var |= e₁›, 7. operátory zvýšení a snížení proměnné o jedničku: ◦ prefixové ‹++var›, ‹--var›, ◦ postfixové ‹var++›, ‹var--›, 8. operátor čárka, ‹e₁, e₂›, 9. booleovské logické operace: ◦ binární ‹e₁ && e₂› (and), ‹e₁ || e₂› (or), ◦ unární ‹!e₁›, ◦ ternární ‹e₁ ? e₂ : e₃›, ### Vyhodnocení výrazu Nyní víme, jak výrazy vypadají (jakou mají «syntaxi»), můžeme tedy přistoupit k otázce, co takové výrazy «znamenají» (jakou mají «sémantiku»). Všechny zde uvedené výrazy² popisují nějakou «hodnotu» a výraz samotný je návodem, jak tuto hodnotu získat. Vyhodnocení výrazu (provedení výpočtu tímto výrazem popsaného) budeme samozřejmě realizovat pomocí již zavedeného výpočetního stroje ‹tiny›. Abychom mohli výpočet skutečně provést, musíme určit registr, do kterého má být výsledek zapsán – budeme mluvit o «vyhodnocení výrazu E do registru R».³ 1. Výraz ‹lit› se vyhodnotí přímo na číselnou hodnotu zapsanou ve zdrojovém kódu. Například vyhodnocení výrazu ‹7› do registru ‹rv› se realizuje instrukcí ‹put 7 → rv›. 2. Výraz ‹var› se vyhodnotí na hodnotu, která je v momentě vyhodnocení tohoto výrazu uložena v objektu svázaném s proměnnou ‹var›. Prozatím uvažujeme pouze situace, kdy je objekt svázaný s ‹var› uložen přímo v registru. Je-li např. ‹var› uloženo v ‹l1›, vyhodnocení výrazu ‹var› do registru ‹rv› realizujeme instrukcí ‹copy l1 → rv›. 3. Uvažme nyní výraz tvaru ‹e₁ + e₂›. Víme, že ‹e₁› a ‹e₂› popisují nějaké hodnoty. Abychom mohli vyčíslit hodnotu ‹e₁ + e₂›, budeme nejprve potřebovat tyto hodnoty. Na to použijeme «dočasné registry» – vyhodnocení ‹e₁ + e₂› do ‹rv› bude vypadat takto: a. vyhodnoť ‹e₁› do registru ‹t₁›, b. vyhodnoť ‹e₂› do registru ‹t₂›, c. proveď ‹add t₁, t₂ → rv›. Musíme samozřejmě zabezpečit, že výpočet ‹e₂› nepřepíše registr ‹t₁› – jak přesně se toho dosáhne budeme zkoumat později.⁴ Analogicky se vypočtou ostatní aritmetické, bitové, atd. operátory (k hodnotám s/bez znaménka a operacím dělení se ještě vrátíme). 4. Výrazy tvaru ‹var = e₁› mají krom hodnoty také «vedlejší efekt» – zápis do objektu svázaného s proměnnou ‹var›. Jejich realizace vypadá takto – vyhodnocujeme do registru ‹rv›, objekt svázaný s ‹var› nechť žije v ‹l1›: a. vyhodnoť ‹e₁› do registru ‹rv› b. proveď ‹copy rv → l1›. Všimněte si, že hodnota ‹e₁› je zároveň hodnotou celého výrazu, a zůstává uložená v registru ‹rv›, jak bylo požadováno. 5. Složené přiřazení ‹var += e₁› je analogické, pouze je operaci ‹copy› předřazena příslušná aritmetická nebo logická operace:⁵ a. vyhodnoť ‹e₁› do registru ‹t₁› b. proveď ‹add t1, l1 → rv›, c. proveď ‹copy rv → l1›. Výrazy zvýšení a snížení o jedničku jsou analogické, liší se pouze ve výsledné hodnotě. Prefixové verze, ‹++var›, ‹--var› jsou pouze syntaktické zkratky pro ‹var += 1› resp. ‹var -= 1›, ale postfixové se liší – vyhodnocení ‹var++› do ‹rv› proběhne takto (‹var› je svázáno s ‹l1›): a. proveď ‹copy l1 → rv›, b. proveď ‹add l1, 1 → l1›. «Hodnota» výrazu ‹var++› je tedy «původní» hodnota ‹var›, předtím, než bylo provedeno zvýšení proměnné o jedničku. 6. Výraz ‹e₁, e₂› představuje „zapomenutí hodnoty“ výrazu ‹e₁› – výraz ‹e₁› je proveden pouze pro svoje vedlejší efekty (např. výše uvedené přiřazení). Vyhodnocení ‹e₁, e₂› do registru ‹rv› lze realizovat např. takto: a. vyhodnoť ‹e₁› do ‹rv›, b. vyhodnoť ‹e₂› do ‹rv›. 7. Zbývá zatím nejsložitější typ výrazů, a to jsou booleovské logické operace. XXX Uvažme nyní několik konkrétních příkladů: 1. ‹var + 1› se vypočte XXX ¹ S dalšími operátory se setkáme v pozdějších kapitolách. ² Toto tvrzení v jazyce C neplatí obecně pro všechny výrazy – existují i takové, které hodnotu nemají. ³ Tato konstrukce skutečně tvoří základ překladu výrazů v překladači jazyka C. Rozdílem je, že překladač pracuje s dočasnými registry mnohem hospodárněji, než naivní překlad zde popsaný – tím šetří nejen volné registry, ale i instrukce, které by hodnoty mezi registry zbytečně přesouvaly. Toto platí i pro velmi jednoduché překladače (např. také ‹tinycc›). ⁴ Prozatím si vystačíme s představou, že při překladu udržujeme množinu volných dočasných registrů (takových, které jsme zatím nepoužili, nebo kterých hodnotu už jsme upotřebili, a nebudeme ji v dalším výpočtu potřebovat). Je asi jasné, že ať začneme s jakkoliv velkou konečnou množinou dočasných registrů, při výpočtu dostatečně složitého výrazu nám musí dojít – jak se s tímto problémem vypořádat si ukážeme v příští kapitole. ⁵ Pro výrazy tvarů, které jsme zatím zavedli, je ‹var += e₁› ekvivalentní výrazu ‹var = var + e₁›. V obecném případě, kdy je na levé straně složeného přiřazení složitější výraz (a nikoliv pouze název proměnné), to už ale neplatí! ### Příkazy • výraz + středník • složený příkaz • ‹if›, ‹else› • ‹for› • ‹while› • ‹break› • ‹continue› # Podprogramy Tato kapitola zavádí důležitý nový koncept, totiž «podprogram» a s ním související nový typ výrazu – volání (použití) podprogramu. ### Definice Syntaxi «definice podprogramu» již zběžně známe: typ₀ jméno₀( typ₁ jméno₁, … ,typₙ jménoₙ ) /* C */ { příkaz₁ příkaz₂ … příkazₘ } Jednotlivé prvky zápisu mají tento význam: • ‹typ₀› je tzv. «návratový typ» – může být prozatím pouze jeden z již známých typů (‹int›, ‹unsigned›, …), • ‹jméno₀› je název zaváděného podprogramu, • ‹typ₁› … ‹typₙ› jsou typy jednotlivých «parametrů», • ‹jméno₁› … ‹jménoₙ› jsou «jména» parametrů, • ‹příkaz₁› … ‹příkazₘ› tvoří «tělo» podprogramu. ### Výrazy Hlavní nový typ výrazů je v této kapitole «použití podprogramu» nebo také «volání podprogramu» (možná znáte také jako „volání funkce“). Tento typ výrazu má následovný tvar: funcall ≡ jméno( expr₁, expr₂, …, exprₙ ) Předpokládejme, že ‹jméno› odpovídá definici z předchozí sekce. Výraz je pak typově správný v případě, že: • typ výrazu ‹expr₁› je možné implicitně převést na ‹typ₁›, • typ ‹expr₂› na typ ‹typ₂›, atd., až ‹exprₙ› na ‹typₙ›. Typ výrazu ‹funcall› jako celku je pak ‹typ₀› z definice výše. Vyhodnocení tohoto výrazu probíhá následovně: 1. Pro každý formální parametr je vytvořen objekt odpovídajícího typu; uvnitř těla podprogramu pak jména formálních parametrů pojmenovávají právě tyto objekty. 2. Výrazy ‹expr₁› až ‹exprₙ› jsou vyhodnoceny na hodnoty (v blíže neurčeném pořadí!) a každá takto získaná hodnota je zapsána do příslušného objektu z předchozího bodu. 3. Řízení je předáno tělu podprogramu (vzniká při tom mimo jiné nový rozsah platnosti jmen). 4. Hodnota celého výrazu ‹funcall› je pak určena prvním spuštěným příkazem ‹return› uvnitř těla. Tento příkaz zároveň předá řízení zpátky volajícímu podprogramu. ### Příkazy Nový příkaz ‹return expr;› má dva efekty: 1. vyhodnotí výraz ‹expr› a jeho hodnotu «vrátí» volajícímu (viz předchozí podsekce), 2. ukončí vykonávání podprogramu a předá řízení volajícímu. # Adresy a ukazatele Tato kapitola přidává ukazatele a (TODO!) operátor přetypování. ### Definice V definici podprogramu umožníme, aby se na místě návratového typu objevilo klíčové slovo ‹void›, které značí, že výsledek vyhodnocení podprogramu «není hodnota». ### Hodnoty a typy V této kapitole přidáváme velmi důležitou novou třídu hodnot, a společně s ní příslušné typy. Je-li ‹T› libovolný typ, pak ‹T *› je typ „ukazatele na objekt typu ‹T›“. Hodnota typu ‹T *› je reprezentovaná celým číslem bez znaménka, které odpovídá «adrese», na které je uložen příslušný objekt.¹ Klíčové slovo ‹void› označuje (pseudo)typ ‹void›. Nejedná se o typ v běžném smyslu, protože neexistuje žádná hodnota typu ‹void›. Abychom odlišili „běžné“ typy (s existujícími hodnotami), zavedeme pojem «hodnotový typ». Typ ‹void› je tak prvním typem, který hodnotový není. Přesto, že nemůže existovat hodnota typu ‹void›, je možné napsat «výraz» tohoto typu. Takový výraz ale není možné ve většině případů použít jako podvýraz. Jediná místa, kde se «podvýraz» typu ‹void› objevit smí, jsou: • libovolný operand operátoru čárka (nezávisle), • ‹e₁› a ‹e₂› ve výrazu ‹ternary ≡ e₀ ? e₁ : e₂› – pak je typ výrazu ‹ternary› jako celku také ‹void›,² • ‹e₁› ve výrazu přetypování ‹( void ) e₁›. Je-li ‹expr› výraz typu ‹void›, může se také objevit v příkazu tvaru ‹expr;› (příkaz tvořený výrazem – v tomto případě se ovšem nejedná o podvýraz). ¹ To neznamená, že objekt je s touto adresou pevně svázán – pouze to, že kdykoliv může být objekt «sekvenčně pozorován», bude k nalezení na této adrese. ² Pravidla pro typy ‹e₁› a ‹e₂› zároveň vynucují, že musí být ‹void› oba nebo ani jeden. ### Výrazy Tato kapitola zavádí tři nové tvary výrazů. Abychom ale mohli tyto výrazy správně popsat, musíme nejprve upravit způsob, jakým uvažujeme o vyhodnocení výrazů a zavést několik nových pojmů. Některé výrazy je možné «vyhodnotit na objekt» – prozatím se jedná pouze o výrazy tvaru ‹jméno› kde ‹jméno› pojmenovává nějakou proměnnou.¹ Vyhodnotí-li se nějaký výraz na objekt, další postup závisí na «kontextu» v jakém se objevuje: 1. Většina podvýrazů tvoří «r-kontexty», tzn. takové, které očekávají hodnotu – např. operandy aritmetických nebo relačních operátorů, parametry předávané podprogramu, pravý operand operátoru přiřazení, atd. Je-li nějaký podvýraz vyhodnocen na objekt v «r-kontextu», je z tohoto objektu navíc «přečtena hodnota» a výsledkem výrazu je až tato hodnota. 2. Některé podvýrazy jsou ale «l-kontextem» a v takovém případě se vyhodnocení zastaví určením «objektu» a čtení hodnoty ze získaného objektu se «neprovede». Jedná se zejména o levý operand přiřazovacího operátoru (odtud také název «l-kontext»). Objektu získanému vyhodnocením výrazu se říká také «l-hodnota» (chceme-li pak zdůraznit, že mluvíme o „normálních“ «hodnotách» a nikoliv «objektech»/«l-hodnotách», můžeme použít také pojem «r-hodnota»). Nyní můžeme konečně přistoupit k popisu nových tvarů výrazů: 1. Výraz ‹*expr₁›, tzv. «dereferenci», lze použít pouze vyhodnotí-li se ‹expr₁› na «platný ukazatel» (jedná-li se o ukazatel neplatný, program je chybný a jeho chování není určeno), a vyhodnotí se na «objekt» (l-hodnotu), který je tímto ukazatelem popsán. Je-li výraz ‹expr₁› typu ‹T *›, je výraz ‹*expr₁› typu ‹T›. 2. Výraz ‹&expr₁› lze použít jen tehdy, vyhodnotí-li se ‹expr₁› na «objekt» (je l-hodnotou) a výsledkem je «ukazatel» na tento objekt. Unární operátor ‹&› se anglicky nazývá „address of“, nicméně jeho výsledkem není striktně vzato adresa.² Je-li výraz ‹expr₁› typu ‹T›, je výraz ‹&expr₁› typu ‹T *›. 3. ‹expr₁ = expr₂› (jedná se o zobecnění již zavedeného ‹var = expr₂›) lze použít, vyhodnotí-li se ‹expr₁› na objekt (tzn. ‹expr₁› popisuje l-hodnotu). Efektem tohoto výrazu je, že hodnota uložená v takto popsaném objektu se přepíše na hodnotu, kterou získáme vyhodnocením výrazu ‹expr₂›. ¹ Na rozdíl od jazyka C++ výrazy tvaru ‹var = e₁› ani tvaru ‹e₀ ? e₁ : e₂› nikdy objekt nepopisují (nejsou l-hodnotami). ² Tuto zkratku si můžeme dovolit pouze proto, že použití operátoru ‹&› donutí překladač „zafixovat“ pozorovatelnou adresu objektu – každé použití ‹&› na objekt musí vrátit stejnou hodnotu a každá dereference takto získaného ukazatele musí, po dobu jeho platnosti, popisovat tento objekt. ### Příkazy Příkaz ‹return› v definici podprogramu bez návratové hodnoty (návratový typ je ‹void›) píšeme ‹return;› – nesmí se zde zejména objevit výraz. # Pole Tato kapitola přináší «pole» – první složený typ, se kterým budeme v tomto kurzu pracovat. Speciální vlastností pole v jazyce C je, že neexistují «hodnoty» typu pole, pouze «objekty». Protože se jedná o složené objekty, budou sestávat z «podobjektů» – jednotlivých položek. Všechny podobjekty (položky) daného pole jsou stejného typu. ### Deklarace Pole vytvoříme podobně jako jiné objekty «deklarací proměnné». Krom objektu tak vznikne jméno, kterým můžeme takto vytvořený objekt odkázat. Deklarace pole má tento tvar: typ jméno[výraz]; Přitom ‹typ› může být libovolný dosud zavedený hodnotový typ (nemůže to tedy být pole, protože pole není hodnotový typ). # Struktury, zřetězený seznam Tato kapitola přináší novou třídu složených typů – struktury, neboli záznamové typy. ### Definice Definice struktury má tento tvar: struct jméno₀ { typ₁ jméno₁; typ₂ jméno₂; … typₙ jménoₙ; }; Každé jméno uvnitř definice (‹jméno₁› až ‹jménoₙ›) definuje «složku» struktury odpovídajícího typu.¹ Konečně ‹jméno₀› je jménem struktury (pozor, není totéž jako jméno typu!). Definujeme-li strukturu ‹foo›, na místech, kde je očekáván typ, můžeme psát ‹struct foo›. ### Výrazy Se strukturami souvisí také dva nové tvary výrazů: • ‹expr₁.jméno› – přístup ke složce; typ výrazu ‹expr₁› musí být struktura, která má složku pojmenovanou ‹jméno›. Vyhodnotí-li se ‹expr₁› na objekt, výraz jako celek pojmenovává příslušný podobjekt (a může tedy stát na levé straně přiřazení). • ‹expr₁->jméno› – nepřímý přístup ke složce skrze ukazatel – podobně jako dereference, vstupní podmínkou je, že ‹expr₁› je «platný» ukazatel. Výsledkem je vždy objekt (l-hodnota). ¹ Složky můžeme sdružovat podle typu, nicméně pozor na ukazatele – stejně jako u lokálních proměnných, deklarace položek ‹int *x, y;› zavádí položku ‹x› typu ‹int *› a položku typu ‹y› typu ‹int›. Dvě položky typu ‹int *› zapisujeme jako ‹int *x, *y;›.