digitalmars.D - How templates work (bonus) - Full instantiation of Iota!(1,5)
- Stefan Koch (47/47) Jun 04 2020 As part of my series of templates
- Simen =?UTF-8?B?S2rDpnLDpXM=?= (34/36) Jun 04 2020 The way you're doing it seems to change about halfway (notice the
- Stefan Koch (6/16) Jun 04 2020 The reason I show every step explicitly is because that's what's
- Simen =?UTF-8?B?S2rDpnLDpXM=?= (65/81) Jun 04 2020 More:
- Stefan Koch (7/20) Jun 04 2020 Wow That's amazing.
- Simen =?UTF-8?B?S2rDpnLDpXM=?= (79/85) Jun 04 2020 By hand. I first established the pattern, so it was easy to see
- Stefan Koch (5/10) Jun 04 2020 Oh wow. I have to puke while reading but it's awesome you did
- Stefan Koch (2/15) Jun 04 2020 I meant to write if I showed your versions on my youtube channel.
- Simen =?UTF-8?B?S2rDpnLDpXM=?= (4/21) Jun 04 2020 Not at all - take it, paint it red, say you wrote it, whatever. :)
- Stefan Koch (3/7) Jun 04 2020 I will credit you of course!
- Manu (35/82) Jun 04 2020 Iota should be this:
- Stanislav Blinov (12/19) Jun 04 2020 Is that really full? I.e. you're not counting the instantiations
- Stefan Koch (3/25) Jun 04 2020 I cannot answer that right now.
- Simen =?UTF-8?B?S2rDpnLDpXM=?= (11/33) Jun 04 2020 That is a cool (but pretty darn ugly) trick. Of course, it uses
- Steven Schveighoffer (31/55) Jun 04 2020 That's a cool trick. I like the fact that it uses mixins to output the
- Stefan Koch (3/8) Jun 04 2020 Preallocate. or it'll be slow.
- Steven Schveighoffer (6/16) Jun 04 2020 Sure, I could do that.
- Stefan Koch (3/20) Jun 04 2020 Ideally we would not pile a hack on top of a hack.
- Adam D. Ruppe (4/5) Jun 04 2020 thar be dragons here matey
- Steven Schveighoffer (4/10) Jun 04 2020 Easy to fix.
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
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
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 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.[...]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!())))). [...]
Jun 04 2020
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: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, ...)).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.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
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: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?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!())))))) [...][...]
Jun 04 2020
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
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: -- SimenOh 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
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:I meant to write if I showed your versions on my youtube channel.On Thursday, 4 June 2020 at 12:44:30 UTC, Stefan Koch wrote: [snip] Bonus, here's the divide-and-conquer version: -- SimenOh 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
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:Not at all - take it, paint it red, say you wrote it, whatever. :) -- SimenOn Thursday, 4 June 2020 at 13:05:04 UTC, Simen Kjærås wrote:I meant to write if I showed your versions on my youtube channel.On Thursday, 4 June 2020 at 12:44:30 UTC, Stefan Koch wrote: [snip] Bonus, here's the divide-and-conquer version: -- SimenOh 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
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. :) -- SimenI will credit you of course! You deserve it for suffering through it.
Jun 04 2020
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
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
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:I cannot answer that right now. My head is already spinning from the mental exercise.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
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: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) -- SimenAs 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
On 6/4/20 9:21 AM, Stanislav Blinov wrote:On Thursday, 4 June 2020 at 11:33:48 UTC, Stefan Koch wrote: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. -SteveAs 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
On Thursday, 4 June 2020 at 17:03:38 UTC, Steven Schveighoffer wrote:On 6/4/20 9:21 AM, Stanislav Blinov wrote:Preallocate. or it'll be slow.[...]That's a cool trick. I like the fact that it uses mixins to output the numbers as well. [...]
Jun 04 2020
On 6/4/20 1:09 PM, Stefan Koch wrote:On Thursday, 4 June 2020 at 17:03:38 UTC, Steven Schveighoffer wrote: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). -SteveOn 6/4/20 9:21 AM, Stanislav Blinov wrote:Preallocate. or it'll be slow.[...]That's a cool trick. I like the fact that it uses mixins to output the numbers as well. [...]
Jun 04 2020
On Thursday, 4 June 2020 at 17:16:48 UTC, Steven Schveighoffer wrote:On 6/4/20 1:09 PM, Stefan Koch wrote:Ideally we would not pile a hack on top of a hack.On Thursday, 4 June 2020 at 17:03:38 UTC, Steven Schveighoffer wrote: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). -SteveOn 6/4/20 9:21 AM, Stanislav Blinov wrote:Preallocate. or it'll be slow.[...]That's a cool trick. I like the fact that it uses mixins to output the numbers as well. [...]
Jun 04 2020
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
On 6/4/20 1:12 PM, Adam D. Ruppe wrote:On Thursday, 4 June 2020 at 17:03:38 UTC, Steven Schveighoffer wrote:Easy to fix. auto num = "0x00000000,".dup; -Stevechar[11] num = "0x00000000,";thar be dragons here matey https://issues.dlang.org/show_bug.cgi?id=20811
Jun 04 2020