www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Generic structural recursion

reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
Got stuck on this metaprogramming problem, and can't seem to find a way
to make it work, just wondering if any of you guys can come up with a
clean solution:

I have a bunch of nested structs of the form:

	struct S { double data; }
	struct T { S s1, s2; }
	struct U { S s, T[2] ts; }
	struct V { T t, U u; }
	... // etc.

and a bunch of functions that operate on structs of this form via
structural recursion, of the following form (the exact number of
parameters of type X differs across functions):

--------
X interpolate(X)(ref X result, double idx, X data1, X data2) {
	foreach (field; FieldNameTuple!X) {
		alias Type = typeof(__traits(getMember, X, field));
		if (is(Type == double))
			__traits(getMember, result, field) =
				(1.0-idx)*__traits(getMember, data1, field)
				+ idx*__traits(getMember, data2, field);
		else if (is(Type == struct)) {
			interpolate(
				__traits(getMember, result, field), idx,
				__traits(getMember, data1, field),
				__traits(getMember, data2, field));
		} else if (is(Type == U[n], U, size_t n)) {
			foreach (i; 0 .. n) {
				interpolate(
					__traits(getMember, result, field)[i], idx,
					__traits(getMember, data1, field)[i],
					__traits(getMember, data2, field)[i]);
			}
		}
	}
}
--------

IOW, given some number of structs of type X, each function recurses down
the nested structs and invokes some operation (in this case an
interpolation function) on the corresponding double fields of each
argument.

As you can see above, there's a LOT of boilerplate needed for each
function. Whenever I want to change the recursion (e.g., support dynamic
arrays, or exclude certain types from the recursion) I have to modify
every function by hand -- a tedious and error-prone process.  I'd like
to factor out the code that recurses down the nested structs into a
separate template function, say call it structuralRecurse, and have each
of the operations simply call structuralRecurse with some delegate or
function literal that would be invoked on each set of corresponding
double fields.

But so far, I've not been able to do this in its full generality, i.e.,
something of the form:

------
void structuralRecurse(alias fun, T, size_t n)(T t0, T t1, ... T tn) {
	// invoke fun(t0.x.y.z, t1.x.y.z, ...); for each double field in T
}
------

Even using a giant string mixin so far hasn't been obvious, because of
the recursive descent required. And I'd like if possible to avoid using
giant string mixins for obvious reasons.

Anybody has any ideas?


T

-- 
If it breaks, you get to keep both pieces. -- Software disclaimer notice
Jan 26 2022
next sibling parent reply John Colvin <john.loughran.colvin gmail.com> writes:
On Wednesday, 26 January 2022 at 18:22:18 UTC, H. S. Teoh wrote:

 [...]


You could define a template that introspects a struct type and 
gives you a tuple of getters (each taking a struct and returning 
one of the doubles), then your functions that do real work would 
just loop over those getters. I suspect using the new(-ish) alias 
assign feature would help in defining that template.
Jan 26 2022
next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Jan 26, 2022 at 06:41:50PM +0000, John Colvin via Digitalmars-d wrote:

 On Wednesday, 26 January 2022 at 18:22:18 UTC, H. S. Teoh wrote:

 [...]


 
 You could define a template that introspects a struct type and gives
 you a tuple of getters (each taking a struct and returning one of the
 doubles), then your functions that do real work would just loop over
 those getters. I suspect using the new(-ish) alias assign feature
 would help in defining that template.


Excellent idea!!  Instead of trying to inject some arbitrary function
with multiple arguments into the middle of a recursive traversal, do the
traversal separately at compile-time exclusively on the type, generate
an array of fields, and let the caller loop over them.

Here's the solution I settled on:

--------
string[] eachParam(T)(string prefix = "")
{
    string[] result;
    if (__ctfe)
    {
        foreach (field; FieldNameTuple!T)
        {
            alias F = typeof(__traits(getMember, T, field));
            static if (is(F == double))
            {
                result ~= prefix ~ "." ~ field;
            }
            else static if (is(F == struct))
            {
                result ~= eachParam!F(prefix ~ "." ~ field);
            }
            else static if (is(F == E[n], E, size_t n))
            {
                foreach (j; 0 .. __traits(getMember, T, field).length)
                {
                    result ~= eachParam!E(text(prefix, ".", field,
                                               "[", j, "]"));
                }
            }
        }
        return result;
    }
    else assert(0);
}

void interpolate(alias ipol = linearInterpolate, T)
                (ref T model, double idx, T t1, T t2)
{
    static foreach (param; eachParam!T)
    {
        mixin("model" ~ param) = ipol(idx, mixin("pose1" ~ param),
                                           mixin("pose2" ~ param));
    }
}

void nullify(ref T model)
{
    static foreach (param; eachParam!T)
    {
    	mixin("model" ~ param) = double.nan;
    }
}

// ... and so on
--------

Both parts nice and clean. Well OK, so I used a bunch of mixins. But
they are little self-contained snippets rather than entire function
bodies. That's a win.


T

-- 
Why ask rhetorical questions? -- JC
Jan 26 2022
prev sibling parent =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 1/26/22 10:41, John Colvin wrote:


 You could define a template that introspects a struct type and gives you
 a tuple of getters


I've done something similar for ROS where data is a bunch of bytes but 
with a well-defined structure. The difference there is array elements 
are inline with their length encoded first.

So I introspected a FieldSkipper for each struct member which actually 
consisted of the FieldSkippers of the previous members (array skippers 
being smart and recursive to skip over the elements as well).

Then I had a FieldGetter that would use the corresponding FieldSkipper 
to find the right bytes. Fun stuff... :)

Ali
Jan 27 2022
prev sibling parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 1/26/22 1:22 PM, H. S. Teoh wrote:


 --------
 X interpolate(X)(ref X result, double idx, X data1, X data2) {
 	foreach (field; FieldNameTuple!X) {
 		alias Type = typeof(__traits(getMember, X, field));
 		if (is(Type == double))
 			__traits(getMember, result, field) =
 				(1.0-idx)*__traits(getMember, data1, field)
 				+ idx*__traits(getMember, data2, field);
 		else if (is(Type == struct)) {
 			interpolate(
 				__traits(getMember, result, field), idx,
 				__traits(getMember, data1, field),
 				__traits(getMember, data2, field));
 		} else if (is(Type == U[n], U, size_t n)) {
 			foreach (i; 0 .. n) {
 				interpolate(
 					__traits(getMember, result, field)[i], idx,
 					__traits(getMember, data1, field)[i],
 					__traits(getMember, data2, field)[i]);
 			}
 		}
 	}
 }
 --------


This looks a lot like serialization. What you have done looks more 
specific to your use case though. Why not call a function recursively 
for each type encountered?

e.g.:

```d
auto interpolate(alias fn, X : double)(ref X val1, ref X val2)
{
    static if(is(typeof(fn(val1, val2)))) return fn(val1, val2);
}

auto interpolate(alias fn, X)(ref X val1, ref X val2) if (is(X == struct))
{
    // loop and recurse
}
...
```

Then you can write a set of templates that act on the right types, and 
do the thing you want for that specific type, pass that in as `fn`.

I find splitting the work into distinct portions when doing these kinds 
of introspection tasks to be more straightforward and testable.

-Steve
Jan 26 2022
parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Jan 26, 2022 at 02:06:18PM -0500, Steven Schveighoffer via
Digitalmars-d wrote:
[...]

 ```d
 auto interpolate(alias fn, X : double)(ref X val1, ref X val2)
 {
    static if(is(typeof(fn(val1, val2)))) return fn(val1, val2);
 }
 
 auto interpolate(alias fn, X)(ref X val1, ref X val2) if (is(X == struct))
 {
    // loop and recurse
 }
 ...
 ```


That's what I had, but the problem is that the number of X arguments
differs from function to function.  So I'd have to duplicate the
recursion part for each number of arguments, which is bad because
there's a chance I might change the recursion in the unary version and
forget to update it in the binary/ternary/etc. version.


T

-- 
Why can't you just be a nonconformist like everyone else? -- YHL
Jan 26 2022
parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 1/26/22 2:57 PM, H. S. Teoh wrote:

 On Wed, Jan 26, 2022 at 02:06:18PM -0500, Steven Schveighoffer via
Digitalmars-d wrote:
 [...]

 ```d
 auto interpolate(alias fn, X : double)(ref X val1, ref X val2)
 {
     static if(is(typeof(fn(val1, val2)))) return fn(val1, val2);
 }

 auto interpolate(alias fn, X)(ref X val1, ref X val2) if (is(X == struct))
 {
     // loop and recurse
 }
 ...
 ```


 
 That's what I had, but the problem is that the number of X arguments
 differs from function to function.  So I'd have to duplicate the
 recursion part for each number of arguments, which is bad because
 there's a chance I might change the recursion in the unary version and
 forget to update it in the binary/ternary/etc. version.


Well, this is what I would do then.

```d
auto interpolateImpl(alias fn, Vals...)(ref Vals vals) if (is(Vals[0] == 
double))
{
    return fn(vals);
}

// handle all the other specific types etc.

auto interpolate(alias fn, Vals...)(ref Vals vals) if (allSameType!Vals)
{
    return interpolateImpl!fn(vals);
}
```

Then the only complex one is the one for aggregates.

-Steve
Jan 27 2022