llvm dev - Mar 2014 - [LLVMdev] [cfe-dev] C++11 reverse iterators (was C++11 is here)

On 2014 Mar 4, at 20:23, Chandler Carruth <chandlerc at google.com> wrote:
> On Tue, Mar 4, 2014 at 8:07 PM, Duncan P. N. Exon Smith <dexonsmith at
apple.com> wrote:
> There’s a decent selection of range adaptors in Boost.Range [1].  I’m not
sure the license [2] allows copying the source (IANAL), but any reason not use
the same names?  I don’t see any reason to reinvent the wheel here.
> 
> Because I think that algorithms (and functions more generally) should be
verbs. The names will be very similar all the same.
I agree.  Algorithms should be verbs.

However, I disagree that range adaptors are algorithms.

“reverse” sounds like an algorithm.  Consider, from the STL:

    template <class Iterator> void reverse(Iterator F, Iterator L);

I’d expect a range version of the algorithm to look like this:

    template <class Range> void reverse(Range &R) {
      reverse(std::begin(R), std::end(R));
    }

On the other hand, “reversed” sounds like an accessor, and I’d expect it to look
something like this:

    template <class Range> reversed_range<Range::iterator>
        reversed(Range &R) {
      return make_range(make_reverse_iterator(std::end(R)),
                        make_reverse_iterator(std::begin(R)));
    }
    template <class Range> reversed_range<Range::const_iterator>
        reversed(const Range &R) {
      return make_range(make_reverse_iterator(std::end(R)),
                        make_reverse_iterator(std::begin(R)));
    }
    template <class Iterator> iterator_range<Iterator>
        reversed(const reversed_range<Iterator> &R) {
      return make_range(R.end().base(), R.begin().base());
    }

IMO, Adaptors are more akin to accessors than they are to algorithms.  If it has
to be a verb, then I think getReversed() is better than reverse().

I suspect that at a certain point (soon) those of us who feel strongly
about this should sit down if possible and hash this out either over lunch,
beers, or a whiteboard. =D

On Tue, Mar 4, 2014 at 9:26 PM, Duncan P. N. Exon Smith <
dexonsmith at apple.com> wrote:
> I agree.  Algorithms should be verbs.
>
> However, I disagree that range adaptors are algorithms.
>
> “reverse” sounds like an algorithm.  Consider, from the STL:
>
>     template <class Iterator> void reverse(Iterator F, Iterator L);
>
> I’d expect a range version of the algorithm to look like this:
>
>     template <class Range> void reverse(Range &R) {
>       reverse(std::begin(R), std::end(R));
>     }
>
> On the other hand, “reversed” sounds like an accessor, and I’d expect it
> to look something like this:
>
I understand the point you're trying to make here, and how you would
implement it, however I'm not persuaded this is the right design.

First, while an in-place approach to the interface of range algorithms is
one possibility, it has a fatal flaw: it is not composable. I want to be
able to write something equivalent to "x = reverse(sort(slice(std::move(x),
1, 10)))" because this allows us to factor apart the different aspects of
using ranges. It addresses the "<foo>_if" composition problem,
the
"<foo>_n" composition problem, etc. The solution requires us to
bring value
semantics to algorithms, what I think would be the best result of ranges in
C++.

Second, I really don't want two different patterns, because I find it very
hard to tell what is an algorithm and what isn't. Maybe "sliced"
clearly
isn't an algorithm, and "sort" clearly is, but
"reversed" starts to blur
the line. What about rotate? I have heard many argue that filter should be
an accessor. If sort is an algorithm, than surely partition is. But
partition is just the same as filter! I think it is all simpler if these
all follow the same fundamental pattern.

Third, this is *exactly* what I mean that we don't yet know what ranges
look like in C++. Whatever we end up with, I think we should be prepared to
change it based on experience and based on the discussions that go on in
the committee. My hope is that we can try out some of these approaches and,
if they work, also contribute to that discussion.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140304/385cd83d/attachment.html>

> On Mar 4, 2014, at 22:25, Chandler Carruth <chandlerc at google.com>
wrote:
> 
> I suspect that at a certain point (soon) those of us who feel strongly
about this should sit down if possible and hash this out either over lunch,
beers, or a whiteboard. =D
> 
I'm in for beers, anyway!
>> On Tue, Mar 4, 2014 at 9:26 PM, Duncan P. N. Exon Smith <dexonsmith
at apple.com> wrote:
>> I agree.  Algorithms should be verbs.
>> 
>> However, I disagree that range adaptors are algorithms.
>> 
>> “reverse” sounds like an algorithm.  Consider, from the STL:
>> 
>>     template <class Iterator> void reverse(Iterator F, Iterator
L);
>> 
>> I’d expect a range version of the algorithm to look like this:
>> 
>>     template <class Range> void reverse(Range &R) {
>>       reverse(std::begin(R), std::end(R));
>>     }
>> 
>> On the other hand, “reversed” sounds like an accessor, and I’d expect
it to look something like this:
> 
> I understand the point you're trying to make here, and how you would
implement it, however I'm not persuaded this is the right design.
> 
Admittedly, I'm coming in with a Boost bias, having used that range library
for years.
> First, while an in-place approach to the interface of range algorithms is
one possibility, it has a fatal flaw: it is not composable. I want to be able to
write something equivalent to "x = reverse(sort(slice(std::move(x), 1,
10)))"
This is interesting.  I hadn't considered r-value references with ranges. 
Is there a problem with supporting both semantics with the same names?

    template <class Range> Range reverse(Range &&R);
    template <class Range> void reverse(Range &R);
> because this allows us to factor apart the different aspects of using
ranges. It addresses the "<foo>_if" composition problem, the
"<foo>_n" composition problem, etc. The solution requires us to
bring value semantics to algorithms, what I think would be the best result of
ranges in C++.
> 
> Second, I really don't want two different patterns, because I find it
very hard to tell what is an algorithm and what isn't. Maybe
"sliced" clearly isn't an algorithm, and "sort" clearly
is, but "reversed" starts to blur the line. What about rotate? I have
heard many argue that filter should be an accessor. If sort is an algorithm,
than surely partition is. But partition is just the same as filter! I think it
is all simpler if these all follow the same fundamental pattern.
You're right, it needs to somehow be clear.  I think one reasonable rule is
"past participle" means adaptor, while "present tense" means
algorithm.  (That's why "reversed" makes some sense to me.)  By
that rule, I'd say reverse, filter and rotate are algorithms (mutating the
input), but reversed, filtered and rotated are adaptors (providing a mutated
view of the input).  If we're consistent it'll be clear.
> 
> Third, this is *exactly* what I mean that we don't yet know what ranges
look like in C++. Whatever we end up with, I think we should be prepared to
change it based on experience and based on the discussions that go on in the
committee. My hope is that we can try out some of these approaches and, if they
work, also contribute to that discussion.
Agreed. 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140304/18c9b0c9/attachment.html>

Chandler Carruth <chandlerc at google.com> writes:
> I suspect that at a certain point (soon) those of us who feel strongly
> about this should sit down if possible and hash this out either over lunch,
> beers, or a whiteboard. =D
>
> On Tue, Mar 4, 2014 at 9:26 PM, Duncan P. N. Exon Smith <
> dexonsmith at apple.com> wrote:
>
>> I agree.  Algorithms should be verbs.
>>
>> However, I disagree that range adaptors are algorithms.
>>
>> “reverse” sounds like an algorithm.  Consider, from the STL:
>>
>>     template <class Iterator> void reverse(Iterator F, Iterator
L);
>>
>> I’d expect a range version of the algorithm to look like this:
>>
>>     template <class Range> void reverse(Range &R) {
>>       reverse(std::begin(R), std::end(R));
>>     }
>>
>> On the other hand, “reversed” sounds like an accessor, and I’d expect
it
>> to look something like this:
>>
>
> I understand the point you're trying to make here, and how you would
> implement it, however I'm not persuaded this is the right design.
>
> First, while an in-place approach to the interface of range algorithms is
> one possibility, it has a fatal flaw: it is not composable. I want to be
> able to write something equivalent to "x =
reverse(sort(slice(std::move(x),
> 1, 10)))" because this allows us to factor apart the different aspects
of
> using ranges. It addresses the "<foo>_if" composition
problem, the
> "<foo>_n" composition problem, etc. The solution requires
us to bring value
> semantics to algorithms, what I think would be the best result of ranges in
> C++.
>
I strongly agree with this point of view. [Don't take my opinion too
seriously though, I'm merely a (very interested) external observer]

Being able to compose adaptors is a strong plus, as it solves the
problem of needing different variants of each algorithm with different
combinations of "_n", "_if", "_if_not",
"_backward", etc. without
needing to split an expression that logically belongs together and
declare temporary containers that you only intend to use as "glue"
between different algorithms, whose type and size could be deduced by
the library itself if adaptors with value semantics were used as you
suggest.
> Second, I really don't want two different patterns, because I find it
very
> hard to tell what is an algorithm and what isn't. Maybe
"sliced" clearly
> isn't an algorithm, and "sort" clearly is, but
"reversed" starts to blur
> the line. What about rotate? I have heard many argue that filter should be
> an accessor. If sort is an algorithm, than surely partition is. But
> partition is just the same as filter! I think it is all simpler if these
> all follow the same fundamental pattern.
>
I completely agree that we'd be better off with just one pattern.  I
think that the "adaptor" pattern (as it is implemented by
boost::range,
i.e. as an expression template with range-like semantics that transforms
a given source range) is the way to go in most cases, because it
alleviates the overhead of temporary object allocation, and it's a neat
way to decouple the definition of an adaptor from the container type you
ultimately intend to assign its contents to.  E.g. it's more concise and
more efficient to do something like:

| std::deque<float> result = map(minus<float>(), xs, reverse(ys));

and have things directly calculated into the deque (if that's what you
want to assign the result to) than to pick a preferred container type as
the return type for every algorithm and copy things unnecessarily when
doing composition.

Quite often you can replace the use of a mutating algorithm with the use
of an adaptor followed by an assignment.  Even some traditionally
mutating algorithms like sort() can be implemented reasonably as
adaptors without much loss of efficiency by leveraging C++11's move
semantics.
> Third, this is *exactly* what I mean that we don't yet know what ranges
> look like in C++. Whatever we end up with, I think we should be prepared to
> change it based on experience and based on the discussions that go on in
> the committee. My hope is that we can try out some of these approaches and,
> if they work, also contribute to that discussion.
There's quite a bit of prior art, starting with boost::range.  In Mesa's
Clover project (which was written in C++11 from the start) we use a
utility library [1] that was greatly influenced by boost::range, but it
attempts to make more extensive use of some C++11 features.  Among other
things, it takes into account the rvalue-ness of its arguments properly
to allow code like:

| auto result = map(f,
automatically_allocated_container_or_nested_adaptor(...));
| //...
| for (auto x : result) // Crash, because the nested range went out of
|                       // scope and it's been destroyed already.
|    //...

by moving range arguments which are passed as rvalue references into an
internal copy inside the adaptor object.

It also provides variadic variants of some algorithms, e.g. there's a
variadic map() that takes an n-argument functor along with n different
range arguments which are iterated in parallel (which mostly solves the
parallel iteration problem discussed earlier in this thread in a
convenient way), a variadic zip() that combines n ranges as a range of
n-tuples, variadic all_of(), any_of(), etc.

I admit that in some respects it's very sketchy compared to
boost::range, but it would be easy to relicense it under the LLVM
license if someone finds it useful as starting point.

[1]
http://cgit.freedesktop.org/mesa/mesa/tree/src/gallium/state_trackers/clover/util
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 229 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140305/1698a27e/attachment.sig>