Search
Ú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.
std::shared_ptr
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.
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 Visibility2) na Private, abyste se vyhnuli problémům s plagiátorstvím.
Do upload systému tentokrát nahrajte všechny zdrojové soubory3). Soubory s testy (podadresář tests) a knihovnu mapbox neodevzdávejte.
tests
mapbox
Na gitlabu je i konfigurace pro Gitlab CI4) .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.
.gitlab-ci.yml
Jméno souboru v hranatých závorkách vyjadřuje doporučené místo implementace.
expr_base
expr_impl.cpp
expr_impl.hpp
write
throw std::logic_error(“not implemented yet”);
expr
expr::number
expr::variable
expr.cpp
create_expression_tree
parse_error
handle_expr_line
app.cpp
parse_command
process_expr
main
main.cpp
evaluate
expr::ZERO
expr::ONE
derive
equals
dynamic_cast
simplify
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.
std::unique_ptr
shared_ptr
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)
this
std::make_shared(this)
std::enable_shared_from_this
shared_from_this()
Reference:
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.
sin
cos
log
^
*
/
+
-
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)).
1 + 2
1+2
1 +2
1+ 2
(1 + 2)
((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á.
)2 + 1(
1 + 1 +
1+5%
tanh(x)
Unární mínus (tedy negace) není pro jednoduchost zahrnuto – výraz -x se dá ekvivalentně zapsat jako 0-x.
-x
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.
Tokenizer
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říklad6):
$ ./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.
proměnná=číslo
varB
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.
x
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é.
$ ./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.
==
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.
$ ./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ů7). Pro ladění doporučujeme použít přímé unit testy (tests-direct), případně potom tests-runner-direct.
tests-direct
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.
./tests-direct “[evaluate],[simplify]”
./tests-direct “~[evaluate]~[simplify]”
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.
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=./symcalc8).
TEST_CMD
make test
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í:
std::shared_ptr<expr_base>
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.
typedef
valgrind ./symcalc