Comment on N4191 - Folding expressions (Sutton, Smith)

[George Makrydakis]

Two observations on N4191:

First, given that the paper proposes making catamophisms (left and right folds) as a primary language construct,
is there a reason as to why this should be limited to just values and not types as well? Instead of an operator, a
template template parameter could be used as is the case for the following examples of valid C++11 code for
providing the "folded" instantiation in this case:

#include <cstdio>

template< template<typename...> class F
             , typename A, typename B, typename C, typename D>
void fun (F<A,F<B,F<C,D>>>)
{ printf("folding in one way...\n"); }

template< template<typename...> class F
             , typename A, typename B, typename C, typename D>
void fun (F<F<F<A,B>,C>,D>)
{ printf("folding in another way...\n"); }

template<typename A, typename B>
struct funny {};

int main() {
    fun(funny<int,funny<int,funny<int,long>>>());
    fun(funny<funny<funny<int,int>,int>,long>());
    return {};
}

With the intention of expanding this to packs of course, manipulating the tripple-dot syntax. Could N4191 address
this as well in a future iteration?

Second, why should the folding expressions be limited to operators using (... + args) and not functions as well,
using (... f args) as well with f being a function identifier, or some sort of other syntax including that f function
can be used with, inspired for example from N4165 / N4174 (uniform function call syntax)?

Regards,

George

[Jens Maurer]

I'd prefer not to derail N4191 with additional features
or depend on other proposals.

It seems your suggestions are purely add-on and should
be handled in a separate paper.

Jens

> --
>
> ---
> You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to std-proposal...@isocpp.org <mailto:std-proposal...@isocpp.org>.
> To post to this group, send email to std-pr...@isocpp.org <mailto:std-pr...@isocpp.org>.
> Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

[George Makrydakis]

On 10/15/2014 04:55 PM, Jens Maurer wrote:
> I'd prefer not to derail N4191 with additional features
> or depend on other proposals.
>
> It seems your suggestions are purely add-on and should
> be handled in a separate paper.
>
> Jens

I agree with your observation on the first one on expanding this to type
parameters (and why not on template-template type ones) being part of a
separate paper (are they going to write it?). Regardless, for when
values are concerned in folding I do not see how N4191 is derailed.
Given that (... op args) and (args op ...) where 'op' is to be an
operator during folding (as Sutton and Smith argue), allowing a function
(constexpr or not) or a lambda to be used in 'op' would seem a rather
good idea:

(... [](auto x){ /* implementation here */} args)

(... function_identifier args)

Such a plain substitution of 'op' for allowing any function identifier /
lambda with the same context of use as 'op', does not depend on other
proposals nor is there an attempt to create another one for what
concerns it. It is a legitimate observation for a likely omission.

Regards,

George

>
> On 10/15/2014 01:45 PM, George Makrydakis wrote:

[...snip...]

[George Makrydakis]

On 10/15/2014 05:18 PM, George Makrydakis wrote:
>
> On 10/15/2014 04:55 PM, Jens Maurer wrote:
>> I'd prefer not to derail N4191 with additional features
>> or depend on other proposals.
>>
>> It seems your suggestions are purely add-on and should
>> be handled in a separate paper.
>>
>> Jens
> I agree with your observation on the first one on expanding this to
> type parameters (and why not on template-template type ones) being
> part of a separate paper (are they going to write it?). Regardless,
> for when values are concerned in folding I do not see how N4191 is
> derailed. Given that (... op args) and (args op ...) where 'op' is to
> be an operator during folding (as Sutton and Smith argue), allowing a
> function (constexpr or not) or a lambda to be used in 'op' would seem
> a rather good idea:
>
> (... [](auto x){ /* implementation here */} args)

Typing mistake, I left the second argument out due to haste:

(... [](auto x, auto y) { /* implementation here */ } args)

[Jens Maurer]

On 10/15/2014 04:18 PM, George Makrydakis wrote:
>
> On 10/15/2014 04:55 PM, Jens Maurer wrote:
>> I'd prefer not to derail N4191 with additional features
>> or depend on other proposals.
>>
>> It seems your suggestions are purely add-on and should
>> be handled in a separate paper.

> I agree with your observation on the first one on expanding this to type
> parameters (and why not on template-template type ones) being part of a
> separate paper (are they going to write it?).

Probably not. Ask the author to be sure. Otherwise, feel free to
write a paper yourself.

> Regardless, for when
> values are concerned in folding I do not see how N4191 is derailed.
> Given that (... op args) and (args op ...) where 'op' is to be an
> operator during folding (as Sutton and Smith argue), allowing a function
> (constexpr or not) or a lambda to be used in 'op' would seem a rather
> good idea:
>
> (... [](auto x){ /* implementation here */} args)
>
> (... function_identifier args)
>
> Such a plain substitution of 'op' for allowing any function identifier /
> lambda with the same context of use as 'op', does not depend on other
> proposals nor is there an attempt to create another one for what
> concerns it. It is a legitimate observation for a likely omission.

Well, for one, the operators in N4191 are all binary, and that's
how the folding is applied. Your lambda above only has one
parameter, so I don't know how the folding would work there.
Same for functions with more than two parameters.
Are there constraints on the function's return type vs. the
parameter types?

Second, I'm pretty certain that "..." adjacent to a binary operator,
surrounded by parens, is pretty unambiguous grammar-wise.
An identifier followed by ... is certainly allowed elsewhere in the
grammar, so I'm a bit more cautious there.

Extending this later to arbitrary functions is an add-on that
doesn't invalidate existing code. Personally, the source code
looks of the "arbitrary function" part of the proposal require
a lot more getting-used-to than the corresponding operator
case. And there is an actual use case for the operator case
in the concepts TS.

Jens

[George Makrydakis]

On 10/15/2014 09:55 PM, Jens Maurer wrote:

On 10/15/2014 04:18 PM, George Makrydakis wrote:

On 10/15/2014 04:55 PM, Jens Maurer wrote:

I'd prefer not to derail N4191 with additional features
or depend on other proposals.

It seems your suggestions are purely add-on and should
be handled in a separate paper.

I agree with your observation on the first one on expanding this to type 
parameters (and why not on template-template type ones) being part of a 
separate paper (are they going to write it?).

Probably not.  Ask the author to be sure.  Otherwise, feel free to
write a paper yourself.

Unlikely to happen not because I am not equipped to do it but because it would serve no purpose doing it since there are working on it. I am not new anymore to how they actually work :)

 Regardless, for when 
values are concerned in folding I do not see how N4191 is derailed. 
Given that (... op args) and (args op ...) where 'op' is to be an 
operator during folding (as Sutton and Smith argue), allowing a function 
(constexpr or not) or a lambda to be used in 'op' would seem a rather 
good idea:

(... [](auto x){ /* implementation here */} args)

(... function_identifier args)

Such a plain substitution of 'op' for allowing any function identifier / 
lambda with the same context of use as 'op', does not depend on other 
proposals nor is there an attempt to create another one for what 
concerns it. It is a legitimate observation for a likely omission.

Well, for one, the operators in N4191 are all binary, and that's
how the folding is applied.  Your lambda above only has one
parameter, so I don't know how the folding would work there.
Same for functions with more than two parameters.
Are there constraints on the function's return type vs. the
parameter types?

See my reply almost five (5) hours before your email, I missed a second parameter while typing and I did send an email for it within twelve minutes in case that was missed by you. Such catamorphisms over lists obviously require a binary function, as is the way through which we define left and right folds in languages having proper support for them. The omission due to haste was fixed so I think you don't present an argument here for using this in your defense:

https://groups.google.com/a/isocpp.org/d/msg/std-proposals/O18-SNExUdw/wxf5VleV6uEJ:

(... [](auto x, auto y) { /* implementation here */ } args)

The correct comment in your defense on this would be to ascertain that 'args' has a sufficient number of arguments inside for the fold to occur, without bailing out on the last call, not just function arity. The authors deal with this in their own paper (in a way), while it is obvious that there are far too many ways to ascertain that. Also, given that there is a single function identifier to be used there, the type signature is predictable in case of arguments of the same type, or it can even be engineered to be in arguments of different types through function template overloads, to the horror of people not understanding templates (or concepts). In that case you would not just be doing a fold though, you would be entering territory best described by the functional programming paradigm (see Haskell etc) which would be off-topic for us to discuss in here.

As for n-ary functions over 2-nary ones as is the case for folds, I remind that we do have default arguments in functions (one case where an n-ary can work in a 2-nary), while it is fairly obvious that not even a beginner would commit the error of calling a function with an improper arity of arguments, regardless of whether the syntax proposed in N4191 existed or not. A lot of algorithms in C++'s <algorithm> do have a requirement for unary functions to be passed for example. I do not think that people cannot relate to this by precedent nor is it responsible for them to omit such trivial knowledge.

Finally, forcing a constraint over C++'s current latent typing approach, it can be done either through concepts or sfinae based overload resolution for implementing bounded polymorphism, though the latter option is obviously one the concepts team would like to avoid. I see no issue here other than waiting for people to learn the notion of function arity, which is already in multiple paragraphs of the standard itself and even beginners are familiar with it.

Second, I'm pretty certain that "..." adjacent to a binary operator,
surrounded by parens, is pretty unambiguous grammar-wise.
An identifier followed by ... is certainly allowed elsewhere in the
grammar, so I'm a bit more cautious there.

I think you should think more about it. In essence, they are providing a new kind of "binary operator expression" if you think about it with the (... ) and ( ...) semantics. Therefore the domain within which ... is applicable is not ambiguous since there is no identifier prior to the triple dot in the first case where triple-dot is the first, while in the second case of folding the triple dot is last following all identifiers, including those used for inline lambda definition (if ever). I think that they did this by design. So I really think that you are not presenting a real argument here against it nor have a valid construct for when () are used in this domain with the addition of non-operator identifiers. Again, this is their syntax and yet, it is perfectly suitable for that.

For the record, the syntax is reminiscent of S-expressions in a way as well as point-free function application style, though that is not actually stated by the authors (http://en.wikipedia.org/wiki/S-expression).

Extending this later to arbitrary functions is an add-on that
doesn't invalidate existing code.  Personally, the source code
looks of the "arbitrary function" part of the proposal require
a lot more getting-used-to than the corresponding operator
case.  And there is an actual use case for the operator case
in the concepts TS.

Sure thing, which means that we are in agreement that this does not break existing or future code. For such a little evident omission on their behalf, it is of doubtful value to have to wait at least another 4 years post C++17 to get it as a feature, given that the only way to go through this using the operators, would be to emulate the result using operator overloading and/or expression template semantics within the proposed syntax over the type sequences involved. I doubt that Sutton would love to encourage such uses. For what concerns constraints, I refer you to my previous paragraphs as to what the actual constraint is.

It is very nice to see some sort of catamorphism make it as a language construct in C++, despite we are not yet on full par with general catamorphisms. I remind that such an addition as the one proposed by N4191, together with the semantics of pack expansion as we have them right now, complete an important fold/fmap duo for the purposes of an interesting take on functional programming style. So yes, having something more than operators there is important.

Regards,

George

[Vadim Petrochenkov]

FWIW, I can't recall any precedent in the language where some binary operator can't be trivially substituted with an equivalent named function (except maybe short-circuiting built-in logical operators).

Are there any? 

[Jens Maurer]

On 10/15/2014 10:49 PM, Vadim Petrochenkov wrote:
> FWIW, I can't recall any precedent in the language where some binary operator can't be trivially substituted with an equivalent named function (except maybe short-circuiting built-in logical operators).
> Are there any?

Binary && and || do contextual-bool conversions on their arguments
(possibly invoking an explicit operator bool), whereas a function
call doesn't.

The implicit conversion rules for arguments of + or *
("usual arithmetic conversions") make it hard to provide an
equivalent overload set containing functions, without running
into all sorts of ambiguity issues.

Jens

[Jens Maurer]

On 10/15/2014 09:51 PM, George Makrydakis wrote:
>
> On 10/15/2014 09:55 PM, Jens Maurer wrote:
>> On 10/15/2014 04:18 PM, George Makrydakis wrote:
>>> separate paper (are they going to write it?).
>> Probably not. Ask the author to be sure. Otherwise, feel free to
>> write a paper yourself.
> Unlikely to happen not because I am not equipped to do it but because it would serve no purpose doing it since there are working on it. I am not new anymore to how they actually work :)

I'm not sure who "they" are in the last sentence.

You asked whether the authors of N4191 are going to write a separate
paper discussing folding on template-arguments. I said "probably not,
ask them to be sure". So, if you want to see this extension happen,
yet you refrain from asking the paper authors for a change
directly, all that is left is writing the paper yourself or asking
someone else to do it. Otherwise, it won't happen.

>> Well, for one, the operators in N4191 are all binary, and that's
>> how the folding is applied. Your lambda above only has one
>> parameter, so I don't know how the folding would work there.
>> Same for functions with more than two parameters.
>> Are there constraints on the function's return type vs. the
>> parameter types?

> Such catamorphisms
> over lists obviously require a binary function, as is the way through

I'm not sure about "obvious". I'm mostly hanging around in the core
language working group, and there, we like to have all rules of the
C++ language spelled out explicitly. If you want to say that your
proposal is limited to functions having two parameters, you should
say so. Otherwise, I'm going to ask. The only hint you gave at
the actual function signature to be supported was the lambda, which
didn't match my expectations, so I was confused.

> which we define left and right folds in languages having proper
> support for them. The omission due to haste was fixed so I think you
> don't present an argument here for using this in your defense:
>
> https://groups.google.com/a/isocpp.org/d/msg/std-proposals/O18-SNExUdw/wxf5VleV6uEJ:
>
> (... [](auto x, auto y) { /* implementation here */ } args)

I saw this after I sent my e-mail. Ok.

> The /correct comment/ in your defense on this would be to ascertain

I don't think I need a "defense". All I'm trying to do with my
questions is to clarify what the proposal actually is, so that
I can form a firmer opinion.

> that 'args' has a sufficient number of arguments inside for the fold
> to occur, without bailing out on the last call, not just function
> arity.

That's indeed a good follow-on question: In the function case,
what's the result for 0-argument lists?

> The authors deal with this in their own paper (in a way),

They expressly prescribe the neutral element as the result for
0-argument lists, for each binary operation supported. Is there
something wrong with that?

> while it is obvious that there are far too many ways to ascertain
> that.

I'm sorry, I don't understand this part of the sentence.

> Also, given that there is a single function identifier to be
> used there, the type signature is predictable in case of arguments of
> the same type,

So, is there a constraint that all elements of the pack be of the
same type? That's not a constraint for the operators (conversions
are allowed there). In any case, this would be a further difference
for the function case that needs to be spelled out.

> or it can even be engineered to be in arguments of
> different types through function template overloads, to the horror of
> people not understanding templates (or concepts).

Not just template overloads, simple overloads do it. Or even no
overloads, if you allow implicit conversions. Example:

bool f(short, long);

(args f ...) will expand to f(f(f(a1, a2), a3), a4)
if I understood the syntax right. And that could be made
to work even if a2 would have a different type compared to a1,
using implicit conversions.

What are the rules here?

> In that case you
> would not just be doing a fold though, you would be entering
> territory best described by the functional programming paradigm (see
> Haskell etc) which would be off-topic for us to discuss in here.

Why? Implicit conversions happen in C++ all the time.

> As for n-ary functions over 2-nary ones as is the case for folds, I
> remind that we do have default arguments in functions (one case where
> an n-ary can work in a 2-nary), while it is fairly obvious that not
> even a beginner would commit the error of calling a function with an
> improper arity of arguments, regardless of whether the syntax
> proposed in N4191 existed or not. A lot of algorithms in C++'s
> <algorithm> do have a requirement for unary functions to be passed
> for example. I do not think that people cannot relate to this by
> precedent nor is it responsible for them to omit such trivial
> knowledge.

I'm not sure what you want to say here. Again, I'm asking about
the features of your proposal, and if you wish to require that
"f" (the function subject to the folding) is a binary function,
you should clearly say so, and not assume someone will deduce
it from the surroundings.

> Finally, forcing a constraint over C++'s current latent typing
> approach, it can be done either through concepts or sfinae based
> overload resolution for implementing bounded polymorphism, though the
> latter option is obviously one the concepts team would like to avoid.
> I see no issue here other than waiting for people to learn the notion
> of function arity, which is already in multiple paragraphs of the
> standard itself and even beginners are familiar with it.

I'm not talking about a learning issue, I was asking about the
specification itself. To me, there's no question that the
concept of a binary function is well-established.

>> Second, I'm pretty certain that "..." adjacent to a binary operator,
>> surrounded by parens, is pretty unambiguous grammar-wise.
>> An identifier followed by ... is certainly allowed elsewhere in the
>> grammar, so I'm a bit more cautious there.

> I think you should think more about it. In essence, they are

> providing a new kind of /"binary operator expression"/ if you think

> about it with the (... ) and ( ...) semantics. Therefore the domain
> within which ... is applicable is not ambiguous since there is no
> identifier prior to the triple dot in the first case where triple-dot
> is the first, while in the second case of folding the triple dot is
> last following all identifiers, including those used for inline
> lambda definition (if ever).

I was talking about parsing ambiguities. I'm still feeling uneasy
here. Is the "most vexing parse" getting more difficult?

> Sure thing, which means that we are in agreement that this does not
> break existing or future code. For such a little evident omission on
> their behalf, it is of doubtful value to have to wait at least
> another 4 years post C++17 to get it as a feature,

Why? If you submit the paper now, it certainly has a chance
to get into C++17.

> given that the
> only way to go through this using the operators, would be to emulate
> the result using operator overloading and/or expression template
> semantics within the proposed syntax over the type sequences
> involved. I doubt that Sutton would love to encourage such uses.

Then you should write an e-mail to the authors, maybe they're
sympathetic to your wishes and extend their paper.

Jens

[George Makrydakis]

On 10/16/2014 08:51 AM, Jens Maurer wrote:

On 10/15/2014 09:51 PM, George Makrydakis wrote:

On 10/15/2014 09:55 PM, Jens Maurer wrote:

On 10/15/2014 04:18 PM, George Makrydakis wrote:

separate paper (are they going to write it?).

Probably not.  Ask the author to be sure.  Otherwise, feel free to
write a paper yourself.

Unlikely to happen not because I am not equipped to do it but because it would serve no purpose doing it since there are working on it. I am not new anymore to how they actually work :)

I'm not sure who "they" are in the last sentence.

You asked whether the authors of N4191 are going to write a separate
paper discussing folding on template-arguments.  I said "probably not,
ask them to be sure".   So, if you want to see this extension happen,
yet you refrain from asking the paper authors for a change
directly, all that is left is writing the paper yourself or asking
someone else to do it.  Otherwise, it won't happen.

These people already working on it, I am only only providing feedback they do read. I am not going to be writing a paper on this because it is not worth it. It is just an omission on their behalf and perhaps their plan is to introduce this at some latter point. They have more leverage than an outsider to those working groups so I prefer not being the one doing the enlightenment.

Well, for one, the operators in N4191 are all binary, and that's
how the folding is applied.  Your lambda above only has one
parameter, so I don't know how the folding would work there.
Same for functions with more than two parameters.
Are there constraints on the function's return type vs. the
parameter types?

  Such catamorphisms
over lists obviously require a binary function, as is the way through

I'm not sure about "obvious".  I'm mostly hanging around in the core
language working group, and there, we like to have all rules of the
C++ language spelled out explicitly.  If you want to say that your
proposal is limited to functions having two parameters, you should
say so.   Otherwise, I'm going to ask.  The only hint you gave at
the actual function signature to be supported was the lambda, which
didn't match my expectations, so I was confused.

The very definition of a fold requires a binary function that and I believe that this is not confusing to anybody in the field:

http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29

Also, let's see an example of where the standard itself implies that a binary operation (meaning 2-arity) is passed, this is quite old actually and existing the standard library:

(taken from http://en.cppreference.com/w/cpp/algorithm/transform):

template< class InputIt1, class InputIt2, class OutputIt, class BinaryOperation >
OutputIt transform( InputIt1 first1, InputIt1 last1, InputIt2 first2,
                    OutputIt d_first, BinaryOperation binary_op );

Also, take note that std::accumulate itself, which is actually doing one kind of folding has the following function template overload, again in the standard library:

(taken from http://en.cppreference.com/w/cpp/algorithm/accumulate):

template< class InputIt, class T, class BinaryOperation >
T accumulate( InputIt first, InputIt last, T init, BinaryOperation op );

I understand that in C++, one can simply take any term (see functor in the context of category theory and functor in the context of C++) and change its meaning. But the meaning of a fold, is universal and all discussions on this follow a series of notions taken for granted.

which we define left and right folds in languages having proper
support for them. The omission due to haste was fixed so I think you
don't present an argument here for using this in your defense:

https://groups.google.com/a/isocpp.org/d/msg/std-proposals/O18-SNExUdw/wxf5VleV6uEJ:

(... [](auto x, auto y) { /* implementation here */ } args)

I saw this after I sent my e-mail.  Ok.

Not a problem.

The /correct comment/ in your defense on this would be to ascertain

I don't think I need a "defense".  All I'm trying to do with my
questions is to clarify what the proposal actually is, so that
I can form a firmer opinion.

Sure, the term "defense" is for the argument, I grant that it sounds too aggressive and can be taken in the wrong way. Substitute with "in defense of the argument" and we are in context.

that 'args' has a sufficient number of arguments inside for the fold
to occur, without bailing out on the last call, not just function
arity.

That's indeed a good follow-on question: In the function case,
what's the result for 0-argument lists?

You already reply yourself in the following paragraph. An empty list should by definition return the identity (e.g. additive, multiplicative etc) of the operation involved. Or in context of the paper, the "neutral" element.

  The authors deal with this in their own paper (in a way),

They expressly prescribe the neutral element as the result for
0-argument lists, for each binary operation supported.  Is there
something wrong with that?

There is nothing wrong with that because that is how it is done in mathematics. The terms multiplicative and additive identity are globally acceptable as well for example when you multiply (*) or add (+) and so on for other operations.

while it is obvious that there are far too many ways to ascertain
that.

I'm sorry, I don't understand this part of the sentence.

Concepts, sfinae, etc depending on the pack size to be processed, proper use of the "neutral" element, which actually refers to the notion of an identity for said operator and so on. I will not write an entire library to prove it. Just think about concepts and that is one way to ascertain that the semantics have a certain coherence. It is not by chance that one of the authors is involved in concepts ts anyway.

 Also, given that there is a single function identifier to be
used there, the type signature is predictable in case of arguments of
the same type,

So, is there a constraint that all elements of the pack be of the
same type?  That's not a constraint for the operators (conversions
are allowed there).  In any case, this would be a further difference
for the function case that needs to be spelled out.

If you use function template overloads or even plain non-template functions restricting by type in any combination, you are doing a fold in a heterogeneous list (made up of arguments of different types).

Folds on homogeneous lists (made up of arguments of the same type, to clarify the term) as the one they propose in their "folding expressions" already imply that the type is the same. It is not a further difference given that even cases of binary operators that are overloadable in C++ can have a variety of signatures:

http://en.wikipedia.org/wiki/Operators_in_C_and_C%2B%2B

Aren't operators just 2-ary functions in the end given that a lot of conversions take place there when desired? You also bring an example later on for the function case, let's see it.

  or it can even be engineered to be in arguments of
different types through function template overloads, to the horror of
people not understanding templates (or concepts).

Not just template overloads, simple overloads do it.  Or even no
overloads, if you allow implicit conversions.   Example:

  bool f(short, long);

  (args f ...) will expand to   f(f(f(a1, a2), a3), a4)
if I understood the syntax right.  And that could be made
to work even if a2 would have a different type compared to a1,
using implicit conversions.

What are the rules here?

We are not disagreeing, see previous paragraph.

The syntax expansion is correct, that is the same expansion implied by the authors (that is the universal way we do a left fold actually, so they are not changing that). In that case, you will be having a "bool" recursively passed through implicit conversion to f at each step of the way.

Again, it is not that you do not have operator+ overloads that accept different types and return a different type as the link above shows, but you have to respect the fact that the result of the operation is not a simple "fold" in the sense implied by the authors. You are working on a heterogeneous list with implicit conversions between calculations. In a list made up of multiple types, just like a case where packs are involved, you would be changing the function that is applied through overload resolution each time. You would have to have some sort of type deduction to occur to allow the fold or say that it cannot happen. It isn't that this is not the same problem operator-only solutions won't face (given that they are overloadable in all parts of their signature).

 In that case you
would not just be doing a fold though, you would be entering
territory best described by the functional programming paradigm (see
Haskell etc) which would be off-topic for us to discuss in here.

Why?  Implicit conversions happen in C++ all the time.

See before, It is not about implicit conversions, it is about the fact that folds on heterogeneous lists can have some interesting properties. This should be better discussed in the setting of general catamorphisms. I do not think that discussing it in this setting it would help the discussion. It would confuse people who lack the background (not implying you, I don't know you), and my experience with this list shows that most are blissfully unaware of these things. Implicit conversions are evil here if not properly managed.

As for n-ary functions over 2-nary ones as is the case for folds, I
remind that we do have default arguments in functions (one case where
an n-ary can work in a 2-nary),  while it is fairly obvious that not
even a beginner would commit the error of calling a function with an
improper arity of arguments, regardless of whether the syntax
proposed in N4191 existed or not. A lot of algorithms in C++'s
<algorithm> do have a requirement for unary functions to be passed
for example. I do not think that people cannot relate to this by
precedent nor is it responsible for them to omit such trivial
knowledge.

I'm not sure what you want to say here.  Again, I'm asking about
the features of your proposal, and if you wish to require that
"f" (the function subject to the folding) is a binary function,
you should clearly say so, and not assume someone will deduce
it from the surroundings.

It is not my proposal, it is their proposal and I asked why they did not consider this or if they will consider it.

By definition, you need a binary function in a such fold (I am not saying to change that), but that does not mean that you cannot use an n-ary where you can default some of the arguments through partial application (the notion comes from functional programming). It is especially easy to do in C++11 with std::bind or even a lambda encapsulating the n-ary function some of whose arguments are "defaulted" within the body body of a lambda:
--- code
#include <algorithm>
#include <cstdio>
#include <functional>
// C++11 code
using namespace std::placeholders;

int f(int x, int y, int z, int w)
{ return x + y + z + w; }

int main() {
    std::vector<int> v{1,2,3,4,5,6,7,8,9};
  
    printf("%d\n", std::accumulate( v.begin()
                                  , v.end()
                                  , 0
                                  , std::bind(f,_1,_2,100,200))); // here

    printf("%d\n", std::accumulate( v.begin()
                                  , v.end()
                                  , 0
                                  , [](int x, int y){ return f(x*y,1,2,3);})); // here
    return {};
}
--- code

I think that it should be clear right now (std::accumulate is doing the folding here as is widely known).

Finally, forcing a constraint over C++'s current latent typing
approach, it can be done either through concepts or sfinae based
overload resolution for implementing bounded polymorphism, though the
latter option is obviously one the concepts team would like to avoid.
I see no issue here other than waiting for people to learn the notion
of function arity, which is already in multiple paragraphs of the
standard itself and even beginners are familiar with it.

I'm not talking about a learning issue, I was asking about the
specification itself.  To me, there's no question that the
concept of a binary function is well-established.

We have been over this quite a few times. We are always talking about binary functions, just like the operators are binary. However, any kind of n-ary function that can be purposefully transformed into a 2-ary through one of the ways we can do partial application. This is equally fine since we can provide defaulted arguments, provided that such application is being done of course in the correct context. The example given before is clear. I am glad that the notion of function arity is clear to you, as should be the notion of partial application and currying. I tried to avoid using these terms (since some C++ programmers insist on them being just "taxonomy" of no practical use) but no reason to continue to do so :)

Second, I'm pretty certain that "..." adjacent to a binary operator,
surrounded by parens, is pretty unambiguous grammar-wise.
An identifier followed by ... is certainly allowed elsewhere in the
grammar, so I'm a bit more cautious there.

I think you should think more about it. In essence, they are
providing a new kind of /"binary operator expression"/ if you think
about it with the (... ) and ( ...) semantics. Therefore the domain
within which ... is applicable is not ambiguous since there is no
identifier prior to the triple dot in the first case where triple-dot
is the first, while in the second case of folding the triple dot is
last following all identifiers, including those used for inline
lambda definition (if ever).

I was talking about parsing ambiguities.  I'm still feeling uneasy
here.  Is the "most vexing parse" getting more difficult?

I can very much relate to this because their chosen syntax is uneasy, but not exactly ambiguous the way they are tackling it. However, it is their proposal, not mine, you should address them on that when it comes to the core language group from evolution :). The way they play with the parentheses and the triple-dot as tokens there is interesting enough. Not going to present an alternative, it would mean writing a different paper and I do not wish to do so.

Sure thing, which means that we are in agreement that this does not
break existing or future code. For such a little evident omission on
their behalf, it is of doubtful value to have to wait at least
another 4 years post C++17 to get it as a feature,

Why?  If you submit the paper now, it certainly has a chance
to get into C++17.

It has to do with this being worthy of the time for doing something separate as well as being compatible with whatever agenda there is on the matter. I am of those people whose experience with the EWG has disillusioned him about whatever integrity certain procedures have. So I really do not see the point and let's do not get off topic now, you can search the mailing lists for this. You have to be part of a lobby in the end with some people and I see no reason to invest in building that. It is not that important. I gain zero out of this since it neither enhances my knowledge, nor does it give me additional credit I do not already have. I just happen to like the language despite of its woeful design aspects.

As a library feature, it isn't that this cannot be properly done through code generation either through template/constexpr trickery etc. If one needs "weird syntax" to go with it as well, there is the preprocessor that can help out. So, why bother doing it and going through a process that yields nothing, other than just offering feedback on what is already written in N4191?

  given that the
only way to go through this using the operators, would be to emulate
the result using operator overloading and/or expression template
semantics within the proposed syntax over the type sequences
involved. I doubt that Sutton would love to encourage such uses.

Then you should write an e-mail to the authors, maybe they're
sympathetic to your wishes and extend their paper.

Again, unlikely to happen for both parts involved in such a process given that I am doubtful of the process that is to be followed in its quality and mutual respect. Our discussion was enjoyable indeed. I prefer the feedback given on this mailing list.

If I were to work on introducing a construct for folding expressions myself, I would have not taken a path that would be limited to values but also to types, making sure that the semantics of both fold (see std::accumulate for example) and fmap (see what std::transform does for example) would be covered equally in all cases. I however do not think that C++ is suitable to such thinking at a language level because some of the people involved in taking decisions have their own ideas on who is allowed to do what - or perhaps are not all well equipped by their background for these things yet.

Nothing that metaprogramming can't cover for those of us who may wish these things today, despite we don't have them as language features. Or perhaps a better language than C++, given that true professionals have to be polyglots. So really, why abuse myself in any other way other than giving feedback :) It the feedback is good, at some point it will be used, whether short-term or long-term. It is not that important.

What is important is being honest.

Regards,

George

[Jens Maurer]

On 10/16/2014 12:07 PM, George Makrydakis wrote:
>
> On 10/16/2014 08:51 AM, Jens Maurer wrote:

>> That's indeed a good follow-on question: In the function case,
>> what's the result for 0-argument lists?
>
> You already reply yourself in the following paragraph. An empty list should by definition return the identity (e.g. additive, multiplicative etc) of the operation involved. Or in context of the paper, the "neutral" element.

That's easy for + and * in particular, but, again, what's the
result for 0-argument lists in the (general) function case?
Or is that supposed to be ill-formed?

>> Not just template overloads, simple overloads do it. Or even no
>> overloads, if you allow implicit conversions. Example:
>>
>> bool f(short, long);
>>
>> (args f ...) will expand to f(f(f(a1, a2), a3), a4)
>> if I understood the syntax right. And that could be made
>> to work even if a2 would have a different type compared to a1,
>> using implicit conversions.
>>
>> What are the rules here?
>
> We are not disagreeing, see previous paragraph.

I'm sorry, but I'm not trying to make a counter-proposal
of any sort; I'm trying hard to understand your suggestion.

N4191 doesn't describe any constraints on the element types
of the pack; I'm just asking whether your "function" extension
suggestion has any such constraints. If the answer is "no"
(for consistency with overloaded operators, to say the least),
that's fine and I'm happy.

>>> In that case you
>>> would not just be doing a fold though, you would be entering
>>> territory best described by the functional programming paradigm (see
>>> Haskell etc) which would be off-topic for us to discuss in here.
>> Why? Implicit conversions happen in C++ all the time.
>
> See before, It is not about implicit conversions, it is about the fact that folds on heterogeneous lists can have some interesting properties. This should be better discussed in the setting of general catamorphisms. I do not think that discussing it in this setting it would help the discussion. It would confuse people who lack the background (not implying you, I don't know you), and my experience with this list shows that most are blissfully unaware of these things. Implicit conversions are evil here if not properly managed.

I'm sorry; now I'm really confused. N4191 shows a syntax expansion
of the fold, and, since no further constraints are given, I'd assume
that syntax expansion is then interpreted according to the usual C++
rules, including overload resolution and implicit conversions.

And yes, implicit conversions might mean all sorts of trouble, including
possibly picking a different overload for each step in the fold.

Do you suggest to prohibit differing element types in the pack
(i.e. having a homogenous list only) to avoid such troubles or not?

> It is not my proposal, it is their proposal and I asked why they did not consider this or if they will consider it.
>
> By definition, you need a binary function in a such fold (I am not saying to change that),

Great. One more question answered.

> As a library feature, it isn't that this cannot be properly done through code generation either through template/constexpr trickery etc. If one needs "weird syntax" to go with it as well, there is the preprocessor that can help out. So, why bother doing it and going through a process that yields nothing, other than just offering feedback on what is already written in N4191?

And maybe it's the right approach to use std::accumulate for (named) functions.

The desire for core language support of the operator case in N4191 comes
from "requires" expressions in concepts where we can't really call other
library functions.

> If I were to work on introducing a construct for folding expressions myself, I would have not taken a path that would be limited to values but also to types, making sure that the semantics of both fold (see std::accumulate for example) and fmap (see what std::transform does for example) would be covered equally in all cases. I however do not think that C++ is suitable to such thinking at a language level because some of the people involved in taking decisions have their own ideas on who is allowed to do what - or perhaps are not all well equipped by their background for these things yet.

My understanding is that there are indeed people in EWG that look at the
entire picture, even though individual proposals are usually just changing
one focused aspect of the language.

In general, when someone asks a question, that's usually a genuine question
to help understand the workings of a proposed feature (often giving a specific
code example), and a short, factual answer is all that is expected. It's
helpful to keep in mind that the people attending meetings are from a diverse
field of experience and few are experts in the domain being presented.

I felt that our discussion above wasn't sufficiently to the point:
I have no background in type theory, and all I wanted to know is whether
you'd want to support functions with other than two arguments for the
foldings, and if so, how that might work. The short answer is
"binary functions only, as per the syntax expansion shown in N4191", and
that would have saved quite a few bits in the communication.

Jens

[George Makrydakis]

On 10/16/2014 10:21 PM, Jens Maurer wrote:

On 10/16/2014 12:07 PM, George Makrydakis wrote:

On 10/16/2014 08:51 AM, Jens Maurer wrote:

That's indeed a good follow-on question: In the function case,
what's the result for 0-argument lists?

You already reply yourself in the following paragraph. An empty list should by definition return the identity (e.g. additive, multiplicative etc) of the operation involved. Or in context of the paper, the "neutral" element.

That's easy for + and * in particular, but, again, what's the
result for 0-argument lists in the (general) function case?
Or is that supposed to be ill-formed?

The authors give an interesting hint as to what happens with the comma operator in their proposal, which gives the return of void(). I would think that this is an excellent suggestion to use for function related folds, because void represents the most fundamental representation of "empty"-ness in C/C++ context. I would prefer having well-formedness for empty lists by having the fold conclude into the same void() by convention.

Not just template overloads, simple overloads do it.  Or even no
overloads, if you allow implicit conversions.   Example:

  bool f(short, long);

  (args f ...) will expand to   f(f(f(a1, a2), a3), a4)
if I understood the syntax right.  And that could be made
to work even if a2 would have a different type compared to a1,
using implicit conversions.

What are the rules here?

We are not disagreeing, see previous paragraph.

I'm sorry, but I'm not trying to make a counter-proposal
of any sort; I'm trying hard to understand your suggestion.

N4191 doesn't describe any constraints on the element types
of the pack; I'm just asking whether your "function" extension
suggestion has any such constraints.  If the answer is "no"
(for consistency with overloaded operators, to say the least),
that's fine and I'm happy.

There shouldn't be any constraints in a few words, correct. I am over-analyzing it.

 In that case you
would not just be doing a fold though, you would be entering
territory best described by the functional programming paradigm (see
Haskell etc) which would be off-topic for us to discuss in here.

Why?  Implicit conversions happen in C++ all the time.

See before, It is not about implicit conversions, it is about the fact that folds on heterogeneous lists can have some interesting properties. This should be better discussed in the setting of general catamorphisms. I do not think that discussing it in this setting it would help the discussion. It would confuse people who lack the background (not implying you, I don't know you), and my experience with this list shows that most are blissfully unaware of these things. Implicit conversions are evil here if not properly managed.

I'm sorry; now I'm really confused.  N4191 shows a syntax expansion
of the fold, and, since no further constraints are given, I'd assume
that syntax expansion is then interpreted according to the usual C++
rules, including overload resolution and implicit conversions.

And yes, implicit conversions might mean all sorts of trouble, including
possibly picking a different overload for each step in the fold.

Do you suggest to prohibit differing element types in the pack
(i.e. having a homogenous list only) to avoid such troubles or not?

There is no reason to constrain the language-level construct of folds if they ever become part of it. One can use for example material coming from N3878 and a successive revision to do the following with functions:

template<typename A, typename B>

void fun(A,B) {} /* using void on purpose here of course */

template<typename T>
int fun(T, T) { /* implementation here */ }

(... fun<auto{T},T> args)             /* the types are the same */
(... fun<auto{A},auto{B}> args) /* the types can be different */

I am using "Suttonian/Ballonian" syntax in a way that is not proposed by them (other than auto{} conventions), but I don't think I would be far off from what they may come up with, should this be a case for folding expressions with functions used with concepts in-situ. This is fairly well contained and predictable. The alternative would be sfinae-ing the function template instantiation using args... expansion within a enable_if like template for such purpose. Pick any likely solution that may appeal. So it shouldn't be a problem. If you are interested in this, talk to them in Urbana and see what they think about it. Perhaps it is already in their plans or you could form a proposal for it since you are better acquainted with the working groups in general. I won't pursue this.

It is not my proposal, it is their proposal and I asked why they did not consider this or if they will consider it.

By definition, you need a binary function in a such fold (I am not saying to change that),

Great.  One more question answered.

As a library feature, it isn't that this cannot be properly done through code generation either through template/constexpr trickery etc. If one needs "weird syntax" to go with it as well, there is the preprocessor that can help out. So, why bother doing it and going through a process that yields nothing, other than just offering feedback on what is already written in N4191?

And maybe it's the right approach to use std::accumulate for (named) functions.

The desire for core language support of the operator case in N4191 comes
from "requires" expressions in concepts where we can't really call other
library functions.

Concepts are the issue because they are problematic with such things, but in aiding them to achieve their goals, you are only going to be helping infamous techniques of template meta-programming in becoming more numerous, intense and arcane.

One needs to understand that in order for the predicate nature of concepts to work with variadics, the fold is the fundamental construct upon through which they actually work, as per N3701. In page 31 of 56, the authors are effectively performing a fold over an argument list using a binary operator (&&). The example also implies that 'Args' list had been passed through an fmap (structure preserving transformation, "mapping") has been made to a Convertible<ArgN,size_t> in each argument. In essence, they are working with functors type-theoretically (distinguishing this from the term we use in C++) and that is what I see when I deal with such work.

The interesting thing is that if they go through with these folding expressions, they can also be used for using sfinae manipulations based on folds. I remind that we already have the fmap construct as a language level feature because of the triple-dot pack expansion semantics, so adding a fold expression that can use that, one way or the other, yields interesting effects. For the record, here is the basic construct we already have:

template<template<typename> class F, typename... X>
void fun(F<X>...) {}; /* F<X0>,F<X1>,.... */

Dare I say this now: if by C++17 we get folding expressions to combine with the above, with concrete semantics for empty lists, combining them with pack expansion semantics will make it easier for people like me to implement extremely efficient compile-time monads over such lists of arguments without even touching concepts. There is bibliography for this already by some authors and the benefit for at least error-reporting during compile-time, but I digress.

If I were to work on introducing a construct for folding expressions myself, I would have not taken a path that would be limited to values but also to types, making sure that the semantics of both fold (see std::accumulate for example) and fmap (see what std::transform does for example) would be covered equally in all cases. I however do not think that C++ is suitable to such thinking at a language level because some of the people involved in taking decisions have their own ideas on who is allowed to do what - or perhaps are not all well equipped by their background for these things yet.

My understanding is that there are indeed people in EWG that look at the
entire picture, even though individual proposals are usually just changing
one focused aspect of the language.

In general, when someone asks a question, that's usually a genuine question
to help understand the workings of a proposed feature (often giving a specific
code example), and a short, factual answer is all that is expected.  It's
helpful to keep in mind that the people attending meetings are from a diverse
field of experience and few are experts in the domain being presented.

I felt that our discussion above wasn't sufficiently to the point:
I have no background in type theory, and all I wanted to know is whether
you'd want to support functions with other than two arguments for the
foldings, and if so, how that might work.  The short answer is
"binary functions only, as per the syntax expansion shown in N4191", and
that would have saved quite a few bits in the communication.
,
Jens

I do not doubt your motivation. Sorry if I sounded offensive.

In all honesty, I am quite a bit sour from my dealings with the EWG and that leads to needless defensivism.

Of course, I do not claim that I am the sole person with such ideas; it is just that in their meeting I was and such ideas were deemed "too complex". Indeed some people are getting some of the picture (with some delay) since they are re-proposing in part what I was trying to say; having entrusted a partially complete work to them was a mistake and I have no care for political correctness.

I think I will conclude my lamentful contributions in this standards community for now, since they spawned what they had to spawn. It isn't that I won't be seeing these things in C++ (eventually), even though with different syntax and more limited scope. In a sense, it is flattering for me to witness these things. My first-hand view of this community is complete so there isn't much else to say from either parties.

Regards and good luck,

George

[Markus Grech]

In functional languages, the initial value of a fold can be specified by the user. Why does the proposal mandate a specific value? Is there anything that prevents the following syntax:

(args + ... 0) // foldl args (+) 0
(0 ... + args) // foldr args (+) 0

Would this work?

[David Krauss]

It would be easy to do, with a tuple_fold function.

What worries me about this proposal is that its functionality is easily done with a generic template, yet no such template is in popular use, nor does a library proposal exist. We’re jumping straight to the core language with no usage experience.

Here’s some sort-of working library code. Only problem is, I wanted a left-fold but I got a right-fold because I’m a little drunk :P

#include <tuple>
#include <utility>

template< typename tuple_type, typename ftor, typename acc_type >
auto && tuple_fold_impl( tuple_type && t, ftor f, acc_type && acc,
    std::index_sequence<> )
    { return std::forward< acc_type >( acc ); }

template< typename tuple_type, typename ftor, typename acc_type,
    std::size_t index, std::size_t ... index_tail >
decltype(auto) tuple_fold_impl( tuple_type && t, ftor f, acc_type && acc,
    std::index_sequence< index, index_tail ... > ) {
    return f(
        tuple_fold_impl(
            std::forward< tuple_type >( t ),
            f,
            std::forward< acc_type >( acc ),
            std::index_sequence< index_tail ... >{}
        ),
        std::get< index >( std::forward< tuple_type >( t ) )
    );
}

template< typename tuple_type, typename ftor, std::size_t ... index_tail >
decltype(auto) tuple_fold_impl( tuple_type && t, ftor f, std::index_sequence< 0, index_tail ... > ) {
    return tuple_fold_impl(
        std::forward< tuple_type >( t ),
        f,
        std::get< 0 >( std::forward< tuple_type >( t ) ),
        std::index_sequence< index_tail ... >{}
    );
}

template< typename tuple_type, typename ftor,
    typename seq = std::make_index_sequence< std::tuple_size< tuple_type >::value > >
decltype(auto) tuple_fold( tuple_type && t, ftor f )
    { return tuple_fold_impl( std::forward< tuple_type >( t ), f, seq{} ); }

template< typename tuple_type, typename ftor, typename acc_type,
    typename seq = std::make_index_sequence< std::tuple_size< tuple_type >::value > >
decltype(auto) tuple_fold( tuple_type && t, ftor f, acc_type && acc )
    { return tuple_fold_impl( std::forward< tuple_type >( t ), f, std::forward< acc_type >( acc ), seq{} ); }

#include <iostream>

int main() {
tuple_fold( std::make_tuple( 1, " hello ", false, std::boolalpha, '\n' ), [] ( std::ostream & s, auto && o ) -> std::ostream & { return s << o; }, std::cout );

}

[Richard Smith]

That is already in the proposal (with a very slightly different syntax).

> --
>
> ---
> You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to std-proposal...@isocpp.org.
> To post to this group, send email to std-pr...@isocpp.org.