## digitalmars.D - How templates work (2) - Recursive templates

```Hi,

it's time for the second part of my posts on templates.
Today we are going to look into how template recursion works,
using the same substitution method that we learned about in the
previous post.

Let's create a template which gives us a sequence of numbers 0 to
N
// credits for this one go to the from member Mehrdad [0] ...
since I couldn't figure out how to write it :)

template Iota(size_t i, size_t n)
{
static if (n == 0) { alias Iota = AliasSeq!(); }
else { alias Iota = AliasSeq!(i, Iota!(i + 1, n - 1)) ; }
}

template AliasSeq (seq...)
{
alias AliasSeq = seq;
}

With that out of the way let's look at the smallest interesting
case.
Iota!(0, 1)
which yields a tuple with the element 1

Iota!(0, 1) rewrites to
{
static if (1 == 0) { alias Iota = AliasSeq!(); }
else { alias Iota = AliasSeq!(0, {Iota!(0 + 1, 1 - 1)}.Iota); }
}
since (1 == 0) is obviously false we take the else branch
that makes the template to come out as
{ alias Iota = AliasSeq!(0, {Iota!(0 + 1, 1 - 1)) }.Iota

which causes us to instantiate
Iota!(0 + 1, 1 - 1) => Iota!(1, 0)
and it looks like:
Iota!(1, 0)
{
static if (0 == 0) { alias Iota = AliasSeq!(); }
else { alias Iota = AliasSeq!(1, {Iota!(1 + 1, 0 - 1)}.Iota);
}
}
here the else branch is taken and it resolves to
{ alias Iota = AliasSeq!(); }.Iota => AliasSeq!();
Lets substitute this into the above.

{ alias Iota = AliasSeq!(0, {alias Iota = AliasSeq!()}.Iota }.Iota
and resolve it
Iota!(0, 1) => AliasSeq(0)
this works because the empty aliasSeq resolves to nothing.

Now let's repeat the same process with the slightly more
intensive Iota!(0, 2)

Iota!(0, 2)
{
static if (2 == 0) { alias Iota = AliasSeq!(); }
else { alias Iota = AliasSeq!(1, Iota!(0 + 1, 2 - 1; }
}
drop the static if branch which does not apply
Iota!(0, 2)
{
{ alias Iota = AliasSeq!(0, Iota!(0 + 1, 2 - 1)); }
}
resolve the next Iota and drop the static if which does not apply
Iota!(1, 1)
{
{ alias Iota = AliasSeq!(1, Iota!(1 + 1, 1 - 1)); }
}
resolve the next Iota and drop the static if which does not apply
Iota!(2, 0)
{
{ alias Iota = AliasSeq!(); }
}
Substitute
Iota!(0, 2)
{
{ alias Iota = AliasSeq!(0,{AliasSeq!(1, {alias Iota =
Iota!(1 + 1, 1 - 1)}.Iota )}.Iota ); }.Iota
}
Substitute again
Iota!(0, 2)
{
{ alias Iota = AliasSeq!(0 ,alias Iota{ AliasSeq!(1, {alias
Iota = AliasSeq!( )}.Iota )}.Iota) }.Iota
}
Now we need to resolve.
The empty AliasSeq resolves to nothing leaving us with:
Iota!(0, 2)
{
{ alias Iota = AliasSeq!(0 , {alias Iota = AliasSeq!(1)}.Iota
) }.Iota
}
The one element AliasSeq resolves to that element
Iota!(0, 2)
{
{ alias Iota = AliasSeq!(0 , 1) }.Iota
}

Which leaves us with the desired Sequence {0, 1}

I am sorry that the example came out a bit long and inelegant.
But I could not find a better one :-/

You can verify these examples yourself by pasing the Iota
template into a .d file
And compiling with the -vcg-ast flag.
You should see all the templates instantiated which we
instantiated by hand just now.

I would like to note that although DMD just those steps;
It does them in a different order and they are slightly more
involves since it still has to perform type inference as well as
type and error checking.

I hope you liked this article ;)

[0]
https://forum.dlang.org/post/zzyxchnisumpjodczvcz forum.dlang.org
```
Jun 01
```On Monday, 1 June 2020 at 09:05:51 UTC, Stefan Koch wrote:
Hi,

it's time for the second part of my posts on templates.
Today we are going to look into how template recursion works,
using the same substitution method that we learned about in the
previous post.

[...]

Please do leave feedback.

If you are interested in the actual sequence that dmd will
execute on this.
I am happy give you some insight into that; although I will still
have to skip some steps to make it suitable for a post.

If you haven't read the first part of this series you can find it
here.
```
Jun 01
Guillaume Piolat <first.last gmail.com> writes:
```On Monday, 1 June 2020 at 10:20:14 UTC, Stefan Koch wrote:
Please do leave feedback.

Is the takeaway that recursive templates are intensive and should
be avoided (vs CTFE mixins)?
```
Jun 01
```On Monday, 1 June 2020 at 12:27:39 UTC, Guillaume Piolat wrote:
On Monday, 1 June 2020 at 10:20:14 UTC, Stefan Koch wrote:
Please do leave feedback.

Is the takeaway that recursive templates are intensive and
should be avoided (vs CTFE mixins)?

It depends on the case.
I have become careful of giving general recommendations.
```
Jun 01
Simen =?UTF-8?B?S2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
```On Monday, 1 June 2020 at 10:20:14 UTC, Stefan Koch wrote:
On Monday, 1 June 2020 at 09:05:51 UTC, Stefan Koch wrote:
Hi,

it's time for the second part of my posts on templates.
Today we are going to look into how template recursion works,
using the same substitution method that we learned about in
the previous post.

[...]

Please do leave feedback.

Great work!

First off, a few minor typos:

here the else branch is taken and it resolves to
{ alias Iota = AliasSeq!(); }.Iota => AliasSeq!();

That's the 'if' branch.

I would like to note that although DMD just those steps;

s/just/does

Second, your Iota doesn't match D's existing iota - your takes a
start and number of items, while the one in std.range takes
beginning and end items. Here's the equivalent in templates:

template Iota(size_t from, size_t to) {
static if (from >= to) {
alias Iota = AliasSeq!();
} else {
alias Iota = AliasSeq!(from, Iota!(from+1, to));
}
}

This may also be slightly easier to follow, since it's simply
counting up in the 'from' parameter, rather than changing two
values each step (so for Iota!(0, 2) you get AliasSeq!(0,
Iota!(1, 2)) => AliasSeq!(0, AliasSeq!(1, Iota!(2, 2)) =>
AliasSeq!(0, AliasSeq!(1, AliasSeq!())))).

All in all though, a great walkthough on what happens behind the
scenes. Makes me lightly disappointed I can't just write `alias x
= { alias y = int; }.y;` in regular code.

--
Simen
```
Jun 01
matheus <matheus gmail.com> writes:
```On Monday, 1 June 2020 at 09:05:51 UTC, Stefan Koch wrote:
...

Very nice, but why not writing a Blog Post so we could update
later and share?

By the way a blog post would be nice for other people to see
there is new content being added to the site.

Matheus.
```
Jun 01
```On Monday, 1 June 2020 at 15:26:54 UTC, matheus wrote:
On Monday, 1 June 2020 at 09:05:51 UTC, Stefan Koch wrote:
...

Very nice, but why not writing a Blog Post so we could update
later and share?

By the way a blog post would be nice for other people to see
there is new content being added to the site.

Matheus.

I am going to do one.
First I want to get part three out.
Scope Lookup.
```
Jun 01