How templates work (2) - Recursive templates

[Stefan Koch]

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