Přidej si svou IT školu do profilu a najdi spolužáky zde na síti :)

Součtové typy v C++

C a C++ C++ Pokročilé konstrukce v C++ Součtové typy v C++

Unicorn College ONEbit hosting Tento obsah je dostupný zdarma v rámci projektu IT lidem. Vydávání, hosting a aktualizace umožňují jeho sponzoři.

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.


 

 

Článek pro vás napsal Petr Homola
Avatar
Jak se ti líbí článek?
Ještě nikdo nehodnotil, buď první!
Miniatura
Předchozí článek
Knihovny v jazyce C a C++
Miniatura
Všechny články v sekci
Pokročilé konstrukce C++
Aktivity (2)

 

 

Komentáře

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zatím nikdo nevložil komentář - buď první!