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.