Jump to page: 1 27  
Page
Thread overview
challenge #2: implement the varargs_reduce metafunction
Jan 23, 2007
Bruno Medeiros
Jan 23, 2007
Christian Kamm
Jan 23, 2007
Lutger
Jan 23, 2007
janderson
Jan 23, 2007
Lutger
Jan 23, 2007
janderson
Jan 23, 2007
Frits van Bommel
Jan 24, 2007
janderson
Jan 23, 2007
Kevin Bealer
Real World usage of D, Today (was Re: challenge #2: implement the varargs_reduce metafunction)
Jan 24, 2007
kris
Jan 24, 2007
kris
Jan 24, 2007
kris
Jan 25, 2007
Bill Baxter
Jan 25, 2007
Bill Baxter
Jan 25, 2007
John Reimer
Jan 26, 2007
Walter Bright
Jan 26, 2007
BCS
Jan 26, 2007
Walter Bright
Jan 27, 2007
James Dennett
Jan 27, 2007
Walter Bright
Jan 27, 2007
James Dennett
Issues with constants, and inout (was Real World usage of D, Today)
Jan 26, 2007
kris
Jan 27, 2007
kris
Jan 27, 2007
Frits van Bommel
Jan 27, 2007
kris
Jan 27, 2007
Bill Baxter
Jan 29, 2007
Oskar Linde
Jan 29, 2007
Frits van Bommel
Jan 27, 2007
Sean Kelly
Jan 26, 2007
Kevin Bealer
Jan 26, 2007
Frits van Bommel
Jan 26, 2007
Sean Kelly
Jan 27, 2007
Bill Baxter
Jan 27, 2007
Frits van Bommel
Jan 27, 2007
Bill Baxter
Jan 26, 2007
Sean Kelly
Jan 27, 2007
Kevin Bealer
Jan 27, 2007
Sean Kelly
Jan 24, 2007
Lionello Lunesu
Jan 24, 2007
kris
Jan 24, 2007
Sean Kelly
Jan 24, 2007
Lionello Lunesu
Jan 24, 2007
Sean Kelly
Jan 24, 2007
Thomas Kuehne
Jan 24, 2007
Sean Kelly
Jan 24, 2007
Thomas Kuehne
Jan 24, 2007
Thomas Kuehne
Jan 25, 2007
Sean Kelly
Jan 24, 2007
Thomas Kuehne
Jan 24, 2007
Frits van Bommel
January 23, 2007
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
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
> 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
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
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
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
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
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
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
== 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 6 7