www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - How templates work (bonus) - Full instantiation of Iota!(1,5)

reply Stefan Koch <uplink.coder googlemail.com> writes:
As part of my series of templates
I have done a a full instantiation of Iota!(1,5).
(By hand!)
And here is the result:

Iota!(1,5)
{
     {
         alias Iota = Seq!(1, Iota!(1 + 1, 5));
     }
     Seq!(1, Iota!(1 + 1, 5))
     {
         alias Seq = (1, Iota!(1 + 1, 5));
         Iota!(1 + 1, 5) => Iota!(2, 5)
         {
             alias Iota = Seq!(2, Iota!(2 +1, 5));
         }
         Seq!(2, Iota(2 + 1, 5))
         {
             alias seq = (2, Iota!(2 + 1, 5))
             Iota!(2 + 1, 5) => Iota!(3, 5)
             {
                 alias Iota = Seq!(3, Iota!(3 +1, 5));
             }
             Seq!(3, Iota!(3 + 1, 5))
             {
                 alias Seq = (3, Iota!(3 + 1, 5));
                 Iota!(3 + 1, 5) => Iota!(4, 5)
                 {
                     alias Iota = Seq!(4, Iota!(4 +1, 5));
                     Seq!(4, Iota!(4 + 1, 5))
                     {
                         alias seq = (4, Iota!(4 + 1, 5));
                         Iota!(4 + 1, 5) => Iota!(5, 5)
                         {
                             {
                                 alias Iota = Seq!();
                                 { Seq!() => () }.Seq => ()
                             }
                         }.Iota => Seq!()
                     }.Seq => (4, Seq!())
                 }.Iota => (3, Seq!(4, Seq!())
             }.Seq => (3, Seq!(4, Seq())))
         }.Seq => (2, (Seq!(3, Seq!(4, Seq!()))))
     }.Seq => (1, Seq!(2, Seq!(3, Seq(4, Seq!())))))
}.Iota => (1, Seq!(2, Seq!3, Seq!4, Seq!()))))))

Because it has been done manually there are probably some bugs.
Can you find them all?
Jun 04 2020
next sibling parent reply Simen =?UTF-8?B?S2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On Thursday, 4 June 2020 at 11:33:48 UTC, Stefan Koch wrote:
 Because it has been done manually there are probably some bugs.
 Can you find them all?
The way you're doing it seems to change about halfway (notice the sudden change in slope in the indentation at Seq!(3, ...)), and it's not really proper D in any case, but there's a few missing exclamation marks (after Iota in Seq!(2, Iota(2 + 1, 5)), and after the final Seq in }.Seq => (3, Seq!(4, Seq())))). There's also a spurious set of parentheses in }.Seq => (2, (Seq!(3, Seq!(4, Seq!())))). Here's how I would have shown it: Iota!(1,5): { alias Iota = Seq!(1, Iota!(1 + 1, 5)); Iota!(1 + 1, 5): { alias Iota = Seq!(2, Iota!(2 + 1, 5)); Iota!(2 + 1, 5): { alias Iota = Seq!(3, Iota!(3 + 1, 5)); Iota!(3 + 1, 5): { alias Iota = Seq!(4, Iota!(4 + 1, 5)); Iota!(4 + 1, 5): { alias Iota = Seq!(); }.Iota => () }.Iota => (4) }.Iota => (3, 4) }.Iota => (2, 3, 4) }.Iota => (1, 2, 3, 4) (Seq is trivial, so I don't really see a need to expand it every step) Next challenge: Do the divide-and-conquer version. -- Simen
Jun 04 2020
parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Thursday, 4 June 2020 at 12:03:00 UTC, Simen Kjærås wrote:
 On Thursday, 4 June 2020 at 11:33:48 UTC, Stefan Koch wrote:
 [...]
The way you're doing it seems to change about halfway (notice the sudden change in slope in the indentation at Seq!(3, ...)), and it's not really proper D in any case, but there's a few missing exclamation marks (after Iota in Seq!(2, Iota(2 + 1, 5)), and after the final Seq in }.Seq => (3, Seq!(4, Seq())))). There's also a spurious set of parentheses in }.Seq => (2, (Seq!(3, Seq!(4, Seq!())))). [...]
The reason I show every step explicitly is because that's what's the compiler has to do. I actually did omit a few steps. Such as finding the right template declaration to use. Which requires you to go up the scopes you just created.
Jun 04 2020
parent reply Simen =?UTF-8?B?S2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On Thursday, 4 June 2020 at 12:08:58 UTC, Stefan Koch wrote:
 On Thursday, 4 June 2020 at 12:03:00 UTC, Simen Kjærås wrote:
 On Thursday, 4 June 2020 at 11:33:48 UTC, Stefan Koch wrote:
 [...]
The way you're doing it seems to change about halfway (notice the sudden change in slope in the indentation at Seq!(3, ...)), and it's not really proper D in any case, but there's a few missing exclamation marks (after Iota in Seq!(2, Iota(2 + 1, 5)), and after the final Seq in }.Seq => (3, Seq!(4, Seq())))). There's also a spurious set of parentheses in }.Seq => (2, (Seq!(3, Seq!(4, Seq!())))).
More: This line is missing a trailing parenthesis: }.Iota => (3, Seq!(4, Seq!()) This line has an extra trailing parenthesis: }.Seq => (3, Seq!(4, Seq()))) This line has an extra trailing parenthesis: }.Seq => (1, Seq!(2, Seq!(3, Seq(4, Seq!()))))) This line is missing some starting parentheses (Seq!3 and Seq!4), and has an extra trailing one: }.Iota => (1, Seq!(2, Seq!3, Seq!4, Seq!())))))) This line looks different from all the other expansions: { Seq!() => () }.Seq => () I assume it should be { alias Seq = (); }.Seq => () There's two instances of seq in lowercase (alias seq = Seq!(2, ...) and alias seq = Seq!(4, ...)).
 The reason I show every step explicitly is because that's 
 what's the compiler has to do.
 I actually did omit a few steps. Such as finding the right 
 template declaration to use.
 Which requires you to go up the scopes you just created.
Good point. With that, it looks like this: Iota!(1, 5): { alias Iota = Seq!(1, Iota!(1 + 1, 5)); Seq!(1, Iota!(1 + 1, 5)): { alias Seq = (1, Iota!(1 + 1, 5)); Iota!(1 + 1, 5): { alias Iota = Seq!(2, Iota!(2 + 1, 5)); Seq!(2, Iota!(2 + 1, 5)): { alias Seq = (2, Iota!(2 + 1, 5)); Iota!(2 + 1, 5): { alias Iota = Seq!(3, Iota!(3 + 1, 5)); Seq!(2, Iota!(2 + 1, 5)): { alias Seq = (3, Iota!(3 + 1, 5)); Iota!(3 + 1, 5): { alias Iota = Seq!(4, Iota!(4 + 1, 5)); Seq!(4, Iota!(4 + 1, 5)): { alias Seq = (4, Iota!(4 + 1, 5)); Iota!(4 + 1, 5): { alias Iota = Seq!(); Seq!(): { alias Seq = (); }.Seq => () }.Iota => () }.Seq => (4, ()) }.Iota => (4, ()) }.Seq => (3, (4, ())) }.Iota => (3, (4, ())) }.Seq => (2, (3, (4, ()))) }.Iota => (2, (3, (4, ()))) }.Seq => (1, (2, (3, (4, ())))) }.Iota => (1, (2, (3, (4, ())))) An argument could certainly be made to include Seq!(...) in every list after =>, but when should I finally evaluate those, then? I opted for parenthesized groups instead. -- Simen
Jun 04 2020
parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Thursday, 4 June 2020 at 12:34:14 UTC, Simen Kjærås wrote:
 On Thursday, 4 June 2020 at 12:08:58 UTC, Stefan Koch wrote:
 [...]
More: This line is missing a trailing parenthesis: }.Iota => (3, Seq!(4, Seq!()) This line has an extra trailing parenthesis: }.Seq => (3, Seq!(4, Seq()))) This line has an extra trailing parenthesis: }.Seq => (1, Seq!(2, Seq!(3, Seq(4, Seq!()))))) This line is missing some starting parentheses (Seq!3 and Seq!4), and has an extra trailing one: }.Iota => (1, Seq!(2, Seq!3, Seq!4, Seq!())))))) [...]
Wow That's amazing. You found them all. (All I put it deliberately ;) and more) Your expansion also looks much nicer. Although it does not quite reflect the order in which it happens it helps explaining. Did you do them by hand as well or did you use a script?
Jun 04 2020
parent reply Simen =?UTF-8?B?S2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On Thursday, 4 June 2020 at 12:44:30 UTC, Stefan Koch wrote:

 Wow That's amazing.
 You found them all. (All I put it deliberately ;) and more)
Cool, I didn't expect that. :)
 Your expansion also looks much nicer.
 Although it does not quite reflect the order in which it 
 happens it helps explaining.

 Did  you do them by hand as well or did you use a script?
By hand. I first established the pattern, so it was easy to see where each number would go, then just filled it in and did the opposite of what you did when you deliberately inserted mistakes. :p Bonus, here's the divide-and-conquer version: template Iota(int from, int to) { static assert (from <= to); static if (from == to) { alias Iota = AliasSeq!(); } else static if (from == to-1) { alias Iota = AliasSeq!from; } else { alias Iota = AliasSeq!( Iota!(from, (from + to) / 2), Iota!((from + to) / 2, to)); } } Iota!(1, 5): { alias Iota = Seq!(Iota!(1, 3), Iota!(3, 5)); Seq!(Iota!(1, 3), Iota!(3, 5)): { alias Seq = (Iota!(1, 3), Iota!(3, 5)); Iota!(1, 3): { alias Iota = Seq!(Iota!(1, 2), Iota!(2, 3)); Seq!(Iota!(1, 2), Iota!(2, 3)): { alias Seq = (Iota!(1, 2), Iota!(2, 3)); Iota!(1, 2): { alias Iota = Seq!1; Seq!1: { alias Seq = (1); }.Seq => (1) }.Iota => (1) Iota!(2, 3): { alias Iota = Seq!2; Seq!2: { alias Seq = (2); }.Seq => (2) }.Iota => (2) }.Seq => ((2), (3)) }.Iota => ((2), (3)) Iota!(3, 5): { alias Iota = Seq!(Iota!(3, 4), Iota!(4, 5)); Seq!(Iota!(3, 4), Iota!(4, 5)): { alias Seq = (Iota!(3, 4), Iota!(4, 5)); Iota!(3, 4): { alias Iota = Seq!3; Seq!3: { alias Seq = (3); }.Seq => (3) }.Iota => (3) Iota!(4, 5): { alias Iota = Seq!4; Seq!4: { alias Seq = (4); }.Seq => (4) }.Iota => (4) }.Seq => ((3), (4)) }.Iota => ((3), (4)) }.Seq => (((2), (3)), ((3), (4))) }.Iota => (((2), (3)), ((3), (4))) Haven't checked that for mistakes as rigorously as the other version, so there might be some. -- Simen
Jun 04 2020
parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Thursday, 4 June 2020 at 13:05:04 UTC, Simen Kjærås wrote:
 On Thursday, 4 June 2020 at 12:44:30 UTC, Stefan Koch wrote:

 [snip]
 Bonus, here's the divide-and-conquer version:


 --
   Simen
Oh wow. I have to puke while reading but it's awesome you did this. Would you be opposed if I your unrolled versions on my youtube channel?
Jun 04 2020
parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Thursday, 4 June 2020 at 13:10:56 UTC, Stefan Koch wrote:
 On Thursday, 4 June 2020 at 13:05:04 UTC, Simen Kjærås wrote:
 On Thursday, 4 June 2020 at 12:44:30 UTC, Stefan Koch wrote:

 [snip]
 Bonus, here's the divide-and-conquer version:


 --
   Simen
Oh wow. I have to puke while reading but it's awesome you did this. Would you be opposed if I your unrolled versions on my youtube channel?
I meant to write if I showed your versions on my youtube channel.
Jun 04 2020
parent reply Simen =?UTF-8?B?S2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On Thursday, 4 June 2020 at 13:11:33 UTC, Stefan Koch wrote:
 On Thursday, 4 June 2020 at 13:10:56 UTC, Stefan Koch wrote:
 On Thursday, 4 June 2020 at 13:05:04 UTC, Simen Kjærås wrote:
 On Thursday, 4 June 2020 at 12:44:30 UTC, Stefan Koch wrote:

 [snip]
 Bonus, here's the divide-and-conquer version:


 --
   Simen
Oh wow. I have to puke while reading but it's awesome you did this. Would you be opposed if I your unrolled versions on my youtube channel?
I meant to write if I showed your versions on my youtube channel.
Not at all - take it, paint it red, say you wrote it, whatever. :) -- Simen
Jun 04 2020
parent Stefan Koch <uplink.coder googlemail.com> writes:
On Thursday, 4 June 2020 at 13:18:12 UTC, Simen Kjærås wrote:

 Not at all - take it, paint it red, say you wrote it, whatever. 
 :)

 --
   Simen
I will credit you of course! You deserve it for suffering through it.
Jun 04 2020
prev sibling next sibling parent Manu <turkeyman gmail.com> writes:
On Thu, Jun 4, 2020 at 9:35 PM Stefan Koch via Digitalmars-d <
digitalmars-d puremagic.com> wrote:

 As part of my series of templates
 I have done a a full instantiation of Iota!(1,5).
 (By hand!)
 And here is the result:

 Iota!(1,5)
 {
      {
          alias Iota = Seq!(1, Iota!(1 + 1, 5));
      }
      Seq!(1, Iota!(1 + 1, 5))
      {
          alias Seq = (1, Iota!(1 + 1, 5));
          Iota!(1 + 1, 5) => Iota!(2, 5)
          {
              alias Iota = Seq!(2, Iota!(2 +1, 5));
          }
          Seq!(2, Iota(2 + 1, 5))
          {
              alias seq = (2, Iota!(2 + 1, 5))
              Iota!(2 + 1, 5) => Iota!(3, 5)
              {
                  alias Iota = Seq!(3, Iota!(3 +1, 5));
              }
              Seq!(3, Iota!(3 + 1, 5))
              {
                  alias Seq = (3, Iota!(3 + 1, 5));
                  Iota!(3 + 1, 5) => Iota!(4, 5)
                  {
                      alias Iota = Seq!(4, Iota!(4 +1, 5));
                      Seq!(4, Iota!(4 + 1, 5))
                      {
                          alias seq = (4, Iota!(4 + 1, 5));
                          Iota!(4 + 1, 5) => Iota!(5, 5)
                          {
                              {
                                  alias Iota = Seq!();
                                  { Seq!() => () }.Seq => ()
                              }
                          }.Iota => Seq!()
                      }.Seq => (4, Seq!())
                  }.Iota => (3, Seq!(4, Seq!())
              }.Seq => (3, Seq!(4, Seq())))
          }.Seq => (2, (Seq!(3, Seq!(4, Seq!()))))
      }.Seq => (1, Seq!(2, Seq!(3, Seq(4, Seq!())))))
 }.Iota => (1, Seq!(2, Seq!3, Seq!4, Seq!()))))))

 Because it has been done manually there are probably some bugs.
 Can you find them all?
Iota should be this: `tuple(x .. y)` (assuming 1st-class tuples existed), or in the current language: `AliasSeq!(x .. y)`, which is syntactically invalid, but something like this really should exist. Your example expansion above looks kinda broken, but it makes the point... I feel like D is currently awakening to a similar reality as the C++ dark-ages period in the mid 00's, where templates were 'discovered', books were written (by popular authors), and the worst C++ code and patterns ever written came into existence. The reaction for many of us at that time (especially in video games/embedded systems) was to ban C++ completely and revert to C for a decade until such a later time that we could be trusted again. This is essentially D's manifestation of the same negligence, and I think it's time to own it and move forward. I think there are a few obvious solutions: 1. My `...` operator DIP, map/reduce patterns are extremely common and responsible for much/most explosive template bloat 2. Recognise that templates are NOT FOR EXECUTING CODE; templates are for parameterisation of definitions. There is a painfully obvious tool for executing code; functions, made up of a series of statements. The rule of least-surprise should surely dictate that when people want to perform calculations or generate a result, they should use a function. Sadly, functions don't work in static contexts like with types or aliases... so in D, meta with such results can only be written awkwardly with templates. There has been discussion of type functions on and off for ages, and Stefan has recently demonstrated some concrete progress on this front... I think that's the way forward. It is the path that will lead us from the dark instantiation-bloat forest that D finds itself in today. It will be clearer, saner, and faster. A new D user will find a type function intuitive, and will never have to poison their mind with awkward FP-style recursive template expansions with weird edges and considerations.
Jun 04 2020
prev sibling parent reply Stanislav Blinov <stanislav.blinov gmail.com> writes:
On Thursday, 4 June 2020 at 11:33:48 UTC, Stefan Koch wrote:
 As part of my series of templates
 I have done a a full instantiation of Iota!(1,5).
 (By hand!)
 And here is the result:

 // ...

 Because it has been done manually there are probably some bugs.
 Can you find them all?
Is that really full? I.e. you're not counting the instantiations of Seq on purpose? :) If I understand correctly, the below (basically manually written version of std.meta.aliasSeqOf) would just be Iota!(1, 5) => Iota? template Iota(size_t first, size_t last) { struct Result { static foreach (i; first .. last) mixin("auto e", i, " = ", i, ";"); } enum Iota = Result.init.tupleof; }
Jun 04 2020
next sibling parent Stefan Koch <uplink.coder googlemail.com> writes:
On Thursday, 4 June 2020 at 13:21:08 UTC, Stanislav Blinov wrote:
 On Thursday, 4 June 2020 at 11:33:48 UTC, Stefan Koch wrote:
 As part of my series of templates
 I have done a a full instantiation of Iota!(1,5).
 (By hand!)
 And here is the result:

 // ...

 Because it has been done manually there are probably some bugs.
 Can you find them all?
Is that really full? I.e. you're not counting the instantiations of Seq on purpose? :) If I understand correctly, the below (basically manually written version of std.meta.aliasSeqOf) would just be Iota!(1, 5) => Iota? template Iota(size_t first, size_t last) { struct Result { static foreach (i; first .. last) mixin("auto e", i, " = ", i, ";"); } enum Iota = Result.init.tupleof; }
I cannot answer that right now. My head is already spinning from the mental exercise.
Jun 04 2020
prev sibling next sibling parent Simen =?UTF-8?B?S2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On Thursday, 4 June 2020 at 13:21:08 UTC, Stanislav Blinov wrote:
 On Thursday, 4 June 2020 at 11:33:48 UTC, Stefan Koch wrote:
 As part of my series of templates
 I have done a a full instantiation of Iota!(1,5).
 (By hand!)
 And here is the result:

 // ...

 Because it has been done manually there are probably some bugs.
 Can you find them all?
Is that really full? I.e. you're not counting the instantiations of Seq on purpose? :) If I understand correctly, the below (basically manually written version of std.meta.aliasSeqOf) would just be Iota!(1, 5) => Iota? template Iota(size_t first, size_t last) { struct Result { static foreach (i; first .. last) mixin("auto e", i, " = ", i, ";"); } enum Iota = Result.init.tupleof; }
That is a cool (but pretty darn ugly) trick. Of course, it uses CTFE, so there's a whole nother set of complications that we haven't yet covered. But if we ignore those the instantiation graph would be this: Iota!(1, 5): { enum Iota = (1, 2, 3, 4); }.Iota = (1, 2, 3, 4) -- Simen
Jun 04 2020
prev sibling parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 6/4/20 9:21 AM, Stanislav Blinov wrote:
 On Thursday, 4 June 2020 at 11:33:48 UTC, Stefan Koch wrote:
 As part of my series of templates
 I have done a a full instantiation of Iota!(1,5).
 (By hand!)
 And here is the result:

 // ...

 Because it has been done manually there are probably some bugs.
 Can you find them all?
Is that really full? I.e. you're not counting the instantiations of Seq on purpose? :) If I understand correctly, the below (basically manually written version of std.meta.aliasSeqOf) would just be Iota!(1, 5) => Iota? template Iota(size_t first, size_t last) {     struct Result {         static foreach (i; first .. last)             mixin("auto e", i, " = ", i, ";");     }     enum Iota = Result.init.tupleof; }
That's a cool trick. I like the fact that it uses mixins to output the numbers as well. It might be faster though, to generate using a fully CTFE function instead of using static foreach. Can't use the numbers directly, so I have to write a crude "number to string" converter. template iota(size_t first, size_t last) { import std.meta : AliasSeq; string genMixin() { char[11] num = "0x00000000,"; string result = "alias iota = AliasSeq!("; immutable char[16] vals = "0123456789abcdef"; foreach(i; first .. last) { int j = num.length - 1; while(i) { num[--j] = vals[i & 0xf]; i >>= 4; } result ~= num; } return result ~ ");"; } mixin(genMixin()); } alias iota(size_t last) = iota!(0, last); And of course, the fastest would be for the compiler to just do it. -Steve
Jun 04 2020
next sibling parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Thursday, 4 June 2020 at 17:03:38 UTC, Steven Schveighoffer 
wrote:
 On 6/4/20 9:21 AM, Stanislav Blinov wrote:
 [...]
That's a cool trick. I like the fact that it uses mixins to output the numbers as well. [...]
Preallocate. or it'll be slow.
Jun 04 2020
parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 6/4/20 1:09 PM, Stefan Koch wrote:
 On Thursday, 4 June 2020 at 17:03:38 UTC, Steven Schveighoffer wrote:
 On 6/4/20 9:21 AM, Stanislav Blinov wrote:
 [...]
That's a cool trick. I like the fact that it uses mixins to output the numbers as well. [...]
Preallocate. or it'll be slow.
Sure, I could do that. But my point is not to submit a proposal for static iota, but to show that CTFE can handle the whole thing, we don't need to use static foreach (which as I understand it can be very slow). -Steve
Jun 04 2020
parent Stefan Koch <uplink.coder googlemail.com> writes:
On Thursday, 4 June 2020 at 17:16:48 UTC, Steven Schveighoffer 
wrote:
 On 6/4/20 1:09 PM, Stefan Koch wrote:
 On Thursday, 4 June 2020 at 17:03:38 UTC, Steven Schveighoffer 
 wrote:
 On 6/4/20 9:21 AM, Stanislav Blinov wrote:
 [...]
That's a cool trick. I like the fact that it uses mixins to output the numbers as well. [...]
Preallocate. or it'll be slow.
Sure, I could do that. But my point is not to submit a proposal for static iota, but to show that CTFE can handle the whole thing, we don't need to use static foreach (which as I understand it can be very slow). -Steve
Ideally we would not pile a hack on top of a hack.
Jun 04 2020
prev sibling parent reply Adam D. Ruppe <destructionator gmail.com> writes:
On Thursday, 4 June 2020 at 17:03:38 UTC, Steven Schveighoffer 
wrote:
         char[11] num = "0x00000000,";
thar be dragons here matey https://issues.dlang.org/show_bug.cgi?id=20811
Jun 04 2020
parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 6/4/20 1:12 PM, Adam D. Ruppe wrote:
 On Thursday, 4 June 2020 at 17:03:38 UTC, Steven Schveighoffer wrote:
         char[11] num = "0x00000000,";
thar be dragons here matey https://issues.dlang.org/show_bug.cgi?id=20811
Easy to fix. auto num = "0x00000000,".dup; -Steve
Jun 04 2020