www.digitalmars.com         C & C++   DMDScript  

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

reply Stefan Koch <uplink.coder googlemail.com> writes:
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 2020
next sibling parent reply Stefan Koch <uplink.coder googlemail.com> writes:
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
Jun 01 2020
next sibling parent reply 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 2020
parent Stefan Koch <uplink.coder googlemail.com> writes:
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 2020
prev sibling parent 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 2020
prev sibling parent reply 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 2020
parent Stefan Koch <uplink.coder googlemail.com> writes:
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 2020