Optimizing recursive templates

[Stefan Koch]

On Thursday, 24 September 2020 at 19:49:44 UTC, Stefan Koch wrote:
> Hi Guys,
>
> I am starting this thread to talk about the feasibility of 
> rewriting recursive templates as iterative internal forms.
>


Hi,

I very recently had a conversation about template optimization.
And during that an interesting example came up.

For a sequence of types (candidates) select the first one that is 
convertible to a given conversion target (convTarget)

The naive way of writing this template is not even this bad.

---
alias Seq(T...) = T;
alias EmptySeq = Seq!()
template  selectFirstConvertable(convTarget, candidates...)
{
     static if (!candidates.length)
         selectFirstConvertable = EmptySeq;
     else static if (is(candidates[0] : convTarget))
         selectFirstConvertable = candidates[0];
     else
         selectFirstConvertable = 
selectFirstConvertable!(candidates[1 .. $]);
}
---
So if I wanted to get rid of the recursion here, what would I do?
....
I don't really know.
Let's write the type function:

---
type selectFirstConvertable(type convTarget, type[] candidates 
...)
{
     type result; // initialzed to ∅
     foreach(c;candidates)
     {
        if (is(c : convTarget))
        {
           result = c;
           break;
        }
     }
     return result;
}
---

now let's search for commonalities.
a good one would be the exit condition of the loop

`if (is(c : convTarget))`

we can find a line in the template which almost looks like that

`else static if (is(candidates[0] : convTarget))`

we could substitute c for candidates[0] and get

`else static if (is(c : convTarget))`

which looks a lot like the condition in our loop.
so how can we determine that this will "break;" ?

Well as long as it does not recurse (directly or indirectly).
It must end the recursion.
That means if what's inside the static if branch does not 
instantiate any template,
we can assume it to be  termination.

is this true for the static if body in question?
yes. `selectFirstConvertable = candidates[0];`

does not recurse into itself.

So we've established a "break point" if you've pardon the pun :)
 From that we can deduce that the 'exit' condition is 
`is(candidates[0] : convTarget)`
We can further establish from `selectFirstConvertable = 
candidates[0];`
that we essentially do `return candidates[0]`;

which gives us a rewrite rule

   templateName = X;

can be rewritten as

return X;

let's apply those rewrite rule.
And annotate meaning.

template selectFirstConvertable(convTarget, candidates...)
{
     static if (!candidates.length)                   // reversed 
loop entrance condition
         return EmptySeq;
     else static if (is(candidates[0] : convTarget))  // loop exit 
condition
         return candidates[0];
     else
         return selectFirstConvertable!(candidates[1 .. $]); // 
loop increment
}

Now that's more like a function wouldn't you say?

so let's build a loop
template selectFirstConvertable(convTarget, candidates...)
{
	bool exitCondition = is(candidates[0] : convTarget);
     if (!canidates.length)
		return EmptySeq;
	else while (!exitCondition) // hitting this means the entrance 
condition was met
	{
		candidates = candidates[1 .. $] // problem is we can't do this!
		// re-evaluate exit condition
		exitCondition = is(candidates[0] : convTarget)
	}
	return candidates[0];
}

As we see, the loop necessitates for the language to be able to 
store a tuple in a variable
and for that variable to be mutable!
Also we need to be able to actually interpret the loop.

Which (for this example) requires for CTFE to know about is 
expressions
And for CTFE to turn Type into expressions (An ability which 
exists internal to dmd but is not exposed to the user)

Alternatively we could of course implement another interpretation 
system which would mirror most of CTFE but also allows
type variables.

In order to keep the systems unchanged.

The question then is, if we already have to do this.
Why not expose it to the user?

And when you follow that line of inquiry that leads you directly 
to ...

Well you can figure that out for yourself ;)

Cheers,

Stefan