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.

• 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

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í) ¹⁾. Až program narazí na konec vstupu (EOF), skončí.

Detailní zadání je uvedeno níže.

Protože implementovat celou aplikaci od nuly je poměrně dost práce, připravili jsme pro vás šablonu, která je dostupná na 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²⁾ na Private, abyste se vyhnuli problémům s plagiátorstvím.

Do upload systému tentokrát nahrajte všechny zdrojové soubory³⁾. Soubory s testy (podadresář tests) a knihovnu mapbox neodevzdávejte.

Na gitlabu je i konfigurace pro Gitlab CI⁴⁾ .gitlab-ci.yml pro možnost spuštění testů tam. Více informací na stránce o gitu a stránce o semestrálce.

Jméno souboru v hranatých závorkách vyjadřuje doporučené místo implementace.

• 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 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.

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 reference)

Reference:

• std::shared_ptr
• std::enable_shared_from_this

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.

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.

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.

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⁶⁾:

$ ./symcalc print
> 1
1
> variable
variable
> 1+x
(+ x 1)
> 1 * sin(x)
(* 1 (sin x))

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

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))

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 nemusí být pravda, nicméně toto je častá interpretace a je konzistentní s chováním std::pow.

• 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

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.

• Dynamický typ zachycené výjimky můžete zjistit pomocí operátoru typeid

$ ./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.

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á).

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};

Připomínáme, že z úlohy musíte získat alespoň 40% možných bodů (bez bonusu), tj. alespoň 8.

K úkolu dodáváme 3 druhy testů⁷⁾. Pro ladění doporučujeme použít přímé unit testy (tests-direct), případně potom tests-runner-direct.

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.

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⁸⁾.

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.

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<expr_base>, 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<expr_base>.
• 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<expr_base> – 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.