PB111 Nízkourovňové programování P. Ročkai & A. Matoušek Část A: Pravidla a organizace ................................ 1 Část 2 Část B: Úvod .............................................. 5 Část K Část 1: Výpočetní stroj .................................... 9 Část T Lokální proměnné, řízení toku ....................... 12 Vzorová řešení .................................... 17 Technické informace ............................... 18 Část U: Doporučení k zápisu kódu 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í verzi1 (ve všech variantách) můžete získat dvěma způsoby: 1. Ve studijních materiálech2 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 sl 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 1.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.mum.cz/auth/el/fi/1aro2025/PB111 /um/ Část A: Pravidla a organizace A.1: 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 neodkladali 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 vně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ě. A,1,1 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 A.1.2 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.3 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. A.1,3 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): Pravidla jsou velmi podobná těm v kurzu IB111, ale přesto si je pozorně přečtěte. 1/20 • „#X" - číslo týdne v semestru, • „cvB" - 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. Nej dů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 cv 0 17 18 19 20 01/v 21 22 01/p 23 #2 cv 1 24 S1/1 25 26 s1/2 bř 27 02/v =zen 28 s1/3 Po Út St Čt Pá So Ne #2 1 02/p 2 #3 cv 2 3 s1/4 4 5 s1/5 6 03/v 7 s1/6 8 03/p 9 #4 cv 3 10 s1/7 11 12 s1/8 13 04/v 14 s1/9 15 04/p 16 #5 cv 4 17 si/10 18 19 si/11 20 05/v 21 si/12 22 05/p 23 #6 cv 5 24 s2/1 25 26 s2/2 27 06/v 28 s2/3 29 06/p 30 #7 cv 6 31 s2/4 duben Po Út St Čt Pá So Ne #7 1 2 s2/5 3 07/v 4 s2/6 5 07/p 6 #8 cv 7 7 s2/7 8 9 s2/8 10 08/v 11 s2/9 12 08/p 13 #9 cv 8 14 S2/10 15 16 S2/11 17 09/v 18 S2/12 19 09/p 20 #10 cv 9 21 s3/1 22 23 s3/2 24 10/v 25 s3/3 26 10/P 27 #11 cv10 28 s3/4 29 30 s3/5 kv šten Po Út St Čt Pá So Ne #11 1 sv 11/v 2 s3/6 3 11/p 4 #12 cv11 5 s3/7 6 7 s3/8 8 sv 12/v 9 s3/9 10 12/p 11 #13 cv12 12 S3/10 13 14 S3/11 15 16 S3/12 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 A. 2: Hodnocení Abyste předmět úspěšně ukončili, musíte v každém bloku4 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 4x50 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ě 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 3x50 bodů z bloků v semestru. odpovídala očekávané distribuci dle ECTS.5 známka předběžné minimum po vyhodnocení semestru A 360 90. percentu + 60 B 320 65. percentu + 60 C 280 35. percentu + 60 D 240 10. percentu + 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 účast6 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). A.3: 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. 5 Percentíl budeme počítat z bodů v semestru (první tří 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 3x50 bodů). 6 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). Memůž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-2x za semestr. 2/20 PB111 Nízkoúrovňové programování, 21. února 2025 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). A,3,1 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. A.4: 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úspěš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í). A.5: 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. A,5,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_oueens). 2. příkazem pb111 submit sN_úkol ve složce ~/pb111/sN, např. pb111 sub-mit s1_a_gueens. Podrobnější instrukce naleznete opět v kapitole T. A.5.2 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í 3/20 se tedy maximálně čtyři úspěšně vyřešené úkoly). A,5,3 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, kdybyste 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). A.6: 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). A.6.1 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. 7 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. A. 7: 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émaně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í. Žá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ří - at už z přednášky, z této sbírky, nebo kód svých spolužáků, který uvidíte ve cvičení. 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áni 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í). 4/20 PB111 Nízkoúrovňové programování, 21. února 2025 Část 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ízkourovň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. B.1: 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.8 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. B.2: 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 11 až 17 (local), ° registry tj_ až tB (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 16bi-tové celé číslo (bez znaménka), které přesně určuje právě jednu pamě- 8 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). ťovou buňku, přitom každá taková buňka obsahuje celé číslo v rozsahu 8 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 po 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í baltu (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. smpd), ° dělení bez znaménka (udiv a ympd), 4. operace pro srovnání dvou hodnot: ° rovnost (eg, ne), ° znaménkové ostré nerovnosti (slt, sgt), ° znaménkové neostré nerovnosti (sle. soe). ° bezznaménkové ostré (ult, ygt), a konečně ° bezznaménkové neostré (ule, uge), 5. bitové operace: ° logické operace and, pr a xpr 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ý. B.3: 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 ry 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 11: put 0 -» 11 ; vynuluj registr 11 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í 5/20 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 instrukce3 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. B.d: Demonstrace (ukázky) B.d.1 rtinyvml 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 převede jednu instrukci. Vstupními parametry jscu: 1. p_c 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 B 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). 9 Pro typy int a unsiqned je konkrétní rozsah přípustných hodnot daný implementací - na mnoha systémech jsou tyto typy 32bítové. def step( pc: int, regs: list[ int ], mem: list[ int ] ) -> tuple[ int, int ]: Následující tvrzení popisují základní vstupní podmínky. assert 3 <= pc < 65536 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 pp_. V šestnáctkcvém zápisu tedy epcode = 3x12 značí operaci 2 z kategorie 1. opcode = mem[pc] 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 3x82, je výstupním registrem ten s číslem 8 (ti) a (prvním) vstupním registrem je registr číslo 2, totiž 12. rrout = mem[ pc + 1 ] // 16 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 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ýpečet streje žádný vliv, není tedy nutné ji blíže zkeumat. Můžete si ji ale přizpůsobit dle vlastníhe vkusu nebe pptřeby. print_state( pc, regs, cat, op, imm, rrout, r_1, r_2 ) 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 == Bxee and regs[ r_1 ] == 3: tt asrt return pc, ERROR if opcode == Oxef: t 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 p_yt 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 == 0xBc: t copy regs[ rrout ] = regs[ r_1 ] if opcode == BxBd: t put regs[ rrout ] = imm if opcode == BxBe: t sext regs[ rrout ] = as_signed( regs[ r_1 ], 8 ) % 65536 Dále do kategorie B 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 [ BxB3, 0x04 ]: t st, stb addr = ( addr + regs[ rrout ] ) % 65536 if opcode == 3x33: t stb mem[ addr ] = regs[ r_1 ] % 256 if opcode == 3x34: t st mem[ addr + 3 ] = 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ýml nulami. if opcode in [ 0x01, 0x02 ]: t ld, ldb addr = ( addr + regs[ r_1 ] ) % 65536 if opcode == 0x01: t ldb regs[ rrout ] = mem[ addr ] if opcode == 0x02: t ld regs[ rrout ] = mem[ addr ] * 256 + mem[ addr + 1 ] Konečně jsou v kategorii 0 operace push a p_pp_ pro práci se zásobníkem. 6/20 PB111 Nízkoúrovňové programování, 21. února 2025 Jejich efekt je implementován pomocnými procedurami push a p_op_ 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: t push push( regs, mem, regs[ r_1 ] ) if opcode == 0x0b: t 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 == Oxfe: t call 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 == Oxff: t ret 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 == Oxf and ( op == 0 or t jmp op == 1 and regs[ r_1 ] == 0 or t jz op == 2 and regs[ r_1 ] != 0 ): tt 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: 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 - bud ve variantě se dvěma registry, nebo srovnání vstupního registru s přímým operandem. if cat == 0xa: 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 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: regs[ 15 ] = ( regs[ 15 ] - 2 ) % 65536 mem[ regs[ 15 ] ] = val def pop( regs: list[ int ], mem: list[ int ] ) -> int: 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 {-2b~1,2Í,~1), 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: 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 oo_1 a oo_2 v rozsahu (0,216), výsledek je v temže rozsahu. def arith( op: int, op_1: int, op_2: int ) -> int: 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) í(a) - t(b) = t(a - b) í(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 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 oř op == 0x7: t signed div/rem dividend = as_signed( op_1, 16 ) divisor = as_signed( op_2, 16 ) guot, rem = divmod( dividend, divisor ) if ( dividend > 0 ) != ( divisor > 0 ) and rem != 0: rem -= divisor if guot < 0 and rem != 0: guot += 1 return ( guot if op == 0x5 else rem ) % 65536 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, oř nebo xor), čím získá odpovídající bit výsledku. Operandy jsou vždy 16bitové. if op in [ 0xa, 0xb, 0xc ]: result = 0 for idx in range(16): bitJ = opj // 2 ** idx % 2 bit_2 = op_2 // 2 ** idx % 2 7/20 if op == 0xa: oit_r = bit_1 == 1 and bit_2 == 1 if op == 0xb: oit.r = bitJ == 1 oř bit_2 == 1 if op == Bxc: bit.r = ( bitJ == 1 ) != ( bit_2 == 1 ) result += bit.r * 2 ** ídx return result 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: "eturn ( op_1 * 2 ** op_2 ) % 65536 if op == 0xe: ~eturn ( op_1 112** op_2 ) % 65536 if op == 0xf: return ( as_signed( opj, 16 ) // 2 ** op_2 ) % 65536 assert Falše Čistá funkce compare realizuje aritmetická srovnání. Krom rovnosti (= , =f) 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 vetší, než kódy čísel kladných, např. 16bitové kódování -1 je Bxffff, přitom 16bitové kódování +1 je 3x0001, výsledek Bxffff < 0x0001 ale jisté v tomtc kontextu nedává smysl. def compare( op: int, arg_1: int, arg_2: int ) -> int: sig_1 = as_signed( arg_1, 16 ) sig-2 = as_signed( arg_2, 16 ) if op == 0X0 result = arg_1 == arg if op == 0xf result = arg_1 != arg if op == 0x1 result = arg_1 < arg if op == 0x2 result = arg_1 <= arg if op == 0x3 result = arg_1 > arg if op == 9x4 result = arg_1 >= arg if op == Bxa result = sig_1 < s-: if op == 0xb result = slg_1 <= sig if op == 0xc result = sig_1 > sig if op == 0xd result = sig_1 >= sig "eturn 1 if result else 0 Tím j e 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 HALT = 1 ERROR = 2 boo! : "ex list[ int ] ) op_2 out " + 13 14 15 16 t4 t5 t6 sp 17 print( " pc inst op_' 11 rv 11 12 11 t1 t2 t3 status = CONT pc = 0 while status == CONT: oc, status = step( pc, regs, mem ) ~eturn status == HALT Další částí je podprogram read_prooram, 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: mem[ index // 2 ] += nibble * 16 if index % 2 == 0 else nibble def read_program( filename: str ) -> list[ int ]: mem = [ 0 for i in range( 65536 ) ] index = 0 with open( filename, r' ) as file: for line in file.readlines(): if line[ 0 ] == ;': break for word in line.rstrip().replace( , M ).split( ' ' ): for hex_nibble in word: write_nibble( mem, index, FROM_HEX[ hex_nibble ] ) index += 1 ~eturn mem 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 pochopeni funkčnosti výpočetního stroje tiny nijak podstatný. 8/2E PB111 Nízkoúrovnové programovaní, 21. února 2825 Cast 1: 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. flb - ra-té Fibonacciho číslo (mod 216), adder - dvouslovná sčítačka (32b), gcd - Euklidův algoritmus, prime - rozhodování prvočíselnosti, popcnt - počítání jedniček ve slově, perfect - součet dělitelů. Řešené příklady: hamming packed -bitswap collatz shift - - otočení bitů ve slově, - Hammingova vzdálenost slov, - sečtení dvou dvojic po složkách, - prohození dvou bitů ve slově, - počítání kroků iterovaného výpočtu, 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. 1,1,1 Kopírování hodnot Nejzákladnější operací, kterou můžeme vprogramu 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 p_ut, která nastaví výstupní registr na hodnotu přímého operandu. Zápis této instrukce bude vypadat např. takto: put 13 -» rv put 8x78 -> 11 halt Tento program nastaví registr rv na hodnotu 13 a registr 11 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 put 17 -> 11 copy rv -» 12 ; sets 12 = 13 copy 11 -» rv ; sets rv = 17 halt Po provedení tohoto programu budou hodnoty registrů rv = 17, 11 = 17 a 12 = 13. 1.1.2 Aritmetika Další důležitou kategorií jsou aritmetické instrukce. Následující tabulka shrnuje operace, které máte k dispozici. Registr 11 odpovídá proměnné a, registr 12 proměnné b, registr rv pak proměnné x. název python tiny sčítání x = a + b add 11, 12 -> rv odečítání x = a - b sub 11, 12 -> rv násobení x = a * b mul 11, 12 -> rv dělení x = a // b sdiv 11 12 -> rv udiv 11 12 -> rv zbytek x = a % b smod 11 12 -> rv umod 11 12 -> 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ě fe-bitový registr obvykle chápeme jako: 1. celé číslo n bez znaménka v rozsahu (0,2b) - pak sekvence bitů přímo odpovídá binárnímu zápisu tohoto čísla, 2. jako celé číslo s se znaménkem v rozsahu (-2i'~112i'~1), a to tak, že: a. je-li ne j vyšší bit nastaven na 1, s = n- 2b, b. jinak s — n Podmínku z bodu (a) můžeme také chápat jako [n i 2b"1]. Pro 16bitová čísla, která budeme v tomto předmětu používat zdaleka nejčastěji, to jsou tyto rozsahy: • (0,65535) (nebo B-ffff v šestnáctkovém zápisu) pro reprezentaci bez znaménka, • (-32768,32767) (nebo -8888 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). 1,1,3 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 eg 11, 12 -» rv equal not egual signed less than unsigned less than signed greater than unsigned greater than signed less or egual unsigned less or egual signed greater or egual unsigned greater or egual x = a != b ne 11, 12 -» rv x = a < b slt 11, 12 -> rv x = a > b ult 11, 12 -> rv sgt 11, 12 -» rv x = a <= b ugt 11, 12 -» rv sle 11, 12 -» rv x = a >= b ule 11, 12 -» rv sae 11, 12 -» rv uae 11, 12 -» rv 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 8 (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 8 nebo 1, v souladu s definicí příslušné logické operace (k těmto se vrátíme níže). 1.1.4 Ří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. 9/20 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), • íz reg, addr (jump if zero) nejprve ovéří, je-li hodnota registru řep nulová-pokud ano, provede skok stejné jako jmp addr, v případe 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 11 slt 11, 3 -> t1 j z t1, else a = 1 t = a < 3 if t: then: put 2 jmp endif else: put 3 endif: halt 12 -> 12 b = 2 else: Zkuste si program spustit pomocí tinyvm.py z kapitoly B, a také upravit první instrukci na put 5 -» 11 a srovnejte výsledek. Podobně můžeme zapsat také while cyklus (cykly fgr 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 -> 11 loop: end: sit 11, 3 -> t1 j z t1, end add 11, 1 -> 11 jmp loop halt a = 1 while True: t = a < 3 if not t: break a += 1 Cyklus while podmínka jsme přepsali na while True a podmíněný break -ekvivalenci těchto dvou zápisů si rozmyslete. 1.1.5 Bitové logické operace XXX 1.1.6 Bitové posuvy XXX 1.2: Programovací jazyk Tato kapitola jazyk C nepoužívá. 1.d: Demonstrace (ukázky) 1 .d.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 11, 12 a 13 a výsledek (0 nebo 1) zapíšeme do registru rv. test driver ld 17, 0x24 add 17, 2 17, 0x24 17, 2 17, 0x24 ld add ld add 17, 2 -> 11 -> 17 -> 12 -> 17 -> 13 -> 17 eg halt Bxffff -> t1 solution test-end marker data : ; 11 12 13 -» rv .word 3, 4, 5, 1 .word 1, 1, 1, 1 .word 1, 1, 3, 0 .word 2, 3, 1, 0 .word -1, 0 check: ld 17, 0x24 -> t1 eg rv, ti -» t1 asrt t1 add 17, 2 -> 17 jmp test .trigger set _tc_expect_ 4 .trigger inc _tc_ solution: ; zde začíná řešení 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 Každý z následovných tří bloků realizuje jednu nerovnost. Mezivýsledky ukládáme do registrů t[ (součet stran) a t2 (výsledek srovnání součtu se zbývající stranou). add 11, 12 -> t1 sgt t1, 13 -> t2 and rv, t2 -» rv add 11, 13 -> t1 sgt t1, 12 -> t2 and rv, t2 -» rv add 12, 13 -> t1 sgt t1, 11 -> 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 1 ,d,2 [factorial] V této ukázce naprogramujeme jeden z ne j jednodušší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 16, výsledek pak v registru rv. test driver ld 17, 0x10 -> 16 eg 16, Bxffff -> t1 j z t1, solution halt data: ; input, expect test-end marker 10/20 PB111 Nízkoúrovňové programování, 21. února 2025 .word 1, 1 .word 2, 2 .word 3, 6 .word 4, 24 .word -1, B check: add 17, 2 -> 17 Id 17, 0x10 -> t1 eq rv, t1 -> t1 asrt t1 add 17, 2 -> 17 jmp test .trigger set _tc_expect_ 4 .trigger inc _tc_ solution: ; zde začíná řešení Registr ry 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 16 - protože na pořadí násobení nezáleží, můžeme hodnoty násobit sestupné v pořadí n ■ (n - 1) ■ (n - 2)...l. 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 loop: mul rv, 16 -» rv sub 16, 1 -> 16 jnz 16, loop jmp check 1.p: Přípravy 1 ,p,1 [fib] Vaším úkolem je naprogramovat iterativní výpočet ra-tého Fibo-nacciho čísla. Vstupní hodnotu n naleznete v registru 16, výsledek uložte do registru rv. Po skončení výpočtu proveďte skok na návěstí check. Hodnotu registru 17 zachovejte. 1 ,p,2 [adder] Vaším úkolem je tentokrát naprogramovat 32bitovou sčítačku. Vstupem jsou 4 16bitové hodnoty uložené v registrech 11 až 14, kde H a 13 jsou nižší a 12 a 14 jsou vyšší slova sčítanců. Nižší slovo výsledku uložte do rv, to vyšší pak do 16. Hodnotu v registru 17 neměňte. 1 .p.3 fqcdl Vaším úkolem je naprogramovat Euklidův algoritmus pro nalezení největšího společného dělitele hodnot uložených v registrech H a 12 - 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 17 neměňte. 1 ,p,4 [pxjje] Napište program, který rozhodne, je-li hodnota uložená v registru 16 prvočíslem (hodnotu interpretujte jako číslo bez znaménka). Výsledek (1 pokud prvočíslem je, B jinak) uložte do registru ry a proveďte skok na návěstí check. Hodnotu registru 17 nijak neměňte. 1 .p.5 fpopcntl Napište program, který určí, kolik je jedniček v binárním zápisu čísla uloženého v registru 16. Výsledek uložte do registru rv a poté proveďte skok na návěstí check. Hodnotu registru 17 nijak neměňte. 1 ,p.6 fabundantl Napište program, který rozhodne, je-li hodnota uložená v registru 16 abundantním číslem (číslo n je abundantní, je-li součet všech jeho dělitelů d > 2ra). Vstup interpretujte jako číslo bez znaménka. Výsledek (1 pokud abundantní je, B jinak) uložte do registru ry a proveďte skok na návěstí check. Hodnotu registru 17 nijak neměňte. 1 .r: Řešené úlohy 1 .r.1 [reverse] Vaším úkolem bude otočit pořadí bitů ve slově. Vstupní slovo bude uloženo v registru výsledek uložte do rv a skočte na návěstí check. Hodnotu v registru 17 neměňte. 1 .r.2 rhamminql Spočtěte Hammingovu vzdálenost slov uložených v 11 a 12. Hammingovou vzdáleností je počet pozic, v nichž se vstupní slova liší hodnotou bitu. Výsledek uložte do ry a skočte na návěstí check. Hodnotu v registru 17 neměňte. 1 .r.3 [pjcked] 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 H a 12, výsledek uložte do rv a skočte na návěstí check. Hodnotu v registru 17 neměňte. 1 .r.4 fbitswapl Prohoďte dva zadané bity ve slově v registru 11 Indexy bitů jsou v 12 a 13. 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 17 neměňte. 1 ,r,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 11 Počet aplikací funkce uložte do rv, nalezené maximum do 16 a skočte na návěstí check. Hodnotu v registru 17 neměňte. 1 ,r.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 12 a 13 (12 je index nejnižšího, 13 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 17 neměňte. 11/20 Část 2: 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. cjcd - 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 - ne j vyšší čí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 2.1: 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. 2.2: 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řipravení, proto je budeme chápat jako syntaktickou obálku pro kód, který budeme psát. Program bude typicky vypadat takto: int podprogram( int parametri, int parametr ) { } 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 samí napíšeme. 2.2.1 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: • unsioned - celé číslo v rozsahu 0 až 65535,1 • int - celé číslo v rozsahu -32768 do 32767,18 • bool - celé číslo, 0 nebo 1, které typicky reprezentuje pravdivostní hodnotu - 0 pro falše, 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á11 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ě 0 Starší standardy jazyka C neurčují, jaké kódování se použije pro znaménkové typy, novější jíž požadují dvojkový doplňkový kód (víz také předchozí kapitola). 1 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í. složitou vnitřní strukturu, i když takové zatím neumíme v jazyce 0 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.12 2.2.2 Ž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. 2.2.3 Výrazy Na úrovni jazyka 0 je základní jednotkou výpočtu výraz -podobně jako v jazyce Python můžeme výrazy tvořit induktivně. Jsou-li: • Si, e2 ... ea výrazy, • var jméno proměnné, • lit číselný literál (konstanta), existují také výrazy tvaru:13 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. S dalšími operátory se setkáme v pozdějších kapitolách. 12/20 PB111 Nízkoúrovňové programování, 21. února 2025 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): ° Si + s-,, gj - e-,, ° Si * e2, ex / e2, ex %_e2 (modulo) ° unární mínus zři , 4. relační operátory: ° ex == e2 (rovnost), ex != e2 (nerovnost) ° & í^Jg, Si Si Si LJ2 5. bitové logické operace a posuvy: ° binární ex &_e2 (and), ex e2 (oř), ex _e2 (xor), ° unární rex - bitová negace, ° bitové posuvy zapisujeme ex » e-,, ex « 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 = e1, ° složené var += e,, var -= e,, ° dále var *= e1, var /= e1, var %= e1, ° s bitovým posuvem var «= e1, var »= e2, ° 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, elJ_e2, 9. booleovské logické operace: ° binární ex &&_e2 (and), ex I e2 (oř), ° unární |ex, ° ternárníej ? e2 : e?, 2.2.4 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ýrazy14 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.15 Toto tvrzení v jazyce C neplatí obecně pro všechny výrazy - existují í takové, které hodnotu nemají. 5 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 setři 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). 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 ry se realizuje instrukcí put 7 -» rv. 2. Výraz var se vyhodnotí na hodnotu, která je v momente vyhodnocení tohoto výrazu uložena v objektu svázaném s pramennou 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 11, vyhodnocení výrazu var do registru rv realizujeme instrukcí copy 11 -» rv. 3. Uvažme nyní výraz tvaru ex + e2. Víme, žepj a e2 popisují nějaké hodnoty. Abychom mohli vyčíslit hodnotu ex + e2, budeme nejprve potřebovat tyto hodnoty. Na to použijeme dočasné registry - vyhodnocení ex + e^ do ry bude vypadat takto: a. vyhodnoť ex do registru tx, b. vyhodnoť % do registru t2, c. proveď add t,, t, -» rv. Musíme samozřejmé zabezpečit, že výpočet e2 nepřepíše registr tx - jak přesně se toho dosáhne budeme zkoumat později.16 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 = e1 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 11: a. vyhodnoť ex do registru ry b. proveď copy rv -» 11. Všimněte si, že hodnota ex 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 += e1 je analogické, pouze je operaci copy předřazena příslušná aritmetická nebo logická operace:17 a. vyhodnoť ex do registru tx b. proveď add t1, 11 -» rv, c. proveď copy rv -» 11. 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 ry proběhne takto (var je svázáno s 11): a. proveď copy 11 -» rv. b. praverf add 11, 1 -> 11. Hodnota výrazu var++ je tedy původní hodnota var, předtím, než byle 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 at 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 + el. 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í! prevedene zvýšení premenné p jedničku. 6. Výraz elJ_e2 představuje „zapemenutí hednpty" výrazu ex - výraz e1 je převedenpeuze pro svoje vedlejší efekty (např. výše uvedené přiřazení). Vyhodnocení elJ__e2 do registru rv lze realizovat např. takto: a. vyhodnoť ex do rv, b. vyhodnoť e2 do rv. 7. Zbývá zatím nej slož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 2.2.5 Příkazy • výraz + středník • složený příkaz • if, else • fpr • while • break • continue 2. d: Demonstrace (ukázky) 2.d.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 ra-tého Fibonacciho čísla. int fib( int n ) { 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 nato, že sémantika proměnných v jazyce 0 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 13/20 je v pozdější ukázce), 3. volitelného Iniclallzátoru, který popisuje počáteční hodnotu proměnné. int a = 1, b = 1; 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 (vyhodnotili 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 sl zobrazíte příkazem $ tinycc -S ďLfib.c Realizaci podmínky cyklu naleznete ve strojovém kódu pod návěstím .cond.1 - jedná se o instrukce sub 11. 2 -» ťl a slt 14. t1 -» t1. Překladač zde použil registr ti 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 ) { 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; 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; b = o; } 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; } int main() /* demo */ { 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 falše, program ukončí s chybou. assert( fib( 1 ) == 1 ); assert( fib( 2 ) == 1 ); assert( fib( 7 ) == 13 ); assert( fib( 20 ) == 6765 ); return 0; } 2.Ú.2 [orime] 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ý.18 bool is_prime( unsigned number ) { Protože nejmenší prvočíslo je 2, a protože zbytek algoritmu pro hodnoty 1 8 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. ani 0 nebude pracovat správně, tyto hodnoty rovnou zamítneme. if ( number < 2 ) return false; V lokální proměnné divisor budeme udržovat aktuální pokusný dělitel. unsigned divisor = 2; Nej jednodušší 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 65025. Tento problém bude pokračovat po mnoho iterací - takto zapsaný cyklus se zastaví až pro hodnotu divisor = 16203, kdy dostáváme: • 162032 = 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; while ( divisor <= sgrt_uint_max && 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 ) return false; 14/20 PB111 Nízkoúrovňové programování, 21. února 2025 ++ divisor; } return tme; } int main() /* demo */ { 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 ) ); 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( 65521 u ) ); } 2.p: Přípravy 2.p.1 fqcdl 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 ) { Řešení pište sem. x a y jsou proměnné obsahující vstupní čísla. Výsledek vraťte příkazem return. return x; } 2.p.2 f randi 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 ■ 11B3515245 + 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: 8xff • 8xff + 8xff = 8xff88 rand_hi vrací horních 16 bitů výsledku. unsigned rand_hi( unsigned hi, unsigned lo ) { return 0; } rand_lo vrací spodních 16 bitů výsledku. unsigned rand_lo( unsigned hi, unsigned lo ) { return 0; } 2.p.3 [collatz] Uvažme následující funkci13 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. unsigned collatz_lds( unsigned n ) { return 0; } 2,p,4 [gacked] Uvažme slovo, které nereprezentuje jedno šestnáctibitové číslo, ale ra-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 ra-ticích sečíst po složkách a výsledek opět vrátit jako ra-tici stejného Ač mluvíme o matematické funkci f, neočekáváme, že tato bude implementována samostatným podprogramem (tzv. funkcí) jazyka C. 0 těch zatím v kurzu řeč nebyla. tvaru. Implementujte podprogram packed_add, který toto sčítání provede. Jeho první dva argumenty jsou slova reprezentující ra-tice, třetím je šířka čísla v ra-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 ) { Řešení pište sem. yl a y2 jsou proměnné obsahující vstupní n-tice, width obsahuje šířku čísla v n-tici. Výsledek vraťte příkazem return return 0; } 2.P.5 fpopcntl 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 ) { Ř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; } 2.p.6 rhamminql Implementujte podprogram hamming, který spočítá Hamm-mingovu 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 ) { Ř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; } 2.r: Řešené úlohy 2.r.1 rpalindromel Implementujte predikát is_binarv_palindrome, který o zadaném čísle rozhodne, zda je jeho binární reprezentace palindromem. bool is_binary_palindrome( unsigned n ) { 15/20 Řešení píšte sem. retům falše; } 2.r.2 [largest] Implementujte podprogram largest_digit, který pro zadané číslo n vrátí jeho nej vyšší číslici při základu base. unsigned largest_digit( unsigned n, unsigned base ) { Řešení pište sem. return 0; } 2.r.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činltele započítejte opakované. unsigned factor_count( unsigned n ) { assert( n > 0 ); Řešení pište sem. return 0; } 2.r.4 [grimes] 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činltele započítejte pouze jednou. unsigned prime_count( unsigned n ) { assert( n > 0 ); Řešení pište sem. return 0; } 2.r.5 ftransposel Označíme-li postupně bity ve slově tak, že nejméně významný je 0 a nej vý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 10 Implementujte podprogram transpose, který zadanou matici transponuje, tj. vráti 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 0 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 ) { Řešení pište sem. return 0; } 2.r.6 fbalancedl 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 ■ 31 + (-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 ) { Řešení pište sem. return 0; } 2.v: Volitelné úlohy 2.V.1 fdigitsl 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 ) { Řešení pište sem. return 0; } 2.V.2 [rabate] 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 ) { Řešení pište sem. return 0; } 16/20 PB111 Nízkoúrovňové programování, 21. února 2025 Část K: Vzorová řešení K.1: Týden 1 K.1.B1.1 [reverse] put 0x0001 -> t1 put 0x8000 -> t2 put 0 -» rv loop: and 11, ti ^ t3 jz t3, zero oř rv, 12 -» rv zero: shl t1, 1 -> t1 shr t2, 1 -> t2 j z t2, check jmp loop K.1.B1.2 rhamminql put put 0 -» rv -> t3 loop and ne add maska zdrojového bitu maska cílového bitu zjišténí zdrojového bitu nastavení cílového bitu posuv obou masek skončit, když cílový bit vypadl z registru maska srovnávaného bitu and 13, 11 -» t1 ; hodnoty srovnávaných bitů ; zvýšit čítač, pokud se bity nerovnají 13, 12 -> t2 t1, t2 -> t4 rv, 14 -» rv shr t3, 1 -> t3 ; j z 13, check ; jmp loop K.1.B1.3 ľ packed! add 11, 12 -> rv and rv, 0x00ff -» rv and 11, 0xff00 -> 11 and 12, 0xff00 -> 12 add 11, 12 -> t1 or t1, rv -» rv jmp check K.1.B1.4 fbitswap] put 0x0000 -> rv shl 1, 12 -» t2 ; masky zadaných bitú posunout masku srovnávaného bitu konec, pokud maskovaný bit vypadl z registru součet spodní slabiky vynulovat spodní slabiky vstupů součet horních slabik promítnout horní součet do výsledku shl 1, 13 -> t3 and 11, t2 -> t4 extrakce zadaných bitů and 11, t3 -> t5 xor t2, -1 -> t6 vynulování zadaných bitů and 11, t6 -> rv xor 13, -1 -> t6 and rv, t6 -> rv jz t4, zero nastavení bitů oř rv, t3 -> rv j z t5, check oř rv, t2 -» rv jmp check K.1.31.5 [collatz] put 0 -» rv put 0 ^ 16 checkjax: ugt 11, 16 -> t1 j z t1, loop copy 11 -» 16 loop: eg 11 jnz t1 add rv and 11 j z t1 mul 11 1 -> t1 check 1 -» rv 1 -> t1 even 3 -> 11 add 11, 1 -> 11 jmp checkjax udiv 11, 2 -> 11 jmp loop K.1.B1.6 [shift] put 0xffff -> t2 sub 15, 13 -> t3 shl t2, t3 -> t2 shr t2, 13 -> t2 shr t2, 12 -> t2 shl t2, 12 -> t2 vynulovat výstupní registry ovéřit a nastavit nové maximum ; ukončit při jedničce ; jinak zvýšit čítač ; test sudosti ; n = 3n + 1 ; možná jsme našli nové maximum ; n = n / 2 ; při délení jsme jisté maximum nenašli do t2 nachystáme masku počet horních nulových bitů vynulujeme horní bity vynulujeme spodní bity xor t2, -1 -» 13 ; inverzní maska and rv, t2 -» t4 shl t4, 1 -> t4 and t4, t2 -> t4 and rv, t3 -» rv oř rv, t4 -» rv jmp check 17/20 Cast 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. T.1: 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. T.1.1 Diskusní fórum Máte-li dotazy k úlohám, organizaci, atp., využijte k jejich položení prosím vždy prednostné diskusní fórum.28 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čtete 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í. T.1.2 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. T.1.3 Odevzdání řešení Vypracované příklady můžete odevzdat do odevzdá- Nebojte se do fóra napsat - když si s něčím nevíte rady a/nebo nemůžete najít v materiálech, řádí Vám pomůžeme nebo Vás nasměrujeme na místo, kde odpověď naleznete. 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í §1 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 jev pořádku, název souboru po vložení do ISu neměňte) . 0 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). T.1.4 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áme 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-00-17 22:43 CEST subtest p1_foo passed [ 1] subtest p2_bar failed subtest p3_baz failed subtest p4_guux passed [ 1] subtest p5_wibble passed [ 1] subtest p6_xyzzy failed {bližší popis chyby} verity test failed testing syntax of submission from 2025-00-17 22:43 CEST subtest p1_foo passed subtest p2_bar failed {bližší popis chyby} subtest p3_baz failed {bližší popis chyby} subtest p4_guux passed subtest p5_wibble passed subtest p6_xyzzy passed syntax test failed testing sanity of submission from 2025-00-17 22:43 CEST subtest p1_foo passed [ 1] subtest p2_bar failed subtest p3_baz failed subtest p4_guux passed [ 1] subtest p5_wibble passed [ 1] subtest p6_xyzzy passed [ 1] sanity test failed best submission: 2025-00-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ů. 0 konečném zisku rozhoduje vždy poslední odevzdání před příslušným termínem (opět jako jeden celek).21 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) Můžete si tak odevzdáním nefunkčních řešení na poslední chvílí 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". 18/20 PB111 Nízkoúrovňové programování, 21. února 2025 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). T.1.5 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 mise 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. T.2: 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 WSL22 - Windows Subsystém f oř 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). T.2.1 Pracovní stanice Veškeré instrukce, které zde uvádíme pro použití Jako alternativu, nechcete-li z nějakého důvodu WSL instalovat, lze použít program putt\ 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). T.2.2 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ř. Q1/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 ed učitelů, tak ed spplužáků). To, že máte k dispozici nové recenze, uvidíte ve výpisu. Recenze najdete ve složce ~/pb111/reviews. T.2.3 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 polil, ujistěte se, že odevzdáváte vždy všechny příklady. T.2.4 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. T.3: 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 seubpru bez přípeny (např. tedy make p1_fib.bin). Tento příkaz přeloží program překladačem tinyce 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). T.3.1 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 emaes. 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í. T.3.2 Vlastní prostředí Prozatím je překladač tinvec 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ě. 19/20 Cast 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 nej dů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.23 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é laj. 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: findjin, findjax, erasejax - nikolivnapř. erasejaximum nebo erase_greatest nebo max_re-move). 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- 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 definicí 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í. ň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álne. 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.24 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ždý přečíst v samotném kódu. 7 Formální úprava TBD. 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á. 20/20 PB111 Nízkoúrovňové programování, 21. února 2025