View mode: basic / threaded / horizontal-split · Log in · Help
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
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
> 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
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
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
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
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
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
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
== 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;
}
« First   ‹ Prev
1 2 3 4 5
Top | Discussion index | About this forum | D home