: title : PB111 Nízkoúrovňové programování : authors : P. Ročkai & A. Matoušek : doctype : workbook : typing : plain : lang : cs : toc : yes # A. Pravidla a organizace Tento dokument je sbírkou cvičení a komentovaných příkladů zdrojového kódu. Každá kapitola odpovídá jednomu týdnu semestru a tedy jednomu cvičení. Cvičení v prvním týdnu semestru („nulté“) je určeno k seznámení se s výukovým prostředím, studijními materiály a základními nástroji ekosystému. Každá část sbírky (zejména tedy všechny ukázky a příklady) jsou také k dispozici jako samostatné soubory, které můžete upravovat a spouštět. Této rozdělené verzi sbírky říkáme «zdrojový balík». Aktuální verzi¹ (ve všech variantách) můžete získat dvěma způsoby: 1. Ve «studijních materiálech²» předmětu v ISu – soubory PDF ve složce ‹text›, zdrojový balík ve složkách ‹00› (organizační informace), ‹01› až ‹12› (jednotlivé kapitoly = týdny semestru), dále ‹s1› až ‹s3› (sady úloh) a konečně ve složce ‹sol› vzorová řešení. Doporučujeme soubory stahovat dávkově pomocí volby „stáhnout jako ZIP“. 2. Po přihlášení na studentský server ‹aisa› (buď za pomoci ‹ssh› nebo ‹putty›) zadáním příkazu ‹pb111 update›. Všechny výše uvedené složky pak naleznete ve složce ‹~/pb111›. Tato kapitola (složka) dále obsahuje «závazná» pravidla a organizační pokyny. Než budete pokračovat, pozorně si je prosím přečtěte. Pro komunikaci s organizátory kurzu slouží «diskusní fórum» v ISu (více informací naleznete v části T.1). Nepište prosím organizátorům ani cvičícím maily ohledně předmětu, nejste-li k tomu specificky vyzváni. S žádostmi o výjimky ze studijních povinností, omluvenkami, atp., se obracejte vždy na studijní oddělení. ¹ Studijní materiály budeme tento semestr doplňovat průběžně. Než začnete pracovat na přípravách nebo příkladech ze sady, vždy se prosím ujistěte, že máte jejich aktuální verzi. Zadání příprav lze považovat za finální počínaje půlnocí na pondělí odpovídajícího týdne, sady podobně půlnocí na první pondělí odpovídajícího bloku. Pro první týden tedy 17.2.2025 00:00 a první sadu 24.2.2025 00:00. ² ‹https://is.muni.cz/auth/el/fi/jaro2025/PB111/um/› ## Přehled Tento předmět sestává z cvičení, sad domácích úloh a závěrečného praktického testu (zkoušky). Protože se jedná o „programovací“ předmět, většina práce v předmětu – a tedy i jeho hodnocení – se bude zaměřovat na praktické programování. Je důležité, abyste programovali co možná nejvíce, ideálně každý den, ale minimálně několikrát každý týden. K tomu Vám budou sloužit příklady v této sbírce a domácí úlohy, kterých budou za semestr 3 sady, a budou znatelně většího rozsahu (maximálně malé stovky řádků). V obou případech bude v průběhu semestru stoupat náročnost – je tedy důležité, abyste drželi krok a práci neodkládali na poslední chvíli. Protože programování je těžké, bude i tento kurz těžký – je zcela nezbytné vložit do něj odpovídající úsilí. Doufáme, že kurz úspěšně absolvujete, a co je důležitější, že se v něm toho naučíte co nejvíce. Je ale nutno podotknout, že i přes svou náročnost je tento kurz jen malým krokem na dlouhé cestě. ### Probíraná témata Předmět je rozdělen do 4 bloků (čtvrtý blok patří do zkouškového období). Do každého bloku v semestru patří 4 kapitoly (témata) a jim odpovídající 4 cvičení. │ bl. │ │ téma │ ├─────│────▻┼◅──────────────────────────────────────│ │ 1 │ 1. │ výpočetní stroj │ │ │ 2. │ lokální proměnné, řízení toku │ │ │ 3. │ podprogram │ │ │ 4. │ adresa, ukazatel │ │┄┄┄┄┄│┄┄┄┄┄│┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄│ │ 2 │ 5. │ pole, index, ukazatel do pole │ │ │ 6. │ struktura, zřetězený seznam │ │ │ 7. │ základy alokace paměti │ │ │ 8. │ TBD │ │┄┄┄┄┄│┄┄┄┄┄│┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄│ │ 3 │ 9. │ dynamické pole │ │ │ 10. │ slovník a množina │ │ │ 11. │ správa paměti │ │ │ 12. │ TBD │ ### Organizace sbírky V následujících sekcích naleznete detailnější informace a «závazná» pravidla kurzu: doporučujeme Vám, abyste se s nimi důkladně seznámili.¹ Zbytek sbírky je pak rozdělen na části, které odpovídají jednotlivým týdnům semestru. «Důležité:» během prvního týdne semestru už budete řešit přípravy z první kapitoly, přestože první cvičení je ve až v týdnu druhém. Nulté cvičení je volitelné a není nijak hodnoceno. Kapitoly jsou číslovány podle témat z předchozí tabulky: ve druhém týdnu semestru se tedy «ve cvičení» budeme zabývat tématy, ke kterým jste v prvním týdnu vypracovali a odevzdali přípravy. ¹ Pravidla jsou velmi podobná těm v kurzu IB111, ale přesto si je pozorně přečtěte. ### Plán semestru Tento kurz vyžaduje značnou aktivitu během semestru. V této sekci naleznete přehled důležitých událostí formou kalendáře. Jednotlivé události jsou značeny takto (bližší informace ke každé naleznete v následujících odstavcích tohoto úvodu): • „#X“ – číslo týdne v semestru, • „cv0“ – tento týden běží „nulté“ cvičení (kapitola B), • „cv1“ – tento týden probíhají cvičení ke kapitole 1, • „X/v“ – mezivýsledek verity testů příprav ke kapitole X, • „X/p“ – poslední termín odevzdání příprav ke kapitole X, • „sX/Y“ – Yté kolo verity testů k sadě X, • „test“ – termín programovacího testu. Nejdůležitější události jsou zvýrazněny: termíny odevzdání příprav a poslední termín odevzdání úloh ze sad (obojí vždy o 23:59 uvedeného dne). │ únor │ │┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│ │      │   Po  │   Út  │   St  │   Čt  │   Pá  │   So  │   Ne  │ ├─────▻│◅──────│◅──────│◅──────│◅──────│◅──────│◅──────│◅──────│ │ #1 │ 17 │ 18 │ 19 │ 20 │ 21 │ 22 │ 23 │ │ cv 0 │   │   │   │ 01/v │   │«01/p» │   │ │┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│ │ #2 │ 24 │ 25 │ 26 │ 27 │ 28 │   │   │ │ cv 1 │ s1/1 │   │ s1/2 │ 02/v │ s1/3 │   │   │ │┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│ │ březen │ │┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│ │      │   Po  │   Út  │   St  │   Čt  │   Pá  │   So  │   Ne  │ ├─────▻│◅──────│◅──────│◅──────│◅──────│◅──────│◅──────│◅──────│ │ #2 │   │   │   │   │   │ 1 │ 2 │ │ │   │   │   │   │   │«02/p» │   │ │┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│ │ #3 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ │ cv 2 │ s1/4 │   │ s1/5 │ 03/v │ s1/6 │«03/p» │   │ │┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│ │ #4 │ 10 │ 11 │ 12 │ 13 │ 14 │ 15 │ 16 │ │ cv 3 │ s1/7 │   │ s1/8 │ 04/v │ s1/9 │«04/p» │   │ │┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│ │ #5 │ 17 │ 18 │ 19 │ 20 │ 21 │ 22 │ 23 │ │ cv 4 │ s1/10 │   │ s1/11 │ 05/v │«s1/12»│«05/p» │   │ │┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│ │ #6 │ 24 │ 25 │ 26 │ 27 │ 28 │ 29 │ 30 │ │ cv 5 │ s2/1 │   │ s2/2 │ 06/v │ s2/3 │«06/p» │   │ │┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│ │ #7 │ 31 │   │   │   │   │   │   │ │ cv 6 │ s2/4 │   │   │   │   │   │   │ │┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│ │ duben │ │┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│ │      │   Po  │   Út  │   St  │   Čt  │   Pá  │   So  │   Ne  │ ├─────▻│◅──────│◅──────│◅──────│◅──────│◅──────│◅──────│◅──────│ │ #7 │   │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ │ │   │   │ s2/5 │ 07/v │ s2/6 │«07/p» │   │ │┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│ │ #8 │ 7 │ 8 │ 9 │ 10 │ 11 │ 12 │ 13 │ │ cv 7 │ s2/7 │   │ s2/8 │ 08/v │ s2/9 │«08/p» │   │ │┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│ │ #9 │ 14 │ 15 │ 16 │ 17 │ 18 │ 19 │ 20 │ │ cv 8 │ s2/10 │   │ s2/11 │ 09/v │«s2/12»│«09/p» │   │ │┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│ │ #10 │ 21 │ 22 │ 23 │ 24 │ 25 │ 26 │ 27 │ │ cv 9 │ s3/1 │   │ s3/2 │ 10/v │ s3/3 │«10/p» │   │ │┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│ │ #11 │ 28 │ 29 │ 30 │   │   │   │   │ │ cv10 │ s3/4 │   │ s3/5 │   │   │   │   │ │┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│ │ květen │ │┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│ │      │   Po  │   Út  │   St  │   Čt  │   Pá  │   So  │   Ne  │ ├─────▻│◅──────│◅──────│◅──────│◅──────│◅──────│◅──────│◅──────│ │ #11 │   │   │   │ 1 sv │ 2 │ 3 │ 4 │ │ │   │   │   │ 11/v │ s3/6 │«11/p» │   │ │┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│ │ #12 │ 5 │ 6 │ 7 │ 8 sv │ 9 │ 10 │ 11 │ │ cv11 │ s3/7 │   │ s3/8 │ 12/v │ s3/9 │«12/p» │   │ │┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│ │ #13 │ 12 │ 13 │ 14 │ 15 │ 16 │ 17 │ 18 │ │ cv12 │ s3/10 │   │ s3/11 │   │«s3/12»│   │   │ │┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│ │ │ 19 │ 20 │ 21 │ 22 │ 23 │ 24 │ 25 │ │ │   │   │   │   │   │   │   │ │┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│ │ │ 26 │ 27 │ 28 │ 29 │ 30 │ 31 │   │ │ │   │   │   │   │   │   │   │ │┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│┄┄┄┄┄┄┄│ ## Hodnocení Abyste předmět úspěšně ukončili, musíte v «každém bloku¹» získat «50 bodů». Žádné další požadavky nemáme. Výsledná známka závisí na celkovém součtu bodů (splníte-li potřebných 4×50 bodů, automaticky získáte známku alespoň E). Hodnota ve sloupci „předběžné minimum“ danou známku zaručuje – na konci semestru se hranice ještě mohou posunout směrem dolů tak, aby výsledná stupnice přibližně odpovídala očekávané distribuci dle ECTS.² │ známka │ předběžné minimum │ po vyhodnocení semestru │ ├─────────│───────────────────│─────────────────────────┤ │ A │ 360 │ 90. percentil + 60 │ │ B │ 320 │ 65. percentil + 60 │ │ C │ 280 │ 35. percentil + 60 │ │ D │ 240 │ 10. percentil + 60 │ │ E │ 200 │ 200 │ Body lze získat mnoha různými způsoby (přesnější podmínky naleznete v následujících sekcích této kapitoly). V blocích 1-3 (probíhají během semestru) jsou to: • za každou úspěšně odevzdanou přípravu «1» bod (max. 6 bodů každý týden, nebo «24/blok»), • za každou přípravu, která projde „verity“ testy navíc další «1» bod (max. 6 bodů každý týden, nebo «24/blok»), • za účast³ na cvičení získáte 3 body (max. tedy «12/blok»), • za aktivitu ve cvičení 3 body (max. tedy «12/blok»). Za přípravy a cvičení lze tedy získat teoretické maximum «72» bodů. Dále můžete získat: • «7» bodů za úspěšně vyřešený příklad ze sady domácích úloh (maximálně 4 příklady, celkem tedy až «28/blok»). Konečně blok 4, který patří do zkouškového období, nemá ani cvičení ani sadu domácích úloh. Body získáte účastí na programovacím testu: • «20» bodů za každý zkouškový příklad (5 příkladů, maximálně tedy celkem «100/blok»). ¹ Máte-li předmět ukončen zápočtem, čtvrtý blok a tedy ani závěrečný test pro Vás není relevantní. Platí požadavek na 3×50 bodů z bloků v semestru. ² Percentil budeme počítat z bodů v semestru (první tři bloky) a bude brát do úvahy všechny studenty, bez ohledu na ukončení, kteří splnili tyto tři bloky (tzn. mají potřebné minimum 3×50 bodů). ³ V případě, že jste «řádně omluveni» v ISu, nebo Vaše cvičení «odpadlo» (např. padlo na státní svátek), můžete body za účast získat buď náhradou v jiné skupině (pro státní svátky dostanete instrukce mailem, individuální případy si domluvte s cvičícími obou dotčených skupin). Nemůžete-li účast nahradit takto, «domluvte se» se svým cvičícím (v tomto případě lze i mailem) na vypracování 3 rozšířených příkladů ze sbírky (přesné detaily Vám sdělí cvičící podle konkrétní situace). Neomluvenou neúčast lze nahrazovat «pouze» v jiné skupině a to max. 1–2× za semestr. ## Přípravy Jak již bylo zmíněno, chcete-li se naučit programovat, musíte programování věnovat nemalé množství času, a navíc musí být tento čas rozložen do delších období – semestr nelze v žádném případě doběhnout tím, že budete týden programovat 12 hodin denně, i když to možná pokryje potřebný počet hodin. Proto od Vás budeme chtít, abyste každý týden odevzdali několik vyřešených příkladů z této sbírky. Tento požadavek má ještě jeden důvod: chceme, abyste vždy v době cvičení už měli látku každý samostatně nastudovanou, abychom mohli řešit zajímavé problémy, nikoliv opakovat základní pojmy. Také Vás prosíme, abyste příklady, které plánujete odevzdat, řešili vždy samostatně: případnou zakázanou spolupráci budeme trestat (viz také konec této kapitoly). ### Odevzdání Každý příklad obsahuje základní sadu testů. To, že Vám tyto testy prochází, je jediné kritérium pro zisk základních bodů za odevzdání příprav. Poté, co příklady odevzdáte, budou «tytéž testy» na Vašem řešení automaticky spuštěny, a jejich výsledek Vám bude zapsán do poznámkového bloku. Smyslem tohoto opatření je zamezit případům, kdy omylem odevzdáte nesprávné, nebo jinak nevyhovující řešení, aniž byste o tom věděli. Velmi silně Vám proto doporučujeme odevzdávat s určitým předstihem, abyste případné nesrovnalosti měli ještě čas vyřešit. Krom základních („sanity“) testů pak ve čtvrtek o 23:59 a znovu v sobotu o 23:59 (těsně po konci odevzdávání) spustíme «rozšířenou» sadu testů („verity“). Za každý odevzdaný příklad, který splnil «základní» („sanity“) testy získáváte jeden bod. Za příklad, který navíc splnil «rozšířené» testy získáte další bod (tzn. celkem 2 body). Výsledky testů naleznete v «poznámkovém bloku» v informačním systému. Příklady můžete odevzdávat: 1. do «odevzdávárny» s názvem ‹NN› v ISu (např. ‹01›), 2. příkazem ‹pb111 submit› ve složce ‹~/pb111/NN›. Podrobnější instrukce naleznete v kapitole T (technické informace, soubory ‹00/t*›). Termíny pro odevzdání příprav k jednotlivým kapitolám jsou shrnuty v přehledovém kalendáři v části A.1 takto: • „01/v“ – předběžné (čtvrteční) verity testy pro příklady z první kapitoly, • „01/p“ – poslední (sobotní) termín odevzdání příprav z 1. kapitoly, • analogicky pro další kapitoly. ## Cvičení Těžiště tohoto předmětu je jednoznačně v samostatné domácí práci – učit se programovat znamená zejména hodně programovat. Společná cvičení sice nemohou tuto práci nahradit, mohou Vám ale přesto v lecčem pomoct. Smyslem cvičení je: 1. analyzovat problémy, na které jste při samostatné domácí práci narazili, a zejména prodiskutovat, jak je vyřešit, 2. řešit programátorské problémy společně (s cvičícím, ve dvojici, ve skupině) – nahlédnout jak o programech a programování uvažují ostatní a užitečné prvky si osvojit. Cvičení je rozděleno na dva podobně dlouhé segmenty, které odpovídají těmto bodům. První část probíhá přibližně takto: • cvičící vybere ty z Vámi odevzdaných příprav, které se mu zdají něčím zajímavé – ať už v pozitivním, nebo negativním smyslu, ◦ řešení bude «anonymně» promítat na plátno a u každého otevře diskusi o tom, čím je zajímavé; ◦ Vaším úkolem je aktivně se do této diskuse zapojit (můžete se například ptát proč je daná věc dobře nebo špatně a jak by se udělala lépe, vyjádřit svůj názor, odpovídat na dotazy cvičícího), ◦ k promítnutému řešení se můžete přihlásit a ostatním přiblížit, proč je napsané tak jak je, nebo klidně i rozporovat případnou kritiku (není to ale vůbec nutné), • na Vaši žádost lze ve cvičení analogicky probrat «neúšpěšná» řešení příkladů (a to jak příprav, tak příkladů z uzavřených sad). Druhá část cvičení je variabilnější, ale bude se vždy točit kolem bodů za aktivitu (každý týden můžete za aktivitu získat maximálně 3 body). Ve čtvrtém, osmém a dvanáctém týdnu proběhnou „vnitrosemestrálky“ kde budete řešit samostatně dva příklady ze sbírky, bez možnosti hledat na internetu – tak, jak to bude na závěrečném testu; každé úspěšné řešení (tzn. takové, které splní verity testy) získá 3 body za aktivitu pro daný týden (celkem tedy lze za příklady získat 6 bodů). Navíc dostanete 3 teoretické otázky, po jednom bodu, celkově lze tedy během vnitrosemestrálky získat až 9 bodů (počítají se jako aktivita, tzn. platí celkový limit 12/blok). V ostatních týdnech budete ve druhém segmentu kombinovat různé aktivity, které budou postavené na příkladech typu ‹r› z aktuální kapitoly (které konkrétní příklady budete ve cvičení řešit vybere cvičící, může ale samozřejmě vzít v potaz Vaše preference): 1. Můžete se přihlásit k řešení příkladu na plátně, kdy primárně vymýšlíte řešení Vy, ale zbytek třídy Vám bude podle potřeby radit, nebo se ptát co/jak/proč se v řešení děje. U jednodušších příkladů se od Vás bude také očekávat, že jako součást řešení doplníte testy. 2. Cvičící Vám může zadat práci ve dvojicích – první dvojice, která se dopracuje k funkčnímu řešení získá možnost své řešení předvést zbytku třídy – vysvětlit jak a proč funguje, odpovědět na případné dotazy, opravit chyby, které v řešení publikum najde, atp. – a získat tak body za aktivitu. Získané 3 body budou rozděleny rovným dílem mezi vítězné řešitele. 3. příklad můžete také řešit společně jako skupina – takto vymyšlený kód bude zapisovat cvičící (body za aktivitu se v tomto případě neudělují). ## Sady domácích úloh Ke každému bloku patří sada 4–6 domácích úloh. Na úspěšné odevzdání každé domácí úlohy budete mít 12 pokusů rozložených do 4 týdnů odpovídajícího bloku cvičení. Odevzdávání bude otevřeno vždy v 0:00 prvního dne bloku (tzn. 24h před prvním spuštěním verity testů). Termíny odevzdání (vyhodnocení verity testů) jsou vždy v pondělí, středu a pátek v 23:59 – vyznačeno jako s1/1–12, s2/1–12 a s3/1–12 v přehledovém kalendáři v části A.1. ### Odevzdávání Součástí každého zadání je jeden zdrojový soubor (kostra), do kterého své řešení vepíšete. Vypracované příklady lze pak odevzdávat stejně jako přípravy: 1. do «odevzdávárny» s názvem ‹sN_úkol› v ISu (např. ‹s1_a_queens›), 2. příkazem ‹pb111 submit sN_úkol› ve složce ‹~/pb111/sN›, např. ‹pb111 submit s1_a_queens›. Podrobnější instrukce naleznete opět v kapitole T. ### Vyhodnocení Vyhodnocení Vašich řešení probíhá ve třech fázích, a s každou z nich je spjata sada automatických testů. Tyto sady jsou: • „syntax“ – kontroluje, že odevzdaný program je syntakticky správně, lze jej přeložit a prochází základními statickými kontrolami, • „sanity“ – kontroluje, že odevzdaný program se chová „rozumně“ na jednoduchých případech vstupu; tyto testy jsou rozsahem a stylem podobné těm, které máte přiložené k příkladům ve cvičení, • „verity“ – důkladně kontrolují správnost řešení, včetně složitých vstupů a okrajových případů a kontroly paměťových chyb. Fáze na sebe navazují v tom smyslu, že nesplníte-li testy v některé fázi, žádná další se už (pro dané odevzdání) nespustí. Pro splnění domácí úlohy je klíčová fáze „verity“, za kterou jsou Vám uděleny body. Časový plán vyhodnocení fází je následovný: • kontrola „syntax“ se provede obratem (do cca 5 minut od odevzdání), • kontrola „sanity“ každých 6 hodin počínaje půlnocí (tzn. 0:00, 6:00, 12:00, 18:00), • kontrola „verity“ se provede v pondělí, středu a pátek ve 23:59 (dle tabulky uvedené výše). Vyhodnoceno je vždy pouze nejnovější odevzdání, a každé odevzdání je vyhodnoceno v každé fázi nejvýše jednou. Výsledky naleznete v poznámkových blocích v ISu (každá úloha v samostatném bloku), případně je získáte příkazem ‹pb111 status›. Za každý domácí úkol, ve kterém Vaše odevzdání v příslušném termínu splní testy „verity“, získáte 7 bodů (strop bodů za úkoly je 28 za blok, počítají se tedy maximálně čtyři úspěšně vyřešené úkoly). ### Neúspěšná řešení Příklady, které se Vám nepodaří vyřešit kompletně (tzn. tak, aby na nich uspěla kontrola „verity“) nebudeme hodnotit. Nicméně může nastat situace, kdy byste potřebovali na „téměř hotové“ řešení zpětnou vazbu, např. proto, že se Vám nepodařilo zjistit, proč nefunguje. Taková řešení můžou být předmětem společné analýzy ve cvičení, v podobném duchu jako probíhá rozprava kolem odevzdaných příprav (samozřejmě až poté, co pro danou sadu skončí odevzdávání). Máte-li zájem takto rozebrat své řešení, domluvte se, ideálně s předstihem, se svým cvičícím. To, že jste autorem, zůstává mezi cvičícím a Vámi – Vaši spolužáci to nemusí vědět (ke kódu se samozřejmě můžete v rámci debaty přihlásit, uznáte-li to za vhodné). Stejná pravidla platí také pro nedořešené přípravy (musíte je ale odevzdat). Tento mechanismus je omezen prostorem ve cvičení – nemůžeme zaručit, že v případě velkého zájmu dojde na všechny (v takovém případě cvičící vybere ta řešení, která bude považovat za přínosnější pro skupinu – je tedy možné, že i když se na Vaše konkrétní řešení nedostane, budete ve cvičení analyzovat podobný problém v řešení někoho jiného). ## Závěrečný programovací test Zkouškové období tvoří pomyslný 4. blok a platí zde stejné kritérium jako pro všechny ostatní bloky: musíte získat alespoň 50 bodů. Závěrečný test: • proběhne v počítačové učebně bez přístupu k internetu nebo vlastním materiálům, • k dispozici bude tato sbírka (bez vzorových řešení příkladů typu ‹e› a ‹r›) a skripta, • budete moct používat textový editor nebo vývojové prostředí VS Code, standardní překladače jazyka C a odpovídající nástroje, překladač ‹tiny› a odpovídající virtuální stroj. Na vypracování praktické části budete mít 4 hodiny čistého času, a bude sestávat z pěti příkladů, které budou hodnoceny automatickými testy, s maximálním ziskem 100 bodů. Příklady jsou hodnoceny binárně (tzn. příklad je uznán za plný počet bodů, nebo uznán není). Příklady budou na stejné úrovni obtížnosti jako příklady typu ‹p›/‹r›/‹v› ze sbírky. Během zkoušky můžete kdykoliv odevzdat (na počet odevzdání není žádný konkrétní limit) a vždy dostanete zpět výsledek testů syntaxe a sanity. Součástí zadání bude navíc soubor ‹tokens.txt›, kde naleznete 3 kódy. Každý z nich lze použít nejvýše jednou (vložením do komentáře do jednoho z příkladů), a každé použití kódu odhalí výsledek verity testu pro ten soubor, do kterého byl vložen. Toto se projeví pouze při prvním odevzdání s vloženým kódem, v dalších odevzdáních bude tento kód ignorován (bez ohledu na soubor, do kterého bude vložen). ### Vnitrosemestrálky V posledním týdnu každého bloku, tedy • cvičení 4 (17.-21. března), • cvičení 8 (14.-18. dubna), • cvičení 12 (12.-16. května), proběhne v rámci cvičení programovací test na 60 minut. Tyto testy budou probíhat za stejných podmínek, jako výše popsaný závěrečný test (slouží tedy mimo jiné jako příprava na něj). Řešit budete vždy ale pouze dva příklady, přitom za každý můžete získat 3 body, které se počítají jako body za aktivitu v tomto cvičení. Navíc dostanete 3 teoretické otázky, každou za 1 bod. Konečně dostanete také 1 token pro odhalení verity testu. ¹ Může se stát, že termíny budeme z technických nebo organizačních důvodů posunout na jiný den nebo hodinu. V takovém případě Vám samozřejmě změnu s dostatečným předstihem oznámíme. ## Opisování Na všech zadaných problémech pracujte prosím zcela samostatně – toto se týká jak příkladů ze sbírky, které budete odevzdávat, tak domácích úloh ze sad. To samozřejmě neznamená, že Vám zakazujeme společně studovat a vzájemně si pomáhat látku pochopit: k tomuto účelu můžete využít všechny zbývající příklady ve sbírce (tedy ty, které nebude ani jeden z Vás odevzdávat), a samozřejmě nepřeberné množství příkladů a cvičení, které jsou k dispozici online. Příklady, které odevzdáváte, slouží ke kontrole, že látce skutečně rozumíte, a že dokážete nastudované principy prakticky aplikovat. Tato kontrola je pro Váš pokrok naprosto klíčová – je velice snadné získat pasivním studiem (čtením, posloucháním přednášek, studiem již vypracovaných příkladů) pocit, že něčemu rozumíte. Dokud ale sami nenapíšete na dané téma několik programů, jedná se pravděpodobně skutečně pouze o pocit. Abyste nebyli ve zbytečném pokušení kontroly obcházet, nedovolenou spolupráci budeme relativně přísně trestat. Za každý prohřešek Vám bude strženo «v každé instanci» (jeden týden příprav se počítá jako jedna instance, příklady ze sad se počítají každý samostatně): • 1/2 bodů získaných (ze všech příprav v dotčeném týdnu, nebo za jednotlivý příklad ze sady), • 10 bodů z hodnocení bloku, do kterého opsaný příklad patří, • 10 bodů (navíc k předchozím 10) z celkového hodnocení. Opíšete-li tedy například 2 přípravy ve druhém týdnu a: • Váš celkový zisk za přípravy v tomto týdnu je 4,5 bodu, • Váš celkový zisk za první blok je 60 bodů, jste «automaticky hodnoceni známkou X» (60 - 2,25 - 10 je méně než potřebných 50 bodů). Podobně s příkladem z první sady (60 - 5 - 10), atd. Máte-li v bloku bodů dostatek (např. 80 - 5 - 10 ≥ 50), ve studiu předmětu pokračujete, ale započte se Vám ještě navíc penalizace 10 bodů do celkové známky. Přestává pro Vás proto platit pravidlo, že 4 splněné bloky jsou automaticky E nebo lepší. V situaci, kdy: • za bloky máte před penalizací 67, 52, 51, 54, • v prvním bloku jste opsali domácí úkol, budete penalizováni: • v prvním bloku 10 + 5, tzn. bodové zisky za bloky budou efektivně 52, 52, 51, 54, • v celkovém hodnocení 10, tzn. celkový zisk 52 + 52 + 51 + 54 - 10 = 199, a budete tedy hodnoceni známkou «F». To, jestli jste příklad řešili společně, nebo jej někdo vyřešil samostatně, a poté poskytl své řešení někomu dalšímu, není pro účely kontroly opisování důležité. Všechny „verze“ řešení odvozené ze společného základu budou penalizovány stejně. Taktéž «zveřejnění řešení» budeme chápat jako pokus o podvod, a budeme jej trestat, bez ohledu na to, jestli někdo stejné řešení odevzdá, nebo nikoliv. Podotýkáme ještě, že kontrola opisování «nespadá» do desetidenní lhůty pro hodnocení průběžných kontrol. Budeme se sice snažit opisování kontrolovat co nejdříve, ale odevzdáte-li opsaný příklad, můžete být bodově penalizováni kdykoliv (tedy i dodatečně, a to až do konce zkouškového období). # B. Úvod Účelem tohoto kurzu je seznámit Vás s tím, jak probíhá výpočet na úrovni procesoru, a jaký je vztah mezi tímto nízkoúrovňovým výpočetním modelem a tzv. jazyky vyšší úrovně. Abychom mohli tento vztah zkoumat, musíme porozumět jak 1. onomu vyššímu jazyku (v tomto kurzu to bude ten nejnižší z nich – jazyk C – abychom co nejvíce zmenšili vzdálenost, kterou musíme překlenout) tak 2. výpočetnímu stroji (který odpovídá procesoru a paměti), který bude výpočty našich programů realizovat. Z předchozího již znáte jiný vyšší programovací jazyk, Python – ten použijeme jako odrazový bod. Potřebovat budete samozřejmě pouze ty části jazyka, které znáte z kurzu IB111. ## Programovací jazyk Podobně jako v kurzu IB111, budeme používat omezenou podmnožinu „skutečného“ (prakticky běžně používaného) programovacího jazyka – v tomto kurzu to bude podmnožina jazyka C. Každá kapitola, počínaje tou druhou, bude obsahovat popis všech prvků jazyka C, které musíte v dané kapitole zvládnout.¹ V nulté a první kapitole se budeme zabývat pouze strojovým kódem a jazykem symbolických adres – budeme tedy programovat přímo výpočetní stroj, se zcela minimální abstrakcí. (Omezený) jazyk C se objeví teprve ve 2. kapitole. ¹ Žádné jiné v kurzu nebudou k dispozici, máte tedy zaručeno, že dokážete přečíst každý program, který k dané kapitole patří – ať už z přednášky, z této sbírky, nebo kód svých spolužáků, který uvidíte ve cvičení. ## Výpočetní stroj Stav výpočetního stroje, se kterým budeme v tomto předmětu pracovat, je velmi jednoduchý. Skládá se z: 1. šestnácti registrů, každý o šířce 16 bitů: ◦ registr ‹rv› (return value), ◦ registry ‹l1› až ‹l7› (local), ◦ registry ‹t1› až ‹t6› (temporary), ◦ registry ‹bp› a ‹sp›, 2. speciálního 16bitového registru ‹pc› (program counter), 3. 64 KiB paměti adresované po slabikách (bajtech) – adresa je tedy 16bitové celé číslo (bez znaménka), které přesně určuje právě jednu paměťovou buňku, přitom každá taková buňka obsahuje celé číslo v rozsahu 0 až 255. Sémanticky speciální jsou pouze registry ‹pc› a ‹sp› – všechny ostatní jsou z pohledu stroje ekvivalentní a jejich jména nemají pro samotný výpočet žádný speciální význam – jedná se pouze o konvenci, která nám usnadní čtení (a psaní) programů. Výpočet stroje probíhá takto: 1. z adresy uložené v registru ‹pc› se načtou dvě šestnáctibitová slova – ‹hi› z adresy ‹pc› a ‹lo› z adresy ‹pc + 2› – která kódují jednu instrukci, 2. instrukce je strojem dekódována a provedena: ◦ slovo ‹hi› kóduje operaci (vyšší slabika), cílový registr a první registrový operand, ◦ slovo ‹lo› kóduje přímý (immediate) operand, nebo druhý registrový operand (v nejvyšší půlslabice), ◦ provede se efekt instrukce (tento efekt samozřejmě závisí jak na operaci, tak na operandech) – obvykle je součástí tohoto efektu změna hodnoty uložené v registru ‹pc›, 3. nebyl-li výpočet zastaven, pokračuje bodem 1. Registry jsou očíslovány v pořadí uvedeném výše, totiž ‹rv› je registr číslo 0 a ‹sp› je registr číslo 15. Je vidět, že číslo registru lze zakódovat do jedné půlslabiky (registr ‹pc› operandem být nemůže). Následuje výčet všech operací, které umí stroj provést. Nebudeme všechny operace potřebovat hned, a nebudeme se tedy zatím ani podrobněji zabývat jejich sémantikou – tu si rozebereme vždy na začátku kapitoly, v níž začnou být tyto operace relevantní. 1. speciální operace: ◦ práce se zásobníkem (‹push›, ‹pop›), ◦ nastavení registru na konstantu (‹put›), ◦ nastavení registru na hodnotu z jiného registru (‹copy›), ◦ znaménkové rozšíření bajtu (‹sext›), 2. operace pro práci s pamětí: ◦ kopírování dat z paměti do registru (‹ld›, ‹ldb›), ◦ kopírování z registru do paměti (‹st›, ‹stb›), 3. aritmetické operace: ◦ aditivní – bez rozlišení znaménkovosti (‹add›, ‹sub›), ◦ násobení ‹mul›, ◦ dělení se znaménkem (‹sdiv›, ‹smod›), ◦ dělení bez znaménka (‹udiv› a ‹umod›), 4. operace pro srovnání dvou hodnot: ◦ rovnost (‹eq›, ‹ne›), ◦ znaménkové ostré nerovnosti (‹slt›, ‹sgt›), ◦ znaménkové neostré nerovnosti (‹sle›, ‹sge›), ◦ bezznaménkové ostré (‹ult›, ‹ugt›), a konečně ◦ bezznaménkové neostré (‹ule›, ‹uge›), 5. bitové operace: ◦ logické operace ‹and›, ‹or› a ‹xor› aplikované po bitech, ◦ bitové posuvy ‹shl› (levý), ‹shr› (pravý) a aritmetický ‹sar›, 6. řízení toku: ◦ nepodmíněný skok ‹jmp›, ◦ podmíněné skoky ‹jz› (jump if zero) a ‹jnz› (if not zero), ◦ volání a návrat z podprogramu (‹call›, ‹ret›), 7. ovládaní stroje: ◦ ‹halt› zastaví výpočet, ◦ ‹asrt› zastaví výpočet s chybou, je-li operand nulový. ## Jazyk symbolických adres Stroj jako takový pracuje pouze s «číselnými» adresami – instrukce, která obsahuje adresu, ji vždy obsahuje jako číslo. To při programování představuje značný problém, protože adresy jednotlivých částí programu závisí na tom, kolik instrukcí se nachází v části předchozí. Uvažme třeba tento program (uložený v paměti od adresy nula): put 0 → rv ; vynuluj registr rv add 1, rv → rv ; do registru rv přičti 1 jnz rv, 0x0004 ; je-li rv nenulové, skoč na adresu 4 Protože každá instrukce je kódována do 4 bajtů, adresa druhé instrukce (operace ‹add›) je 4 (její kódování je uloženo na adresách 4, 5, 6 a 7). Program jak je napsaný provede prázdný cyklus 65535× (v poslední iteraci je v registru ‹rv› hodnota ‹ffff›, přičtením jedničky se změní na nulu, podmíněný skok „není-li ‹rv› nula“ se neprovede a cyklus tak skončí). Uvažme nyní situaci, kdy do programu potřebujeme (na začátek) zařadit další instrukci, např. nastavení registru l1: put 0 → l1 ; vynuluj registr l1 put 0 → rv ; vynuluj registr rv add 1, rv → rv ; do registru rv přičti 1 jnz rv, 0x0004 ; je-li rv nenulové, skoč na adresu 4 Tím se ale posunuly všechny další instrukce v programu na jiné adresy – proto adresa skoku předaná operaci ‹jnz› neodpovídá původnímu programu – tento nový program bude cyklit donekonečna (rozmyslete si proč). Je asi zřejmé, že kdyby měla každá změna programu (přidání nebo odebrání instrukce) znamenat, že musíme opravit všechny adresy ve všech ostatních instrukcích, moc dobře by se nám neprogramovalo. Proto pro zápis strojového kódu používáme tzv. jazyk «symbolických adres». Ten nám umožňuje místa v programu – adresy – pojmenovat «symbolem» – textovým názvem, podobně jako nazýváme třeba proměnné v jazyce Python. Symbol zavedeme tzv. «návěstím» a použijeme v zápisu instrukce¹ na místě adresy: put 0 → rv ; vynuluj registr rv loop: ; návěstí pro první instrukci cyklu add 1, rv → rv ; do registru rv přičti 1 jnz rv, loop ; je-li rv nenulové, skoč na začátek cyklu Když nyní přidáme na začátek programu instrukci, nic špatného se nestane – při sestavení (angl. «assembly») programu se pak do podmíněného skoku místo adresy 4 doplní adresa 8 – totiž adresa instrukce, která bezprostředně následuje za návěstím. ¹ Striktně vzato se v takové chvíli nejedná o zápis instrukce, pouze o předpis, jak konkrétní instrukci dopočítat – protože je to ale výpočet velmi jednoduchý, nebudeme obvykle tyto případy rozlišovat (tzn. návěstí budeme přímo interpretovat jako adresu, kterou reprezentuje v daném programu). ## d. Demonstrace (ukázky) ### 1. [‹tinyvm›] Tento program implementuje kompletní sémantiku výpočetního stroje, který budeme v tomto kurzu používat. Je naprogramován v jazyce z 11. týdne kurzu IB111, měli byste tedy samotnému zápisu programu bez problémů rozumět. V komentářích je pak vysvětlena sémantika (jak stroj pracuje). Protože se jedná o spustitelný program, popisuje sémantiku výpočetního stroje velmi přesně – můžete jej tedy použít jako referenční příručku strojového kódu, který budeme používat. Doporučujeme Vám program si pozorně přečíst už nyní, na začátku semestru, ale je zcela v pořádku, pokud neporozumíte ihned všemu. Očekáváme, že se budete k programu minimálně několik následujících týdnů pravidelně vracet. Studium sémantiky nových operací na začátku několika příštích kapitol je k tomu ideální příležitostí. Jádro celého stroje tvoří procedura ‹step›, která načte, dekóduje a provede jednu instrukci. Vstupními parametry jsou: 1. ‹pc› je aktuální hodnota programového čítače, 2. ‹regs› je seznam 16 celých čísel, každé v rozsahu 0 až 65535, jenž reprezentují hodnoty uložené v registrech, 3. ‹mem› je seznam 65536 celých čísel, každé v rozsahu 0 až 255, přitom číslo uložené na indexu ‹i› reprezentuje paměťovou buňku s adresou ‹i›. Návratovou hodnotou je dvojice celých čísel (nová hodnota programového čítače, příznak má-li výpočet pokračovat). def step( pc: int, regs: list[ int ], # python mem: list[ int ] ) -> tuple[ int, int ]: Následující tvrzení popisují základní vstupní podmínky. assert 0 <= pc < 65536 # python assert len( regs ) == 16 assert len( mem ) == 65536 Abychom mohli instrukci co nejsnadněji provést, dekódujeme ji na několik pojmenovaných hodnot. Hodnota ‹opcode› je číslo operace, složené ze dvou půlslabik – kategorie ‹cat› a konkrétní operace z dané kategorie ‹op›. V šestnáctkovém zápisu tedy ‹opcode = 0x12› značí operaci 2 z kategorie 1. opcode = mem[pc] # python cat = opcode // 16 op = opcode % 16 Druhá slabika popisuje vstupní a výstupní registr – tyto se uplatní u většiny operací (výjimky tvoří zejména operace z kategorie 0 – speciální instrukce, a kategorie 15 – řízení toku). Je-li šestnáctkový zápis druhé slabiky ‹0x82›, je výstupním registrem ten s číslem 8 (‹t1›) a (prvním) vstupním registrem je registr číslo 2, totiž ‹l2›. r_out = mem[ pc + 1 ] // 16 # python r_1 = mem[ pc + 1 ] % 16 Třetí a čtvrtá slabika pak popisují buď tzv. přímý (immediate) operand (číselnou hodnotu, která je přímo součástí instrukce) nebo druhý vstupní registr (pro binární operace nad registry, např. ty dobře známé aritmetické). Nemá-li instrukce přímý operand, je poslední slabika nevyužitá. imm = mem[ pc + 3 ] + mem[ pc + 2 ] * 256 # python r_2 = mem[ pc + 2 ] // 16 addr = imm Než instrukci vykonáme, vypíšeme dekódovanou instrukci a aktuální stav stroje – procedura ‹print_state› nemá na výpočet stroje žádný vliv, není tedy nutné ji blíže zkoumat. Můžete si ji ale přizpůsobit dle vlastního vkusu nebo potřeby. print_state( pc, regs, cat, op, imm, r_out, r_1, r_2 ) # python Nyní již následuje samotné vykonání instrukce. První dvě operace jsou z kategorie 14 – řízení stroje. Instrukce ‹asrt› ukončí výpočet s chybou, je-li ve vstupním registru hodnota nula, jinak pokračuje ve výpočtu další instrukcí. Instrukce ‹halt› výpočet zastaví vždy (nikoliv ale chybou). if opcode == 0xee and regs[ r_1 ] == 0: # asrt # python return pc, ERROR if opcode == 0xef: # halt return pc, HALT Následují speciální operace z kategorie 0. Operace ‹copy› uloží do výstupního registru hodnotu registru vstupního, operace ‹put› uloží přímý operand do výstupního registru a konečně ‹sext› provede znaménkové rozšíření spodní slabiky vstupního registru a výsledek uloží do toho výstupního. if opcode == 0x0c: # copy # python regs[ r_out ] = regs[ r_1 ] if opcode == 0x0d: # put regs[ r_out ] = imm if opcode == 0x0e: # sext regs[ r_out ] = as_signed( regs[ r_1 ], 8 ) % 65536 Dále do kategorie 0 patří operace pro obecnou práci s pamětí. Operace ‹st› (store): • uloží slovo ze vstupního registru • na adresu, která vznikne jako součet přímého operandu a hodnoty ve «výstupním» registru (jedná se zde o výjimečné použití výstupního registru jako vstupní hodnoty). Varianta ‹stb› zapíše pouze spodní slabiku vstupního registru a přepíše tedy jedinou buňku paměti. if opcode in [ 0x03, 0x04 ]: # st, stb # python addr = ( addr + regs[ r_out ] ) % 65536 if opcode == 0x03: # stb # python mem[ addr ] = regs[ r_1 ] % 256 if opcode == 0x04: # st # python mem[ addr + 0 ] = regs[ r_1 ] // 256 mem[ addr + 1 ] = regs[ r_1 ] % 256 Operace ‹ld› analogicky: • vypočte adresu jako součet přímého operandu a hodnoty ve «vstupním» registru, • z vypočtené adresy načte slovo a uloží ho do «výstupního» registru. Varianta ‹ldb› přečte z paměti pouze jednu slabiku a na celé slovo ji doplní levostrannými nulami. if opcode in [ 0x01, 0x02 ]: # ld, ldb # python addr = ( addr + regs[ r_1 ] ) % 65536 if opcode == 0x01: # ldb # python regs[ r_out ] = mem[ addr ] if opcode == 0x02: # ld # python regs[ r_out ] = mem[ addr ] * 256 + mem[ addr + 1 ] Konečně jsou v kategorii 0 operace ‹push› a ‹pop› pro práci se zásobníkem. Jejich efekt je implementován pomocnými procedurami ‹push› a ‹pop› níže, protože stejný efekt budeme potřebovat i při implementaci některých dalších operací. Operace ‹push› sníží hodnotu uloženou v registru ‹sp› o dvě a na výslednou adresu uloží slovo ze vstupního registru. Operace ‹pop› analogicky nejprve přečte slovo uložené na adrese dané registrem ‹sp›, uloží ho do výstupního registru a konečně hodnotu registru ‹sp› o dvě zvýší. if opcode == 0x0a: # push # python push( regs, mem, regs[ r_1 ] ) if opcode == 0x0b: # pop regs[ r_out ] = pop( regs, mem ) Tím je kategorie 0 vyřešena. Dále pokračujeme kategorií 15, která obsahuje operace pro řízení toku. Operace ‹call› uloží hodnotu programového čítače na zásobník (podobně jako operace ‹push›) – jedná se o tzv. návratovou adresu. Dále nastaví ‹pc› na hodnotu přímého operandu, čím předá řízení podprogramu na této adrese uloženému. if opcode == 0xfe: # call # python push( regs, mem, pc ) return imm, CONT Operace ‹ret› ukončí vykonávání podprogramu a řízení vrátí volajícímu – návratovou adresu načte ze zásobníku podobně jako operace ‹pop›. Tuto adresu nezapomeneme zvýšit, protože adresa na uložená zásobníku ukazuje na instrukci ‹call›, která volání způsobila. if opcode == 0xff: # ret # python return pop( regs, mem ) + 4, CONT Konečně operace skoků – nepodmíněné ‹jmp› a podmíněné ‹jz› a ‹jnz› – pouze nastaví programový čítač na hodnotu přímého operandu. Podmíněný skok se provede v případě, že je hodnota vstupního registru nulová (‹jz›) nebo naopak nenulová (‹jnz›). Není-li podmínka splněna, tyto operace nemají žádný efekt a výpočet pokračuje další instrukcí. if cat == 0xf and ( op == 0 or # jmp # python op == 1 and regs[ r_1 ] == 0 or # jz op == 2 and regs[ r_1 ] != 0 ): # jnz return imm, CONT Kategorie 1 až 3 obsahují binární aritmetické operace v několika variantách: • operace z kategorie 1 použije přímý operand jako levý a vstupní registr jako pravý, • v kategorii 2 je tomu naopak, levý operand je vstupní registr a pravý operand je přímý, • konečně kategorie 3 pracuje se dvěma vstupními registry (přímý operand nemá). Implementace aritmetických operací naleznete v čisté funkci ‹arith› definované níže. if cat == 1: # python regs[ r_out ] = arith( op, imm, regs[ r_1 ] ) if cat == 2: regs[ r_out ] = arith( op, regs[ r_1 ], imm ) if cat == 3: regs[ r_out ] = arith( op, regs[ r_1 ], regs[ r_2 ] ) Konečně kategorie 10 a 11 provádí aritmetické srovnání dvou hodnot – buď ve variantě se dvěma registry, nebo srovnání vstupního registru s přímým operandem. if cat == 0xa: # python regs[ r_out ] = compare( op, regs[ r_1 ], regs[ r_2 ] ) if cat == 0xb: regs[ r_out ] = compare( op, regs[ r_1 ], imm ) Tím je implementace kompletní. S výjimkou několika málo operací pokračuje výpočet další instrukcí, tzn. té, která je uložena na adrese o 4 vyšší, než byla ta aktuální (každá instrukce je kódována čtyřmi slabikami). return pc + 4, CONT # python Následující dva podprogramy realizují operace se zásobníkem – adresa vrcholu zásobníku je uložena v registru ‹sp› (registr číslo 15). def push( regs: list[ int ], mem: list[ int ], val: int ) -> None: # python regs[ 15 ] = ( regs[ 15 ] - 2 ) % 65536 mem[ regs[ 15 ] ] = val def pop( regs: list[ int ], mem: list[ int ] ) -> int: # python rv = mem[ regs[ 15 ] ] regs[ 15 ] = ( regs[ 15 ] + 2 ) % 65536 return rv Čistá funkce ‹as_signed› bijektivně zobrazí celé číslo ⟦n⟧ z rozsahu ⟦⟨0, 2ᵇ)⟧ na číslo v rozsahu ⟦⟨-2ᵇ⁻¹, 2ᵇ⁻¹)⟧, metodou známou jako dvojkový doplňkový kód. Opačné zobrazení lze v Pythonu provést velmi jednoduše, jako ‹m % 2 ** b›. Protože stejný výraz popisuje zkrácení výsledku, které se používá při bezznaménkové aritmetice s pevnou šířkou slova, budeme jej níže zapisovat přímo, bez použití pomocné funkce. Zobrazení realizované funkcí ‹as_signed› budeme níže značit ⟦t(n)⟧. def as_signed( num: int, bits: int ) -> int: # python mod = 2 ** bits num = num % mod return num if num < mod // 2 else num - mod Čistá funkce ‹arith› realizuje základní aritmetické a logické operace – sčítání, odečítání, násobení a dělení se zbytkem, bitové logické operace a bitové posuvy. Vstupem jsou dvě celá čísla ‹op_1› a ‹op_2› v rozsahu ⟦⟨0, 2¹⁶)⟧, výsledek je v témže rozsahu. def arith( op: int, op_1: int, op_2: int ) -> int: # python Užitečnou vlastností dvojkového doplňkového kódu je, že operace sčítání (odečítání) a násobení se provádí zcela stejně, jako jejich bezznaménkové verze – platí: ⟦ t(a) + t(b) = t(a + b) t(a) - t(b) = t(a - b) t(a) ⋅ t(b) = t(a ⋅ b) ⟧ Pro dělení podobná rovnost žel neplatí, proto musíme rozlišovat operace ‹sdiv›/‹udiv› a ‹smod›/‹umod›. if op == 0x1: return ( op_1 + op_2 ) % 65536 # python if op == 0x2: return ( op_1 - op_2 ) % 65536 if op == 0x3: return ( op_1 * op_2 ) % 65536 if op == 0x4: return op_1 // op_2 if op == 0x6: return op_1 % op_2 Pro jednoduchost budeme při dělení dodržovat znaménkovou konvenci, která se používá v jazyce C, a která je žel odlišná od té, která se používá v jazyce Python. if op == 0x5 or op == 0x7: # signed div/rem # python dividend = as_signed( op_1, 16 ) divisor = as_signed( op_2, 16 ) quot, rem = divmod( dividend, divisor ) if ( dividend > 0 ) != ( divisor > 0 ) and rem != 0: # python rem -= divisor if quot < 0 and rem != 0: quot += 1 return ( quot if op == 0x5 else rem ) % 65536 # python Bitové logické operace se provádí po jednotlivých bitech (číslicích ve dvojkovém zápisu). Každá operace provede na odpovídajících bitech v operandech příslušnou logickou operaci (‹and›, ‹or› nebo ‹xor›), čím získá odpovídající bit výsledku. Operandy jsou vždy 16bitové. if op in [ 0xa, 0xb, 0xc ]: # python result = 0 for idx in range(16): bit_1 = op_1 // 2 ** idx % 2 bit_2 = op_2 // 2 ** idx % 2 if op == 0xa: # python bit_r = bit_1 == 1 and bit_2 == 1 if op == 0xb: bit_r = bit_1 == 1 or bit_2 == 1 if op == 0xc: bit_r = ( bit_1 == 1 ) != ( bit_2 == 1 ) result += bit_r * 2 ** idx # python return result # python Bitové posuvy jsou jednoduché – posuv doleva odpovídá násobení a posuv doprava dělení příslušnou mocninou dvojky. Při pravých posuvech (dělení) musíme opět rozlišit bezznaménkovou (‹shr›) a znaménkovou (‹sar›) verzi. Znaménkový (tzv. aritmetický) posuv pak lze chápat i jako operaci, která posouvá jednotlivé bity doprava, ale zleva doplňuje místo nul kopie znaménkového bitu. if op == 0xd: # python return ( op_1 * 2 ** op_2 ) % 65536 if op == 0xe: return ( op_1 // 2 ** op_2 ) % 65536 if op == 0xf: return ( as_signed( op_1, 16 ) // 2 ** op_2 ) % 65536 assert False # python Čistá funkce ‹compare› realizuje aritmetická srovnání. Krom rovnosti (⟦=, ≠⟧) jsou všechny operace závislé na tom, pracujeme-li se znaménkovou reprezentací – v dvojkovém doplňkovém kódu jsou kódy záporných čísel větší, než kódy čísel kladných, např. 16bitové kódování -1 je ‹0xffff›, přitom 16bitové kódování +1 je ‹0x0001›, výsledek ‹0xffff < 0x0001› ale jistě v tomto kontextu nedává smysl. def compare( op: int, arg_1: int, arg_2: int ) -> int: # python sig_1 = as_signed( arg_1, 16 ) # python sig_2 = as_signed( arg_2, 16 ) if op == 0x0: result = arg_1 == arg_2 # python if op == 0xf: result = arg_1 != arg_2 if op == 0x1: result = arg_1 < arg_2 # python if op == 0x2: result = arg_1 <= arg_2 if op == 0x3: result = arg_1 > arg_2 if op == 0x4: result = arg_1 >= arg_2 if op == 0xa: result = sig_1 < sig_2 # python if op == 0xb: result = sig_1 <= sig_2 if op == 0xc: result = sig_1 > sig_2 if op == 0xd: result = sig_1 >= sig_2 return 1 if result else 0 # python Tím je implementace ‹step› a jejích pomocných funkcí hotova. Za pomoci ‹step› je již velmi jednoduché implementovat podprogram ‹run›, který provede celý výpočet. Program je uložen od adresy 0. CONT = 0 # python HALT = 1 ERROR = 2 def run( regs: list[ int ], mem: list[ int ] ) -> bool: # python print( " pc inst op_1 op_2 out │ " + " rv l1 l2 l3 l4 l5 l6 l7 " + " t1 t2 t3 t4 t5 t6 sp bp" ) status = CONT pc = 0 while status == CONT: # python pc, status = step( pc, regs, mem ) return status == HALT # python Další částí je podprogram ‹read_program›, který ze vstupního souboru přečte počáteční stav paměti (kterému můžeme také říkat «program»). def write_nibble( mem: list[ int ], index: int, nibble: int ) -> None: # python mem[ index // 2 ] += nibble * 16 if index % 2 == 0 else nibble def read_program( filename: str ) -> list[ int ]: # python mem = [ 0 for i in range( 65536 ) ] index = 0 with open( filename, 'r' ) as file: # python for line in file.readlines(): if line[ 0 ] == ';': break for word in line.rstrip().replace( "'", '' ).split( ' ' ): for hex_nibble in word: write_nibble( mem, index, FROM_HEX[ hex_nibble ] ) index += 1 return mem # python Zbývá vstupní bod (podprogram ‹main›) a procedury pro výpis aktuálního stavu výpočetního stroje. Zbývající kód není pro pochopení funkčnosti výpočetního stroje ‹tiny› nijak podstatný. # Výpočetní stroj Předmětem této kapitoly je přímé programování výpočetního stroje ‹tiny› (v jazyce symbolických adres). Ukázky: 1. ‹triangle› – trojúhelníková nerovnost, 2. ‹factorial› – iterativní výpočet faktoriálu. Přípravy: 1. ‹fib› – ⟦n⟧-té Fibonacciho číslo (mod ⟦2¹⁶⟧), 2. ‹adder› – dvouslovná sčítačka (32b), 3. ‹gcd› – Euklidův algoritmus, 4. ‹prime› – rozhodování prvočíselnosti, 5. ‹popcnt› – počítání jedniček ve slově, 6. ‹perfect› – součet dělitelů. Řešené příklady: 1. ‹reverse› – otočení bitů ve slově, 2. ‹hamming› – Hammingova vzdálenost slov, 3. ‹packed› – sečtení dvou dvojic po složkách, 4. ‹bitswap› – prohození dvou bitů ve slově, 5. ‹collatz› – počítání kroků iterovaného výpočtu, 6. ‹shift› – bitový posuv na části slova. ## Strojový kód V této kapitole budeme potřebovat 2 typy instrukcí – výpočetní (aritmetické, logické, atp.) a instrukce pro řízení toku (nepodmíněné a podmíněné skoky). Zejména prozatím nebudeme potřebovat pracovat s adresami, pamětí obecně, ani zásobníkem. ### Kopírování hodnot Nejzákladnější operací, kterou můžeme v programu potřebovat, je nastavení registru, a to buď na předem známou konstantu, nebo na hodnotu aktuálně uloženou v některém jiném registru. K nastavení registru na konstantu můžeme použít operaci ‹put›, která nastaví výstupní registr na hodnotu přímého operandu. Zápis této instrukce bude vypadat např. takto: put 13 → rv ; tiny put 0x70 → l1 halt Tento program nastaví registr ‹rv› na hodnotu 13 a registr ‹l1› na hodnotu 112. Pro kopírování hodnot mezi registry použijeme operaci ‹copy› – ta nastaví výstupní registr na tutéž hodnotu, jakou má registr vstupní. Například: put 13 → rv ; tiny put 17 → l1 copy rv → l2 ; sets l2 = 13 copy l1 → rv ; sets rv = 17 halt Po provedení tohoto programu budou hodnoty registrů ‹rv = 17›, ‹l1 = 17› a ‹l2 = 13›. ### Aritmetika Další důležitou kategorií jsou aritmetické instrukce. Následující tabulka shrnuje operace, které máte k dispozici. Registr ‹l1› odpovídá proměnné ‹a›, registr ‹l2› proměnné ‹b›, registr ‹rv› pak proměnné ‹x›. │ název │ python │ tiny │ ├──────────▻│──────────────│────────────────────│ │ sčítání │ ‹x = a + b› │ ‹add l1, l2 → rv› │ │ odečítání │ ‹x = a - b› │ ‹sub l1, l2 → rv› │ │ násobení │ ‹x = a * b› │ ‹mul l1, l2 → rv› │ │ dělení │ ‹x = a // b› │ ‹sdiv l1, l2 → rv› │ │ │ │ ‹udiv l1, l2 → rv› │ │ zbytek │ ‹x = a % b› │ ‹smod l1, l2 → rv› │ │ │ │ ‹umod l1, l2 → rv› │ Všimněte si, že operaci celočíselného dělení a zbytku po dělení odpovídají dvě různé instrukce. Je to proto, že fyzicky jsou registry realizované jako sekvence binárních přepínačů – každý přepínač reprezentuje jeden bit. Tyto binární sekvence lze interpretovat různými způsoby, nicméně ⟦b⟧-bitový registr obvykle chápeme jako: 1. celé číslo ⟦n⟧ bez znaménka v rozsahu ⟦⟨0, 2ᵇ)⟧ – pak sekvence bitů přímo odpovídá binárnímu zápisu tohoto čísla, 2. jako celé číslo ⟦s⟧ se znaménkem v rozsahu ⟦⟨-2ᵇ⁻¹, 2ᵇ⁻¹)⟧, a to tak, že: a. je-li nejvyšší bit nastaven na 1, ⟦s = n - 2ᵇ⟧, b. jinak ⟦s = n⟧ Podmínku z bodu (a) můžeme také chápat jako ⟦n ≥ 2ᵇ⁻¹⟧. Pro 16bitová čísla, která budeme v tomto předmětu používat zdaleka nejčastěji, to jsou tyto rozsahy: • ⟦⟨0, 65535⟩⟧ (nebo ‹0–ffff› v šestnáctkovém zápisu) pro reprezentaci bez znaménka, • ⟦⟨-32768, 32767⟩⟧ (nebo ‹-8000› až ‹7fff› šestnáctkově) pro reprezentaci se znaménkem. Tato reprezentace má tu vlastnost, že sčítání, odečítání a násobení používá na úrovni bitů stejný algoritmus v obou případech – proto operace ‹add› funguje stejně dobře bez ohledu na to, chápeme-li operandy jako znaménkové nebo bezznaménkové. To ale neplatí pro dělení (a nebude to platit ani pro srovnání, jak uvidíme za chvíli) – výsledek se bude lišit v závislosti na tom, je-li operace znaménková (‹sdiv›, ‹smod›) nebo nikoliv (‹udiv›, ‹umod›). ### Srovnání Prakticky každý vyšší programovací jazyk má nějakou formu «podmíněného příkazu». Aby byla tato konstrukce užitečná, potřebujeme mít k dispozici «predikáty» – operace, kterých výsledkem je pravdivostní hodnota. Ty nejběžnější již dobře znáte – jsou to celočíselné srovnávací operátory. V Pythonu je zapisujeme jako ‹a == b›, ‹a < b›, atp. Náš výpočetní stroj má pro tento účel sadu operací – jsou shrnuty v tabulce níže. Jak již bylo výše naznačeno, s výjimkou rovnosti musíme rozlišovat znaménkovou a bezznaménkovou verzi. Na rozdíl od Pythonu (nebo jazyka C) nemá strojový kód složené výrazy, proto musíme výsledek srovnání vždy uložit do registru (analogem v Pythonu je booleovská proměnná – budeme ji zde opět značit ‹x›). │ python │ tiny │ │ │ ├──────────────│────────────────────│─────────▻┼◅─────────────────│ │ ‹x = a == b› │ ‹eq l1, l2 → rv› │ │ 𝐞𝐪ual │ │ ‹x = a != b› │ ‹ne l1, l2 → rv› │ │ 𝐧ot 𝐞qual │ │ ‹x = a < b› │ ‹slt l1, l2 → rv› │ 𝐬igned │ 𝐥ess 𝐭han │ │ │ ‹ult l1, l2 → rv› │ 𝐮nsigned │ 𝐥ess 𝐭han │ │ ‹x = a > b› │ ‹sgt l1, l2 → rv› │ 𝐬igned │ 𝐠reater 𝐭han │ │ │ ‹ugt l1, l2 → rv› │ 𝐮nsigned │ 𝐠reater 𝐭han │ │ ‹x = a <= b› │ ‹sle l1, l2 → rv› │ 𝐬igned │ 𝐥ess or 𝐞qual │ │ │ ‹ule l1, l2 → rv› │ 𝐮nsigned │ 𝐥ess or 𝐞qual │ │ ‹x = a >= b› │ ‹sge l1, l2 → rv› │ 𝐬igned │ 𝐠reater or 𝐞qual │ │ │ ‹uge l1, l2 → rv› │ 𝐮nsigned │ 𝐠reater or 𝐞qual │ Výsledek uložený do výstupního registru (v příkladech výše ‹rv›) je u instrukcí z této rodiny vždy 1 (pravda) nebo 0 (nepravda). To zejména znamená, že je možné tyto výsledky kombinovat operacemi ‹and›, ‹or› a ‹xor› a výsledek bude vždy opět 0 nebo 1, v souladu s definicí příslušné logické operace (k těmto se vrátíme níže). ### Řízení toku Abychom mohli realizovat podmíněné příkazy a cykly, budeme k tomu potřebovat speciální operace – podobně jako příslušným příkazům ve vyšším jazyce jim budeme říkat «řízení toku». Výpočetní stroj ‹tiny› obsahuje 3 operace tohoto typu: • ‹jmp addr› způsobí, že výpočet bude pokračovat od adresy ‹addr› – bez ohledu na aktuální stav registrů; adresu můžeme (a typicky budeme) zadávat jako «symbol» (jméno «návěstí» – viz též část B.3), • ‹jz reg, addr› (jump if zero) nejprve ověří, je-li hodnota registru ‹reg› nulová – pokud ano, provede skok stejně jako ‹jmp addr›, v případě opačném pokračuje na další instrukci bez jakéhokoliv dalšího efektu, • ‹jnz reg, addr› (jump if not zero) se chová stejně, ale skok provede pouze je-li hodnota uložená v ‹reg› nenulová. V kombinaci s aritmetickými a srovnávacími operacemi popsanými výše dokážeme zapsat jednoduchou podmínku např. takto (odpovídající program v Python-u je uveden v komentářích): put 1 → l1 ; a = 1 slt l1, 3 → t1 ; t = a < 3 jz t1, else ; if t: then: put 2 → l2 ; b = 2 jmp endif ; else: else: put 3 → l2 ; b = 3 endif: halt Zkuste si program spustit pomocí ‹tinyvm.py› z kapitoly B, a také upravit první instrukci na ‹put 5 → l1› a srovnejte výsledek. Podobně můžeme zapsat také ‹while› cyklus (cykly ‹for› do strojového kódu přímo přepsat nemůžeme, ale jak jistě víte, je vždy možné nejprve je přepsat na cykly ‹while›). Uvažme tento velmi jednoduchý program v Pythonu: a = 1 while a < 3: a += 1 Přepis do strojového kódu bude opět vyžadovat určitou kreativitu, protože máme pouze instrukce skoku, nikoliv instrukce cyklu. Stačí si ale uvědomit, že ‹while True› se realizuje snadno: pomocí nepodmíněného skoku zpět (na nižší adresu). put 1 → l1 ; a = 1 loop: ; while True: slt l1, 3 → t1 ; t = a < 3 jz t1, end ; if not t: break add l1, 1 → l1 ; a += 1 jmp loop end: halt Cyklus ‹while podmínka› jsme přepsali na ‹while True› a podmíněný ‹break› – ekvivalenci těchto dvou zápisů si rozmyslete. ### Bitové logické operace XXX ### Bitové posuvy XXX ## Programovací jazyk Tato kapitola jazyk C nepoužívá. ## d. Demonstrace (ukázky) ### 1. [‹triangle›] V této ukázce napíšeme jednoduchý program, který rozhodne zadává-li trojice vstupních čísel trojúhelník (tzn. určí, zda vstup splňuje potřebné trojúhelníkové nerovnosti). V Pythonu tento problém řeší výraz: (a + b > c) and (b + c > a) and (c + a > b) Nejprve si nachystáme testovací kód a testovací data (tuto část můžete při čtení přeskočit – to bude platit i v dalších ukázkách). Testovací kód načte testovací data z paměti – jak tyto instrukce fungují si blíže ukážeme v dalších kapitolách. Vstup budeme očekávat v registrech ‹l1›, ‹l2› a ‹l3› a výsledek (0 nebo 1) zapíšeme do registru ‹rv›. test: ; driver ; tiny ld l7, 0x24 → l1 add l7, 2 → l7 ld l7, 0x24 → l2 add l7, 2 → l7 ld l7, 0x24 → l3 add l7, 2 → l7 eq l1, 0xffff → t1 ; test-end marker jz t1, solution halt data: ; l1 l2 l3 → rv ; tiny .word 3, 4, 5, 1 .word 1, 1, 1, 1 .word 1, 1, 3, 0 .word 2, 3, 1, 0 .word -1, 0 check: ; tiny ld l7, 0x24 → t1 eq rv, t1 → t1 asrt t1 add l7, 2 → l7 jmp test .trigger set _tc_expect_ 4 ; tiny .trigger inc _tc_ solution: ; zde začíná řešení ; tiny Protože potřebujeme implementovat konjunkci, nastavíme do registru ‹rv› její neutrální hodnotu – ‹true›, tzn. 1. Každý ze tří testů pak bude implementovaný stejně – sečte dvě strany, srovná tento součet se stranou třetí a výsledek tohoto srovnání přidá do registru ‹rv› bitovou operací ‹and›. put 1 → rv ; tiny Každý z následovných tří bloků realizuje jednu nerovnost. Mezivýsledky ukládáme do registrů ‹t1› (součet stran) a ‹t2› (výsledek srovnání součtu se zbývající stranou). add l1, l2 → t1 ; tiny sgt t1, l3 → t2 and rv, t2 → rv add l1, l3 → t1 ; tiny sgt t1, l2 → t2 and rv, t2 → rv add l2, l3 → t1 ; tiny sgt t1, l1 → t2 and rv, t2 → rv Tím je výpočet ukončen a protože je již výsledek uložen ve správném registru, nezbývá než předat řízení zpátky do testovacího kódu. jmp check ; tiny ### 2. [‹factorial›] V této ukázce naprogramujeme jeden z nejjednodušších číselných algoritmů vůbec – iterativní výpočet faktoriálu celého kladného čísla. Novým prvkem bude tedy «cyklus» – opakované spuštění stejného segmentu kódu. Testovací kód můžete opět přeskočit, řešení začíná návěstím ‹solution›. Vstupní hodnota bude v registru ‹l6›, výsledek pak v registru ‹rv›. test: ; driver ; tiny ld l7, 0x10 → l6 eq l6, 0xffff → t1 ; test-end marker jz t1, solution halt data: ; input, expect ; tiny .word 1, 1 .word 2, 2 .word 3, 6 .word 4, 24 .word -1, 0 check: ; tiny add l7, 2 → l7 ld l7, 0x10 → t1 eq rv, t1 → t1 asrt t1 add l7, 2 → l7 jmp test .trigger set _tc_expect_ 4 ; tiny .trigger inc _tc_ solution: ; zde začíná řešení ; tiny Registr ‹rv› budeme používat jako střadač (akumulátor) – před vstupem do cyklu jej nastavíme na neutrální hodnotu 1 a v každé iteraci jej vynásobíme počítadlem iterací. Jako řídící proměnnou použijeme přímo ‹l6› – protože na pořadí násobení nezáleží, můžeme hodnoty násobit sestupně v pořadí ⟦n⋅(n - 1)⋅(n - 2) … 1⟧. Jakmile řídící proměnná dosáhne hodnoty nula, cyklus ukončíme (musíme si pouze dát pozor, abychom nulou již nenásobili). put 1 → rv ; tiny loop: mul rv, l6 → rv sub l6, 1 → l6 jnz l6, loop jmp check ; tiny ## p. Přípravy ### 1. [‹fib›] Vaším úkolem je naprogramovat iterativní výpočet ⟦n⟧-tého Fibonacciho čísla. Vstupní hodnotu ⟦n⟧ naleznete v registru ‹l6›, výsledek uložte do registru ‹rv›. Po skončení výpočtu proveďte skok na návěstí ‹check›. Hodnotu registru ‹l7› zachovejte. ### 2. [‹adder›] Vaším úkolem je tentokrát naprogramovat 32bitovou sčítačku. Vstupem jsou 4 16bitové hodnoty uložené v registrech ‹l1› až ‹l4›, kde ‹l1› a ‹l3› jsou nižší a ‹l2› a ‹l4› jsou vyšší slova sčítanců. Nižší slovo výsledku uložte do ‹rv›, to vyšší pak do ‹l6›. Hodnotu v registru ‹l7› neměňte. ### 3. [‹gcd›] Vaším úkolem je naprogramovat Euklidův algoritmus pro nalezení největšího společného dělitele hodnot uložených v registrech ‹l1› a ‹l2› – obě hodnoty interpretujte jako 16bitová celá čísla bez znaménka. Výsledek uložte do registru ‹rv›. Po ukončení výpočtu skočte na návěstí ‹check›. Hodnotu registru ‹l7› neměňte. ### 4. [‹prime›] Napište program, který rozhodne, je-li hodnota uložená v registru ‹l6› prvočíslem (hodnotu interpretujte jako číslo bez znaménka). Výsledek (1 pokud prvočíslem je, 0 jinak) uložte do registru ‹rv› a proveďte skok na návěstí ‹check›. Hodnotu registru ‹l7› nijak neměňte. ### 5. [‹popcnt›] Napište program, který určí, kolik je jedniček v binárním zápisu čísla uloženého v registru ‹l6›. Výsledek uložte do registru ‹rv› a poté proveďte skok na návěstí ‹check›. Hodnotu registru ‹l7› nijak neměňte. ### 6. [‹abundant›] Napište program, který rozhodne, je-li hodnota uložená v registru ‹l6› abundantním číslem (číslo ⟦n⟧ je abundantní, je-li součet všech jeho dělitelů ⟦d > 2n⟧). Vstup interpretujte jako číslo bez znaménka. Výsledek (1 pokud abundantní je, 0 jinak) uložte do registru ‹rv› a proveďte skok na návěstí ‹check›. Hodnotu registru ‹l7› nijak neměňte. ## r. Řešené úlohy ### 1. [‹reverse›] Vaším úkolem bude otočit pořadí bitů ve slově. Vstupní slovo bude uloženo v registru ‹l1›, výsledek uložte do ‹rv› a skočte na návěstí ‹check›. Hodnotu v registru ‹l7› neměňte. ### 2. [‹hamming›] Spočtěte Hammingovu vzdálenost slov uložených v ‹l1› a ‹l2›. Hammingovou vzdáleností je počet pozic, v nichž se vstupní slova liší hodnotou bitu. Výsledek uložte do ‹rv› a skočte na návěstí ‹check›. Hodnotu v registru ‹l7› neměňte. ### 3. [‹packed›] Mnohé procesory nabízí tzv. vektorové instrukce, které se k jednomu velkému registru chovají, jako by obsahoval několik menších čísel uložených vedle sebe. Vaším úkolem bude emulovat jednu z těchto instrukcí; konkrétně sčítání, které 16bitové registry považuje za dvojice dvou osmibitových čísel a dvě takové dvojice sečte po složkách. Vstup je v registrech ‹l1› a ‹l2›, výsledek uložte do ‹rv› a skočte na návěstí ‹check›. Hodnotu v registru ‹l7› neměňte. ### 4. [‹bitswap›] Prohoďte dva zadané bity ve slově v registru ‹l1›. Indexy bitů jsou v ‹l2› a ‹l3›. Můžete předpokládat, že budou v rozsahu 0–15, nula označuje nejméně významný bit slova. Výsledek uložte do ‹rv› a skočte na návěstí ‹check›. Hodnotu v registru ‹l7› neměňte. ### 5. [‹collatz›] Uvažme následující funkci ‹f› na kladných celých číslech: f(n) = n / 2 je-li n sudé f(n) = 3n +1 je-li n liché Collatzova domněnka říká, že budeme-li na libovolné kladné celé číslo tuto funkci opakovaně aplikovat, dostaneme se nakonec k výsledku 1. Vaším úkolem je tento výpočet provést a 1. spočítat, po kolika aplikacích funkce ‹f› na vstup je poprvé výsledkem jednička a 2. zjistit nejvyšší mezivýsledek, který při výpočtu vznikl. Můžete předpokládat, že pro číslo na vstupu domněnka skutečně platí a že v průběhu výpočtu nevznikne mezivýsledek, který by se nevlezl do šestnáctibitového registru. Počáteční číslo naleznete v registru ‹l1›. Počet aplikací funkce uložte do ‹rv›, nalezené maximum do ‹l6› a skočte na návěstí ‹check›. Hodnotu v registru ‹l7› neměňte. ### 6. [‹shift›] Proveďte levý bitový posuv: • každý bit se posune o jednu pozici doleva, • pracujeme na bitech v registru ‹rv›, • na pozicích zadaných registry ‹l2› a ‹l3› (‹l2› je index nejnižšího, ‹l3› index nejvyššího bitu). Rotaci provádějte na místě (v registru ‹rv›), poté skočte na návěstí ‹check›. Hodnotu v registru ‹l7› neměňte. # Lokální proměnné, řízení toku Ukázky: 1. ‹fib› – lokální proměnné, cyklus 2. ‹prime› – aritmetika a rozsah číselných hodnot Přípravy: 1. ‹gcd› – euklid podruhé 2. ‹rand› – generování pseudonáhodných čísel 3. ‹collatz› – počítání kroků iterovaného výpočtu 4. ‹packed› – součet n-tic po složkách 5. ‹popcnt› – počet nenulových cifer při daném základu 6. ‹hamming› – hammingova vzdálenost při daném základu Řešené příklady: 1. ‹palindrome› – binární palindrom 2. ‹largest› – nejvyšší číslice při daném základu 3. ‹factors› – rozklad na prvočinitele 4. ‹primes› – rozklad na prvočinitele podruhé 5. ‹transpose› – překlopení bitové matice 6. ‹balanced› – vyvážená trojková soustava Volitelné příklady: 1. ‹digits› – ciferný součet při daném základu 2. ‹rotate› – bitová rotace slova ## Strojový kód V této kapitole žádné nové operace potřebovat nebudeme – budeme se soustředit na jazyk C a jak se jeho základní konstrukce přeloží na operace, které známe z předchozí kapitoly. ## Programovací jazyk 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› ## d. Demonstrace (ukázky) ### 1. [‹fib›] Toto je první ukázka v jazyce C. Struktura souboru se bude od programů v jazyce symbolických adres poněkud lišit. Přesto, že zatím nevíme jak podprogramy pracují, budou součástí kostry a řešení tedy budeme vkládat do nachystaného podprogramu. Práci s lokálními proměnnými a základní konstrukce řízení toku – podmíněný příkaz a cyklus – si demonstrujeme na klasickém iterativním algoritmu pro výpočet ⟦n⟧-tého Fibonacciho čísla. int fib( int n ) /* C */ { První dvě Fibonacciho čísla jsou 1, 1 – uložíme je do proměnných ‹a›, ‹b›. V jazyce C jsou proměnné pevně svázány s «objekty» – jakmile proměnná (jméno) vznikne, její vazbu na objekt již není možné změnit. Operátor přiřazení způsobí «změnu hodnoty objektu». Více o proměnných a přiřazení naleznete v sekci 2.2. Zejména si dejte pozor na to, že sémantika proměnných v jazyce C se výrazně liší od té, kterou znáte z jazyka Python! Deklarace lokálních proměnných zapisujeme takto: 1. jména typu, v tomto případě znaménkového celočíselného typu ‹int›, 2. neprázdného seznamu deklarovaných jmen (oddělených čárkou), které mohou být doplněny tzv. deklarátory (označují např. ukazatele: uvidíme je v pozdější ukázce), 3. volitelného inicializátoru, který popisuje počáteční hodnotu proměnné. int a = 1, b = 1; /* C */ Jazyk C má 3 typy cyklů. Cyklus ‹for› používáme zejména v situaci, kdy předem známe potřebný počet iterací. Má následující strukturu: 1. klíčové slovo ‹for›, 2. hlavička cyklu, uzavřená v kulatých závorkách, a. inicializační příkaz (výraz, deklarace proměnné, nebo prázdný příkaz) je vždy ukončen středníkem a provede se jednou před začátkem cyklu; deklaruje-li proměnné, tyto jsou platné právě po dobu vykonávání cyklu, b. podmínka cyklu («výraz» nebo prázdný příkaz) je opět vždy ukončena středníkem a určuje, zda se má provést další iterace cyklu (vyhodnotí-li se na ‹true›), c. «výraz» iterace (výraz, který «není» ukončen středníkem), který je vyhodnocen «vždy» na konci těla (před dalším vyhodnocením podmínky cyklu), 3. tělo cyklu (libovolný příkaz, často složený). Všimněte si také, že podmínka cyklu ‹i < n - 2› je složený výraz – jedná se o použití operátoru ‹<› (menší než), přitom pravý operand – ‹n - 2› je opět použití operátoru (‹-›, odečítání). Je velmi důležité si uvědomit, že náš výpočetní stroj takové výrazy neumí přímo zpracovat – dekomponovat takovéto výrazy na sekvence instrukcí je jednou z hlavních úloh překladače jazyka C. Strojový kód k této ukázce si zobrazíte příkazem $ tinycc -S d1_fib.c Realizaci podmínky cyklu naleznete ve strojovém kódu pod návěstím ‹.cond.1› – jedná se o instrukce ‹sub l1, 2 → t1› a ‹slt l4, t1 → t1›. Překladač zde použil registr ‹t1› pro uložení «mezivýsledku», který je na úrovni jazyka C implicitní a nemá žádné jméno. for ( int i = 0; i < n - 2; ++i ) /* C */ { Platnost proměnných má v jazyce C, opět na rozdíl od jazyka Python, blokovou strukturu – složené příkazy (bloky) zároveň tvoří rozsah platnosti jmen. Proměnná, která je deklarovaná uvnitř bloku, existuje pouze během vykonávání tohoto bloku. Po ukončení bloku (uzavírací složenou závorkou) tato proměnná, příslušný objekt a tedy i uložená hodnota přestanou existovat. Cyklus v tomto ohledu není nijak speciální – před další iterací cyklu je blok ukončen. Je-li tedy «v těle» cyklu deklarovaná proměnná, jedná se v každé iteraci o zcela novou proměnnou. Srovnejte situaci s řídící proměnnou (v tomto případě ‹i›). int c = a + b; /* C */ Posun výpočetního „okna“ realizujeme přiřazením. Počet existujících objektů (a tedy využitá paměť nebo registry) se přiřazením nemění, pouze se provede kopie hodnoty z jedné strany na druhou. a = b; /* C */ b = c; } Podprogramy jsme se zatím nezabývali, nicméně příkaz ‹return› ukončí vykonáváni podprogramu a volajícímu předá návratovou hodnotu, podobně jako v jazyce Python. return b; /* C */ } int main() /* demo */ /* C */ { Na tomto místě opět trochu předběhneme látku – použití (volání) podprogramu je «výraz» a jeho vyhodnocení odpovídá naší intuitivní představě: skutečné parametry (uvedené v kulatých závorkách za jménem) se použijí jako pomyslné inicializátory formálních parametrů a s takto inicializovanými parametry se vykoná tělo podprogramu. Po jeho ukončení se výraz volání podprogramu vyhodnotí na návratovou hodnotu. Jak se tento mechanismus realizuje na úrovni výpočetního stroje si povíme v příští kapitole. Speciální výraz ‹assert› (tvrzení) vyhodnotí svůj parametr a je-li výsledek ‹false›, program ukončí s chybou. assert( fib( 1 ) == 1 ); /* C */ assert( fib( 2 ) == 1 ); assert( fib( 7 ) == 13 ); assert( fib( 20 ) == 6765 ); return 0; /* C */ } ### 2. [‹prime›] V této ukázce vyřešíme klasický úkol rozhodování prvočíselnosti, a to metodou pokusného dělení. Hlavička podprogramu deklaruje ‹number› jako hodnotu typu ‹unsigned› – celé číslo bez znaménka. Protože náš cílový stroj – ‹tiny› – má slova velikosti 16 bitů, bude i typ ‹unsigned› 16bitový.¹ bool is_prime( unsigned number ) /* C */ { Protože nejmenší prvočíslo je 2, a protože zbytek algoritmu pro hodnoty 1 ani 0 nebude pracovat správně, tyto hodnoty rovnou zamítneme. if ( number < 2 ) /* C */ return false; V lokální proměnné ‹divisor› budeme udržovat aktuální pokusný dělitel. unsigned divisor = 2; /* C */ Nejjednodušší podmínka cyklu, která by zde fungovala, je ‹divisor < number›. To je ale relativně neefektivní, protože je-li ⟦n⟧ prvočíslo, provedeme mnoho zbytečných iterací. Je-li totiž ⟦d⟧ dělitelem ⟦n⟧, existuje nějaké ⟦c⟧ takové, že ⟦cd = n⟧. Je-li ⟦c ≤ d⟧, potom ⟦c² ≤ cd = n⟧ a tedy ⟦c² ≤ n⟧ (je-li ⟦d ≤ c⟧, platí analogicky ⟦d² ≤ n⟧). Proto existuje-li libovolný dělitel v intervalu ⟦⟨2, n)⟧, existuje i takový, pro který ⟦d² ≤ n⟧. Tuto podmínku umíme jednoduše zapsat s použitím základní aritmetiky a srovnání (operace, které jsou k dispozici tak v stroji ‹tiny›, tak v jazyce C). Přesto ale narazíme na problém: nepracujeme totiž se skutečnými celými čísly, ale s 16bitovými slovy. A zde potřebné nerovnosti mohou selhat, je-li výsledek násobení mimo rozsah daného typu – v našem případě mimo rozsah ⟦⟨0, 2¹⁶)⟧. Konkrétně např. ⟦261² = 68121⟧, šestnáctkově ‹0x10a19› – pokusíme-li se toto číslo zapsat do 16 bitů, dostaneme ‹0x0a19›, desítkově 2585. Jaké má tento jev důsledky pro náš výpočet? Uvažme např. test prvočíselnosti 65521. Pro ‹divisor = 255› se ‹divisor * divisor› vyhodnotí na 65025, což je méně než 65521 a proto se vykoná tělo cyklu. V další iteraci dostaneme ‹divisor = 256›, ale ‹divisor * divisor› se na 16 bitech vyhodnotí na nulu a do cyklu tedy opět vstoupíme – a to i přesto, že při standardním celočíselném násobení bychom dostali výsledek ⟦256² = 65536 > 65025⟧. Tento problém bude pokračovat po mnoho iterací – takto zapsaný cyklus se zastaví až pro hodnotu ‹divisor = 16203›, kdy dostáváme: • ⟦16203² = 262537209⟧, šestnáctkově ‹0xfa5fff9›, • omezeno na 16 bitů ‹0xfff9›, desítkově tedy 65529. To ale jistě není počet iterací, který jsme očekávali – náš plán byl, že se cyklus provede pouze 256krát. unsigned sqrt_uint_max = 1 << sizeof( unsigned ) * 4; /* C */ while ( divisor <= sqrt_uint_max && /* C */ divisor * divisor <= number ) { Zjistíme-li, že ‹divisor› dělí hodnotu ‹number› beze zbytku, jistě to znamená, že ‹number› není prvočíslo (‹divisor› nemůže být ani 1 ani rovný ‹number›). if ( number % divisor == 0 ) /* C */ return false; ++ divisor; /* C */ } return true; /* C */ } int main() /* demo */ /* C */ { assert( is_prime( 2 ) ); assert( is_prime( 3 ) ); assert( is_prime( 5 ) ); assert( is_prime( 13 ) ); assert( is_prime( 29 ) ); assert( is_prime( 97 ) ); assert( is_prime( 619 ) ); assert( !is_prime( 1 ) ); /* C */ assert( !is_prime( 4 ) ); assert( !is_prime( 6 ) ); assert( !is_prime( 8 ) ); assert( !is_prime( 68 ) ); assert( !is_prime( 77 ) ); assert( !is_prime( 81 ) ); assert( !is_prime( 323 ) ); assert( !is_prime( 36863u ) ); assert( is_prime( 65521u ) ); /* C */ } ¹ Standard jazyka C neurčuje přesné velikosti základních typů. Na většině současných systémů je typ ‹unsigned› 32bitový (a to i na 64bitových architekturách), ale není to nijak zaručeno. ## p. Přípravy ### 1. [‹gcd›] Implementujte podprogram ‹gcd›, který Euklidovým algoritmem spočte největší společný dělitel dvou přirozených čísel, která obdrží jako argumenty. unsigned gcd( unsigned x, unsigned y ) /* C */ { Řešení pište sem. ‹x› a ‹y› jsou proměnné obsahující vstupní čísla. Výsledek vraťte příkazem ‹return›. return x; /* C */ } ### 2. [‹rand›] V této přípravě budete generovat pseudonáhodná 32bitová čísla. Protože náš stroj ani jazyk 32bitovou aritmetiku nepodporuje, budeme každé takové číslo representovat dvěma 16bitovými hodnotami ‹hi› (horních 16 bitů) a ‹lo› (spodních 16 bitů). Protože zatím neumíme z podprogramu vrátit dvě hodnoty zároveň, napíšete podprogramy dva, každý vracející jednu polovinu 32bitového čísla. Vzorec pro generování dalšího čísla v řadě na základě předchozího vypadá takto: rand( prev ) = prev · 1103515245 + 12345 Nápověda: Vynásobte si na papír pod sebe dvě čtyřciferná čísla. Každá cifra je jeden bajt. Vynásobení dvou bajtů a přičtení třetího se do jednoho slova vejde: 0xff · 0xff + 0xff = 0xff00 ‹rand_hi› vrací horních 16 bitů výsledku. unsigned rand_hi( unsigned hi, unsigned lo ) /* C */ { return 0; } ‹rand_lo› vrací spodních 16 bitů výsledku. unsigned rand_lo( unsigned hi, unsigned lo ) /* C */ { return 0; } ### 3. [‹collatz›] Uvažme následující funkci¹ ‹f› na kladných celých číslech: f(n) = n / 2 je-li n sudé f(n) = 3n +1 je-li n liché Collatzova domněnka říká, že budeme-li na libovolné kladné celé číslo tuto funkci opakovaně aplikovat, dostaneme se nakonec k výsledku 1. Implementujte podprogram ‹collatz_lds›, který na svůj vstup bude opakovaně aplikovat funkci ‹f› než dojde k jedničce. Výsledkem podprogramu bude délka nejdelší klesající posloupnosti mezivýsledků, tj. kolikrát nejvíce po sobě prováděl půlení čísla. Můžete předpokládat, že pro číslo na vstupu domněnka skutečně platí a že v průběhu výpočtu nevznikne mezivýsledek, který by se nevlezl do šestnáctibitového registru. ¹ Ač mluvíme o matematické «funkci» ‹f›, neočekáváme, že tato bude implementována samostatným podprogramem (tzv. funkcí) jazyka C. O těch zatím v kurzu řeč nebyla. unsigned collatz_lds( unsigned n ) /* C */ { return 0; } ### 4. [‹packed›] Uvažme slovo, které nereprezentuje jedno šestnáctibitové číslo, ale ⟦n⟧-tici několika kratších čísel uložených vedle sebe (například 2 osmibitová nebo 4 čtyřbitová). Vaším úkolem bude čísla ve dvou takovýchto ⟦n⟧-ticích sečíst po složkách a výsledek opět vrátit jako ⟦n⟧-tici stejného tvaru. Implementujte podprogram ‹packed_add›, který toto sčítání provede. Jeho první dva argumenty jsou slova reprezentující ⟦n⟧-tice, třetím je šířka čísla v ⟦n⟧-tici. V případě, že tato šířka nedělí šířku slova, je číslo uložené v nejvyšších bitech kratší. Můžete předpokládat, že šířka nebude nulová. unsigned packed_add( unsigned v1, unsigned v2, unsigned width ) /* C */ { Řešení pište sem. ‹v1› a ‹v2› jsou proměnné obsahující vstupní n-tice, ‹width› obsahuje šířku čísla v n-tici. Výsledek vraťte příkazem ‹return› return 0; /* C */ } ### 5. [‹popcnt›] Implementujte podprogram ‹popcnt›, který spočítá počet nenulových číslic representace zadaného čísla při zadaném základu. Můžete předpokládat, že základ je alespoň dva. unsigned popcnt( unsigned n, unsigned base ) /* C */ { Řešení pište sem. ‹n› je proměnná obsahující vstupní číslo, ‹base› obsahuje základ. Výsledek vraťte příkazem ‹return› return 0; /* C */ } ### 6. [‹hamming›] Implementujte podprogram ‹hamming›, který spočítá Hammmingovu vzdálenost mezi reprezentacemi dvou zadaných čísel při daném číselném základu, tj. počet pozic, v nichž se reprezentace čísel liší cifrou. Je-li jedna z reprezentací kratší, doplňte ji zleva nulami do délky delší reprezentace. Můžete předpokládat, že základ je alespoň dva. unsigned hamming( unsigned x, unsigned y, unsigned base ) /* C */ { Řešení pište sem. ‹x› a ‹y› jsou proměnné obsahující vstupní čísla, ‹base› obsahuje základ. Výsledek vraťte příkazem ‹return› return 0; /* C */ } ## r. Řešené úlohy ### 1. [‹palindrome›] Implementujte predikát ‹is_binary_palindrome›, který o zadaném čísle rozhodne, zda je jeho binární reprezentace palindromem. bool is_binary_palindrome( unsigned n ) /* C */ { Řešení pište sem. return false; /* C */ } ### 2. [‹largest›] Implementujte podprogram ‹largest_digit›, který pro zadané číslo ‹n› vrátí jeho nejvyšší číslici při základu ‹base›. unsigned largest_digit( unsigned n, unsigned base ) /* C */ { Řešení pište sem. return 0; /* C */ } ### 3. [‹factors›] Implementujte podprogram ‹factor_count›, který vrátí počet všech činitelů v prvočíselném rozkladu zadaného kladného čísla. Opakující se prvočinitele započítejte opakovaně. unsigned factor_count( unsigned n ) /* C */ { assert( n > 0 ); Řešení pište sem. return 0; /* C */ } ### 4. [‹primes›] Implementujte podprogram ‹prime_count›, který vrátí počet unikátních činitelů v prvočíselném rozkladu zadaného kladného čísla. Opakující se prvočinitele započítejte pouze jednou. unsigned prime_count( unsigned n ) /* C */ { assert( n > 0 ); Řešení pište sem. return 0; /* C */ } ### 5. [‹transpose›] Označíme-li postupně bity ve slově tak, že nejméně významný je ‹0› a nejvýznamnější je ‹F›, pak slovo reprezentuje následující bitové čtvercové matice o velikostech 4×4 až 1×1: F E D C 8 7 6 3 2 0 B A 9 8 5 4 3 1 0 7 6 5 4 2 1 0 3 2 1 0 Implementujte podprogram ‹transpose›, který zadanou matici transponuje, tj. vrátí slovo reprezentující jednu z matic: F B 7 3 8 5 2 3 1 0 E A 6 2 7 4 1 2 0 D 9 5 1 6 3 0 C 8 4 0 Velikost jedné strany matice je také argumentem podprogramu. Můžete předpokládat, že se bude jednat o číslo mezi 1 a 4. Pro velikosti menší než 4 nevyužité bity na vstupu ignorujte a ve výsledku nechť jsou nulové. unsigned transpose( unsigned m, int size ) /* C */ { Řešení pište sem. return 0; /* C */ } ### 6. [‹balanced›] Vyvážená trojková soustava nepoužívá číslice s hodnotami 0, 1 a 2, nýbrž 0, 1 a -1 (zapisované zde 0, ‹+› a ‹-›). Například číslo dvě se v ní representuje jako ‹+-›: ⟦1·3¹ + (−1)·3⁰⟧. Implementujte podprogram ‹balanced_digits›, který vrátí dvě 8bitová čísla zabalená (jako v ‹p4_packed›) do jednoho slova: spodní slabika bude obsahovat počet číslic ‹+› a horní počet číslic ‹-› ve vyváženětrojkovém zápisu zadaného «celého» čísla. unsigned balanced_digits( int n ) /* C */ { Řešení pište sem. return 0; /* C */ } ## v. Volitelné úlohy ### 1. [‹digits›] Implementujte podprogram ‹digit_sum›, který spočítá ciferný součet čísla při zadaném základu. Můžete předpokládat, že základ je alespoň dva. unsigned digit_sum( unsigned n, unsigned base ) /* C */ { Řešení pište sem. return 0; /* C */ } ### 2. [‹rotate›] Implementujte podprogram ‹rotate›, který provede bitovou rotaci zadaného slova o zadaný počet pozic. Kladný počet provádí rotaci vlevo, záporný vpravo. unsigned rotate( unsigned word, int amount ) /* C */ { Řešení pište sem. return 0; /* C */ } # K. Vzorová řešení ## 1. Týden 1 ### 01.1. [‹reverse›] put 0x0001 → t1 ; maska zdrojového bitu ; tiny put 0x8000 → t2 ; maska cílového bitu put 0 → rv loop: and l1, t1 → t3 ; zjištění zdrojového bitu jz t3, zero or rv, t2 → rv ; nastavení cílového bitu zero: shl t1, 1 → t1 ; posuv obou masek shr t2, 1 → t2 jz t2, check ; skončit, když cílový bit vypadl z registru jmp loop $$tex \blank ### 01.2. [‹hamming›] put 0 → rv ; tiny put 0x8000 → t3 ; maska srovnávaného bitu loop: and t3, l1 → t1 ; hodnoty srovnávaných bitů and t3, l2 → t2 ne t1, t2 → t4 ; zvýšit čítač, pokud se bity nerovnají add rv, t4 → rv shr t3, 1 → t3 ; posunout masku srovnávaného bitu jz t3, check ; konec, pokud maskovaný bit vypadl z registru jmp loop $$tex \blank ### 01.3. [‹packed›] add l1, l2 → rv ; součet spodní slabiky ; tiny and rv, 0x00ff → rv and l1, 0xff00 → l1 ; vynulovat spodní slabiky vstupů and l2, 0xff00 → l2 add l1, l2 → t1 ; součet horních slabik or t1, rv → rv ; promítnout horní součet do výsledku jmp check $$tex \blank ### 01.4. [‹bitswap›] put 0x0000 → rv ; tiny shl 1, l2 → t2 ; masky zadaných bitů shl 1, l3 → t3 and l1, t2 → t4 ; extrakce zadaných bitů and l1, t3 → t5 xor t2, -1 → t6 ; vynulování zadaných bitů and l1, t6 → rv xor t3, -1 → t6 and rv, t6 → rv jz t4, zero ; nastavení bitů or rv, t3 → rv zero: jz t5, check or rv, t2 → rv jmp check $$tex \blank ### 01.5. [‹collatz›] put 0 → rv ; vynulovat výstupní registry ; tiny put 0 → l6 check_max: ugt l1, l6 → t1 ; ověřit a nastavit nové maximum jz t1, loop copy l1 → l6 loop: eq l1, 1 → t1 ; ukončit při jedničce jnz t1, check add rv, 1 → rv ; jinak zvýšit čítač and l1, 1 → t1 ; test sudosti jz t1, even mul l1, 3 → l1 ; n = 3n + 1 add l1, 1 → l1 jmp check_max ; možná jsme našli nové maximum even: udiv l1, 2 → l1 ; n = n / 2 jmp loop ; při dělení jsme jistě maximum nenašli $$tex \blank ### 01.6. [‹shift›] put 0xffff → t2 ; do t2 nachystáme masku ; tiny sub 15, l3 → t3 ; počet horních nulových bitů shl t2, t3 → t2 ; vynulujeme horní bity ; tiny shr t2, t3 → t2 shr t2, l2 → t2 ; vynulujeme spodní bity ; tiny shl t2, l2 → t2 xor t2, -1 → t3 ; inverzní maska ; tiny and rv, t2 → t4 ; tiny shl t4, 1 → t4 and t4, t2 → t4 and rv, t3 → rv ; tiny or rv, t4 → rv jmp check ; tiny # T. Technické informace Tato kapitola obsahuje informace o technické realizaci předmětu, a to zejména: • jak se pracuje s kostrami úloh, • jak sdílet obrazovku (terminál) ve cvičení, • jak se odevzdávají úkoly, • kde najdete výsledky testů a jak je přečtete, • kde najdete hodnocení kvality kódu (učitelské recenze), • jak získáte kód pro vzájemné recenze. ## Informační systém Informační systém tvoří primární „rozhraní“ pro stahování studijních materiálů, odevzdávání řešení, získání výsledků vyhodnocení a čtení recenzí. Zároveň slouží jako hlavní komunikační kanál mezi studenty a učiteli, prostřednictvím diskusního fóra. ### Diskusní fórum Máte-li dotazy k úlohám, organizaci, atp., využijte k jejich položení prosím vždy přednostně diskusní fórum.¹ Ke každé kapitole a ke každému příkladu ze sady vytvoříme samostatné vlákno, kam patří dotazy specifické pro tuto kapitolu nebo tento příklad. Pro řešení obecných organizačních záležitostí a technických problémů jsou podobně v diskusním fóru nachystaná vlákna. Než položíte libovolný dotaz, přečtěte si relevantní část dosavadní diskuse – je možné, že na stejný problém už někdo narazil. Máte-li ve fóru dotaz, na který se Vám nedostalo do druhého pracovního dne reakce, připomeňte se prosím tím, že na tento svůj příspěvek odpovíte. Máte-li dotaz k výsledku testu, nikdy tento výsledek nevkládejte do příspěvku (podobně nikdy nevkládejte části řešení příkladu). Učitelé mají přístup k obsahu Vašich poznámkových bloků, i k Vámi odevzdaným souborům. Je-li to pro pochopení kontextu ostatními čtenáři potřeba, odpovídající učitel chybějící informace doplní dle uvážení. ¹ Nebojte se do fóra napsat – když si s něčím nevíte rady a/nebo nemůžete najít v materiálech, rádi Vám pomůžeme nebo Vás nasměrujeme na místo, kde odpověď naleznete. ### Stažení koster Kostry naleznete ve «studijních materiálech» v ISu: ‹Student› → ‹PB111› → ‹Studijní materály› → ‹Učební materiály›. Každá kapitola má vlastní složku, pojmenovanou ‹00› (tento úvod a materiály k nultému cvičení), ‹01› (první běžná kapitola), ‹02›, …, ‹12›. Veškeré soubory stáhnete jednoduše tak, že na složku kliknete pravým tlačítkem a vyberete možnost ‹Stáhnout jako ZIP›. Stažený soubor rozbalte a můžete řešit. ### Odevzdání řešení Vypracované příklady můžete odevzdat do «odevzdávárny» v ISu: ‹Student› → ‹PB111› → ‹Odevzdávárny›. Pro přípravy používejte odpovídající složky s názvy ‹01›, …, ‹12›. Pro příklady ze sad pak ‹s1_a_csv›, atp. (složky začínající ‹s1› pro první, ‹s2› pro druhou a ‹s3› pro třetí sadu). Soubor vložíte výběrem možnosti ‹Soubor – nahrát› (první ikonka na liště nad seznamem souborů). Tímto způsobem můžete najednou nahrát souborů několik (například všechny přípravy z dané kapitoly). Vždy se ujistěte, že vkládáte správnou verzi souboru (a že nemáte v textovém editoru neuložené změny). «Pozor!» Všechny vložené soubory se musí jmenovat stejně jako v kostrách, jinak nebudou rozeznány (IS při vkládání automaticky předřadí Vaše UČO – to je v pořádku, název souboru po vložení do ISu «neměňte») . O každém odevzdaném souboru (i nerozeznaném) se Vám v poznámkovém bloku ‹log› objeví záznam. Tento záznam i výsledky testu syntaxe by se měl objevit do několika minut od odevzdání (nemáte-li ani po 15 minutách výsledky, napište prosím do diskusního fóra). Archiv všech souborů, které jste úspěšně odevzdali, naleznete ve složce ‹Private› ve studijních materiálech (‹Student› → ‹PB111› → ‹Studijní materiály› → ‹Private›). ### Výsledky automatických testů Automatickou zpětnou vazbu k odevzdaným úlohám budete dostávat prostřednictvím tzv. «poznámkových bloků» v ISu. Ke každé odevzdávárně existuje odpovídající poznámkový blok, ve kterém naleznete aktuální výsledky testů. Pro přípravy bude blok vypadat přibližně takto: testing verity of submission from 2025-09-17 22:43 CEST subtest p1_foo passed [ 1] subtest p2_bar failed subtest p3_baz failed subtest p4_quux passed [ 1] subtest p5_wibble passed [ 1] subtest p6_xyzzy failed {bližší popis chyby} verity test failed testing syntax of submission from 2025-09-17 22:43 CEST subtest p1_foo passed subtest p2_bar failed {bližší popis chyby} subtest p3_baz failed {bližší popis chyby} subtest p4_quux passed subtest p5_wibble passed subtest p6_xyzzy passed syntax test failed testing sanity of submission from 2025-09-17 22:43 CEST subtest p1_foo passed [ 1] subtest p2_bar failed subtest p3_baz failed subtest p4_quux passed [ 1] subtest p5_wibble passed [ 1] subtest p6_xyzzy passed [ 1] sanity test failed best submission: 2025-09-17 22:43 CEST worth *7 point(s) Jednak si všimněte, že každý odstavec má «vlastní časové razítko», které určuje, ke kterému odevzdání daný výstup patří. Tato časová razítka nemusí být stejná. V hranatých závorkách jsou uvedeny dílčí body, za hvězdičkou na posledním řádku pak celkový bodový zisk za tuto kapitolu. Také si všimněte, že ‹best submission› se vztahuje na jedno konkrétní odevzdání jako celek: v situaci, kdy odstavec „verity“ a odstavec „sanity“ nemají stejné časové razítko, «nemusí» být celkový bodový zisk součtem všech dílčích bodů. O konečném zisku rozhoduje vždy poslední odevzdání před příslušným termínem (opět jako jeden celek).¹ Výstup pro příklady ze sad je podobný, uvažme například: testing verity of submission from 2025-10-11 21:14 CEST subtest foo-small passed subtest foo-large passed verity test passed [ 7] testing syntax of submission from 2025-10-14 23:54 CEST subtest build passed syntax test passed testing sanity of submission from 2025-10-14 23:54 CEST subtest foo passed sanity test passed best submission: 2025-10-11 21:14 CEST worth *7 point(s) Opět si všimněte, že časová razítka se mohou lišit (a v případě příkladů ze sady bude k této situaci docházet poměrně často, vždy tedy nejprve ověřte, ke kterému odevzdání se který odstavec vztahuje a pak až jej dále interpretujte). ¹ Můžete si tak odevzdáním nefunkčních řešení na poslední chvíli snížit výsledný bodový zisk. Uvažte situaci, kdy máte v pátek 4 body za sanity příkladů p1, p2, p3, p6 a 1 bod za verity p1, p2. V sobotu odevzdáte řešení, kde p1 neprochází sanity testem, ale p4 ano a navíc projdou verity testy příklady p4 a p6. Váš výsledný zisk bude 5.5 bodu. Tento mechanismus Vám nikdy nesníží výsledný bodový zisk pod již jednou dosaženou hranici „best submission“. ### Další poznámkové bloky Blok ‹corr› obsahuje záznamy o manuálních bodových korekcích (např. v situaci, kdy byl Váš bodový zisk ovlivněn chybou v testech). Podobně se zde objeví záznamy o penalizaci za opisování. Blok ‹log› obsahuje záznam o všech odevzdaných souborech, včetně těch, které nebyly rozeznány. Nedostanete-li po odevzdání příkladu výsledek testů, ověřte si v tomto poznámkovém bloku, že soubor byl správně rozeznán. Blok ‹misc› obsahuje záznamy o Vaší aktivitě ve cvičení (netýká se bodů za vzájemné recenze ani vnitrosemestrální testy). Nemáte-li před koncem cvičení, ve kterém jste řešili příklad u tabule, záznam v tomto bloku, připomeňte se svému cvičícímu. Konečně blok ‹sum› obsahuje souhrn bodů, které jste dosud získali, a které ještě získat můžete. Dostanete-li se do situace, kdy Vám ani zisk všech zbývajících bodů nebude stačit pro splnění podmínek předmětu, tento blok Vás o tom bude informovat. Tento blok má navíc přístupnou statistiku bodů – můžete tak srovnat svůj dosavadní bodový zisk se svými spolužáky. Je-li blok ‹sum› v rozporu s pravidly uvedenými v tomto dokumentu, přednost mají pravidla zde uvedená. Podobně mají v případě nesrovnalosti přednost dílčí poznámkové bloky. Dojde-li k takovéto neshodě, informujte nás o tom prosím v diskusním fóru. Případná známka uvedená v poznámkovém bloku ‹sum› je podobně pouze informativní – rozhoduje vždy známka zapsaná v hodnocení předmětu. ## Studentský server ‹aisa› Použití serveru ‹aisa› pro odevzdávání příkladů je zcela volitelné a vše potřebné můžete vždy udělat i prostřednictvím ISu. Nevíte-li si s něčím z níže uvedeného rady, použijte IS. Na server ‹aisa› se přihlásíte programem ‹ssh›, který je k dispozici v prakticky každém moderním operačním systému (v OS Windows skrze WSL¹ – Windows Subsystem for Linux). Konkrétní příkaz (za ‹xlogin› doplňte ten svůj): $ ssh xlogin@aisa.fi.muni.cz Program se zeptá na heslo: použijte to fakultní (to stejné, které používáte k přihlášení na ostatní fakultní počítače, nebo např. ve ‹fadmin›-u nebo fakultním ‹gitlab›-u). ¹ Jako alternativu, nechcete-li z nějakého důvodu WSL instalovat, lze použít program ‹putty›. ### Pracovní stanice Veškeré instrukce, které zde uvádíme pro použití na stroji ‹aisa› platí beze změn také na libovolné školní UNIX-ové pracovní stanici (tzn. z fakultních počítačů není potřeba se hlásit na stroj ‹aisa›, navíc mají sdílený domovský adresář, takže svoje soubory z tohoto serveru přímo vidíte, jako by byly uloženy na pracovní stanici). ### Stažení koster Aktuální zdrojový balík stáhnete příkazem: $ pb111 update Stažené soubory pak naleznete ve složce ‹~/pb111›. Je bezpečné tento příkaz použít i v případě, že ve své kopii již máte rozpracovaná řešení – systém je při aktualizaci nepřepisuje. Došlo-li ke změně kostry u příkladu, který máte lokálně modifikovaný, aktualizovanou kostru naleznete v souboru s dodatečnou příponou ‹.pristine›, např. ‹01/e2_concat.cpp.pristine›. V takovém případě si můžete obě verze srovnat příkazem ‹diff›: $ diff -u e2_concat.cpp e2_concat.cpp.pristine Případné relevantní změny si pak již lehce přenesete do svého řešení. Krom samotného zdrojového balíku Vám příkaz ‹pb111 update› stáhne i veškeré recenze (jak od učitelů, tak od spolužáků). To, že máte k dispozici nové recenze, uvidíte ve výpisu. Recenze najdete ve složce ‹~/pb111/reviews›. ### Odevzdání řešení Odevzdat vypracované (nebo i rozpracované) řešení můžete ze složky s relevantními soubory takto: $ cd ~/pb111/01 $ pb111 submit Přidáte-li přepínač ‹--wait›, příkaz vyčká na vyhodnocení testů fáze „syntax“ a jakmile je výsledek k dispozici, vypíše obsah příslušného poznámkového bloku. Chcete-li si ověřit co a kdy jste odevzdali, můžete použít příkaz $ pb111 status nebo se podívat do informačního systému (blíže popsáno v sekci T.1). «Pozor!» Odevzdáváte-li stejnou sadu příprav jak v ISu tak prostřednictvím příkazu ‹pb111›, ujistěte se, že odevzdáváte vždy všechny příklady. ### Sdílení terminálu Řešíte-li příklad typu ‹r› ve cvičení, bude se Vám pravděpodobně hodit režim sdílení terminálu s cvičícím (který tak bude moct promítat Váš zdrojový kód na plátno, případně do něj jednoduše zasáhnout). Protože se sdílí pouze terminál, budete se muset spokojit s negrafickým textovým editorem (doporučujeme použít ‹micro›, případně ‹vim› umíte-li ho ovládat). Spojení navážete příkazem: $ pb111 beamer Protože příkaz vytvoří nové sezení, nezapomeňte se přesunout do správné složky příkazem ‹cd ~/pb111/NN›. ## Kostry úloh Pracujete-li na studentském serveru ‹aisa›, můžete pro překlad jednotlivých příkladů použít přiložený soubor ‹makefile›, a to zadáním příkazu $ make příklad.bin kde ‹příklad› je název souboru bez přípony (např. tedy ‹make p1_fib.bin›). Tento příkaz přeloží program překladačem ‹tinycc› a rovnou jej také spustí, tzn. selže-li nějaký test, tuto informaci rovnou uvidíte na obrazovce. Selže-li některý krok, další už se provádět nebude. Povede-li se překlad v prvním kroku, v pracovním adresáři naleznete spustitelný soubor s názvem ‹příklad.bin›, se kterým můžete dále pracovat (např. jej načíst do virtuálního stroje ‹tinyvm.py› z kapitoly B). Existující přeložené soubory můžete smazat příkazem ‹make clean› (vynutíte tak jejich opětovný překlad a spuštění všech kontrol). ### Textový editor Na stroji ‹aisa› je k dispozici jednoduchý editor ‹micro›, který má podobné ovládání jako klasické textové editory, které pracují v grafickém režimu, a který má slušnou podporu pro práci se zdrojovým kódem. Doporučujeme zejména méně pokročilým. Další možností jsou samozřejmě pokročilé editory ‹vim› a ‹emacs›. Mimo lokálně dostupné editory si můžete ve svém oblíbeném editoru, který máte nainstalovaný u sebe, nastavit režim vzdálené editace (použitím protokolu ‹ssh›). Minimálně ve VS Code je takový režim k dispozici a je uspokojivě funkční. ### Vlastní prostředí Prozatím je překladač ‹tinycc› k dispozici pouze na stroji ‹aisa›. Jakmile to bude možné, zveřejníme zdrojové kódy a/nebo již přeložené binárky tak, abyste si je mohli spustit i lokálně. # U. Doporučení k zápisu kódu Tato sekce rozvádí obecné principy zápisu kódu s důrazem na čitelnost a korektnost. Samozřejmě žádná sada pravidel nemůže zaručit, že napíšete dobrý (korektní a čitelný) program, o nic více, než může zaručit, že napíšete dobrou povídku nebo namalujete dobrý obraz. Přesto ve všech těchto případech pravidla existují a jejich dodržování má obvykle na výsledek pozitivní dopad. Každé pravidlo má samozřejmě nějaké výjimky. Tyto jsou ale výjimkami proto, že nastávají «výjimečně». Některá pravidla připouští výjimky častěji než jiná: ### 1. Dekompozice Vůbec nejdůležitější úlohou programátora je rozdělit problém tak, aby byl schopen každou část správně vyřešit a dílčí výsledky pak poskládat do korektního celku. A. Kód musí být rozdělen do ucelených jednotek (kde jednotkou rozumíme funkci, typ, modul, atd.) přiměřené velikosti, které lze studovat a používat nezávisle na sobě. B. Jednotky musí být od sebe odděleny jasným «rozhraním», které by mělo být jednodušší a uchopitelnější, než kdybychom použití jednotky nahradili její definicí. C. Každá jednotka by měla mít «jeden» dobře definovaný účel, který je zachycený především v jejím pojmenování a případně rozvedený v komentáři. D. Máte-li problém jednotku dobře pojmenovat, může to být známka toho, že dělá příliš mnoho věcí. E. Jednotka by měla realizovat vhodnou «abstrakci», tzn. měla by být «obecná» – zkuste si představit, že dostanete k řešení nějaký jiný (ale dostatečně příbuzný) problém: bude Vám tato konkrétní jednotka k něčemu dobrá, aniž byste ji museli (výrazně) upravovat? F. Má-li jednotka parametr, který fakticky identifikuje místo ve kterém ji používáte (bez ohledu na to, je-li to z jeho názvu patrné), je to často známka špatně zvolené abstrakce. Máte-li parametr, který by bylo lze pojmenovat ‹called_from_bar›, je to jasná známka tohoto problému. G. Daný podproblém by měl být vyřešen v programu pouze jednou – nedaří-li se Vám sjednotit různé varianty stejného nebo velmi podobného kódu (aniž byste se uchýlili k taktice z bodu d), může to být známka nesprávně zvolené dekompozice. Zkuste se zamyslet, není-li možné problém rozložit na podproblémy jinak. ### 2. Jména Dobře zvolená jména velmi ulehčují čtení kódu, ale jsou i dobrým vodítkem při dekompozici a výstavbě abstrakcí. A. Všechny entity ve zdrojovém kódu nesou «anglická» jména. Angličtina je univerzální jazyk programátorů. B. Jméno musí být «výstižné» a «popisné»: v místě použití je obvykle jméno náš hlavní (a často jediný) «zdroj informací» o jmenované entitě. Nutnost hledat deklaraci nebo definici (protože ze jména není jasné, co volaná funkce dělá, nebo jaký má použitá proměnná význam) čtenáře nesmírně zdržuje.¹ C. Jména «lokálního» významu mohou být méně informativní: je mnohem větší šance, že význam jmenované entity si pamatujeme, protože byla definována před chvílí (např. lokální proměnná v krátké funkci). D. Obecněji, informační obsah jména by měl být přímo úměrný jeho rozsahu platnosti a nepřímo úměrný frekvenci použití: globální jméno musí být informativní, protože jeho definice je „daleko“ (takže si ji už nepamatujeme) a zároveň se nepoužívá příliš často (takže si nepamatujeme ani to, co jsme se dozvěděli, když jsme ho potkali naposled). E. Jméno parametru má dvojí funkci: krom toho, že ho používáme v těle funkce (kde se z pohledu pojmenování chová podobně jako lokální proměnná), slouží jako dokumentace funkce jako celku. Pro parametry volíme popisnější jména, než by zaručovalo jejich použití ve funkci samotné – mají totiž dodatečný globální význam. F. Některé entity mají ustálené názvy – je rozumné se jich držet, protože čtenář automaticky rozumí jejich významu, i přes obvyklou stručnost. Zároveň je potřeba se vyvarovat použití takovýchto ustálených jmen pro nesouvisející entity. Typickým příkladem jsou iterační proměnné ‹i› a ‹j›. G. Jména s velkým rozsahem platnosti by měla být také «zapamatovatelná». Je vždy lepší si přímo vzpomenout na jméno funkce, kterou právě potřebuji, než ho vyhledávat (podobně jako je lepší znát slovo, než ho jít hledat ve slovníku). H. Použitý slovní druh by měl odpovídat druhu entity, kterou pojmenovává. Proměnné a typy pojmenováváme přednostně podstatnými jmény, funkce přednostně slovesy. I. Rodiny příbuzných nebo souvisejících entit pojmenováváme podle společného schématu (‹table_name›, ‹table_size›, ‹table_items› – nikoliv např. ‹items_in_table›; ‹list_parser›, ‹string_parser›, ‹set_parser›; ‹find_min›, ‹find_max›, ‹erase_max› – nikoliv např. ‹erase_maximum› nebo ‹erase_greatest› nebo ‹max_remove›). J. Jména by měla brát do úvahy kontext, ve kterém jsou platná. Neopakujte typ proměnné v jejím názvu (‹cars›, nikoliv ‹list_of_cars› ani ‹set_of_cars›) nemá-li tento typ speciální význam. Podobně jméno nadřazeného typu nepatří do jmen jeho metod (třída ‹list› by měla mít metodu ‹length›, nikoliv ‹list_length›). K. Dávejte si pozor na překlepy a pravopisné chyby. Zbytečně znesnadňují pochopení a (zejména v kombinaci s našeptávačem) lehce vedou na skutečné chyby způsobené záměnou podobných ale jinak napsaných jmen. Navíc kód s překlepy v názvech působí značně neprofesionálně. ¹ Nejde zde pouze o samotný fakt, že je potřeba něco vyhledat. Mohlo by se zdát, že tento problém řeší IDE, které nás umí „poslat“ na příslušnou definici samo. Hlavní zdržení ve skutečnosti spočívá v tom, že musíme přerušit čtení předchozího celku. Na rozdíl od počítače je pro člověka „zanořování“ a zejména pak „vynořování“ na pomyslném zásobníku docela drahou operací. ### 3. Stav a data Udržet si přehled o tom, co se v programu děje, jaké jsou vztahy mezi různými stavovými proměnnými, co může a co nemůže nastat, je jedna z nejtěžších částí programování. TBD: Vstupní podmínky, invarianty, … ### 4. Řízení toku Přehledný, logický a co nejvíce lineární sled kroků nám ulehčuje pochopení algoritmu. Časté, komplikované větvení je naopak těžké sledovat a odvádí pozornost od pochopení důležitých myšlenek. TBD. ### 5. Volba algoritmů a datových struktur TBD. ### 6. Komentáře Nejde-li myšlenku předat jinak, vysvětlíme ji doprovodným komentářem. Čím těžší myšlenka, tím větší je potřeba komentovat. A. Podobně jako jména entit, komentáře které jsou součástí kódu píšeme anglicky.² B. Případný komentář jednotky kódu by měl vysvětlit především „co“ a „proč“ (tzn. jaký plní tato jednotka účel a za jakých okolností ji lze použít). C. Komentář by také neměl zbytečně duplikovat informace, které jsou k nalezení v hlavičce nebo jiné „nekomentářové“ části kódu – jestli máte například potřebu komentovat parametr funkce, zvažte, jestli by nešlo tento parametr lépe pojmenovat nebo otypovat. D. Komentář by «neměl» zbytečně duplikovat samotný spustitelný kód (tzn. neměl by se zdlouhavě zabývat tím „jak“ jednotka vnitřně pracuje). Zejména jsou nevhodné komentáře typu „zvýšíme proměnnou i o jedna“ – komentář lze použít k vysvětlení «proč» je tato operace potřebná – co daná operace dělá si může kažďý přečíst v samotném kódu. ² Tato sbírka samotná představuje ústupek z tohoto pravidla: smyslem našich komentářů je naučit Vás poměrně těžké a často nové koncepty, a její cirkulace je omezená. Zkušenost z dřívějších let ukazuje, že pro studenty je anglický výklad značnou bariérou pochopení. Přesto se snažte vlastní kód komentovat anglicky – výjimku lze udělat pouze pro rozsáhlejší komentáře, které byste jinak nedokázali srozumitelně formulovat. V praxi je angličtina zcela běžně bezpodmínečně vyžadovaná. ### 7. Formální úprava TBD.