January 23, 2007 challenge #2: implement the varargs_reduce metafunction | ||||
---|---|---|---|---|
| ||||
My previous post defines max by availing itself of a metafunction called varargs_reduce. Your challenge is to define it. varargs_reduce takes an alias which it assumes is a function of two arguments, and it defines a vararg function that applies that alias repeatedly, similarly to the reduce primitive that is present in functional languages. Again, for background on functional reduce, see e.g.: http://www.joelonsoftware.com/items/2006/08/01.html Define varargs_reduce to deduce the result type properly, and to generate code as efficient as possible. Andrei |
January 23, 2007 Re: challenge #2: implement the varargs_reduce metafunction | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu (See Website for Email) | Andrei Alexandrescu (See Website for Email) wrote: > My previous post defines max by availing itself of a metafunction called > varargs_reduce. Your challenge is to define it. varargs_reduce takes an > alias which it assumes is a function of two arguments, and it defines a > vararg function that applies that alias repeatedly, similarly to the > reduce primitive that is present in functional languages. Again, for > background on functional reduce, see e.g.: > > http://www.joelonsoftware.com/items/2006/08/01.html > > Define varargs_reduce to deduce the result type properly, and to generate code as efficient as possible. > > > Andrei Here is my try. I assume the reduce type must be exactly the same in all arguments. Should that not be the case? As for efficiency, I'm not sure what the requirements are. Is there to be any parallelization/vectorization considerations? This one, instead of linear iteration, uses binary recursion to calculate the result, but for *no particular reason* since its not actually any faster than linear recursion. This one seems much more easy that the fist challenge, so I suspect I'm missing something. ----------------------------------- //import stdext.stdio; import std.stdio : writeln = writefln; static import meta.Util; // Gets the typeof if not a type already. template TypeOf(alias ALIAS) { static if(is(ALIAS)) { alias ALIAS TypeOf; } else { alias typeof(ALIAS) TypeOf; } } // See if the types are the same template TypeEquals(alias A1, alias A2) { static if(is(TypeOf!(A1) == TypeOf!(A2))) const bool TypeEquals = true; else const bool TypeEquals = false; } // Duplicated template because primitive types do not match aliases :( template TypeEquals(T1, T2) { static if(is(T1 == T2)) const bool TypeEquals = true; else const bool TypeEquals = false; } /***************** varargsReduce ***************/ // Template implicit property workaround template varargsReduce(alias FN) { alias varargsReduce_Impl!(FN).varargsReduce_Impl varargsReduce; } template varargsReduce_Impl(alias FN) { static import std.traits; static assert(is(typeof(FN) == function) || is(typeof(FN) == delegate)); alias std.traits.ParameterTypeTuple!(FN) Params; alias std.traits.ReturnType!(FN) ReduceType; static assert(Params.length == 2); //static assert(typeof(FNarg1) == typeof(FNarg2)); static assert(TypeEquals!(Params[0], Params[1])); //static assert(typeof(FNarg1) == ReduceType); static assert(TypeEquals!(Params[0], ReduceType)); ReduceType varargsReduce_Impl(ARGS...) (ARGS args) { pragma(msg, "varargsReduce_Impl! length:" ~ meta.Util.itoa!(ARGS.length)); //static assert(ARGS.length != 0, "Error: no args"); static if(ARGS.length == 1) { static assert(TypeEquals!(typeof(args[0]), ReduceType)); return args[0]; } else static if(ARGS.length == 2) { static assert(TypeEquals!(typeof(args[0]), ReduceType)); static assert(TypeEquals!(typeof(args[1]), ReduceType)); return FN(args[0], args[1]); } else static if(ARGS.length >= 3) { ReduceType val1 = varargsReduce_Impl(args[0 .. ARGS.length/2]); ReduceType val2 = varargsReduce_Impl(args[ARGS.length/2 .. ARGS.length]); return FN(val1, val2); } else { static assert(false, "Error: no args"); } } } /***************** Usage ***************/ int sum(int a, int b) { return a + b; } char[] cat(char[] a, char[] b) { return a ~ b; } void main(char[][] args) { auto result = varargsReduce!(sum)(1, 3, 3, 7); writeln(result); auto result2 = varargsReduce!(cat)("H"[], "e"[], "l"[], "l"[], "o"[]); writeln(result2); } ----------------- itoa: toStrings an int -------------------- module meta.Util; template itoa(int i) { static if (i < 0) { static const char[] itoa = "-" ~ itoa!(-i); } else { static if (i / 10 > 0) { static const char[] itoa = itoa(i / 10) ~ "0123456789"[i % 10]; } else { static const char[] itoa = "0123456789"[i % 10 .. i % 10 + 1]; } } } -- Bruno Medeiros - MSc in CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D |
January 23, 2007 Re: challenge #2: implement the varargs_reduce metafunction | ||||
---|---|---|---|---|
| ||||
Posted in reply to Bruno Medeiros | > This one seems much more easy that the fist challenge, so I suspect I'm missing something. Your implementation doesn't work with template functions. Here's a rather straightforward implementation that seems to work: template varargs_reduce(alias reduce2) { private: template ReduceType(ARGS...) { static assert(ARGS.length >= 2, "requires >= 2 arguments"); static if(ARGS.length == 2) alias typeof(reduce2(ARGS[0], ARGS[1])) ReduceType; else static if(ARGS.length > 2) alias typeof(reduce2(ARGS[0], ReduceType!(ARGS[1..$]))) ReduceType; } public: // I'd have prefered a typeof(result) or typeof(return) as return type here. ReduceType!(ARGS) varargs_reduce(ARGS...)(ARGS args) { static assert(args.length >= 2, "requires >= 2 arguments"); static if(args.length == 2) auto result = reduce2(args[0], args[1]); else static if(args.length > 2) auto result = reduce2(args[0], varargs_reduce(args[1..$])); return result; } } typeof(T+Q) plus(T,Q)(T a, Q b) { return a + b; } void main() { alias varargs_reduce!(plus).varargs_reduce plus_va; plus_va(1, 2.1, 3i, 4u); } While it compiles and seems to behave correctly, I'm suspicious of my use of typeof in ReduceType - does the spec guarantee it does what I want? I tried using is and std.traits.ReturnType but typeof lead to the simplest solution. Cheers, Christian |
January 23, 2007 Re: challenge #2: implement the varargs_reduce metafunction | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu (See Website for Email) | Andrei Alexandrescu (See Website for Email) wrote:
> My previous post defines max by availing itself of a metafunction called
> varargs_reduce. Your challenge is to define it. varargs_reduce takes an
> alias which it assumes is a function of two arguments, and it defines a
> vararg function that applies that alias repeatedly, similarly to the
> reduce primitive that is present in functional languages. Again, for
> background on functional reduce, see e.g.:
>
> http://www.joelonsoftware.com/items/2006/08/01.html
>
> Define varargs_reduce to deduce the result type properly, and to generate code as efficient as possible.
>
>
> Andrei
While your at it. What about a multi-threaded version? ie Each function that is called is placed on one of 4 threads.
-Joel
|
January 23, 2007 Re: challenge #2: implement the varargs_reduce metafunction | ||||
---|---|---|---|---|
| ||||
Posted in reply to Bruno Medeiros | Bruno Medeiros wrote:
> This one seems much more easy that the fist challenge, so I suspect I'm missing something.
I suspect the same since I have just a few lines. This is what I came up with, does it meet the requirements? There must be something wrong.
template reduce(alias fn)
{
typeof(T[0]) reduce(T...)(T args)
{
static assert( is(T[0] == T[1]) &&
is( T[0] == typeof( fn(T[0], T[1]) ) ),
"try again" );
static assert( args.length > 1, "nothing to reduce here");
auto result = args[0];
foreach(arg; args[1..$])
result = fn(result, arg);
return result;
}
}
example:
alias reduce!(function(int a, int b) { return (a > b) ? a : b; }) max;
assert( max(2,55,787) == 787 );
|
January 23, 2007 Re: challenge #2: implement the varargs_reduce metafunction | ||||
---|---|---|---|---|
| ||||
Posted in reply to Lutger | Lutger wrote:
> Bruno Medeiros wrote:
>> This one seems much more easy that the fist challenge, so I suspect I'm missing something.
>
> I suspect the same since I have just a few lines. This is what I came up with, does it meet the requirements? There must be something wrong.
>
> template reduce(alias fn)
> {
> typeof(T[0]) reduce(T...)(T args)
> {
> static assert( is(T[0] == T[1]) &&
> is( T[0] == typeof( fn(T[0], T[1]) ) ),
> "try again" );
> static assert( args.length > 1, "nothing to reduce here");
>
> auto result = args[0];
> foreach(arg; args[1..$])
> result = fn(result, arg);
> return result;
> }
> }
>
> example:
>
> alias reduce!(function(int a, int b) { return (a > b) ? a : b; }) max;
> assert( max(2,55,787) == 787 );
What about maxtype support?
|
January 23, 2007 Re: challenge #2: implement the varargs_reduce metafunction | ||||
---|---|---|---|---|
| ||||
Posted in reply to janderson | janderson wrote:
> Andrei Alexandrescu (See Website for Email) wrote:
>> My previous post defines max by availing itself of a metafunction called
>> varargs_reduce. Your challenge is to define it. varargs_reduce takes an
>> alias which it assumes is a function of two arguments, and it defines a
>> vararg function that applies that alias repeatedly, similarly to the
>> reduce primitive that is present in functional languages. Again, for
>> background on functional reduce, see e.g.:
>>
>> http://www.joelonsoftware.com/items/2006/08/01.html
>>
>> Define varargs_reduce to deduce the result type properly, and to generate code as efficient as possible.
>>
>>
>> Andrei
>
>
> While your at it. What about a multi-threaded version? ie Each function that is called is placed on one of 4 threads.
That's a good point, and goes right to the core of my solution, which (similarly to Bruno Medeiros') arranges operations in an optimal way for superscalar evaluation, e.g. max(a, b, c, d) is expanded not to:
max2(max2(max2(a, b), c), d)
but instead to:
max2(max2(a, b), max2(c, d))
The number of operations is the same but in the latter case there is logaritmically less dependency between partial results. When max2 expands into a primitive comparison, the code is easy prey for a superscalar machine to execute in parallel.
This won't count in a great deal of real code, but the fact that this will go in the standard library warrants the thought. Besides, the fact that the language makes it so easy, we can actually think of such subtlety, is very encouraging.
Andrei
|
January 23, 2007 Re: challenge #2: implement the varargs_reduce metafunction | ||||
---|---|---|---|---|
| ||||
Posted in reply to Bruno Medeiros | Bruno Medeiros wrote: > Andrei Alexandrescu (See Website for Email) wrote: >> My previous post defines max by availing itself of a metafunction called >> varargs_reduce. Your challenge is to define it. varargs_reduce takes an >> alias which it assumes is a function of two arguments, and it defines a >> vararg function that applies that alias repeatedly, similarly to the >> reduce primitive that is present in functional languages. Again, for >> background on functional reduce, see e.g.: >> >> http://www.joelonsoftware.com/items/2006/08/01.html >> >> Define varargs_reduce to deduce the result type properly, and to generate code as efficient as possible. >> >> >> Andrei > > Here is my try. I assume the reduce type must be exactly the same in all arguments. Should that not be the case? That is not the case, and is actually an important point in implementing varargs_reduce. > As for efficiency, I'm not sure what the requirements are. Is there to be any parallelization/vectorization considerations? This one, instead of linear iteration, uses binary recursion to calculate the result, but for *no particular reason* since its not actually any faster than linear recursion. It could well be faster. The dependency chain in your expansion has logarithmic depth; in linear expansion it has linear depth. Superscalar machines have the ability to execute independent operations literally in parallel (they have multiple ALUs). > This one seems much more easy that the fist challenge, so I suspect I'm missing something. As Christian Kamm mentioned, your solution does not work with templates, and min2 actually is one. Andrei |
January 23, 2007 Re: challenge #2: implement the varargs_reduce metafunction | ||||
---|---|---|---|---|
| ||||
Posted in reply to Christian Kamm | Christian Kamm wrote:
>> This one seems much more easy that the fist challenge, so I suspect I'm missing something.
>
> Your implementation doesn't work with template functions. Here's a rather straightforward implementation that seems to work:
>
> template varargs_reduce(alias reduce2)
> {
> private:
> template ReduceType(ARGS...)
> {
> static assert(ARGS.length >= 2, "requires >= 2 arguments");
>
> static if(ARGS.length == 2)
> alias typeof(reduce2(ARGS[0], ARGS[1])) ReduceType;
> else static if(ARGS.length > 2)
> alias typeof(reduce2(ARGS[0], ReduceType!(ARGS[1..$]))) ReduceType;
> }
> public:
> // I'd have prefered a typeof(result) or typeof(return) as return type here.
> ReduceType!(ARGS) varargs_reduce(ARGS...)(ARGS args)
> {
> static assert(args.length >= 2, "requires >= 2 arguments");
> static if(args.length == 2)
> auto result = reduce2(args[0], args[1]);
> else static if(args.length > 2)
> auto result = reduce2(args[0], varargs_reduce(args[1..$]));
> return result;
> }
> }
>
> typeof(T+Q) plus(T,Q)(T a, Q b)
> {
> return a + b;
> }
>
> void main()
> {
> alias varargs_reduce!(plus).varargs_reduce plus_va;
> plus_va(1, 2.1, 3i, 4u);
> }
>
> While it compiles and seems to behave correctly, I'm suspicious of my use of typeof in ReduceType - does the spec guarantee it does what I want? I tried using is and std.traits.ReturnType but typeof lead to the simplest solution.
This is a good solution. Ideally, you would combine it with Bruno Medeiros' idea to expand the template in a binary manner so as to spread dependencies.
One subtle point is that you don't want to use auto result = ...; We have not yet defined the semantics of transporting storage class entirely. It is possible that for backward compatibility reasons, auto will eliminate the 'inout' storage class that max2 so laboriously transported out. If that happens, your code will not compile. So the best bet is to simply return the reduce2 expression directly.
(Now I guess it's self-evident why I said earlier that D's handling of storage classes is a source of radioactive waste in the type system. It insidiously hits everywhere and when least expected.)
Great work, thanks!
Andrei
|
January 23, 2007 Re: challenge #2: implement the varargs_reduce metafunction | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu (See Website for Email) | == Quote from Andrei Alexandrescu (See Website for Email) (SeeWebsiteForEmail@erdani.org)'s article > My previous post defines max by availing itself of a metafunction called varargs_reduce. Your challenge is to define it. varargs_reduce takes an alias which it assumes is a function of two arguments, and it defines a vararg function that applies that alias repeatedly, similarly to the reduce primitive that is present in functional languages. Again, for background on functional reduce, see e.g.: > > http://www.joelonsoftware.com/items/2006/08/01.html > > Define varargs_reduce to deduce the result type properly, and to generate code as efficient as possible. > > Andrei There is a really simple solution, but I'm not sure if it does the right thing with respect to your wording above. What exactly is meant by deducing the result type properly? Specifically, if the input types are different kinds of objects, is the result expected to have the same type as a linear sequence of operations? 1. Can we assume the type conversions are non-cyclic? 2. Should we assume that the delegate looks like: T dg(T, T), or like: T dg(U, V) 3. If the signature is T dg(U, V), can we assume that type conversions are non-cyclic? Cyclic types: (requires more template logic than actually shown here) Rock add(Paper x, Scissors y); Paper add(Scissors x, Rock x); Scissors add(Rock x, Paper y); If this kind of stuff is permitted, the solution is possible but a lot messier. // Simple solution: import std.stdio; import std.traits; template reduce(D, E...) { ReturnType!(D) reduce(D dg, E v) { ReturnType!(D) rv; static if (E.length >= 1) { rv = v[0]; foreach(i, a; v[1..$]) { rv = dg(rv, a); } } return rv; } } int main(char[][] args) { int add(int a, int b) { return a + b; } double mul(double a, double b) { return a * b; } int x = reduce(& add, 101, 102, 103, 104); double y = reduce(& mul, .1, .2, .3, .4, .5); writefln("sum=%s prod=%s", x, y); return 0; } |
Copyright © 1999-2021 by the D Language Foundation