D0080R1.latex

\documentclass[11pt]{article}

\usepackage{color}
\usepackage{xcolor}
\usepackage{fullpage}
\usepackage[colorlinks, allcolors=blue]{hyperref}
\usepackage{listings}
\usepackage{parskip}
\usepackage{url}
\usepackage{courier}
\usepackage[T1]{fontenc}
% \usepackage{libertine}%% Only as example for the romans/sans fonts
\usepackage[scaled=0.85]{beramono}
\usepackage{changepage}
\usepackage{nameref}

% Solarized colour scheme for listings
\definecolor{solarized@base03}{HTML}{002B36}
\definecolor{solarized@base02}{HTML}{073642}
\definecolor{solarized@base01}{HTML}{586e75}
\definecolor{solarized@base00}{HTML}{657b83}
\definecolor{solarized@base0}{HTML}{839496}
\definecolor{solarized@base1}{HTML}{93a1a1}
\definecolor{solarized@base2}{HTML}{EEE8D5}
\definecolor{solarized@base3}{HTML}{FDF6E3}
\definecolor{solarized@yellow}{HTML}{B58900}
\definecolor{solarized@orange}{HTML}{CB4B16}
\definecolor{solarized@red}{HTML}{DC322F}
\definecolor{solarized@magenta}{HTML}{D33682}
\definecolor{solarized@violet}{HTML}{6C71C4}
\definecolor{solarized@blue}{HTML}{268BD2}
\definecolor{solarized@cyan}{HTML}{2AA198}
\definecolor{solarized@green}{HTML}{859900}

\lstset{
  basicstyle=\footnotesize\ttfamily,
}

% Define C++ syntax highlighting colour scheme
\lstdefinelanguage{cpp}{
  language=C++,
  basicstyle=\footnotesize\ttfamily,
  numbers=left,
  numberstyle=\footnotesize,
  tabsize=2,
  breaklines=true,
  escapeinside={@}{@},
  numberstyle=\tiny\color{solarized@base01},
  keywordstyle=\color{solarized@green},
  stringstyle=\color{solarized@cyan}\ttfamily,
  identifierstyle=\color{solarized@blue},
  commentstyle=\color{solarized@base01},
  emphstyle=\color{solarized@red},
  frame=single,
  rulecolor=\color{solarized@base2},
  rulesepcolor=\color{solarized@base2},
  showstringspaces=false,
}

\lstdefinelanguage{diff}{
  morecomment=[f][\color{blue}]{@@},           % group identifier
  morecomment=[f][\color{red}]{-},             % deleted lines
  morecomment=[f][\color{green!50!black}]{+},  % added lines
  morecomment=[f][\color{magenta}]{---},       % diff header lines
  morecomment=[f][\color{magenta}]{+++},
}

\lstdefinelanguage{plus}{
  basicstyle=\footnotesize\ttfamily\color{green!50!black},
  emph={see,below,TypeSwitch,unspecified},
  emphstyle=\itshape
}

\lstdefinelanguage{signature}{
  basicstyle=\ttfamily\color{green!50!black},
  emph={see,below,TypeSwitch,unspecified},
  emphstyle=\itshape
}

\newcommand{\desc}[1]{\textit{#1}}
\newcommand{\requires}{\desc{Requires}}
\newcommand{\effects}{\desc{Effects}}
\newcommand{\precondition}{\desc{Precondition}}
\newcommand{\postcondition}{\desc{Postcondition}}
\newcommand{\throws}{\desc{Throws}}
\newcommand{\returns}{\desc{Returns}}
\newcommand{\remarks}{\desc{Remarks}}
\newcommand{\exceptionsafety}{\desc{Exception Safety}}

\newcommand{\fullref}[1]{\ref{#1} \nameref{#1}}

\date{}
\title{Tweaks to the Kona Variant}

\newcommand{\emailaddress}{mcypark@gmail.com}
\newcommand{\email}{\href{mailto:\emailaddress}{\emailaddress}}

\begin{document}

\maketitle\vspace{-2cm}

\begin{flushright}
  \begin{tabular}{ll}
  Document \#:&D0080R1\\
  Date:       &\date{2015-10-20}\\
  Project:    &Programming Language C++\\
              &Library Evolution Group\\
  Reply-to:   &\author{Michael Park}\\
              &\textless\email\textgreater
  \end{tabular}
\end{flushright}

\section{Introduction}
This paper proposes tweaks to the Kona \texttt{variant}.

\section{Motivation and Scope}
The main motivation is to increase consistency, usability and readability of the
Kona \texttt{variant}. It does not question the fundamental design of
\texttt{variant} which reached consensus, but mainly around the visitation
mechanism.

\section{Impact on the Standard}
This proposal is a pure library extension, and does not require any new language
features.

\section{Proposed Wording}
Make the following changes to \texttt{<experimental/optional>} header:

\begin{lstlisting}[language=diff]
namespace std {
namespace experimental {
- constexpr in_place_t in_place{};
+ in_place_t in_place() { return {}; }

- template <class... Args> constexpr explicit optional(in_place_t, Args&&...);
+ template <class... Args> constexpr explicit optional(in_place_t (&)(), Args&&...);

  template <class U, class... Args>
- constexpr explicit optional(in_place_t, initializer_list<U>, Args&&...);
+ constexpr explicit optional(in_place_t (&)(), initializer_list<U>, Args&&...);
} // namespace experimental
} // namespace std
\end{lstlisting}

Make the following changes to \texttt{<experimental/variant>} header:

\begin{lstlisting}[language=diff]
namespace std {
namespace experimental {
- template <class T> struct emplaced_type_t{};
- template <class T> constexpr emplaced_type_t<T> emplaced_type;
+ template <class T> in_place_t in_place(T) { return {}; }

- template <size_t I> struct emplaced_index_t{};
- template <size_t I> constexpr emplaced_index_t<I> emplaced_index;
+ template <size_t I> in_place_t in_place(integral_constant<size_t, I>) { return {}; }

  template <class... Types>
  class variant {
  public:
    /* ... */

    template <class T, class... Args>
-   constexpr explicit variant(emplaced_type_t<T>, Args&&...);
+   constexpr explicit variant(in_place_t (&)(T), Args&&...);

    template <class T, class U, class... Args>
-   constexpr explicit variant(emplaced_type_t<T>, initializer_list<U>, Args&&...);
+   constexpr explicit variant(in_place_t (&)(T), initializer_list<U>, Args&&...);

    template <size_t I, class... Args>
-   constexpr explicit variant(emplaced_index_t<I>, Args&&...);
+   constexpr explicit variant(in_place_t (&)(integral_constant<size_t, I>), Args&&...);

    template <size_t I, class U, class... Args>
-   constexpr explicit variant(emplaced_index_t<I>, initializer_list<U>, Args&&...);
+   constexpr explicit variant(in_place_t (&)(integral_constant<size_t, I>), initializer_list<U>, Args&&...);

    /* ... */
  };

- template <class Visitor, class... Variants>
- decltype(auto) visit(Visitor&&, Variants&&...);

+ template <class R = deduce_tag, class... Variants>
+ unspecified:TypeSwitch<R, Variants...> type_switch(Variants&&...);
} // namespace experimental
} // namespace std
\end{lstlisting}

{\color{green!50!black}
\paragraph{Visitation}\hfill\textbf{[variant.visit]}
}

\begin{lstlisting}[language=signature]
template <class R = deduce_tag, class... Variants>
unspecified:TypeSwitch<R, Variants&&...> type_switch(Variants&&... vs);
\end{lstlisting}

{
\begin{adjustwidth}{2em}{}
\color{green!50!black}

\effects: Constructs a callable object \textit{\texttt{TypeSwitch}} which holds references
to \texttt{forward<Variants>(vs)...}. Because the result may contain references to
temporary variables, a program shall ensure that the return value of this function does
not outlive any of its arguments. (e.g., the program should typically not store
the result in a named variable).

\end{adjustwidth}
}

\begin{lstlisting}[language=signature]
template <class R, class... Variants>
struct TypeSwitch {
  explicit TypeSwitch(Variants...);

  template <class F>
  see below TypeSwitch::operator()(F&&) const;

  template <class... Fs>
  see below TypeSwitch::operator()(Fs&&...) const;

  template <template <class...> class F, class... Args>
  see below TypeSwitch::operator()(const typed_visitor<F, Args...>&) const;
};
\end{lstlisting}

\begin{lstlisting}[language=signature]
explicit TypeSwitch(Variants... vs);
\end{lstlisting}

{
\begin{adjustwidth}{2em}{}
\color{green!50!black}

\effects: Holds references to \texttt{vs...}.

\end{adjustwidth}
}

\begin{lstlisting}[language=signature]
template <class F>
see below TypeSwitch::operator()(F&& f) const;
\end{lstlisting}

{
\begin{adjustwidth}{2em}{}
\color{green!50!black}

Let \texttt{vs...} be the references to instances of \texttt{Variants...} that
\textit{\texttt{TypeSwitch}} holds.

Let \texttt{Variant\textsubscript{I}} be the \texttt{I\textsuperscript{th}} type
in \texttt{decay\_t<Variants>{}>...}.

Let \texttt{Types\textsubscript{I}...} be the template parameter pack
\texttt{Types...} of \texttt{Variant\textsubscript{I}}.

\requires: \texttt{forward<F>(f).template operator()<I\textsubscript{0}, ...,
  I\textsubscript{N}>(get<I\textsubscript{0}>(v\textsubscript{0}), ...,
  get<I\textsubscript{N}>(v\textsubscript{N})) OR invoke(forward<F>(f),
  get<I\textsubscript{0}>(v\textsubscript{0}), ...,
  get<I\textsubscript{N}>(v\textsubscript{N}))}
  must be a valid expression for all \texttt{I\textsubscript{I}} where
  \texttt{I\textsubscript{I}} \(\in\) \texttt{[ 0, sizeof...(Types\textsubscript{I})]}.

\effects: Let \texttt{Is...} be the constant expression of
  \texttt{vs.index()...}. Equivalent to \texttt{forward<F>(f).template
  operator()<Is...>(get<Is>(vs)...)} if it is a valid expression, otherwise
  equivalent to \texttt{invoke(forward<F>(f), get<Is>(vs)...)};

\remarks: If \texttt{!is\_same\_v<R, \textit{unspecified}:deduce\_tag>} is
  \texttt{true}, the return type of this function is \texttt{R}.

  Otherwise, if \texttt{decay\_t<F>} contains a member typedef
  \texttt{result\_type}, the return type is
  \texttt{typename decay\_t<F>::result\_type}.

  Otherwise, the return type is deduced by \texttt{decltype(auto)}.

\end{adjustwidth}
}

\begin{lstlisting}[language=signature]
template <class... Fs>
see below TypeSwitch::operator()(Fs&&... fs) const;
\end{lstlisting}

{
\begin{adjustwidth}{2em}{}
\color{green!50!black}

\effects: Equivalent to \texttt{(*this)(overload(forward<Fs>(fs)...));  // P0051}

\end{adjustwidth}
}

\section{Design Discussion}

\subsection{\texttt{Motifications to \texttt{visit}}}

\cite{N3915} proposed \texttt{apply} which takes a function object \texttt{F}
and a tuple \texttt{Tuple}, and dispatches \texttt{F} with the elements of
\texttt{Tuple}. The \texttt{visit} function was introduced to accompany the Kona
\texttt{variant}. This function is similar to \texttt{apply}, as it takes a
function object \texttt{F} and \texttt{Variants...}, and dispatches \texttt{F}
with the content of each the \texttt{Variants...}.

Although the similarity to \texttt{apply} may seem desirable for consistency,
I claim that there are major drawbacks at the callsite. The inherent difference
between \texttt{apply} and \texttt{visit} is that \texttt{apply} only requires a
single handler that handles the elements of the \texttt{tuple}, whereas
\texttt{visit} (almost always) requires many handlers that handle the
cartesian product of the alternatives of the \texttt{variant} objects.

Consider a few sample usages of visiting a \texttt{variant<int, std::string>}
The following are 3 of the possible ways to provide the handlers via the
\texttt{visit} interface.

\begin{itemize}
  \item Function object which requires out-of-line definition.
  \item Generic lambda to provide a single generic handler inline.
  \item \texttt{overload} to provide specific handlers inline.  // P0051
\end{itemize}

\begin{lstlisting}[language=cpp]
struct Print {
  void operator()(int value) const { std::cout << "int: " << value; }
  void operator()(const std::string& value) const { std::cout << "string: " << value; }
};

int main() {
  std::variant<int, std::string> v(42);

  // Function object defined out-of-line.
  std::visit(Print{}, v);

  // Generic lambda to provide a generic handler inline.
  std::visit([](const auto& value) { std::cout << value; }, v);

  // `overload` to provide specific handlers inline.  // P0051
  std::visit(
    overload([](int value) { std::cout << "int: " << value; },
             [](const std::string& value) { std::cout << "string: " << value; }),
    v);

  // copy construction.
  std::variant<int, std::string> w(v);

  // multi-visitation
  std::visit(
      overload([](int, int) { std::cout << "(int, int)"; },
               [](int, const std::string &) { std::cout << "(int, string)"; },
               [](const std::string &, int) { std::cout << "(string, int)"; },
               [](const std::string &, const std::string &) { std::cout << "(string, string)"; }),
      v, w);
}
\end{lstlisting}

Aside from \texttt{overload} not yet existing in the standard as a utility, it
also flips the order of variants and handlers. It would be enhance readability
to list the variants to be handled, followed by the handlers (similar to the
structure of \texttt{switch}).

Constrast this with \texttt{type\_switch}.

\begin{lstlisting}[language=cpp]
struct Print {
  void operator()(int value) const { std::cout << "int: " << value; }
  void operator()(const std::string& value) const { std::cout << "string: " << value; }
};

int main() {
  std::variant<int, std::string> v(42);

  // Function object defined out-of-line.
  std::type_switch (v) (Print{});

  // Generic lambda to provide a generic handler inline.
  std::type_switch (v) (
    [](const auto& value) { std::cout << value; }
  );

  // No need for `overload`.
  std::type_switch (v) (
    [](int value) { std::cout << "int: " << value; },
    [](const std::string& value) { std::cout << "string: " << value; }
  );

  // copy construction.
  std::variant<int, std::string> w(v);

  // multi-visitation.
  std::type_switch (v, w) (
    [](int               , int               ) { std::cout << "(int, int)"      ; },
    [](int               , const std::string&) { std::cout << "(int, string)"   ; },
    [](const std::string&, int               ) { std::cout << "(string, int)"   ; },
    [](const std::string&, const std::string&) { std::cout << "(string, string)"; }
  );
}
\end{lstlisting}

\subsection{Explicit Return Type}
In order to mitigate the requirement that all handlers must be the same type, it
would be convenient to allow the user to explicitly provide the return type.

Rather than modifying every handler to return the same type, the user can
explicitly provide the return type to which all return types of the handlers
must be implicitly convertible to.

\begin{lstlisting}[language=cpp]
std::variant<int, std::string> v(42);
auto result = std::type_switch<int64_t> (v) (
  [](int value) { return value; },
  [](const std::string& value) { return value.size(); }
);
// decltype(result) == int64_t
\end{lstlisting}

\subsection{Index-Aware Handlers}
In cases where it is useful to know the original type in which the value came
from, an index-aware handler can be provided to retrieve the indices of the
originating types. This situation can arise from duplicate types, but also from
the consequence of allowing references.

\begin{lstlisting}[language=cpp]
int x = 42;
variant<int, int&> v(in_place<1>, x);
type_switch (v) ( [](int&) { /* matches both int, and int& */ );

// index-aware handler
struct index_aware {
  template <size_t I>
  void operator()(int&) const {
    /* still matches both int, and int&, but `I` tells you which one. */
  }
};

type_switch (v) ( index_aware{} );
\end{lstlisting}

Since non-deduced template parameters cannot be specified in a lambda, the
implication here is that an index aware handler must be defined as an
out-of-line function object. However, considering that this is likely a
rare use case, it is unlikely to be an issue.

\section{Acknowledgements}

\begin{itemize}
  \item \textbf{Eric Friedman} and \textbf{Itay Maman} for the development of
    \cite{Boost.Variant}.
  \item \textbf{Agust\'in Berg\'e} (a.k.a K-ballo) for the development of
    \cite{Eggs.Variant}.
  \item \textbf{Axel Naumann} for writing \cite{N4542} and its predecessors
    which started the discussion.
  \item \textbf{David Sankel} for deep design discussions and encouraging me to
    present my ideas during CppCon 2015.
  \item \textbf{Kirk Shoop} for design discussions at CppCon 2015.
  \item \textbf{Eric Niebler} for letting me know that submitting a proposal is a
    must in order to be considered for standardization.
  \item \textbf{Geoffrey Romer} for encouraging me to write this paper since
    CppCon 2014.
  \item \textbf{Andrei Alexandrescu} for starting the work on \texttt{variant},
    writing Dr. Dobb's articles back in 2002, and for encouraging me to
    write this paper.
  \item Everyone on \textbf{std-proposals} mailing list who passionately share
    their thoughts, ideas, and opinions.
\end{itemize}

A special thank you to \textbf{Jason Lucas} for initially introducing me to the
multi-method problem, and for the endless design and tradeoff discussions over
the past few years!

\section{References}
\renewcommand{\section}[2]{}%
\begin{thebibliography}{9}
  \bibitem[N3449]{N3449}
    Bjarne Stroustrup,
    \emph{Open and Efficient Type Switch for C++}\newline
    \url{http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3449.pdf}
  \bibitem[N3915]{N3915}
    Peter Sommerlad,
    \emph{apply() call a function with arguments from a tuple (V3)}\newline
    \url{http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3915.pdf}
  \bibitem[N4542]{N4542}
    Axel Naumann,
    \emph{Variant: a type-safe union (v4)}\newline
    \url{http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4542.pdf}
  \bibitem[P0050]{P0050}
    Vicente J. Botet Escriba,
    \emph{C++ generic match function}\newline
    \url{https://github.com/viboes/tags/blob/master/doc/proposals/match/P0050.pdf}
  \bibitem[P0051]{P0051}
    Vicente J. Botet Escriba,
    \emph{C++ generic overload functions}\newline
    \url{https://github.com/viboes/tags/blob/master/doc/proposals/overload/P0051.pdf}
  \bibitem[The Billion Dollar Mistake]{NullRef}
    Tony Hoare,
    \emph{Null References: The Billion Dollar Mistake}\newline
    \url{http://www.infoq.com/presentations/Null-References-The-Billion-Dollar-Mistake-Tony-Hoare}
  \bibitem[Mach7]{Mach7}
    Yuriy Solodkyy, Gabriel Dos Reis, Bjarne Stroustrup,
    \emph{Mach7: Pattern Matching for C++}\newline
    \url{https://github.com/solodon4/Mach7}
  \bibitem[Boost.Variant]{Boost.Variant}
    Eric Friedman, Itay Maman,
    \emph{Boost.Variant}\newline
    \url{http://www.boost.org/doc/libs/1_59_0/doc/html/variant.html}
  \bibitem[Eggs.Variant]{Eggs.Variant}
    Agust\'in Berg\'e,
    \emph{Eggs.Variant}\newline
    \url{http://eggs-cpp.github.io/variant}
  \bibitem[MPark.Variant]{MPark.Variant}
    Michael Park,
    \emph{Variant: Discriminated Union with Value Semantics}\newline
    \url{https://github.com/mpark/variant}
  \bibitem[C++ Core Guidelines]{CCG}
    Bjarne Stroustrup, Herb Sutter
    \emph{C++ Core Guidelines}\newline
    \url{https://github.com/isocpp/CppCoreGuidelines}
\end{thebibliography}

\end{document}