Projections and constraint verbosity

[ericniebler]

The presence of projection arguments in the algorithm signature seem to make it impossible to use the concept-checking short form. For instance, here is the two sequence overload

template<InputIterator I1, Sentinel<I1> S1, WeakInputIterator I2,
    WeakIterator O, class BinaryOperation, class Proj1 = identity,
    class Proj2 = identity>
    requires Invokable<Proj1, iterator_value_t<I1>> &&
      Invokable<Proj2, iterator_value_t<I2>> &&
      Writable<O, invokable_result_t<
        BinaryOperation,
        iterable_result_t<Proj1, iterator_value_t<I1>>,
        iterable_result_t<Proj2, iterator_value_t<I2>>>>>
  O transform(I1 first1, S1 last1,
              I2 first2, O result,
              BinaryOperation binary_op,
              Proj1 proj1 = Proj1{}, proj2 proj2 = Proj2{});

Figure out how to bring the verbosity under control.

[ericniebler]

More precisely:

template<InputIterator I1, Sentinel<I1> S1, WeakInputIterator I2,
    WeakIterator O, class BinaryOperation,
    Invokable<iterator_value_t<I1>> Proj1 = identity,
    Invokable<iterator_value_t<I2>> Proj2 = identity>
  requires Invokable<BinaryOperation,
      iterable_result_t<Proj1, iterator_value_t<I1>>,
      iterable_result_t<Proj2, iterator_value_t<I2>>> &&
    Writable<O, invokable_result_t<
      BinaryOperation,
      iterable_result_t<Proj1, iterator_value_t<I1>>,
      iterable_result_t<Proj2, iterator_value_t<I2>>>>>
  tuple<I1, I2, O>
    transform(I1 first1, S1 last1,
              I2 first2, O result,
              BinaryOperation binary_op,
              Proj1 proj1 = Proj1{}, proj2 proj2 = Proj2{});

[ericniebler]

Out-of-order template parameters lets us do away with the explicit requires clause. Still lots of verbosity and repetition, but this is better:

template<InputIterator I1, Sentinel<I1> S1, WeakInputIterator I2,
    Invokable<ValueType<I1>> Proj1 = identity,
    Invokable<ValueType<I2>> Proj2 = identity,
    Invokable<ResultType<CallableType<Proj1>, ValueType<I1> >,
      ResultType<CallableType<Proj2>, ValueType<I2> > > F,
    WeakOutputIterator<ResultType<CallableType<F>,
      ResultType<CallableType<Proj1>, ValueType<I1> >,
      ResultType<CallableType<Proj2>, ValueType<I2> > > > O>
  tuple<I1, I2, O>
    transform(I1 first1, S1 last1, I2 first2, O result,
              F binary_op, Proj1 proj1 = Proj1{}, proj2 proj2 = Proj2{});

@asutton , care to give your $0.02?

It sure would be nice to check if something is callable and get its return type in one step. The separate and redundant ResultType calculation is where most of the verbosity in the algorithm signatures comes from. Imagine:

template<InputIterator I1, Sentinel<I1> S1, WeakInputIterator I2,
    Invokable<I1::ValueType> Proj1 = identity,
    Invokable<I2::ValueType> Proj2 = identity,
    Invokable<Proj1::ResultType, Proj2::ResultType> F,
    WeakOutputIterator<F::ResultType> O>
  tuple<I1, I2, O>
    transform(I1 first1, S1 last1, I2 first2, O result,
              F binary_op, Proj1 proj1 = Proj1{}, proj2 proj2 = Proj2{});

[asutton]

Out-of-order template parameters lets us do away with the explicit
requires clause. Still lots of verbosity and repetition, but this is better:

template<InputIterator I1, Sentinel S1, WeakInputIterator I2,
Invokable<ValueType> Proj1 = identity,
Invokable<ValueType> Proj2 = identity,
Invokable<ResultType<CallableType, ValueType >,
ResultType<CallableType, ValueType > > F,
WeakOutputIterator<ResultType<CallableType,
ResultType<CallableType, ValueType >,
ResultType<CallableType, ValueType > > > O>
tuple<I1, I2, O>
transform(I1 first1, S1 last1, I2 first2, O result,
F binary_op, Proj1 proj1 = Proj1{}, proj2 proj2 = Proj2{});

@asutton https://github.com/asutton , care to give your $0.02?

Yuck. That's something we always wanted to steer clear of. It's seems a bit
inevitable when you start having lots of template parameters that are
composed as functions. Let me think about it.

[ericniebler]

Support for proxy references has forced me to solve the verbosity issue by grouping these constraints into an IndirectInvokable set of concepts that take a function, an iterator, and a projection. The above transform is now more like:

template<InputIterator I1, Sentinel<I1> S1, WeakInputIterator I2,
    Semiregular F, Semiregular Proj1 = identity, Semiregular Proj2 = identity,
    WeakOutputIterator<IndirectInvokableResultType2<F, I1, I2, Proj1, Proj2>> O>
requires IndirectInvokable2<F, I1, I2, Proj1, Proj2>
tuple<I1, I2, O>
 transform(I1 first1, S1 last1, I2 first2, O result,
   F binary_op, Proj1 proj1 = Proj1{}, proj2 proj2 = Proj2{});

Much of the complexity gets squirreled away in the IndirectInvokable concepts, and the associated ResultType helper trait. This makes many signatures much simpler, at the expense of increasing the number of concepts.

[asutton]

Support for proxy references have forced me to solve the verbosity issue
by grouping these constraints into an IndirectInvokable set of concepts
that take a function, an iterator, and a projection. The above transform
is now more like:

template<InputIterator I1, Sentinel S1, WeakInputIterator I2,
Semiregular F, Semiregular Proj1 = identity, Semiregular Proj2 = identity,
WeakOutputIterator<IndirectInvokableResultType2<F, I1, I2, Proj1, Proj2>> O>
requires IndirectInvokable2<F, I1, I2, Proj1, Proj2>
tuple<I1, I2, O>
transform(I1 first1, S1 last1, I2 first2, O result,
F binary_op, Proj1 proj1 = Proj1{}, proj2 proj2 = Proj2{});

Much of the complexity gets squirreled away in the IndirectInvokable
concepts, and the associated ResultType helper trait. This makes many
signatures much simpler, at the expense of increasing the number of
concepts

I spent a lot of time thinking about this over the break, and I don't see
any other way of making the requirements more clear -- except by removing
template parameters :)

I'm convinced that this is not hacky. There is simply no other way to
express the composition of constraints on different types except to make
larger concepts. C++0x concepts has the same problem, by the way (see
std::accumulate in n2914).

Also, I thought there was a proposal for default arguments that allowed
this:

template
void f(T = {});

Not sure what its status was.

Andrew

[ericniebler]

I'm convinced that this is not hacky. There is simply no other way to
express the composition of constraints on different types except to make
larger concepts

OK good. I don't feel bad about that. The only hacky bit comes from proxy reference support. That support replaces the const ValueType<I>& v = *it requirement with a new requirement: that of a common reference type between ReferenceType<I> and [const] ValueType<I>&. The implications for type constraints on binary functions is a little weird.

Binary functions could be called like f(*a,*b) or like f(v, *b), where v is a ValueType<I> lvalue. Both v and *b are guaranteed to be convertible to the common ref type, but it's not enough to check that f can be called with 2 args of the common ref type; an asymmetric call like f(v, *b) might fail. As with the cross-type Relation concept, all permutations(?) of argument types need to be checked. It's very messy. I think the existence of a common reference type makes it principled, but I'm not sure. I'm also not sure what we should say about the return types of all these different invocations. Perhaps they also need to share a common reference type.

That whole mess is hidden away in the IndirectInvokable concept, which is why I needed it.

[ericniebler]

Closing this issue, but it would still be nice to be able to say stuff like:

template<InputIterator I1, 
    Invokable<I1::ValueType> Proj1 = identity,
    Invokable<Proj1::ResultType> F, ...

[asutton]

Closing this issue, but it would still be nice to be able to say stuff
like:

template<InputIterator I1,
InvokableI1::ValueType Proj1 = identity,
InvokableProj1::ResultType F, ...

We need some aspects of separate checking to do that (the lookup of I1::
has to bring it's constraints into scope to resolve ValueType).

Andrew

[ericniebler]

Is that another way of saying, "Dream on"? ;-)

[asutton]

Let's put it on our wish list :)
On Jan 14, 2015 4:15 PM, "Eric Niebler" notifications@github.com wrote:

Is that another way of saying, "Dream on"? ;-)

—
Reply to this email directly or view it on GitHub
#5 (comment).