% 2013 Vladimír Štill, CC BY 3.0
\documentclass[10pt]{beamer}
\usepackage[T1]{fontenc} % to make text copyable, before inputenca
\usepackage[utf8]{inputenc}
\usepackage[czech]{babel}
\usepackage{lmodern}

\beamertemplatenavigationsymbolsempty
\usetheme{Frankfurt}
\setbeamercolor{title}{bg=green!40!black}
\setbeamercolor{frametitle}{bg=green!40!black}
\setbeamercolor{block title}{bg=green!45!black}
\setbeamercolor{block title alerted}{bg=yellow!50!red!80!black}
\setbeamercolor{alerted}{bg=yellow!50!red!80!black}
\setbeamertemplate{headline}{}

\usepackage{verbatim}
\usepackage[final]{listings}
\lstset{ language=C++, basicstyle=\footnotesize }
\usepackage{paralist}

\usepackage{xspace}
\usepackage{pgf}
\usepackage{tikz}
\usetikzlibrary{arrows}
\usepackage{pgfplots}

\usepackage{multirow}
\usepackage{microtype}

\usepackage{xcolor}
\newcommand{\red}[1]{\textcolor{red}{#1}}

\newcommand{\tit}{Abusing Templates}

\title{\tit}
\subtitle{(More like using them for non-obvious things)}
\author{Vladimír Štill\\%
    {\footnotesize\href{http://paradise.fi.muni.cz/~xstill/darcs/AbusingTemplates}%
    {paradise.fi.muni.cz/\textasciitilde\,xstill/darcs/AbusingTemplates}{}}}
\date{4. 11. 2013}

\setbeamertemplate{footline}{\ \tit\hfill str. \insertframenumber/\inserttotalframenumber}

\newcommand{\N}{\ensuremath{\mathbb{N}}}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}}
\newcommand{\Q}{\ensuremath{\mathbb{Q}}}
\newcommand{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\C}{\ensuremath{\mathbb{C}}}
\newcommand{\set}[1]{\ensuremath{\{ #1 \}}}

\pgfplotsset{ width = \textwidth 
            , height = \textheight - 1.5em }

\begin{document}
\maketitle

\begin{frame}
\frametitle{C++ šablony}
\begin{itemize}
    \item parametrizované datové typy a funkce
    \item parametrizace:
    \begin{itemize}
        \item typovou proměnnou (type template parameter)
        \item hodnotou (non-type template parameter), jen primitivní hodnoty
        \item typový konstruktorem (template template parameter)
    \end{itemize}
    \item u šablonovaných typů nutné explicitně uvést parametry
    \item u funkcí se parametry mohou (částečně) odvodit
\end{itemize}

\lstinputlisting{ex01.h}
\end{frame}

\begin{frame}
\frametitle{Instanciace šablon}
\begin{itemize}
    \item šablona je jen předpis, skutečný kód se generuje až
        pro konkrétní hodnoty parametrů (pro každou použitou hodnotu
        šablonového parametru zvlášť), při kompilaci
    \item tato instanciace je typicky implicitní, tedy nastává při
        použití šablony
    \item u šablon typů se implicitně instancijují jen potřebné metody,
        ne všechny
\end{itemize}
\lstinputlisting{inst.cpp}
\end{frame}

\begin{frame}
\frametitle{Přetěžování funkcí}
Nešablonovaný parametr podléhá implicitním konverzím:
\lstinputlisting{overload0.cpp}
V přítomnosti šablonované verze mají nešablonované přednost, pokud
typy přesně odpovídají. Šablonovaná funkce má přednost před konverzí:
\lstinputlisting{overload1.cpp}
\end{frame}

\begin{frame}
\frametitle{Zakázání konverze}
Tyto vlastnosti šablon můžeme použít k zakázání implicitní konverze
\lstinputlisting{overload2.cpp}
Nezkompiluje se:
\lstinputlisting{overload2_err.txt}
\end{frame}

\begin{frame}
\frametitle{SFINAE: příklad}
Šablonované varianty funkcí lze zakázat v závislosti na parametru,
nevstupují pak vůbec do rozhodování:
\lstinputlisting{overload_disable.cpp}

Výstup: \texttt{int, T, int,}
\end{frame}

\begin{frame}
\frametitle{SFINAE: motivace, fungování}
Motivace
\begin{itemize}
\item Chceme volit různé verze funkcí v závislosti na daných podmínkách
\item Podmínky v závislosti na typových i netypových parametrech funkce
    (vnořený typ, typová ekvivalence, existence metody\dots)
\end{itemize}
Fungování
\begin{itemize}
\item \textbf{S}ubstitution \textbf{F}ailure \textbf{I}s \textbf{N}ot 
    \textbf{A}n \textbf{E}rror
\item pokud při substituci konkrétních parametrů dojde k tomu, že v
    typu funkce vznikne špatně utvořený výraz, funkce se deaktivuje
\item pokud existuje více verzí funkce a zůstane právě jedna nejspecifičtější
    aktivní pak se tato zvolí
\item pokud je více aktivních nejspecifičtějších funkcí, je to chyba
\item podpora v C++11 knihovně, hlavičkový soubor \texttt{<type\_traits>}
\item díky \texttt{decltype} je možné v typu použít libovolný
    výraz, ne jen typový
\item typicky se podmínky zapisují do návratového typu, pro přehlednost
    je lepší nový (C++11) způsob zápisu typu funkce
\item tělo funkce se v úvahu nebere!
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{SFINAE: příklad II}
\lstinputlisting{sfinae0.cpp}
Není možné zkompilovat:
\lstinputlisting{sfinae0_err.txt}
\end{frame}

\begin{frame}
\frametitle{SFINAE: problém}
Problém
\begin{itemize}
\item pokud existuje víc nejspecifičtějších funkcí, které zůstanou při
    řešení přetěžování, volání je nejednoznačné a způsobí chybu při
    kompilaci
\item řešením by mohlo být uvádět podmínky tak, aby vždy platila nejvýše
    jedna
\item to by však způsobovalo opakování kódu $\rightarrow$ nepřehlednost,
    špatná udržovatelnost
\item navíc některé podmínky nelze negovat (\texttt{decltype})
\end{itemize}
Řešení
\begin{itemize}
\item Prioritizace funkcí s využitím následujícího pravidla:
    \textit{Pokud existují 2 verze funkce takové, že se liší počtem
        implicitních konverzí, které jsou nutné k dosazení
    parametrů, pak má předost funkce kde je počet konverzí nižší.}
\item vyžaduje přidat další parametr/parametry
\item umožňuje zavést
    uspořádání na funkcích podle preference
    $\rightarrow$ vždy se
    zavolá první funkce, která není deaktivovaná, v daném pořadí
\item typické řešení z internetu používá implicitní konverze mezi
    číselnými typy, to však působí nejasně a magicky
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{SFINAE: příklad III}
\lstinputlisting{sfinae1.cpp}
\end{frame}

\begin{frame}
\frametitle{SFINAE: konkrétní problém}
Problém
\begin{itemize}
    \item Máme hierarchii tříd, které plní danou funkčnost (reportování
        výsledků v DIVINE). Tato hierarchie je postavená na virtuálních
        voláních. Kořenem hierarchie je třída \texttt{Report},
        která udává rozhraní.
    \item \texttt{std::shared\_ptr< Report > report}
    \item report chceme vytvářet pomocí statické factory metody
    \begin{itemize}
        \item parametrizovaná typem požadovaného reportu
        \item typicky bude konstruovat \texttt{shared\_ptr} na objekt požadovaného
            typu
        \item ve specifických případech chceme provést nějakou akci nad rámec konstruktoru
            daného typu
        \item například chceme umožnit, že v určitých případech nepůjde daný typ
            reportu zkonstruovat -- chceme vracet nulový ukazatel
    \end{itemize}
\end{itemize}
Naivní řešení
\begin{itemize}
    \item Do každé třídy implementující \texttt{Report} dáme statickou
        metodu \texttt{get}. To nám zároveň zajistí parametrizaci.
    \item Voláme něco jako \texttt{TextReport::get()}.
    \item \textbf{Nevýhoda: } většina get metod je téměř stejná, jen volá
        dynamickou alokaci příslušné třídy.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{SFINAE: konkrétní problém a řešení}
Řešení pomocí šablon a SFINAE
\begin{itemize}
    \item factory metodu umístíme do bázové třídy \texttt{Report}
    \item parametrizovaná požadovaným typem reportu
    \item pokud budeme chtít překrýt, umístíme do příslušné třídy
        statickou metodu \texttt{get}, která bude konstruovat
        objekt této konkrétní třídy
    \item bázová faktory metoda bude volat specifickou \texttt{get}
        metodu požadovaného potomka pokud tato existuje
    \item jinak provede alokaci a konstrukci potomka
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{SFINAE: konkrétní problém a řešení (zjednodušené)}
\lstinputlisting{sfinae_report.cpp}
\end{frame}

\begin{frame}
\frametitle{Variadické šablony}
Variadické funkce v C
\begin{itemize}
    \item C umožňuje mít funkce s volitelným počtem argumentů, jako
        například \texttt{printf}
    \item nulová typová bezpečnost -- kontrola při kompilaci naprosto chybí, nebo
        vyžaduje aby kompilátor znal příslušnou funkci
    \item možné používat i v C++98, ale jen v omezené míře, na jednoduché
        datové typy (bez konstruktorů, virtuálních metod,\dots)
\end{itemize}
Variadické šablony (C++11)
\begin{itemize}
    \item více parametrů můžeme zastoupit šablonou pro \textit{argument pack}
    \item typicky buď přímo předáváme všechny argumenty do jiné funkce,
        nebo postupně rekurzivně rozbalujeme
    \item odvození typů z použitých argumentů
    \item statická typová kontrola a volba funkce
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Variadické šablony -- příklad}
\lstinputlisting{variadic0.cpp}
\begin{itemize}
    \item z LLVM interpretru
    \item \texttt{MDNode} tvoří (n-ární) stromovou strukturu, pomocí funkce \texttt{node}
        můžeme snadno získat uzel v tomto stromě
    \item \texttt{node( root, 1, 4, 3, 0 )}
    \item při kompilaci se ověří, že všechny argumenty jsou typu \texttt{int} (nebo
        konvertovatelné)
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Perfect forwarding}
Motivace
\begin{itemize}
    \item umožňuje nám předat parametry funkce do jiné funkce
        tak jak jsou, bez kopírování
    \item typicky s použitím variadických šablon
    \item předávání parametrů konstruktoru přes factory metodu,\dots
    \item \texttt{std::vector< T >::emplace\_back()}
    \item využívá rvalue reference, \texttt{std::forward< T >()}
    \item rvalue reference = reference na dočasnou hodnotu
\end{itemize}
\lstinputlisting{variadic1.cpp}
\end{frame}

\begin{frame}
\frametitle{\texttt{declcheck}}
\begin{itemize}
    \item někdy chceme uvnitř \texttt{decltype} ověřit platnost více
        výrazů
    \item nebo chceme ověřit jen jejich platnost, ale návratový typ nás
        nezajímá
    \item definujeme speciální funkci, řekněme \texttt{declcheck} -- bere
        libovolné parametry libovolných typů, vrací požadovaný typ
    \item \textbf{pozor:} pokud se nám v \texttt{declcheck} výrazu objeví
        výraz vracející void, je celý výraz neplatný!
        $\rightarrow$ můžeme používat typ, který nese jedinou hodnotu
        namísto \texttt{void}, například \texttt{Unit} v příkladě
\end{itemize}
\lstinputlisting{declcheck.cpp}
\end{frame}

\begin{frame}
\frametitle{Singleton typy}
\begin{itemize}
    \item šablonované funkce dokáží odvodit šablonové parametry
    \item jen parametry, které lze odvodit z typů parametrů funkce
    \item tedy nefunguje přímo pro hodnotové šablonové parametry, typové parametry
        nepoužité v parametrech funkce
    \item někdy nemůžeme explicitně funkci předat typové parametry
    \begin{itemize}
        \item konstruktor
        \item více přetížených variant s různými typovými parametry
    \end{itemize}
    \item je možné používat \textit{type witness}
    \item často typ, který nenese žádnou významnou run-time hodnotu,
        má smysl jen při odvození typu -- singleton typ
    \item pro číselné konstanty lze použít \texttt{std::integral\_constant}
    \item type witness lze snadno předávat (typicky má triviální bezparametrický
        konstruktor, copy-konstruktor)
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Singleton typy -- příklad}
\lstinputlisting{singleton0.cpp}
\end{frame}

\begin{frame}
\begin{center}
    {\huge The Dark Side}

    \bigskip
    Instanciace komponent v DIVINE
\end{center}
\end{frame}

\begin{frame}
\frametitle{Problém}
\begin{itemize}
    \item v DIVINE je mnoho komponent, které jsou z důvodu výkonu
        staticky spojované při kompilaci pomocí šablon
    \item je třeba vybrat správnou kombinaci v závislosti na vstupu
    \item existuje mnoho kombinací (cca 3000)
    \item ne všechny kombinace dávají smysl (jen cca 900 smysluplných,
        některé nesmyslné kombinace nelze ani zkompilovat)
    \item počet kombinací značně roste s tím, jak se DIVINE rozšiřuje
\end{itemize}
Původní řešení
\begin{itemize}
    \item instanciace probíhala od algoritmu, ve fixním pořadí a pro každý
        typ komponenty byla samostatná funkce kódující výběr
    \item špatně se řešili nesmyslné volby, jedině ad-hoc řešení

        $\rightarrow$ spousta zbytečných instancí
    \item instanciace startuje z fixního množství souborů, odpovídá počtu
        algoritmů
        
        $\rightarrow$ kompilace jednoho souboru začala vyžadovat mnoho paměti
        ($> 8GB$)
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{současné řešení}
\begin{itemize}
    \item založené na automaticky generovaném kódu pro kompilaci
        instancí
    \item každá komponenta popsána strukturou obsahující:
    \begin{itemize}
        \item funkci pro výběr
        \item funkci provedenou po výběru
        \item hlavičkový soubor
        \item podmínky aktivace (s ohledem na ostatní komponenty)
    \end{itemize}
    \item selekční mechanismus vytvořený pomocí šablon
    \begin{itemize}
        \item umožňuje projít celý strom selekce (pro generování)
        \item nebo vybrat jedinou položku
    \end{itemize}
    \item podmínky aktivace vyhodnoceny při kompilaci selekčního algoritmu
        \begin{itemize}
            \item v závislosti na již vybraných typech
        \end{itemize}
    \item pořadí typů komponent k selekci a pořadí komponent v rámci typu
        dáno seznamem typů
\end{itemize}

\smallskip
\begin{itemize}
    \item \texttt{divine/toolkit/typelist.h}
    \item \texttt{divine/instances/definitions.h}
    \item \texttt{divine/instances/select-impl.h}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{\texttt{TypeList}}
\begin{itemize}
    \item singleton typ, seznam libovolného počtu typů
    \item zná svou délku, snadná iterace
    \item základní funkce pro manipulaci s typovými seznamy
    \item kóduje komponenty
    \item kóduje rovněž podmínky instanciace
\end{itemize}
\lstinputlisting{typelist.h}
\end{frame}

\begin{frame}
    \lstinputlisting{typelist1.h}
\end{frame}

\begin{frame}
\frametitle{Definice komponent}
\begin{itemize}
    \item pomocí C maker jsou zadefinovány struktury pro příslušné komponenty
    \item seznam komponent je v \texttt{TypeList}
\end{itemize}
\lstinputlisting{definitions.h}
\end{frame}

\begin{frame}
\frametitle{Selektor}
\begin{itemize}
    \item jádro systému
    \item postupně prochází seznamy komponent a z nich vybírá dostupné
    \item příliš dlouhé na ukázku, pro příklad přetížená varianta funkce,
        která se volá pokud nedošlo k chybě instanciace ale komponenta je povolená
\end{itemize}
\lstinputlisting{sel.h}
\end{frame}

\begin{frame}
\frametitle{zhodnocení současného řešení}
Klady
\begin{itemize}
    \item je možné specifikovat snadno kolik instancí se kompiluje najednou
    \item menší nároky na paměť při kompilaci
    \item přesné vyjádření požadavků pro platnou kombinaci
    \item snadno rozšířitelné o další komponenty
    \item lepší využití paralelní kompilace
\end{itemize}
Zápory
\begin{itemize}
    \item s počtem komponent roste doba kompilace samotného generátoru
    \item kompilace je pomalejší na stroji s dostatkem paměti pro původní verzi
    \item vyžaduje samostatný krok v buildu který zkompiluje a spustí generátor
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Závěr}
Děkuji za pozornost

\bigskip
\bigskip
Pokud vás problematika zaujala\dots
\begin{itemize}
    \item \href{http://cppreference.com}{cppreference.com} je 
        vhodným zdrojem pro další studium
    \item \href{http://en.cppreference.com/w/cpp/types}{Type Support} a hlavičkový soubor \texttt{<type\_traits>}
    \item \href{http://en.cppreference.com/w/cpp/language/class_template}{Typové šablony}
        a jejich
        \href{http://en.cppreference.com/w/cpp/language/template_specialization}{specializace}
        +
        \href{http://en.cppreference.com/w/cpp/language/partial_specialization}{částečná specializace}
    \item \href{http://en.cppreference.com/w/cpp/language/function_template}{Funkční šablony}
    \item \href{http://www.gotw.ca/publications/mill17.htm}{Proč nespecializovat funkční šablony}
    \item zdrojové soubory DIVINE \texttt{:-)}
\end{itemize}
\end{frame}


\end{document}
