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í) 1). 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 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é).

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

Na gitlabu je i konfigurace pro Gitlab CI3) .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.

Doporučený postup 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”. Definujte konstanty expr::ZERO, expr::ONE. 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. 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 reference)

Reference:

std::shared_ptr 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

*, / 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 ¹⁾.

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říklad5):

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

( f + g ) ′ = f ′ + g ′ ( f − g ) ′ = f ′ − g ′ ( f ⋅ g ) ′ = f ′ ⋅ g + f ⋅ g ′ ( f / g ) ′ = ( f ′ ⋅ g − f ⋅ g ′ ) / g 2 ( f g ) ′ = f g ⋅ ( ( f ′ ⋅ g ) / f + l o g ( f ) ⋅ g ′ ) s i n ( f ) ′ = c o s ( f ) ⋅ f ′ c o s ( f ) ′ = ( 0 − s i n ( f ) ) ⋅ f ′ l o g ( f ) ′ = f ′ / f 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.

0 + x = x x + 0 = x x − 0 = x 0 ⋅ x = 0 x ⋅ 0 = 0 1 ⋅ x = x x ⋅ 1 = x 0 / 0 = 0 / 0 0 / x = 0 x / 1 = x x 1 = x 0 0 = 1

† x 0 = 1 0 x = 0 l o g ( 1 ) = 0 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.

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

Hodnocení Sekce Body Parse & print 8 Evaluate 2 Derive 3 Simplify 4 Error handling 3 Bonus: different print formats 1 Připomínáme, že z úlohy musíte získat alespoň polovinu možných bodů (bez bonusu), tj. alespoň 10.

Testy K úkolu dodáváme 3 druhy testů6). 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 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=./symcalc7).

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<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 Ctoto navíc nemá žádný performance overhead. Třída expr je tedy ta, kterou by měla používat většina kódu. 1) 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. 2) stále ale platí, že objektové soubory a další produkty překladu odevzdávat nemáte 3) Continuous Integration 4) Exponenciace 5) 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í. 6) ve skutečnosti jsou všechny stejné, liší se jen způsobem, jak spouští váš kód 7) Příkaz může být i něco složitějšího, např. valgrind ./symcalc courses/b6b36pjc/ukoly/symcalc.txt · Last modified: 2019/09/27 10:48 by richta ==== Co odevzdat? ==== Odevzdávejte soubor ''.zip'', který obsahuje jeden nebo více souborů ''.cpp'', ve kterých jsou implementované funkce z hlavičkových souborů z domácího úkolu. Vámi odevzdané soubory by neměly být schované v podsložce a prosíme vás, abyste neodevzdávali soubory vašeho IDE((Pokud má váš úkol 1 MB před zabalením, pravděpodobně toho odevzdáváte příliš. Pokud má váš úkol 1 MB po zabalení, *určitě* toho odevzdáváte příliš.)). Žádný ze souborů s testy není třeba odevzdávat. ==== Catch ==== ''Catch'' je framework pro psaní testů pro C%%++%% kód. Základní použití je jednoduché, stačí v nějakém souboru deklarovat makro ''CATCH_CONFIG_MAIN'' před includováním hlavičky ''catch.hpp'' a v ostatních souborech se již můžou psát testy. Následně stačí zkompilovat zdrojové soubory a spustit výsledný program, čímž se provedou a vypíšou výsledky testů. V archivu, který máte od nás, najdete ''catch.hpp'', hlavičku s aktuální verzí testovací testovacího frameworku, ''tests-main.cpp'', zdrojový soubor s definicí makra ''CATCH_CONFIG_MAIN'', a ''tests-small1.cpp'', ve kterém jsou testy pro vaši implementaci. ==== Valgrind ==== Všechny odevzdané úkoly jsou kontrolovány za použití [[https://cs.wikipedia.org/wiki/Valgrind Valgrindu]]. Valgrind je schopen najít spoustu chyb, které se normálně nemusí projevit, a v případě, že nějakou najde, bude vám sražena část bodů z domácího úkolu. ===== Rady ===== ==== Užitečné hlavičky ==== V různých úkolech si můžete ulehčit práci použitím standardních knihoven. V tomto doporučujeme podívat se blíže na hlavičku <iomanip> a samozřejmě na věci, které se probíraly na cvičení (například std::stringstream). ==== Dlouhá doba kompilace ==== Pokud kompilujete z příkazové řádky²⁾, pravděpodobně zjitíte, že vám kompilace běží velmi dlouho (5-10s). Protože nejdelší dobu se kompiluje soubor tests-main.cpp, který se nebude měnit, vyplatí se ho zkompilovat do tzv. objektového souboru. Objektové soubory jsou mezikrok mezi implementačními soubory a fungujícím programem. Pokud spustíte kompilátor s argumentem -c, místo binárky se vám vytvoří objektové soubory. Volání

clang++ -std=c++14 tests-small.cpp tests-main.cpp -c

vám vytvoří soubory tests-small.o a tests-main.o, které pak můžete použít při kompilaci místo tests-small.cpp a tests-main.cpp. Pozor, soubor s vaší implementací takto nahradit nemůžete, protože .o soubory se automaticky neaktualizují při změnách původních .cpp souborů. Výsledné volání pro kompilaci tedy bude zhruba takovéto

clang++ -std=c++14 tests-small.o tests-main.o small1.cpp -o small1

a kompilace bude trvat výrazně kratší dobu. ==== Čtení kompilačních chyb ==== Pokud se něco pokazí při kompilaci, C++ je schopno generovat opravdu dlouhé chyby. Ve skutečnosti je z nich obvykle relevantní pouze krátká část, protože výpis má formu kompilačního stacktrace – při kompilaci jaké funkce vznikla chyba a proč byla daná funkce kompilována. To znamená, že při čtení kompilační chyby je potřeba najít první výpis, který je ve vašem kódu, protože právě ten způsobuje danou chybu. Kompilátory dále mají tendenci přidat na konec výpisu chyby informace, o co všechno se pokusili. Co to znamená, ukážeme na příkladu:

#include <iostream>
 
int main(){
    int i;
    std::cout >> i;
    std::cout << i;
}

Tento kus kódu se snaží načíst a vypsat jedno číslo, ale místo std::cin je v něm použit std::cout. Když ho proženeme skrz Clang, získáme tento výpis: |

test.cpp:5:15: error: invalid operands to binary expression ('ostream' (aka
'basic_ostream<char>') and 'int')
    std::cout >> i;
    ~~~~~~~~~ ^  ~
/usr/bin/../lib/gcc/x86_64-linux-gnu/5.3.1/../../../../include/c++/5.3.1/streambuf:168:9: note: candidate template ignored: could not match 'basic_istream' against 'basic_ostream'
        operator>>(basic_istream<_CharT2, _Traits2>&,
        ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/5.3.1/../../../../include/c++/5.3.1/istream:756:5: note: candidate template ignored: could not match 'basic_istream' against 'basic_ostream'
    operator>>(basic_istream<char, _Traits>& __in, unsigned char& __c)
    ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/5.3.1/../../../../include/c++/5.3.1/istream:761:5: note: candidate template ignored: could not match 'basic_istream' against 'basic_ostream'
    operator>>(basic_istream<char, _Traits>& __in, signed char& __c)
    ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/5.3.1/../../../../include/c++/5.3.1/istream:803:5: note: candidate template ignored: could not match 'basic_istream' against 'basic_ostream'
    operator>>(basic_istream<char, _Traits>& __in, unsigned char* __s)
    ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/5.3.1/../../../../include/c++/5.3.1/istream:808:5: note: candidate template ignored: could not match 'basic_istream' against 'basic_ostream'
    operator>>(basic_istream<char, _Traits>& __in, signed char* __s)
    ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/5.3.1/../../../../include/c++/5.3.1/bits/istream.tcc:923:5: note: candidate template ignored: could not match 'basic_istream' against 'basic_ostream'
    operator>>(basic_istream<_CharT, _Traits>& __in, _CharT& __c)
    ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/5.3.1/../../../../include/c++/5.3.1/bits/istream.tcc:955:5: note: candidate template ignored: could not match 'basic_istream' against 'basic_ostream'
    operator>>(basic_istream<_CharT, _Traits>& __in, _CharT* __s)
    ^
1 error generated.

++

Hned první řádek výpisu se odkazuje do našeho kódu a zhruba říká, kde je chyba (nemůžeme použít operátor >> na výstupní proud a int), ale výpis obsahuje spoustu dalších řádků, které popisují, co všechno kompilátor zkusil, než došel k tomu, že to je chyba. V tomto případě vyzkoušel různá přetížení operátoru >>, ale zjistil, že žádné z nich nepasuje pro daný výraz.

Pokud vám linkování programu selže s chybou během linkování, pravděpodobně to znamená, že nelinkujete vše, co máte.

• Pokud vám chybí funkce main, nejspíše kompilujete pouze soubor s vaší implementací a nekompilujete soubory s testy.
• Pokud vám chybí funkce, které máte implementovat, nejspíše kompilujete pouze soubory s testy a nekompilujete s nimi i vaši implementaci.
• Pokud vám chybí funkce s Catch:: v názvu, nekompilujete tests-main.cpp.

Úkol obsahuje časově náročné testy, které jsou při normálním spuštění vypnuté. Pokud je chcete spustit, musíte zavolat výslednou binárku s argumentem [.long]:

small1 [.long]

Silně doporučujeme ho spouštět pouze v optimalizované binárce, tj. kompilovat v Release módu nebo na příkazové řádce s parametrem -O3.