Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

Součtové typy v C++

V předešlém cvičení, Řešené úlohy k 14.-17. lekci pokročilých konstrukcí C++, jsme si procvičili nabyté zkušenosti z předchozích lekcí.

V nedávno schváleném standardu C++17 přibyl kromě jiného v STL typ std::variant umožňující definovat vlastní součtové typy. Na součtové typy lze nahlížet jako na seznamu typů, přičemž instance součtového typu je instancí právě jednoho typu ze zmíněného seznamu. Tyto typy se používají především ve funkcionálních jazycích, ale má je také například Swift.

V tomto článku si ukážeme příklad typu pro reprezentaci aritmetických výrazů. V Haskellu by definice podporující konstanty, sčítání a násobení vypadala takto:

data Expr a = Const a | Add (Expr a) (Expr a) | Mul (Expr a) (Expr a)

Vzápětí si ukážeme, jak takový algebraický typ implementovat v C++ včetně metody eval() pro vyhodnocení hodnoty výrazu.

V prvé řadě musíme zajistit dostupnost typu "variant":

#include <variant>

Ještě jednou upozorňuji, že variant je součástí STL až od verze C++17 a překlad bude nejspíše vyžadovat použití přepínače -std=c++17 (v clangu, jiné překladače se mohou lišit).

Než se začneme věnovat typu pro výrazy, definujeme si pomocný typ pro reference:

template<typename T> using Ref = std::shared_ptr<T>;
template<typename T, typename... Args> Ref<T> make_ref(Args&&... args) { return std::make_shared<T>(std::forward<Args>(args)...); }

Jedná se v podstatě jen o "alias" na std::shared_ptr zpřehledňující kód a usnadňující použití jiného typu pro chytré ukazatele.

Jak již bylo uvedeno, náš typ pro výrazy bude podporovat sčítání a násobení (další operace si každý jistě snadno doplní sám). K tomu budeme potřebovat dvě pomocné třídy:

template<template<typename> class F, typename T> struct Add;
template<template<typename> class F, typename T> struct Mul;

Jak názvy napovídají, první z nich použijeme pro výraz reprezentující součet a druhou pro součin. Všimněte si, že nespecifikujeme konkrétní třídu reprezentující výrazy, místo toho máme jen šablonu F. Výrazy, na kterých operují Add a Mul, jsou typu F<T>.

Teď se již dostaneme k třídě pro výraz. Její základní verze vypadá takto:

template<typename T> struct Expr : std::variant<T,Ref<Add<Expr,T>>,Ref<Mul<Expr,T>>> {
  Expr(const T& x) : std::variant<T,Ref<Add<Expr,T>>,Ref<Mul<Expr,T>>>(x) {}
  Expr(const Add<Expr,T>& e) : std::variant<T,Ref<Add<Expr,T>>,Ref<Mul<Expr,T>>>(make_ref<Add<Expr,T>>(e)) {}
  Expr(const Mul<Expr,T>& e) : std::variant<T,Ref<Add<Expr,T>>,Ref<Mul<Expr,T>>>(make_ref<Mul<Expr,T>>(e)) {}
};

Výraz std::variant<T,Ref<Add<Expr,T>>,Ref<Mul<Expr,T>>> je součtovým typem a říká, že naše třída je hodnota typu buď T, nebo Ref<Add<Expr,T>>, nebo Ref<Mul<Expr,T>>. Pro snadnější vytváření instancí máme konstruktor pro konstantu (typ T) a zvlášť konstruktory pro Add a Mul. Všimněte si, že Expr nemá žádná vlastní data, pouze při inicializaci volá konstruktor svého nadtypu. Jednoduchý výraz můžeme vytvořit například takto:

const auto& expr = Expr(Mul(Expr(2), Expr(3)));

Chybí nám ovšem Add a Mul, aby vše fungovalo:

template<template<typename> class F, typename T> struct Add {
  F<T> expr1, expr2;
  Add(const F<T>& e1, const F<T>& e2) : expr1(e1), expr2(e2) {}
  T eval() const {
    return expr1.eval() + expr2.eval();
  }
};

template<template<typename> class F, typename T> struct Mul {
  F<T> expr1, expr2;
  Mul(const F<T>& e1, const F<T>& e2) : expr1(e1), expr2(e2) {}
  T eval() const {
    return expr1.eval() * expr2.eval();
  }
};

Zde je vidět, jak se použije F<T> pro podvýrazy. Metoda eval() pouze jednoduše podvýrazy rekurzivně vyhodnotí a mezivýsledky nakonec sečte nebo vynásobí.

Teď se ještě musíme vrátit k Expr a doplnit metodu eval(). Celá definice vypadá takto:

template<typename T> struct Expr : std::variant<T,Ref<Add<Expr,T>>,Ref<Mul<Expr,T>>> {
  Expr(const T& x) : std::variant<T,Ref<Add<Expr,T>>,Ref<Mul<Expr,T>>>(x) {}
  Expr(const Add<Expr,T>& e) : std::variant<T,Ref<Add<Expr,T>>,Ref<Mul<Expr,T>>>(make_ref<Add<Expr,T>>(e)) {}
  Expr(const Mul<Expr,T>& e) : std::variant<T,Ref<Add<Expr,T>>,Ref<Mul<Expr,T>>>(make_ref<Mul<Expr,T>>(e)) {}
  T eval() const {
    switch (this->index()) {
      case 0:
        return std::get<0>(*this);
      case 1:
        return std::get<1>(*this)->eval();
      case 2:
        return std::get<2>(*this)->eval();
      default:
        throw std::runtime_error("don't know how to evaluate");
    }
  }
};

Implementace metody eval() je poměrně přímočará. this->index() nám říká, jakou hodnotu std::variant zrovna drží, a právě podle toho se rozhodujeme, jak výraz vyhodnotit. Jde-li o konstantu, prostě ji vrátíme (jde o typ T). Jedná-li se o složený výraz, zavoláme na něj eval(), čímž se rekurzivně vyhodnotí podvýrazy. Všimněte si, že vyhodnocení pro case 1 a case 2 musíme uvést zvlášť, protože překlad kódu pro std::get<N> závisí na konkrétní hodnotě N již v čase kompilace.

V článku jsme si ukázali jednoduchý příklad použití generického typu pro reprezentaci aritmetických výrazů využívající součtový typ std::variant z nedávno schváleného standardu C++17.


 

Předchozí článek
Řešené úlohy k 14.-17. lekci pokročilých konstrukcí C++
Všechny články v sekci
Pokročilé konstrukce C++
Článek pro vás napsal Petr Homola
Avatar
Uživatelské hodnocení:
Ještě nikdo nehodnotil, buď první!
Autor se věnuje HPC a umělé inteligenci
Aktivity