future.tex

%!TEX root = stl2-ts.tex
\infannex{future}{Future Work}

\pnum
This document brings ranges and concepts to a minimal useful subset of the Standard Library.
A proper and full implementation has many more moving parts. In addition, we can use the opportunity
this work presents to address long-standing shortcomings in the Standard Library. Some of these
future work items are described below.

\rSec1[future.iterator_range]{Iterator Range Type}

\pnum
This paper does not define a concrete type for storing an iterator and a sentinel that models the
\tcode{Range} concept. Such a type, like that presented in ``A minimal std::range<Iter>,''~\cite{yasskin2012}
by J. Yasskin would be an obvious addition. Algorithms like \tcode{equal_range} and
\tcode{rotate} could use a concrete range type instead of \tcode{pair} as their return type,
improving composability. It would also be useful to implement a \tcode{view::all} range view that
yields a lightweight range object that refers to all the elements of a container.

\pnum
A future paper will propose such a type.

\rSec1[future.views]{Range Views and Actions}

\pnum
The vast majority of the power of ranges comes from their composability. \techterm{Views} on existing
Ranges
can combine in chains of operations that evaluate lazily, giving programmers a concise and efficient
way to express rich transformations on data. This paper is narrowly focused on the concepts and the
algorithms, leaving range views as critically important future work.

\pnum
If range views are composable, non-mutating, lazy algorithms over ranges, then range \techterm{actions}
are composable, (potentially) mutating, eager algorithms over ranges. Such actions would allow users
to send a container through a pipeline to sort it and remove the non-unique elements, for instance.
This is something the range views cannot do. Range actions sit along side the views in the
programmers toolbox.

\rSec1[future.facade]{Range Facade and Adaptor Utilities}

\pnum
Until it becomes trivial for users to create their own iterator types, the full potential of
iterators will remain unrealized. The range abstraction makes that achievable. With the right library
components, it should be possible for users to define a range with a minimal interface
(e.g., \tcode{current}, \tcode{done}, and \tcode{next} members), and have iterator types
automatically generated. Such a range \techterm{facade} class template is left as future work.

\pnum
Another common need is to adapt an existing range. For instance, a lazy \tcode{transform} view
should be as simple as writing an adaptor that customizes the behavior of a range by passing each
element through a transformation function. The specification of a range \techterm{adaptor} class
template is also left as future work.

\rSec1[future.infrng]{Infinite Ranges}

\pnum
It is not hard to define a type that represents an ``infinite'' range. Imagine a random number
generator that keeps generating new random numbers for every application of \tcode{operator++}
and \tcode{operator*} of its iterator. Indeed, the very existence of the \tcode{unreachable}
sentinel type -- which this document proposes -- encourages users to think about some ranges as
``infinite''. The sad reality is that infinite ranges are disallowed by the iterator concept
hierarchy as defined in this document.

\pnum
The problem with infinite ranges is the requirement that \tcode{WeaklyIncrementable} types have an
associated \tcode{difference_type_t}. The
\tcode{difference_type_t} must be a built-in integral type, and
it must be large enough to hold the distance between any two valid iterators. This is implicit in
the fact that the \tcode{distance} iterator primitive returns objects of type
\tcode{difference_type_t}.

\pnum
Given the fact that there are no infinite precision built-in integral types, the presence of
\tcode{difference_type_t} in the concept requirements places a hard upper limit on how big ranges can
be. This is a severe limitation.

\pnum
Some observations:

\begin{itemize}
\item Not all possible ranges have finitely countable elements.
\item Even a range with finitely countable elements may not be countable within the precision of the
built-in integral types.
\item Not all algorithms require the ability to count increments. Algorithms like \tcode{distance}
and \tcode{count} require finitely countable iterators, but \tcode{find} and \tcode{accumulate} do
not.
\end{itemize}

\pnum
The above observations suggest that there is a factorization of the existing concept hierarchy
that could solve the problem. Some \tcode{Incrementable}s are finitely countable with a built-in
integral \tcode{difference_type_t}, and some are not.
The algorithms that require countability must say so with an extra requirement.

\pnum
Obviously, some algorithms like \tcode{accumulate} should never be asked to operate on a truly
infinite sequence, even if they don't actually maintain counters internally. Such algorithms could
still be used with ``possibly'' infinite sequences. Note that the standard already defines such
possibly infinite sequences; for instance, there is no limit in principle to the number of elements
in a range delimited with \tcode{istream_iterator}s. It's not hard to imagine other useful possibly-
infinite range types: an infinite range that is delimited with a predicate or a sentinel value, for
instance. The algorithm requirements should merely enforce that there is no integer overflow
possible if the range happens to be larger than can be represented, not necessarily whether the
algorithm will terminate or not.

\rSec1[future.numcont]{Numeric Algorithms and Containers}

\pnum
The numeric algorithms must also be constrained, and additional range-based overloads must be added.
Also, the containers should be made range-aware; that is, they should have constructors and insert
and append member functions that accept range arguments. These things can be done in a separate
proposal.

\rSec1[future.constraints]{Verbosity in Algorithm Constraints}

\pnum
The constraints of some of the algorithms are verbose. Some composite concepts exist that group
constraints together to increase uniformity, aid comprehensibility, and reduce verbosity for those
algorithms that use them. See \tcode{Sortable}, \tcode{Mergeable}, and \tcode{Permutable}, for
instance. There may be other useful clusters of concepts for other algorithm groups. Finding them
and using them to improve the algorithm constraints is an important work item.

\rSec1[future.initlsts]{Initializer Lists}

\pnum
Algorithms that do not mutate their input should accept \tcode{initializer_list} arguments wherever
\tcode{Iterable}s are allowed. This requires extra overloads in places.