I'll start with the punchline: at the link below you'll find an alpha-quality reimplementation of std.meta in an iterative manner:

https://gist.github.com/andralex/6212ebf2b38c59c96cf66d0009336318

It's the bulk of std.meta - I stopped when it became obvious doing more is just more of the same. Compiles and runs with dmd 2.092 and probably others.

The implementation uses throughout a reification/dereification approach. To reify a type or alias means to convert it into a value. To dereify a value means to turn it back into the type or alias it originated from.

The algorithms follow the following pattern consistently:

1. Reify the compile-time parameters into values
2. Carry processing on these values with the usual algorithms
3. If needed, dereify back the results into compile-time parameters

Not all artifacts need step 3. For example, allSatisfy returns a bool, not a type.

For the most part implementation has been a healthy gallop that took a couple of hours yesterday and a couple of hours today. Its weakest point is it uses .stringof for types, which has issues with local types. Hopefully https://github.com/dlang/dmd/pull/11797 could help with that.

Most implementations are a few lines long because they get to leverage algorithms as implemented in std. Here's a typical one:

alias MostDerived(Args...) = dereify!({
    auto ids = reify!Args;
    sort!((a, b) => is(dereify!a : dereify!b))(ids);
    return ids;
}());

To sort an AliasSeq with most derived elements first, create a lambda to reify the arguments into values, sort the values, and return the sorted result. Then call the lambda and use dereify against its result. And that is IT.

Commments and ideas for improvements are welcome.

On Sat, Sep 26, 2020 at 12:18:27PM -0400, Andrei Alexandrescu via Digitalmars-d wrote: [...]
> The implementation uses throughout a reification/dereification approach. To reify a type or alias means to convert it into a value. To dereify a value means to turn it back into the type or alias it originated from.
[...]
> Its weakest point is it uses .stringof for types, which has issues with local types. Hopefully https://github.com/dlang/dmd/pull/11797 could help with that.
[...]

This is awesome!  I think dmd pull #11797 is the best way forward from our current state.  It closes the reification/dereification loop, and allows CTFE manipulation of types as strings, which sidesteps the issues of how to manipulate types in imperative code without running into all sorts of problems like the ones that Stefan brought up.

In the future, I can imagine CTFE *generation* of these strings, which opens up brand new ways of manipulating types.  There could be a standard set of mangle-string manipulation utilities in druntime or phobos, say, that let you perform operations like adding/removing qualifiers, manipulating type lists (in string form!), so you could implement things like Unqual as a CTFE string manipulation function instead of a bunch of templates. Of course, Unqual is simple enough that there's no reason to do this, but the point is, we can do much more complicated manipulations of types without needing to resort to recursive templates, and it leverages existing machinery instead of inventing a slew of new ones.


T

-- 
LINUX = Lousy Interface for Nefarious Unix Xenophobes.

On Saturday, 26 September 2020 at 16:18:27 UTC, Andrei Alexandrescu wrote:
> 1. Reify the compile-time parameters into values
> 2. Carry processing on these values with the usual algorithms
> 3. If needed, dereify back the results into compile-time parameters

That's the right thought, and that's what type functions were designed to do.

How do they compare to the vision you have?

> Commments and ideas for improvements are welcome.

The PR referenced does not give, actually give you the ability to dereify types within CTFE.
The PR forces a template and template has to have template parameters to take the mangles.
I would think that is against the actual goal.

On Saturday, 26 September 2020 at 16:40:47 UTC, H. S. Teoh wrote:
> On Sat, Sep 26, 2020 at 12:18:27PM -0400, Andrei Alexandrescu via Digitalmars-d wrote: [...]
>> The implementation uses throughout a reification/dereification approach. To reify a type or alias means to convert it into a value. To dereify a value means to turn it back into the type or alias it originated from.
> [...]
>> Its weakest point is it uses .stringof for types, which has issues with local types. Hopefully https://github.com/dlang/dmd/pull/11797 could help with that.
> [...]
>
> This is awesome!  I think dmd pull #11797 is the best way forward from our current state.  It closes the reification/dereification loop, and allows CTFE manipulation of types as strings, which sidesteps the issues of how to manipulate types in imperative code without running into all sorts of problems like the ones that Stefan brought up.
>

#11797 is just a string mixin.
With all the constraints and problems.
Iff you can use a string mixin you can use __stringToType.
If you can't use a string mixin in the context you can't use stringToType.

On Saturday, 26 September 2020 at 16:18:27 UTC, Andrei Alexandrescu wrote:
> For the most part implementation has been a healthy gallop that took a couple of hours yesterday and a couple of hours today. Its weakest point is it uses .stringof for types, which has issues with local types. Hopefully https://github.com/dlang/dmd/pull/11797 could help with that.

It's amazing to me how obvious this idea seems now that I've seen it. D's had type -> string serialization for ages; of course there should also be a way to do the reverse! And yet somehow, it never even crossed my mind until I read Walter's PR.

I think this is a real winner.

On Saturday, 26 September 2020 at 17:30:44 UTC, Stefan Koch wrote:
>
> The PR referenced does not give, actually give you the ability to dereify types within CTFE.
> The PR forces a template and template has to have template parameters to take the mangles.
> I would think that is against the actual goal.

It's against the goal if your goal is for meta-functions to be 100% monomorphic. But it does accomplish the goal of turning template recursion (O(n) instantiations) into flat iteration (O(1) instantiations).

Personally, I don't think 100% monomorphism is necessary or particularly desirable, so I'm ok with a design that eschews it.

On 9/26/20 1:32 PM, Stefan Koch wrote:
> #11797 is just a string mixin.
> With all the constraints and problems.
> Iff you can use a string mixin you can use __stringToType.
> If you can't use a string mixin in the context you can't use stringToType.

mixin("+1000");

-Steve

On 26.09.20 18:18, Andrei Alexandrescu wrote:
> 
> Most implementations are a few lines long because they get to leverage algorithms as implemented in std. Here's a typical one:
> 
> alias MostDerived(Args...) = dereify!({
>      auto ids = reify!Args;
>      sort!((a, b) => is(dereify!a : dereify!b))(ids);
>      return ids;
> }());

I am pretty sure this one does not work though.

On 9/26/20 5:16 PM, Timon Gehr wrote:
> On 26.09.20 18:18, Andrei Alexandrescu wrote:
>>
>> Most implementations are a few lines long because they get to leverage algorithms as implemented in std. Here's a typical one:
>>
>> alias MostDerived(Args...) = dereify!({
>>      auto ids = reify!Args;
>>      sort!((a, b) => is(dereify!a : dereify!b))(ids);
>>      return ids;
>> }());
> 
> I am pretty sure this one does not work though.

Oops, Steve just told me it doesn't have any unittests. So it may as well not be working. Research goes on.

On 9/26/20 5:42 PM, Andrei Alexandrescu wrote:
> On 9/26/20 5:16 PM, Timon Gehr wrote:
>> On 26.09.20 18:18, Andrei Alexandrescu wrote:
>>>
>>> Most implementations are a few lines long because they get to leverage algorithms as implemented in std. Here's a typical one:
>>>
>>> alias MostDerived(Args...) = dereify!({
>>>      auto ids = reify!Args;
>>>      sort!((a, b) => is(dereify!a : dereify!b))(ids);
>>>      return ids;
>>> }());
>>
>> I am pretty sure this one does not work though.
> 
> Oops, Steve just told me it doesn't have any unittests. So it may as well not be working. Research goes on.

So just to follow up on this, the reason it doesn't work is because the relation between a and b must determined BEFORE the call to sort.

In other words, in order for this to work, you have to establish result of the lambda for all a and b in the array.

Or optionally, you can save enough information into the "Id" type that can be able to enable the comparison at runtime.

The general concept works, but only if you can create a relation function that doesn't rely on the types themselves, but on the runtime representation of the types.

In other words, such a function would need 3 steps:

1. transform the types into runtime data that is comparable given the types.
2. Run the runtime function that does the transformation
3. Convert the result back to the types.

Such things are not *impossible*, but something like derivative is a great example that is really difficult to generate a runtime function that can do it.

-Steve