challenge #2: implement the varargs_reduce metafunction

[Frits van Bommel]

Andrei Alexandrescu (See Website For Email) wrote:
> 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))

Assumes the operation is associative. That may not always be the case; 
it's not even necessarily true that the function takes arguments of 
identical types.

Silly example:
char[] accumulate(char[] arr, char element) { return arr ~= element; }


Of course, you could *require* that the operation is associative, but I 
didn't see that anywhere in the specification.
And as far as I can tell, that generally isn't assumed for reduce.
For instance in Lisp, REDUCE is either left-to-right or right-to-left 
(depending on a flag)[1].
In Python, it's always left-to-right[2].
(those were the ones I could most easily find with a quick Google search)


[1]: http://www.lisp.org/HyperSpec/Body/fun_reduce.html
[2]: http://docs.python.org/lib/built-in-funcs.html