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

```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
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
```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
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

--
Simen
```
Jun 04
```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
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
```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
```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
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
```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
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
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
```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.
```
Jun 04
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
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
```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
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
```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
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
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