On Wednesday, 22 April 2020 at 12:04:30 UTC, Manu wrote:
> We should have done this a long time ago.
>
> - Manu

Thanks! Great work.

On Wed, Apr 22, 2020 at 05:07:58PM +0000, Stefan Koch via Digitalmars-d wrote:
> On Wednesday, 22 April 2020 at 14:02:45 UTC, Steven Schveighoffer wrote:
> > 
> > Stefan, where's that implementation of first class types for CTFE-only functions you promised? ;)
> > 
> 
> As you can see I have been busy with something similar.
> ctfe-only type-access or type-functions as I call them, coming closer
> through the work that Manu and I are doing.
> 
> The type-functions I have in mind will essentially supersede  ...
> expressions.
> However ... expressions can be there in the next weeks whereas type
> functions need much heavier machinery; and therefore will take some
> more invasive changes to dmd which are unlikely to be finished soon.
[...]

This is awesome stuff.  While I'm looking forward to 1st-class types for CTFE, I think this DIP is important for the interim, because it will improve D's template metaprogramming, which, as some have said, is D's crown jewel.

Without D's awesome template metaprogramming capabilities, it's a pretty safe bet to say I wouldn't be using D today.  But the current template expansion paradigm, which inherits from early versions of C++, simply isn't scalable enough for non-trivial applications. This DIP, if Manu's improvement measurements are a reliable indicator of the general case, would make template metaprogramming *much* more attractive in D (even more than it already is right now), and will rightly capitalize on D's strengths to make it an even better product.  And most importantly, it can be implemented in the near future, which is saying a lot seeing how a lot of things in D go. :-D

And if newCTFE lands within the next year or so, the combination could well catapult D metaprogramming to whole new levels.

*Then* when 1st class types land, it would be the next revolution. :-D


T

-- 
Why did the mathematician reinvent the square wheel?
Because he wanted to drive smoothly over an inverted catenary road.

On Wednesday, 22 April 2020 at 12:04:30 UTC, Manu wrote:
> We should have done this a long time ago.
>
> - Manu

This is going to be the first DIP in a long time I can actually get behind. With practicality as its foundation rather than ideology.

On Wednesday, 22 April 2020 at 12:19:25 UTC, rikki cattermole wrote:
> Change it to something like .unpackSequence instead of ... and I would be happy.

Since ... is not alphabetic it is hard to search for. If you do this DIP with the ... syntax please put some effort into making it easy to find. For instance if I type "what does ... mean?" and select "entire site" then the search should return this use of ... on the first page of results. And if this syntax is permanent then anyone writing a book should have ... in the index.

On Thu, Apr 23, 2020 at 2:10 AM Steven Schveighoffer via Digitalmars-d < digitalmars-d@puremagic.com> wrote:

> On 4/22/20 11:17 AM, Manu wrote:
> >
> > I have thought about how to discuss this in the DIP; I describe the
> > semantic, and what happens is what happens.
> > This will work, and something will happen... when we implement
> > TemplateInstance, we'll find out exactly what it is :P
> > What I will do is show what such a nested tuple does when code works in
> > the DIP to instantiate TemplateInstances.
> >
> > It's basically the same thing as what you showed above with:
> > Items[0].MemberTup, Items[1].MemberTup, ...
> > In general, in D currently, nested tuples flatten. Evaluate from the
> > leaf upwards. Your answer will materialise.
>
> I think this is more complicated than the MemberTup thing. By inference of the name, MemberTup is a tuple, but only defined in the context of the expanded items. There aren't any tuples for the compiler to expand in there.
>
> A template that returns a tuple based on it's parameters is a tuple with or without expansion.
>
> F!(F!t)) is valid. It's going to return int, char, int, char, int, char,
> int, char
>
> F!(F!t))... what does this do?
>
> Saying "let's see what happens" is not a good way to create a DIP. We have enough of "design by implementation" in D.
>

I only say that because;
1. It was 2am, and I had to think it through.
2. It will just apply the specification I've described in the DIP, absent
of special-cases.

I expect it will do this:

F!(F!t)... =>

expand for `t` (at leaf of tree):
F!( (F!t[0], F!t[1]) )  ~=   F!( (F!int, F!char) )  =>

Spec does not say it will NOW evaluate the template and operate on the
result, it deals with the expression as stated.
If it didn't behave that way, it would be very easy to lead to recursive
expansion expressions, and impossible to reason about the expansion when it
disappears inside of code that's defined elsewhere.

Expansion applies to the expression as-written.

So, take the tuple from expanding `t`, and expand the next level:

( F!( (F!int, F!char)[0] ), F!( (F!int, F!char)[1] ) )  ~=    ( F!( F!int
), F!( F!char ) )

I think that's all the tuples in the expression, now semantic will run as usual, and it will resolve those templates:

Resolve inner F:

( F!(int, int), F!(char, char) )

And outer F:

( int, int, int, int, char, char, char, char )

That's the expansion I would expect from that expression. So, I guess the
point you want to determine is that *evaluating* templates is NOT part of
tuple expansion.
Template resolution will follow normally in semantic. The expansion applies
to the expression as written, and I think that's the only possible
definition, otherwise the expansion starts to recurse inside of
implementation code which is defined elsewhere.

I think that expansion is actually reasonable and 'easy' to understand.
There's nothing unexpected about application of the stated rules.
Of course, I would suggest not writing code like this, unless it's really
clear to the reader what your intent was. There's a million-and-one ways to
write obscure code that does something, but doesn't really help the reader
along the way; this expression is one such thing.

On Thu, Apr 23, 2020 at 2:50 AM Steven Schveighoffer via Digitalmars-d < digitalmars-d@puremagic.com> wrote:

> On 4/22/20 10:37 AM, Manu wrote:
> > I think efficient implementation here would depend on a static fold,
> > which I plan for a follow-up, and it's a very trivial expansion from
> > this DIP.
> > Static reduce would allow `...` as an argument to a BinOp
> > Ie; `Tup + ...` would expand `Tup[0] + Tup[1] + Tup[2] + ...`
> > You could do `is(FindType == Tup) || ...`, and it would evaluate true if
> > FindType exists in Tup, with no junk template instantiations!
>
> This is awesome, and I'm not seeing why you would save it for later.
>

Because it's strictly additive, DIP's with over-reach tend to fail.

In general, couldn't this DIP be done just strictly on binary operators
> and do what this DIP does with commas?
>
> i.e.
>
> foo(T) , ... expands to foo(T[0]), foo(T[1]), ..., foo(T[n])
>

That looks really grammatically challenging to me. I wouldn't know where to
start attempting to implement that :/
The current patch in the compiler is extremely sanitary and self-contained,
but I can't imagine how to do that without making some pretty aggressive
changes to the parser. I think that's likely to have unexpected and
far-reaching side-effects.
It could be expanded to support that syntax in the future, but I'd rather
move with the simple definition I have in the DIP today. I think what you
describe above is very risky :/

On 4/22/20 8:13 PM, Manu wrote:
> On Thu, Apr 23, 2020 at 2:10 AM Steven Schveighoffer via Digitalmars-d <digitalmars-d@puremagic.com <mailto:digitalmars-d@puremagic..com>> wrote:
> 
>     On 4/22/20 11:17 AM, Manu wrote:
>      >
>      > I have thought about how to discuss this in the DIP; I describe the
>      > semantic, and what happens is what happens.
>      > This will work, and something will happen... when we implement
>      > TemplateInstance, we'll find out exactly what it is :P
>      > What I will do is show what such a nested tuple does when code
>     works in
>      > the DIP to instantiate TemplateInstances.
>      >
>      > It's basically the same thing as what you showed above with:
>      > Items[0].MemberTup, Items[1].MemberTup, ...
>      > In general, in D currently, nested tuples flatten. Evaluate from the
>      > leaf upwards. Your answer will materialise.
> 
>     I think this is more complicated than the MemberTup thing. By inference
>     of the name, MemberTup is a tuple, but only defined in the context of
>     the expanded items. There aren't any tuples for the compiler to expand
>     in there.
> 
>     A template that returns a tuple based on it's parameters is a tuple
>     with
>     or without expansion.
> 
>     F!(F!t)) is valid. It's going to return int, char, int, char, int,
>     char,
>     int, char
> 
>     F!(F!t))... what does this do?
> 
> I expect it will do this:
> 
> F!(F!t)... =>
> 
> expand for `t` (at leaf of tree):
> F!( (F!t[0], F!t[1]) )  ~= F!( (F!int, F!char) )  =>

OK, that is what I thought too (that is the most useful), but this needs to be explicit in the DIP.

Remember that templates can also be tuples too, so when it says " for any tuples present in the expression tree", it reads ambiguous.

I will bring up again something like this, which someone might expect to work:

alias G(T) = const(T);

alias F(T) = AliasSeq!(T, T);

alias f = F!(int);
G!(f)...; // seems cool to me
G!(F!int)...; // compiler error or works?
G!(AliasSeq!(int, char))...; // error or works?

> Spec does not say it will NOW evaluate the template and operate on the result, it deals with the expression as stated.

I'm not expecting multiple expansions, but one has to remember that D is full of templates that create tuples, so the DIP has to say at what point "these tuples are generated and considered before the expansion" and "these are not". It seems to me you are saying only tuples that exist BEFORE the expression are considered. Something like that should be in the DIP, with appropriate examples.

> That's the expansion I would expect from that expression. So, I guess the point you want to determine is that *evaluating* templates is NOT part of tuple expansion.

A good way to say it, but still needs examples in the DIP to clarify. To elaborate, you might say:

"expansion is performed only on tuples represented by symbols in the expression. All template instantiations that generate tuples are performed after expansion is finished."

> I think that expansion is actually reasonable and 'easy' to understand. There's nothing unexpected about application of the stated rules.
> Of course, I would suggest not writing code like this, unless it's really clear to the reader what your intent was. There's a million-and-one ways to write obscure code that does something, but doesn't really help the reader along the way; this expression is one such thing.

It's easy to understand, but it's also easy to expect the compiler to understand what you were thinking when you wrote:

foo!(AliasSeq!(int, char))...

instead of the (required) long form:

alias args = AliasSeq!(int, char);
foo!(args)...

proper tuples would make this much less painful...

-Steve

On 4/22/20 8:21 PM, Manu wrote:
> On Thu, Apr 23, 2020 at 2:50 AM Steven Schveighoffer via Digitalmars-d <digitalmars-d@puremagic.com <mailto:digitalmars-d@puremagic..com>> wrote:
> 
>     On 4/22/20 10:37 AM, Manu wrote:
>      > I think efficient implementation here would depend on a static fold,
>      > which I plan for a follow-up, and it's a very trivial expansion from
>      > this DIP.
>      > Static reduce would allow `...` as an argument to a BinOp
>      > Ie; `Tup + ...` would expand `Tup[0] + Tup[1] + Tup[2] + ...`
>      > You could do `is(FindType == Tup) || ...`, and it would evaluate
>     true if
>      > FindType exists in Tup, with no junk template instantiations!
> 
>     This is awesome, and I'm not seeing why you would save it for later.
> 
> 
> Because it's strictly additive, DIP's with over-reach tend to fail.

Without the folding, I think this feature leaves a lot on the table. I'd still be happy with the DIP as-is, but it obviously doesn't help me as much in the projects I'm using.

> 
>     In general, couldn't this DIP be done just strictly on binary operators
>     and do what this DIP does with commas?
> 
>     i.e.
> 
>     foo(T) , ... expands to foo(T[0]), foo(T[1]), ..., foo(T[n])
> 
> 
> That looks really grammatically challenging to me. I wouldn't know where to start attempting to implement that :/

Is this not the same difficulty as `Tup + ...` which is what you suggested above? I thought it was the same thing.

My thought was that if you went for the binary operator implementation, then you have one addition, instead of one now and one later, and the binary form can capture everything this DIP captures without needing to be an "additional" piece.

-Steve

On Thu, Apr 23, 2020 at 2:50 PM Steven Schveighoffer via Digitalmars-d < digitalmars-d@puremagic.com> wrote:

> On 4/22/20 8:13 PM, Manu wrote:
> > On Thu, Apr 23, 2020 at 2:10 AM Steven Schveighoffer via Digitalmars-d <digitalmars-d@puremagic.com <mailto:digitalmars-d@puremagic..com>>
> wrote:
> >
> >     On 4/22/20 11:17 AM, Manu wrote:
> >      >
> >      > I have thought about how to discuss this in the DIP; I describe
> the
> >      > semantic, and what happens is what happens.
> >      > This will work, and something will happen... when we implement
> >      > TemplateInstance, we'll find out exactly what it is :P
> >      > What I will do is show what such a nested tuple does when code
> >     works in
> >      > the DIP to instantiate TemplateInstances.
> >      >
> >      > It's basically the same thing as what you showed above with:
> >      > Items[0].MemberTup, Items[1].MemberTup, ...
> >      > In general, in D currently, nested tuples flatten. Evaluate from
> the
> >      > leaf upwards. Your answer will materialise.
> >
> >     I think this is more complicated than the MemberTup thing. By
> inference
> >     of the name, MemberTup is a tuple, but only defined in the context of
> >     the expanded items. There aren't any tuples for the compiler to
> expand
> >     in there.
> >
> >     A template that returns a tuple based on it's parameters is a tuple
> >     with
> >     or without expansion.
> >
> >     F!(F!t)) is valid. It's going to return int, char, int, char, int,
> >     char,
> >     int, char
> >
> >     F!(F!t))... what does this do?
> >
> > I expect it will do this:
> >
> > F!(F!t)... =>
> >
> > expand for `t` (at leaf of tree):
> > F!( (F!t[0], F!t[1]) )  ~= F!( (F!int, F!char) )  =>
>
> OK, that is what I thought too (that is the most useful), but this needs
> to be explicit in the DIP.
>
> Remember that templates can also be tuples too, so when it says " for any tuples present in the expression tree", it reads ambiguous.
>
> I will bring up again something like this, which someone might expect to work:
>
> alias G(T) = const(T);
>
> alias F(T) = AliasSeq!(T, T);
>
> alias f = F!(int);
> G!(f)...; // seems cool to me
> G!(F!int)...; // compiler error or works?
> G!(AliasSeq!(int, char))...; // error or works?
>
> > Spec does not say it will NOW evaluate the template and operate on the result, it deals with the expression as stated.
>
> I'm not expecting multiple expansions, but one has to remember that D is full of templates that create tuples, so the DIP has to say at what point "these tuples are generated and considered before the expansion" and "these are not". It seems to me you are saying only tuples that exist BEFORE the expression are considered. Something like that should be in the DIP, with appropriate examples.
>

Yes, these are very good points. Thanks for spelling this out clearly.

In the event you want the behaviour where the template resolution is
expanded, I reckon people would expect this is the natural solution:
    alias Tup = TupleFromTemplate!(Instantiation, Args);
    (Tup + expr)...

In this expression, `Tup` would expand, because the instantiation that
created the tuple is not involved in the expression being expanded.
I have to double-check, but I expect that's precisely how the code works
naturally with no intervention. AliasSeq!() itself depends on this
behaviour to work right now in our unittests.

So, if you find yourself in a situation where you want to expand a tuple into a template instantiation, and that instantiation resolves to a tuple which you want to further expand, you just need to break it into 2 lines. That will also have the nice side-effect of being much clearer to read.

> That's the expansion I would expect from that expression. So, I guess
> > the point you want to determine is that *evaluating* templates is NOT part of tuple expansion.
>
> A good way to say it, but still needs examples in the DIP to clarify. To elaborate, you might say:
>
> "expansion is performed only on tuples represented by symbols in the expression. All template instantiations that generate tuples are performed after expansion is finished."
>

Yes, this reads well, thanks again. I was struggling to imagine simple language to describe this behaviour.

> I think that expansion is actually reasonable and 'easy' to understand.
> > There's nothing unexpected about application of the stated rules. Of course, I would suggest not writing code like this, unless it's really clear to the reader what your intent was. There's a million-and-one ways to write obscure code that does something, but doesn't really help the reader along the way; this expression is one such thing.
>
> It's easy to understand, but it's also easy to expect the compiler to understand what you were thinking when you wrote:
>
> foo!(AliasSeq!(int, char))...
>
> instead of the (required) long form:
>
> alias args = AliasSeq!(int, char);
> foo!(args)...
>
> proper tuples would make this much less painful...
>

You're exactly correct, the first instantiation needs to be broken out to a
separate line.
Exactly. I hope this feature might motivate renewed interest in first-class
tuples, and that would improve this situation.

On Thu, Apr 23, 2020 at 2:55 PM Steven Schveighoffer via Digitalmars-d < digitalmars-d@puremagic.com> wrote:

> On 4/22/20 8:21 PM, Manu wrote:
> > On Thu, Apr 23, 2020 at 2:50 AM Steven Schveighoffer via Digitalmars-d <digitalmars-d@puremagic.com <mailto:digitalmars-d@puremagic..com>>
> wrote:
> >
> >     On 4/22/20 10:37 AM, Manu wrote:
> >      > I think efficient implementation here would depend on a static
> fold,
> >      > which I plan for a follow-up, and it's a very trivial expansion
> from
> >      > this DIP.
> >      > Static reduce would allow `...` as an argument to a BinOp
> >      > Ie; `Tup + ...` would expand `Tup[0] + Tup[1] + Tup[2] + ...`
> >      > You could do `is(FindType == Tup) || ...`, and it would evaluate
> >     true if
> >      > FindType exists in Tup, with no junk template instantiations!
> >
> >     This is awesome, and I'm not seeing why you would save it for later.
> >
> >
> > Because it's strictly additive, DIP's with over-reach tend to fail.
>
> Without the folding, I think this feature leaves a lot on the table. I'd still be happy with the DIP as-is, but it obviously doesn't help me as much in the projects I'm using.
>

I think you'll discover that the map's are the more expensive operations.
You'll see a huge improvement from that alone.
If people get behind this DIP, I'm completely confident you'll get fold too.

>     In general, couldn't this DIP be done just strictly on binary
> operators
> >     and do what this DIP does with commas?
> >
> >     i.e.
> >
> >     foo(T) , ... expands to foo(T[0]), foo(T[1]), ..., foo(T[n])
> >
> >
> > That looks really grammatically challenging to me. I wouldn't know where to start attempting to implement that :/
>
> Is this not the same difficulty as `Tup + ...` which is what you suggested above? I thought it was the same thing.


The grammar for binary expression is easy to interact with.
`,` separators are NOT a binary expression, they are frequently just
hard-wired into the grammar as separators, and so everywhere a comma
appears in the grammar where the value may be involved in an expansion need
to have grammatical modifications, and everywhere that a comma is not
present in the grammar where an expansion may be accepted must have a
grammatical modification to allow commas in that location too.

I haven't tried it, but the thought of hacking in such a change to the
grammar everywhere a comma appears terrifies me, resulting ambiguity feels
very likely.
Hooking a special token on the right of a binary expression should be a
1-line change however.

My thought was that if you went for the binary operator implementation,
> then you have one addition, instead of one now and one later, and the binary form can capture everything this DIP captures without needing to be an "additional" piece.


static fold has a degenerate edge case (empty tuple), and handling that case has options subject to value judgement. I don't want this DIP to get lost in that debate. There are a few reasonable options in that case, and I could make arguments for and against each option that I can think of. static fold is probably useful about 10% as often as static map. This DIP as is will make the biggest impact on compile perf and brevity and we should take it as eagerly as we are able.

We'll do fold as an immediate follow up though. If it gets in good shape and it looks no more likely to increase controversy before the DIP's get far through the pipeline, then maybe we can merge the DIPs.