www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Compile-time fold expression vs recursive template

reply Nick Treleaven <nick geany.org> writes:
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?
Jun 13 2020
next sibling parent reply Paul Backus <snarwin gmail.com> writes:
On Saturday, 13 June 2020 at 10:52:46 UTC, Nick Treleaven wrote:

 Recently 2 ideas have been proposed to reduce the need for 
 recursive templates:


[...]

 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


[...]

 What do you think?


This is fundamentally the same kind of thing as the proposed 
`...` operator--a single AST macro added to the language as a 
special-case feature, rather than a general facility for doing 
AST-macro-like things.

Of course, Walter has vetoed full-fledged AST macros, so we won't 
be seeing those in D any time soon, but I think it is perhaps 
worth taking a look at which features of AST macros would be 
useful to have (e.g., not storing intermediate values in the 
symbol table), and attempting to design a general-purpose 
facilities that give the programmer access to those features.
Jun 13 2020
parent reply Nick Treleaven <nick geany.org> writes:
On Saturday, 13 June 2020 at 12:35:58 UTC, Paul Backus wrote:

 This is fundamentally the same kind of thing as the proposed 
 `...` operator--a single AST macro added to the language as a 
 special-case feature, rather than a general facility for doing 
 AST-macro-like things.

 Of course, Walter has vetoed full-fledged AST macros, so we 
 won't be seeing those in D any time soon, but I think it is 
 perhaps worth taking a look at which features of AST macros 
 would be useful to have (e.g., not storing intermediate values 
 in the symbol table), and attempting to design a 
 general-purpose facilities that give the programmer access to 
 those features.


I realized my FoldExpression feature invented too much syntax. 
Really all we need is a way to limit what a template can do, i.e. 
(1) not cache instantiations and (2) not declare symbols (aside 
from eponymous symbols) so it can share a single Scope instance 
in dmd. That Scope instance would be reused upon each recursion, 
and only one recursion is allowed in each inner `static if` 
branch. That could be done just by recognizing a special 
identifer __Fold:

template staticIndexOf(alias A, S...)
{
     template __Fold(uint i = 0)
     {
         static if (i != S.length)
         {
             static if (isSame!(A, S[i]))
                 enum __Fold = i;
             else
                 enum __Fold = __Fold!(i + 1);
         }
         else
             enum __Fold = -1;
     }
     alias staticIndexOf = __Fold!();
}

Or we could have separate template attributes for wider 
applicability. In fact those attributes could potentially be 
inferred, although doing that by default might slow compilation. 
Then existing code could even benefit from the new attributes.
Jun 19 2020
parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Friday, 19 June 2020 at 17:04:57 UTC, Nick Treleaven wrote:

 On Saturday, 13 June 2020 at 12:35:58 UTC, Paul Backus wrote:

 [...]


 I realized my FoldExpression feature invented too much syntax. 
 Really all we need is a way to limit what a template can do, 
 i.e. (1) not cache instantiations and (2) not declare symbols 
 (aside from eponymous symbols) so it can share a single Scope 
 instance in dmd. That Scope instance would be reused upon each 
 recursion, and only one recursion is allowed in each inner 
 `static if` branch. That could be done just by recognizing a 
 special identifer __Fold:

 [...]


We should talk and band together.
Multiple competing proposals won't help here.

We at least have gained some clarity about the problem.
Now let's gain some clarity about the solution space.
Jun 19 2020
parent reply Paul Backus <snarwin gmail.com> writes:
On Friday, 19 June 2020 at 17:36:54 UTC, Stefan Koch wrote:

 We should talk and band together.
 Multiple competing proposals won't help here.

 We at least have gained some clarity about the problem.
 Now let's gain some clarity about the solution space.


Here's my idea: we introduce a new kind of template called "macro 
templates" (working title).

Macro templates are like regular templates, but with two 
differences. First, they are subject to the following 
restrictions:

- A macro template may only contain `enum` and `alias` 
declarations.
- A macro template must have an eponymous member.

Second, each instantiation of a macro template is evaluated 
independently, and once evaluated is immediately replaced in the 
source code with the value of its eponymous member. All 
intermediate results are discarded.

To give a concrete example, here's how `staticMap` could be 
written as a macro template:

macro template staticMap(alias F, Args...)
{
     static if (Args.length == 0)
         alias staticMap = AliasSeq!();
     else
         alias staticMap = AliasSeq!(F!(Args[0]), staticMap!(F, 
Args[1 .. $]));
}

And here's how an instantiation of that version of `staticMap` 
would be evaluated:

alias result = staticMap!(ConstOf, int, char, double);

... = AliasSeq!(
           ConstOf!int,
           staticMap!(ConstOf, char, double));

... = AliasSeq!(
           ConstOf!int,
           AliasSeq!(
               ConstOf!char,
               staticMap!(ConstOf, double)));


... = AliasSeq!(
           ConstOf!int,
           AliasSeq!(
               ConstOf!char,
               AliasSeq!(
                   ConstOf!double,
                   staticMap!(ConstOf))));

... = AliasSeq!(
           ConstOf!int,
           AliasSeq!(
               ConstOf!char,
               AliasSeq!(
                   ConstOf!double,
                   AliasSeq!())));

The total cost here, in terms of symbol-table bloat, is:
- 4 instances of `AliasSeq`
- 3 instances of `ConstOf`

Notice that `staticMap` itself has completely disappeared. By 
making `AliasSeq` and `ConstOf` into macro templates as well, we 
can get the entire thing to reduce down to:

alias result = (const(int), const(char), const(double));

That is, we can eliminate *all* symbol-table bloat, and retain 
only the final result.

To achieve Nick Treleaven's goal of re-using the same Scope for 
each "iteration", all that is necessary is for the compiler to 
implement tail-call optimization for macro templates (a 
well-known and well-studied technique). `staticMap` can then be 
easily re-written to use a tail-recursive helper template.

One big advantage of this approach is that it is largely 
backwards compatible. Many existing templates can be converted 
simply by adding the `macro` keyword to their definition, without 
breaking existing code that depends on them.
Jun 19 2020
parent Stefan Koch <uplink.coder googlemail.com> writes:
On Friday, 19 June 2020 at 18:30:28 UTC, Paul Backus wrote:


 To achieve Nick Treleaven's goal of re-using the same Scope for 
 each "iteration", all that is necessary is for the compiler to 
 implement tail-call optimization for macro templates (a 
 well-known and well-studied technique). `staticMap` can then be 
 easily re-written to use a tail-recursive helper template.


I've tried to implement TCO, and it's really hard to do.
I would think it's best to present iteration as well interation.
There is no need to go into awkward recusion patterns.
Jun 19 2020
prev sibling next sibling parent reply Nick Treleaven <nick geany.org> writes:
On Saturday, 13 June 2020 at 10:52:46 UTC, Nick Treleaven wrote:

 Recently 2 ideas have been proposed to reduce the need for 
 recursive templates:


The reason for these is that recursive template expansion is slow 
and can use a lot of memory which is never freed.


 * A `Seq...` expression to expand inline a named sequence, or 
 an expression containing one or more named sequences.


Sorry, this should've read: "`Expression...` to expand an 
expression containing one or more named sequences". Here's the 
DIP link:
https://github.com/dlang/DIPs/blob/f9790ee6760b2d3cd0dbc1e816080c29c00c6dc2/DIPs/DIP10xx.md#add-unary-operator-


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


Manu did propose a follow up to that would support a very basic 
fold expression, but it seems to be limited to using an operator 
between element expressions (no `static if`):


 Static reduce would allow `...` as an argument to a BinOp
 Ie; `Tup + ...` would expand `Tup[0] + Tup[1] + Tup[2] + ...`
 You could do `is(FindType == Tup) || ...`, and it would 
 evaluate true if
 FindType exists in Tup, with no junk template instantiations!




https://forum.dlang.org/post/mailman.2786.1587566241.31109.digitalmars-d puremagic.com
Jun 14 2020
parent reply Manu <turkeyman gmail.com> writes:
On Sun, Jun 14, 2020 at 9:50 PM Nick Treleaven via Digitalmars-d <
digitalmars-d puremagic.com> wrote:


 On Saturday, 13 June 2020 at 10:52:46 UTC, Nick Treleaven wrote:

 Recently 2 ideas have been proposed to reduce the need for
 recursive templates:


 The reason for these is that recursive template expansion is slow
 and can use a lot of memory which is never freed.


 * A `Seq...` expression to expand inline a named sequence, or
 an expression containing one or more named sequences.


 Sorry, this should've read: "`Expression...` to expand an
 expression containing one or more named sequences". Here's the
 DIP link:

 https://github.com/dlang/DIPs/blob/f9790ee6760b2d3cd0dbc1e816080c29c00c6dc2/DIPs/DIP10xx.md#add-unary-operator-


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


 Manu did propose a follow up to that would support a very basic
 fold expression, but it seems to be limited to using an operator
 between element expressions (no `static if`):


 Static reduce would allow `...` as an argument to a BinOp
 Ie; `Tup + ...` would expand `Tup[0] + Tup[1] + Tup[2] + ...`
 You could do `is(FindType == Tup) || ...`, and it would
 evaluate true if
 FindType exists in Tup, with no junk template instantiations!





 https://forum.dlang.org/post/mailman.2786.1587566241.31109.digitalmars-d puremagic.com


It's implemented in my branch too if you wanna try it out!
Jun 14 2020
parent Nick Treleaven <nick geany.org> writes:
On Sunday, 14 June 2020 at 12:01:51 UTC, Manu wrote:

 On Sun, Jun 14, 2020 at 9:50 PM Nick Treleaven via 
 Digitalmars-d < digitalmars-d puremagic.com> wrote:

 Manu did propose a follow up to that would support a very 
 basic fold expression, but it seems to be limited to using an 
 operator between element expressions (no `static if`):


 Static reduce would allow `...` as an argument to a BinOp
 Ie; `Tup + ...` would expand `Tup[0] + Tup[1] + Tup[2] + 
 ...`
 You could do `is(FindType == Tup) || ...`, and it would
 evaluate true if
 FindType exists in Tup, with no junk template 
 instantiations!




 https://forum.dlang.org/post/mailman.2786.1587566241.31109.digitalmars-d puremagic.com


 It's implemented in my branch too if you wanna try it out!


https://github.com/TurkeyMan/dmd/commit/e150fa03521e1d5d12c77477c6dbcb46c9292fac

Haven't tried it, but it doesn't seem to be able to help with 
recursive templates much. It can do std.meta.anySatisfy and 
allSatisfy, but probably can't do much other folding of sequences 
that don't contain values.
Jun 19 2020
prev sibling parent Nick Treleaven <nick geany.org> writes:
On Saturday, 13 June 2020 at 10:52:46 UTC, Nick Treleaven wrote:

 the FoldExpression evaluates to a sequence of its last 
 parameter values


Actually it probably would be OK to use the parameter names as 
properties of the FoldExpression.


 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]..$]);
 }


alias Merge = AliasSeq!(Result.Acc,
     S[Result.i .. half], S[Result.j .. $]);

Easier to understand.
Jun 14 2020