====== U4: SymCalc - parsování a úpravy matematických výrazů ====== Úkol SymCalc je **nepovinný**. Úloha je zajímavá, odhaluje způsob, jakým jsou prováděny výpočty matematických výrazů v počítačích obecně. Její zpracování je ale poměrně obtížné, a proto ji doporučujeme zejména těm z vás, pro které jsou ostatní úkoly příliš jednoduché. Úloha současně představuje jakéhosi žolíka - jejím vyřešením můžete nahradit body za libovolnou úlohu, kterou jste nestihli nebo nezvládli vyřešit v průběhu semestru. ===== Co si v tomto úkolu vyzkoušíte ===== * Vytvořit a použít hierarchii objektů s dynamickým polymorfismem * Ošetření chyb s použitím výjimek * Praktické využití přetěžování operátorů * Správu paměti s použitím ''std::shared_ptr'' * Zpracování argumentů z příkazové řádky ===== Zadání ===== Implementujte aplikaci pro příkazovou řádku, která bude číst matematické výrazy ze standardního vstupu a provádět nad nimi operace specifikované v argumentech z příkazové řádky (výpis, vyhodnocení, derivace, zjednodušení) ((Uvědomujeme si, že toto rozhraní není zrovna přívětivé pro použitelnost aplikace lidmi. Je to ale kompromis mezi relativně jednoduchým, dobře testovatelným a dobře použitelným.)). Až program narazí na konec vstupu (EOF), skončí. Detailní zadání je uvedeno níže. ===== Odevzdání ===== Protože implementovat celou aplikaci od nuly je poměrně dost práce, připravili jsme pro vás šablonu, která je dostupná na [[https://gitlab.fel.cvut.cz/B6B36PJC/symcalc|gitlabu]]. Součástí jsou Catch testy, pomocí kterých si můžete program postupně testovat. V upload systému se ale bude hodnotit pouze chování aplikace jako celku (byť pokrytí by mělo být stejné). Pokud forknete repozitář se zadáním, **nastavte Visibility((Settings -> General -> Permissions)) na Private**, abyste se vyhnuli problémům s plagiátorstvím. Do upload systému tentokrát nahrajte všechny zdrojové soubory((stále ale platí, že objektové soubory a další produkty překladu odevzdávat nemáte)). Soubory s testy (podadresář ''tests'') a knihovnu ''mapbox'' neodevzdávejte. Na gitlabu je i konfigurace pro Gitlab CI((Continuous Integration)) ''.gitlab-ci.yml'' pro možnost spuštění testů tam. Více informací na [[courses:b6b36pcc:ostatni:git-intro|stránce o gitu]] a [[courses:b6b36pcc:ukoly:sem_tvoralgr#ukazka|stránce o semestrálce]]. ===== Doporučený postup ===== Jméno souboru v hranatých závorkách vyjadřuje doporučené místo implementace. /* keep the long lines, dokuwiki is stupid */ * Vytvořte potomky třídy ''expr_base'' pro každou matematickou operaci (samozřejmě to mohou být i nepřímí potomci, tedy "vnoučata"). [''expr_impl.cpp'' a ''expr_impl.hpp''] * Implementujte metodu ''write''. Všechny ostatní implementujte pomocí dummy kódu ''throw std::logic_error("not implemented yet");''. * Implementujte přetížené operátory (+, -, *, /, ==, %%<<%%) a funkce (sin, cos, log, pow) pro třídu ''expr''. Dále implementujte statické metody ''expr::number'' a ''expr::variable'' [''expr.cpp''] * Parsování matematického výrazu. Doporučujeme použít algoritmus [[https://en.wikipedia.org/wiki/Shunting-yard_algorithm|Shunting yard]]. * Implementujte funkci ''create_expression_tree''. Doporučujeme použít dodaný tokenizer. Při chybě parsování vyhoďte výjimku ''parse_error''. * Nyní by vám už měly procházet všechny testy ze sekce "Parsing and writing". * Implementujte funkci ''handle_expr_line'', která bere seznam příkazů a řádku standardního vstupu. Výstup pak vypisuje do předaného výstupního proudu. [''app.cpp''] * Vyhodnocení příkazů nad výrazem. Pokud jste použili ''parse_command'', stačí použít a doplnit kostru funkce ''process_expr''. * Implementujte funkci ''main'': [''main.cpp''] * Parsování parametrů. Pro parsování příkazů můžete použít dodanou funkci ''parse_command''. * Čtení a parsování výrazů ze standardního vstupu a jejich následné zpracování. * Implementujte metodu ''evaluate''. Měly by začít procházet testy ze sekce "Evaluate". * Konstanty ''expr::ZERO'', ''expr::ONE'' jsou už definované v ''expr.cpp''. * Implementujte metodu ''derive''. Příslušné testy by měly začít procházet. * Implementujte metodu ''equals''. Zde se bude hodit ''dynamic_cast''. * Implementujte metodu ''simplify''. Příslušné testy by měly začít procházet. ===== std::shared_ptr ===== Výchozí kód používá ''std::shared_ptr'', což je další chytrý ukazatel. Na rozdíl od ''std::unique_ptr'' ale jde kopírovat -- interně si počítá, kolik instancí ''shared_ptr'' ukazuje na daný objekt, a teprve když zaniká poslední reference, paměť dealokuje. Někdy nastane situace, že z metody objektu spravovaného pomocí shared_ptr budete chtít vrátit shared_ptr na ''this''. To nejde udělat prostým voláním ''std::make_shared(this)'', protože ''this'' už je někým spravován (nějakým jiným shared pointrem). Takto by měl ''this'' dva vlastníky (s různými reference county) a nastaly by problémy s pamětí (double free, use after free). My chceme využít již existující shared_ptr a pouze zvýšit jeho reference count. Ale jak ho získat? Přesně k tomu slouží pomocná třída ''std::enable_shared_from_this'', od které podědíme náš objekt, a v něm už pak jen zavoláme ''shared_from_this()'' (viz [[https://en.cppreference.com/w/cpp/memory/enable_shared_from_this|reference]]) Reference: * [[https://en.cppreference.com/w/cpp/memory/shared_ptr|std::shared_ptr]] * [[https://en.cppreference.com/w/cpp/memory/enable_shared_from_this|std::enable_shared_from_this]] ===== Detailní zadání ===== ==== Formát výrazů ==== Na každém neprázdném řádku standardního vstupu bude jeden výraz (a každý výraz bude právě na jednom řádku). Evaluátor musí podporovat čísla, proměnné, funkce ''sin'', ''cos'', ''log'' a 5 základních matematických operátorů, včetně jejich priorit a asociativity. Zároveň musí podporovat změnění asociativity a priorit pomocí závorek. ^ Operátor ^ Priorita ^ Asociativita ^ | ''^''((Exponenciace)) | 3 | Pravá | | ''*'', ''/'' | 2 | Levá | | ''+'', ''-'' | 1 | Levá | Vstup se skládá z čísel, identifikátorů, operátorů, závorek a blíže nespecifikovaného množství whitespace. To znamená, že ''1 + 2'' je ekvivalentní ''1+2'', ale i ''1 +2'', ''1+ 2'', ''(1 + 2)'' nebo dokonce ''%%((1) + (2))%%''. Pokud je vstup chybný, to jest, obsahuje špatně ozávorkované výrazy (např. '')2 + 1(''), přebytečné operátory (např. ''1 + 1 +''), neplatné znaky (''1+5%''), neznámou funkci (''tanh(x)'') a podobně, program vypíše chybu a dál daný výraz nezpracovává. Unární mínus (tedy negace) není pro jednoduchost zahrnuto -- výraz ''-x'' se dá ekvivalentně zapsat jako ''0-x''. V parseru doporučujeme použít dodaný ''Tokenizer''. Jeho popis je v hlavičkovém souboru a příklad jeho funkce naleznete v testech. ==== Parametry programu ==== Jako parametry přebírá program pouze sekvenci příkazů, které se postupně provedou nad každým zadaným výrazem. Každý parametr určuje jeden příkaz. === print === Vytiskne aktuální výraz v prefixové notaci. Čísla a proměnné se vypíšou bez závorek. Pokud jste někdy potkali nějakou variantu jazyka LISP, bude vám formát výstupu povědomý. Příklad((Pro rozlišení vstupu a výstupu v příkladech používáme > pro označení vstupu. Na vstupu ani výstupu ale doopravdy není.)): $ ./symcalc print > 1 1 > variable variable > 1+x (+ x 1) > 1 * sin(x) (* 1 (sin x)) === evaluate:varA=1:varB=2 === Vyhodnotí aktuální výraz a vypíše výsledek. Přiřazení hodnot proměnných má tvar ''proměnná=číslo'', jednotlivá přiřazení jsou oddělena dvojtečkou. Není chybou, pokud se např. uvedená ''varB'' ve výrazu nevyskytuje. Pokud je ale ve výrazu proměnná, která nemá přiřazenou hodnotu, je to chyba. Příklad: $ ./symcalc evaluate:x=1:y=2 > x+y 3 > z ! error: unbound variable > 42 42 === derive:x === Zderivuje aktuální výraz podle proměnné ''x''. Proměnná se ve výrazu nemusí vyskytovat. Další příkazy pak pracují nad zderivavaným výrazem. Aby se dala správnost výstupu rozumně vyhodnotit, použijte přesně pravidla uvedená v dokumentaci metody ''derive''. \begin{align*} (f+g)' &= f' + g' \\ (f-g)' &= f' - g' \\ (f\cdot g)' &= f'\cdot g + f\cdot g' \\ (f/g)' &= (f'\cdot g - f\cdot g')/g^2 \\ (f^g)' &= f^g \cdot ( (f'\cdot g)/f + log(f)\cdot g' ) \\ sin(f)' &= cos(f) \cdot f' \\ cos(f)' &= (0-sin(f)) \cdot f' \\ log(f)' &= f' / f \\ \end{align*} kde ' značí derivaci dle dané proměnné. Příklad: $ ./symcalc derive:x print > 42 0 > x 1 > y 0 > 1*x (+ (* 0 x) (* 1 1)) === simplify === Zjednoduší aktuální výraz dle daných pravidel. Další příkazy pak pracují nad zjednodušeným výrazem. Přesný seznam pravidel je v dokumentaci metody ''simplify''. \begin{align*} 0+x &= x \\ x+0 &= x \\ x-0 &= x \\ 0\cdot x &= 0 \\ x\cdot 0 &= 0 \\ 1\cdot x &= x \\ x\cdot 1 &= x \\ 0/0 &= 0/0 \\ 0/x &= 0 \\ x/1 &= x \\ x^1 &= x \\ 0^0 &= 1 ~~ † \\ x^0 &= 1 \\ 0^x &= 0 \\ log(1) &= 0 \\ \end{align*} kde ''x'' je jakýkoliv výraz. † To striktně vzato [[https://cs.wikipedia.org/wiki/Umoc%C5%88ov%C3%A1n%C3%AD#Nula_na_nultou|nemusí být pravda]], nicméně toto je častá interpretace a je konzistentní s chováním [[https://en.cppreference.com/w/cpp/numeric/math/pow|std::pow]]. == Rady == * zde se vám bude hodit operátor porovnání ''=='' pro ''expr'' (který volá metodu ''equals'') a konstanty ''expr::ZERO'', ''expr::ONE'' * zjednodušení aplikujte rekurzivně v post-order pořadí, tj. na již zjednodušených výrazech ==== Formát výpisu chyb ==== Pokud nějaký příkaz selže (např. chybějící proměnná pro evaluate), měl by vypsat chybu. Text chyby by měl být ideálně smysluplný a popisovat její příčinu, pro testy však dostačuje vypsat řádek, který začíná vykřičníkem, zbytek se nekontroluje: $ ./symcalc evaluate > x ! error: 26unbound_variable_exception: no value given for variable x Program by měl také po vyhlášení chyby pokračovat čtením dalšího výrazu. === Rady === * Dynamický typ zachycené výjimky můžete zjistit pomocí operátoru [[https://en.cppreference.com/w/cpp/types/type_info/name|typeid]] ===== Příklady ===== $ ./symcalc evaluate:x=2 derive:x simplify print > 1+2.5*x 6 2.5 > x*x 4 (+ x x) > sin(0.5*x) 0.841471 (* (cos (* 0.5 x)) 0.5) > x/y ! error: unbound variable y > x/5 0.4 (/ 5 (^ 5 2)) V tomto příkladu se zadaný výraz nejdříve vyhodnotí (a vypíše výsledek), pak se zderivuje podle proměnné ''x'', zderivovaný výraz se zjednoduší, a až tento zjednodušený výraz se vypíše. Pokud některý z příkazů pro výraz selže, vypíše se chyba a další příkazy se pro tento výraz již nevykonávají. Program ale pokračuje dál čtením dalšího výrazu ze standardního vstupu. ==== Příklad výrazového stromu ==== /* mezery kolem názvu způsobí zarovnání na střed */ {{ :courses:b6b36pcc:ukoly:symcalc_expr_tree.png }} Takto vypadá výrazový strom (expression tree) pro výraz "sin(x) + 2*6". Každý uzel stromu je sám o sobě výrazem (a tedy jde vypsat, zderivovat, vyhodnotit, atd.) a obsahuje své podvýrazy (pokud nějaké má). ===== Bonusy ===== ==== Rozšířené formátování ==== Pro strojové zpracování je LISPovská prefixová notace výpisu výrazů ideální, pro lidi se ale spíš hodí klasický infixový výpis. Hodilo by se tedy, kdyby šlo výraz vypsat oběma způsoby. To je poměrně přímočaré na úrovni virtuální metody ''write'' (stačí přidat parametr), ale jak tuto variabilitu přenést do veřejného rozhraní? Formátovaný výstup do streamu používá pro rozlišení formátů manipulátory, které mění interní stav streamu. Tady se ukazuje jedna ze slabin tohoto přístupu -- není zrovna rozšiřitelný na další specifikace formátu. Mohli bychom zneužít nějaký flag, který náš výstup jinak neovlivní (např boolalpha), ale to je poměrně ošklivé řešení. Mnohem lepší je zabalit ''expr'' do nového pomocného typu, který si s sebou ponese i informace o formátování, které můžeme využít v přetíženém operátoru zápisu do streamu. struct fmt_expr {const expr &e; expr::WriteFormat fmt;}; std::ostream& operator<<(std::ostream &os, fmt_expr e) { e.e->write(...); ... } ... std::cout << fmt_expr{my_expr, expr::WriteFormat::Infix}; /* * ==== Součtové datové typy ==== * TODO: vyhodit, přesunout do kódu * * Obyčejná struktura (struct) se dá chápat jako //součinový typ//, ve smyslu * [[https://cs.wikipedia.org/wiki/Kart%C3%A9zsk%C3%BD_sou%C4%8Din|kartézského součinu]]. * Naivní definice struktury ''Command'', která reprezentuje naparsovaný příkaz z * argumentů příkazové řádky, by mohla vypadat třeba takto (v ukázce nejsou pro přehlednost všechny příkazy): * * struct Command { * enum class Id { * Print, Evaluate, Derive * } id; * std::string variable; // only for Derive * expr::variable_map_t vm; // only for Evaluate * }; * * * Vidíte už v deklaraci, že některé položky jsou použity pouze jedním typem příkazu. * Např. příkaz ''Command {Id::Print, "x"}'' nedává smysl. ''Command'' je dobrým kandidátem * na součtový datový typ, protože příkaz může být buď ''Print'' (bez parametrů), * nebo ''Derive {variable}'', nebo ''Evaluate {variable_map}''. Jak ale v C++ tento typ reprezentovat? * * Možná si vzpomínáte na ''union'' (TODO: popis). To je sice dobrý stavební prvek, * ale pro pohodlné použití je toho k němu ještě potřeba spoustu dodat. * To už implementovali jiní v důmyslných knihovnách -- v C++17 v std::variant, * pro starší standardy pak třeba [[https://github.com/mapbox/variant|mapbox variant]] * (který je použit v úkolu). * * Pozn: rust/haskell enumy * * Česky součtové datové typy. */ ===== Hodnocení ===== ^ **Sekce** ^ Body ^ | Parse & print | 6 | | Evaluate | 1,5 | | Derive | 2,5 | | Simplify | 2,5 | | Error handling | 2,5 | | Bonus: different print formats | 1 | | **Celkem** | **16** | Připomínáme, že z úlohy musíte získat alespoň 40% možných bodů (bez bonusu), tj. alespoň 8. ===== Testy ===== K úkolu dodáváme 3 druhy testů((ve skutečnosti jsou všechny stejné, liší se jen způsobem, jak spouští váš kód)). Pro ladění doporučujeme použít přímé unit testy (''tests-direct''), případně potom ''tests-runner-direct''. ==== Přímé unit testy ==== Tyto testy pro vás budou nejužitečnější, pokud použijete dodanou kostru aplikace. Jsou to klasické testy v Catchi, které přímo volají jednotlivé funkce vašeho kódu. V CMakeLists jsou definované jako target ''tests-direct''. Pokud chcete spustit jen některé testy, můžete je specifikovat na příkazové řádce. ''./tests-direct "[evaluate],[simplify]"'' spustí všechny testy s tagy "evaluate" nebo "simplify", ''./tests-direct "~[evaluate]~[simplify]"'' pak spustí všechny testy //kromě// testů s tagy "evaluate" nebo "simplify". Více v [[https://github.com/catchorg/Catch2/blob/master/docs/command-line.md#specifying-which-tests-to-run|dokumentaci Catche]]. ==== Testy, které spouští aplikaci v samostatném procesu ==== Tyto testy jsou použity pro hodnocení. Spouští vaši aplikaci jako samostatný proces, kterému předají parametry a výrazy na standardním vstupu dle zadání. V CMakeLists jsou definované jako target ''tests-runner-subprocess''. Pokud si chcete tyto testy spustit i u sebe (což není nutné, viz další sekce), musíte testeru nastavit proměnnou prostředí ''TEST_CMD'', ve které bude příkaz ke spuštění vašeho programu. Pokud spouštíte testy přes ''make test'' (nebo má vaše IDE integraci s CTestem), je už vše nastaveno. CLion tuto integraci zatím nemá, je tedy nutné editovat konfiguraci pro ''tests-runner-subprocess'' a do Environment variables přidat ''TEST_CMD=./symcalc''((Příkaz může být i něco složitějšího, např. ''valgrind ./symcalc'')). ==== Něco mezi ==== Poslední typ testů je velmi podobný předchozím v tom, že k volání vašeho kódu používá vysokoúrovňovou funkci ''handle_expr_line''. Tyty testy jsou tak (téměř) identické s temi, co běží v odevzdávacím systému, ale jsou jednodušší a flexibilnější k použití. V CMakeLists jsou definované jako target ''tests-runner-direct''. ===== Rady ===== ==== Rozdíl mezi expr a expr_base ==== V šabloně úkolu jsou dvě třídy výrazů -- ''expr'' a ''expr_base''. Třída ''expr_base'' slouží jako vlastní //interface// -- definuje (čistě) virtuální metody, které musí její potomci (jednotlivé typy výrazů) implementovat. Naproti tomu třída ''expr'' slouží jako tenký wrapper nad ''std::shared_ptr'', který je její jedinou datovou položkou. Význam této třídy je dvojí: * Umožnit intuitivní psaní ''expr'' místo ''std::shared_ptr''. * Umožnit použití přetížených operátorů a funkcí. Pro první účel by se alternativně dalo využít typových aliasů (''typedef''), nicméně ''expr'' by pak byl identický s ''std::shared_ptr'' -- měl by všechny jeho veřejné metody a přetížené operátory by pracovaly nad tímto ''shared_ptr'' (a potenciálně by nám překážely operátory definované už pro obecný ''shared_ptr''). Toto zapouzdření pomocí kompozice vytváří nový typ a máme plnou kontrolu nad tím, jaké operace bude podporovat. V C%%++%% toto navíc nemá žádný //performance overhead//. Třída ''expr'' je tedy ta, kterou by měla používat většina kódu.