View mode: basic / threaded / horizontal-split · Log in · Help
January 23, 2007
Re: challenge #2: implement the varargs_reduce metafunction
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
January 23, 2007
Re: challenge #2: implement the varargs_reduce metafunction
Kevin Bealer wrote:
> == 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.

Interesting point. I think varargs_reduce can safely assume that linear 
reduction always works f(f(f(f(...f(a1, a2), a3), a4), ...). My solution 
optimizes more aggressively by assuming that reduction can be performed 
in any order.

Your solution is less optimal because it uses a delegate. Ideally you 
just use an alias and deduce the result type by simply using the alias.


Andrei
January 23, 2007
Re: challenge #2: implement the varargs_reduce metafunction
Frits van Bommel wrote:
> 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; }

I think this ia a good point. Probably varargs_reduce must be linear to 
make the most conservative assumptions. There is always the chance of 
defining varargs_reduce_parallel. Thanks!


Andrei
January 23, 2007
Re: challenge #2: implement the varargs_reduce metafunction
janderson wrote:
> What about maxtype support?

I see, it doesn't do that, not good. In fact it demands all arguments 
and return value to be of the same type.
January 23, 2007
Re: challenge #2: implement the varargs_reduce metafunction
Andrei Alexandrescu (See Website For Email) wrote:
> Frits van Bommel wrote:
>> 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; }
> 
> I think this ia a good point. Probably varargs_reduce must be linear to 
> make the most conservative assumptions. There is always the chance of 
> defining varargs_reduce_parallel. Thanks!
> 
> 
> Andrei

I think that would be best (having a semi-seperate _parellel version).  I also wonder 
about applying this same "feature" to functions of 3 or 4 arguments (or even arbitrary! so 
long as none are themselves variadic), but that could come later.

-- Chris Nicholson-Sauls
January 24, 2007
Re: challenge #2: implement the varargs_reduce metafunction
"Andrei Alexandrescu (See Website for Email)" 
<SeeWebsiteForEmail@erdani.org> wrote in message 
news:ep4i7p$2n1t$4@digitaldaemon.com...
> 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

This post is not meant to be inflammatory.

Answer me this: are you just toying with us, tempting us with things which 
are unimplementable without new features which are secretly being developed 
for D?  Or are you just surreptitiously trying to get the community to write 
a bunch of standard library metacode for you?  ;)

How about this: start a thread in which you disclose all the fancy features 
you (you plural, you and Walter, since you now seem to be the _team_ 
designing D) have been planning.

For that matter, is coming up with crazy new features like inout returns and 
opImplicitCast _all_ Walter's doing?  Or is he fixing bugs?
January 24, 2007
Re: challenge #2: implement the varargs_reduce metafunction
Jarrett Billingsley wrote:
> "Andrei Alexandrescu (See Website for Email)" 
> <SeeWebsiteForEmail@erdani.org> wrote in message 
> news:ep4i7p$2n1t$4@digitaldaemon.com...
>> 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
> 
> This post is not meant to be inflammatory.

Definitely not taken as such.

> Answer me this: are you just toying with us, tempting us with things which 
> are unimplementable without new features which are secretly being developed 
> for D?  Or are you just surreptitiously trying to get the community to write 
> a bunch of standard library metacode for you?  ;)

It's really easy. I can't right now disclose all of my agenda for 
objective reasons (I will do it later), but the gist of the matter is 
simple:

1. There are some simple tests for a language gaging very precisely the 
power of that language

2. I want D to pass those tests

3. I want to increase community's awareness of the importance of those 
tests for larger use cases, as well as gather ideas from the community 
about how to overcome D's shortcomings in passing the tests.

> How about this: start a thread in which you disclose all the fancy features 
> you (you plural, you and Walter, since you now seem to be the _team_ 
> designing D) have been planning.

We are doing it already, e.g. by describing my suggested max 
implementation. But I don't want to do that preemptively, because I'd 
bias future responses. I wished, for example, that somebody could 
suggest a better design instead of "storageof(T) T".

> For that matter, is coming up with crazy new features like inout returns and 
> opImplicitCast _all_ Walter's doing?  Or is he fixing bugs? 

Walter and I have been discussing these issues and we have agreement on 
the necessity of certain features (of which indeed better inout handling 
and opImplicitCast are two). At this point, we don't have much more of a 
design than what I've already shown. For all I know, Walter hasn't 
started implementing any of them.


Andrei
January 24, 2007
Real World usage of D, Today (was Re: challenge #2: implement the varargs_reduce metafunction)
Andrei Alexandrescu (See Website For Email) wrote:
[snip]

> It's really easy. I can't right now disclose all of my agenda for 
> objective reasons (I will do it later), but the gist of the matter is 
> simple:
> 
> 1. There are some simple tests for a language gaging very precisely the 
> power of that language
> 
> 2. I want D to pass those tests
> 
> 3. I want to increase community's awareness of the importance of those 
> tests for larger use cases, as well as gather ideas from the community 
> about how to overcome D's shortcomings in passing the tests.

That's great, Andrei. And I, for one, truly want to see some of those 
changes happen (such as read-only arrays, covered by the const you talk of).

However, there are also some rather pressing matters of fixing stuff 
that is simply broken, and is hampering attempts to build real, live, 
useful apps at this time. Yeah, new features are sexy cool, and fixing 
long-standing issues ain't.

How about taking a long hard look at what sucks in D right now, and 
making those a primary priority? Having read many of your posts since 
yesterday, it seems you've identified a number of those. Great! Yet, you 
guys are apparently pressing ahead with wonderful new stuff instead? 
Like, for instance, an updated GC? When did that ever top the list of 
real-world issues for D?

To anticipate a question:

There's some serious issues with templates in libs (you really can't put 
them there successfully), some serious issues with debuggers not being 
able to locate source-files for templates; lots of problems related to 
real-world, end-user, /usability/ of the language on a daily basis.

I submit that such issues are just as important a test to pass than the 
ones you allude to. Dare I say, perhaps more so for people actually 
using the language right now?

Regards;

- Kris
January 24, 2007
Re: Real World usage of D, Today (was Re: challenge #2: implement the varargs_reduce metafunction)
kris wrote:
> Andrei Alexandrescu (See Website For Email) wrote:
> [snip]
> 
>> It's really easy. I can't right now disclose all of my agenda for 
>> objective reasons (I will do it later), but the gist of the matter is 
>> simple:
>>
>> 1. There are some simple tests for a language gaging very precisely 
>> the power of that language
>>
>> 2. I want D to pass those tests
>>
>> 3. I want to increase community's awareness of the importance of those 
>> tests for larger use cases, as well as gather ideas from the community 
>> about how to overcome D's shortcomings in passing the tests.
> 
> That's great, Andrei. And I, for one, truly want to see some of those 
> changes happen (such as read-only arrays, covered by the const you talk 
> of).
> 
> However, there are also some rather pressing matters of fixing stuff 
> that is simply broken, and is hampering attempts to build real, live, 
> useful apps at this time. Yeah, new features are sexy cool, and fixing 
> long-standing issues ain't.
> 
> How about taking a long hard look at what sucks in D right now, and 
> making those a primary priority? Having read many of your posts since 
> yesterday, it seems you've identified a number of those. Great! Yet, you 
> guys are apparently pressing ahead with wonderful new stuff instead? 
> Like, for instance, an updated GC? When did that ever top the list of 
> real-world issues for D?

I'm afraid I am not in the position to help here. All I'm really doin' 
is bitchin'. Walter does the actual work, and prioritizing and 
implementing is entirely his charter.

That being said, my view on what should be fixed in D is a bit 
different. For example, as I said, one of my main foci is putting a lead 
sarcophagus around "inout" before its radioactive waste affects too much 
code that will become broken later. Also, implicit conversion rules will 
change, and again I want to get that in ASAP so not too much code 
suffers. And so on.

> To anticipate a question:
> 
> There's some serious issues with templates in libs (you really can't put 
> them there successfully), some serious issues with debuggers not being 
> able to locate source-files for templates; lots of problems related to 
> real-world, end-user, /usability/ of the language on a daily basis.
> 
> I submit that such issues are just as important a test to pass than the 
> ones you allude to. Dare I say, perhaps more so for people actually 
> using the language right now?

I entirely agree. Figuring out priorities is Walter's call. Let's keep 
our fingers crossed :o).


Andrei
January 24, 2007
Re: Real World usage of D, Today (was Re: challenge #2: implement the varargs_reduce metafunction)
Andrei Alexandrescu (See Website For Email) wrote:
> kris wrote:
> 
>> Andrei Alexandrescu (See Website For Email) wrote:
>> [snip]
>>
>>> It's really easy. I can't right now disclose all of my agenda for 
>>> objective reasons (I will do it later), but the gist of the matter is 
>>> simple:
>>>
>>> 1. There are some simple tests for a language gaging very precisely 
>>> the power of that language
>>>
>>> 2. I want D to pass those tests
>>>
>>> 3. I want to increase community's awareness of the importance of 
>>> those tests for larger use cases, as well as gather ideas from the 
>>> community about how to overcome D's shortcomings in passing the tests.
>>
>>
>> That's great, Andrei. And I, for one, truly want to see some of those 
>> changes happen (such as read-only arrays, covered by the const you 
>> talk of).
>>
>> However, there are also some rather pressing matters of fixing stuff 
>> that is simply broken, and is hampering attempts to build real, live, 
>> useful apps at this time. Yeah, new features are sexy cool, and fixing 
>> long-standing issues ain't.
>>
>> How about taking a long hard look at what sucks in D right now, and 
>> making those a primary priority? Having read many of your posts since 
>> yesterday, it seems you've identified a number of those. Great! Yet, 
>> you guys are apparently pressing ahead with wonderful new stuff 
>> instead? Like, for instance, an updated GC? When did that ever top the 
>> list of real-world issues for D?
> 
> 
> I'm afraid I am not in the position to help here. All I'm really doin' 
> is bitchin'. 

Drat ... that's apparently all I'm achieving too :(


> Walter does the actual work, and prioritizing and 
> implementing is entirely his charter.
> 
> That being said, my view on what should be fixed in D is a bit 
> different. For example, as I said, one of my main foci is putting a lead 
> sarcophagus around "inout" before its radioactive waste affects too much 
> code that will become broken later. Also, implicit conversion rules will 
> change, and again I want to get that in ASAP so not too much code 
> suffers. And so on.

Aye, and that is certainly appreciated. Some of the items you've 
mentioned recently have long been festering sores for many. It'll 
certainly be refreshing to see some attention focused upon those.

Regarding implicit conversion rules -- are you including the "issues" 
currently surrounding signature-matching when using constants?

> 
>> To anticipate a question:
>>
>> There's some serious issues with templates in libs (you really can't 
>> put them there successfully), some serious issues with debuggers not 
>> being able to locate source-files for templates; lots of problems 
>> related to real-world, end-user, /usability/ of the language on a 
>> daily basis.
>>
>> I submit that such issues are just as important a test to pass than 
>> the ones you allude to. Dare I say, perhaps more so for people 
>> actually using the language right now?
> 
> 
> I entirely agree. Figuring out priorities is Walter's call. Let's keep 
> our fingers crossed :o).

Hehe; superstition :-p

Well, thanks for replying. The clarification is much appreciated, though 
I'm honestly sad to hear you're not more deeply involved.

Cheers;

- Kris
1 2 3 4 5 6
Top | Discussion index | About this forum | D home