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

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.
https://forum.dlang.org/thread/nmwjtxssyjsflawxfbaj@forum.dlang.org

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)?

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.

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

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.

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.