Súčtové typy v C ++

V predchádzajúcom cvičení, Riešené úlohy k 10.-13. lekciu pokročilých konštrukcií C ++, sme si precvičili získané skúsenosti z predchádzajúcich lekcií.

V nedávno schválenom štandarde C ++ 17 pribudol okrem iného v STL typ std::variant umožňujúce definovať vlastný súčtové typy. Na súčtové typy možno nazerať ako na zozname typov, pričom inštancia súčtového typu je inštancií práve jedného typu zo spomínaného zoznamu. Tieto typy sa používajú predovšetkým vo funkcionálnych jazykoch, ale má ich aj napríklad Swift.

V tomto článku si ukážeme príklad typu pre reprezentáciu aritmetických výrazov. V Haskell by definícia podporujúce konštanty, sčítanie a násobenie vyzerala takto:

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

Vzápätí si ukážeme, ako taký algebraický typ implementovať v C ++ vrátane metódy eval() pre vyhodnotenie hodnoty výrazu.

V prvom rade musíme zabezpečiť dostupnosť typu "variantov":

#include <variant>

Ešte raz upozorňujem, že variant je súčasťou STL až od verzie C ++ 17 a preklad bude pravdepodobne vyžadovať použitie prepínača -std=c++17 (v Clang, iné prekladača sa môžu líšiť).

Než sa začneme venovať typu pre výrazy, definujeme si pomocný typ pre referencie:

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

Ide v podstate len o "alias" na std::shared_ptr zpřehledňující kód a uľahčujúce použitie iného typu pre chytré ukazovatele.

Ako už bolo uvedené, náš typ pre výrazy bude podporovať sčítanie a násobenie (ďalšie operácie si každý iste ľahko doplní sám). K tomu budeme potrebovať dve pomocné triedy:

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

Ako názvy napovedajú, prvý z nich použijeme pre výraz reprezentujúci súčet a druhú pre súčin. Všimnite si, že nešpecifikuje konkrétne triedu reprezentujúci výrazy, namiesto toho máme len šablónu F. Výrazy, na ktorých operujú Add a Mul, sú typu F<T>.

Teraz sa už dostaneme k triede pre výraz. Jej základná verzia vyzerá 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 súčtovým typom a hovorí, že naša trieda je hodnota typu buď T, alebo Ref<Add<Expr,T>>, alebo Ref<Mul<Expr,T>>. Pre jednoduchšie vytváranie inštancií máme konštruktor pre konštantu (typ T) a zvlášť konštruktory pre Add a Mul. Všimnite si, že Expr nemá žiadne vlastné dáta, iba pri inicializácii volá konštruktor svojho hlavnými typmi. Jednoduchý výraz môžeme vytvoriť napríklad takto:

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

Chýba nám však Add a Mul, aby všetko 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();
  }
};

Tu je vidieť, ako sa použije F<T> pre podvýrazy. Metóda eval() iba jednoducho podvýrazy rekurzívne vyhodnotí a medzivýsledky nakoniec spočíta alebo vynásobí.

Teraz sa ešte musíme vrátiť k Expr a doplniť metódu eval(). Celá definícia vyzerá 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");
    }
  }
};

Implementácia metódy eval() je pomerne priamočiara. this->index() nám hovorí, akú hodnotu std::variant zrovna drží, a práve podľa toho sa rozhodujeme, ako výraz vyhodnotiť. Ak ide o konštantu, jednoducho ju vrátime (ide o typ T). Ak sa jedná o zložený výraz, zavoláme na neho eval(), čím sa rekurzívne vyhodnotí podvýrazy. Všimnite si, že vyhodnotenie pre case 1 a case 2 musíme uviesť osobitne, pretože preklad kódu pre std::get<N> závisí od konkrétnej hodnote N už v čase kompilácie.

V článku sme si ukázali jednoduchý príklad použitia generického typu pre reprezentáciu aritmetických výrazov využívajúce súčtový typ std::variant z nedávno schváleného štandardu C ++ 17.

V nasledujúcom cvičení, Riešené úlohy k 1.-4. lekciu pokročilých konštrukcií C ++, si precvičíme nadobudnuté skúsenosti z predchádzajúcich lekcií.