Compile-time fold expression vs recursive template
Nick Treleaven
nick at geany.org
Sat Jun 13 10:52:46 UTC 2020
Recently 2 ideas have been proposed to reduce the need for
recursive templates:
* A `Seq...` expression to expand inline a named sequence, or an
expression containing one or more named sequences.
https://www.digitalmars.com/d/archives/digitalmars/D/I_dun_a_DIP_possibly_the_best_DIP_ever_337252.html#N337252
This is essentially just a compiler intrinsic to perform the
std.meta.Map operation, so it cannot wholly implement the other
recursive templates in std.meta (though in some cases it may
help).
* 'Type functions' - special functions which can mutate aliases
and sequences using the syntax of runtime constructs.
https://forum.dlang.org/thread/qdirevtnhnejmrpetcpr@forum.dlang.org
This is more general, but it cannot be used internally in
std.meta because it is a different paradigm. AIUI, for example,
instead of passing a template predicate to std.meta.Filter you
would pass a type function to a type-function-based version of
Filter. It would have a fairly big impact on Phobos to make wide
use of it.
So I've come up with something that is between the two, but
hopefully is still general enough to implement a fairly wide
class of recursive templates. The idea is to have an expression
which recursively evaluates arguments for the next iteration,
similar to std.algorithm.fold but at compile-time.
https://dlang.org/phobos/std_algorithm_iteration.html#fold
FoldExpression:
__Fold(AccumulatorDecls) if (Expression) {FoldStatements}
AccumulatorDecl:
Identifier
BasicType Identifier
alias Identifier
Identifier...
FoldStatement:
__Fold!(Expressions);
static if (Expression) FoldStatement else FoldStatement
Here's how you could implement std.meta.Map:
alias Map(alias Tem, S...) =
__Fold(Acc...) if (Acc.length != S.length) {
__Fold!(Acc, Tem!(S[Acc.length]));
};
Initially, Acc is an empty sequence. The __Fold!() expression
defines what the next iteration's parameters will be, in this
case `Tem!(S[0])` if s.length > 0. The second iteration will
evaluate to __Fold!(Tem!(S[0]), Tem!(S[1])) if s.length > 1. When
the `if` expression is false, the FoldExpression evaluates to a
sequence of its last parameter values, i.e. Acc above.
If you like, you can also implement that with an index as a
parameter:
alias Map(alias Tem, S...) =
__Fold(uint i = 0; Acc...) if (i != S.length) {
__Fold!(i + 1, Acc, Tem!(S[i]));
}[1..$];
The result of the __Fold expression is a sequence (i, Acc), so we
slice just the Acc part to remove the final index element and
obtain just the mapped items.
Within the FoldStatements, we can use `static if`, so we can
easily implement Filter:
alias Filter(alias pred, S...) =
__Fold(uint i = 0; Acc...) if (i != S.length) {
static if (pred!(S[i]))
__Fold!(i + 1, Acc, S[i]);
else
__Fold!(i + 1, Acc);
}[1..$];
We can also implement std.meta templates that don't create a
sequence:
enum anySatisfy(alias pred, S...) =
__Fold(bool found = false; uint i = 0)
if (!found && i != S.length) {
static if (pred!(S[i]))
__Fold!(true, i);
else
__Fold!(false, i + 1);
}[0];
Note: core.internal.traits actually implements anySatisfy with
`static foreach` rather than template recursion, but I'm hoping
the above can be competitive with that. The same is true for
std.meta.staticIndexOf:
enum staticIndexOf(alias A, S...) =
__Fold(bool found = false; uint i = 0)
if (!found && i != S.length) {
static if (isSame!(A, S[i]))
__Fold!(true, i));
else
__Fold!(false, i + 1);
}[1];
Note: isSame is a private template of std.meta.
How about templates that can't be implemented with `static
foreach`?
// similar to std.traits.fullyQualifiedName (the real version
would
// instantiate a formatting template instead of using stringof).
enum fqn(alias A) =
__Fold(string acc = A.stringof; alias S = A)
if (__traits(compiles(parent, S))) {
__Fold!(__traits(parent, S).stringof ~ '.' ~ acc,
__traits(parent, S));
}[0];
FoldExpression can't replace divide and conquer recursion, but
for std.meta.staticSort it can replace the private template
staticMerge:
template Merge(alias Less, uint half, S...)
{
alias Result = __Fold(uint i = 0; uint j = half; Acc...)
if (i != half && j != S.length) {
static if (Less!(S[i], S[j]))
__Fold!(i + 1, j, Acc, S[i]);
else
__Fold!(i, j + 1, Acc, S[j]);
};
// fold handles min(half, S.length - half) elements of S
// then append any remaining elements
alias Merge = AliasSeq!(Result[2..$],
S[Result[0]..half], S[Result[1]..$]);
}
But is a FoldExpression really more efficient than a recursive
template? Yes:
* It doesn't insert templateName!args strings into a symbol table
* It doesn't permanently cache the result of each iteration
* It doesn't declare any symbol, so it doesn't need its own scope
* For __Fold(T[] acc), a __Fold!(acc ~ element) expression could
reuse any spare capacity in the array to append element.
* For __Fold(Acc...), a __Fold!(Acc, Element) expression could
reuse any spare capacity in the memory allocated for Acc to
append Element.
What do you think?
More information about the Digitalmars-d
mailing list