www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - RFC: StaticFilter, PApply, Compose, template predicates

reply David Nadlinger <see klickverbot.at> writes:
As we currently aren't reviewing anything (We still need a review 
manager for David's RegionAllocator or whatever we decide to receive 
next? Do you want to get things going Jonathan? Should I do it again? 
Anybody else?), I thought I would take the opportunity to ask for 
comments on a few little template metaprogramming helpers:

https://gist.github.com/1191885

Besides a few helpers for manipulating/combining template predicates, 
the above link contains three main:

StaticFilter – like std.algorithm.filter, but for type tuples using 
template predicates.
PApply – like the unluckily named std.functional.curry, but for template 
parameters
Compose - alias Compose!(A, B, C) Comp; // Comp!D is now A!(B!(C!D)).

I had originally whipped these up on the fly while working on some 
metaprogramming-heavy code, but they have proven useful in other 
projects as well. What do you think? Would some of these be worthy 
additions to Phobos? Do you have similar stuff lying around in your own 
code?

Thanks,
David
Sep 03 2011
next sibling parent reply David Nadlinger <see klickverbot.at> writes:
I should also note that I ripped these out of an existing code base 
without thinking too much, feel free to ping me about any stupid 
documentation, etc. oversights.

David


On 9/4/11 2:46 AM, David Nadlinger wrote:
 As we currently aren't reviewing anything (We still need a review
 manager for David's RegionAllocator or whatever we decide to receive
 next? Do you want to get things going Jonathan? Should I do it again?
 Anybody else?), I thought I would take the opportunity to ask for
 comments on a few little template metaprogramming helpers:

 https://gist.github.com/1191885

 Besides a few helpers for manipulating/combining template predicates,
 the above link contains three main:

 StaticFilter – like std.algorithm.filter, but for type tuples using
 template predicates.
 PApply – like the unluckily named std.functional.curry, but for template
 parameters
 Compose - alias Compose!(A, B, C) Comp; // Comp!D is now A!(B!(C!D)).

 I had originally whipped these up on the fly while working on some
 metaprogramming-heavy code, but they have proven useful in other
 projects as well. What do you think? Would some of these be worthy
 additions to Phobos? Do you have similar stuff lying around in your own
 code?

 Thanks,
 David

Sep 03 2011
next sibling parent reply David Nadlinger <see klickverbot.at> writes:
On 9/4/11 2:57 AM, Andrej Mitrovic wrote:
 I think `not` is already in std.functional, the others look very
 interesting though!

std.functional.not negates a function, my Not negates a template predicate. Should probably make that clearer, though… David
Sep 03 2011
parent David Nadlinger <see klickverbot.at> writes:
On 9/4/11 3:04 AM, Andrej Mitrovic wrote:
 Ooh ok. But how is it different from just using a bang? An example
 would be nice there.

Imagine you have a template predicate »hasType«, which checks if the passed expression has a type: --- template hasType(T...) if (T.length == 1) { enum hasType = is(typeof(T[0])); } --- Now, you want to get the elements from a type tuple that don't have a type (e.g. types themselves, and this is one of the situations that show how confusing the name »type tuple« really is). But you can't just do »StaticFilter!(!hasType, Tuple)«, because you can't just »negate a template« like this. In this situation, Not makes sense: »StaticFilter(Not!hasType, Tuple)«. If D supported something like template literals, Not wouldn't be needed, but as we don't have them, I know no other (easy) way of achieving the same. By the way, Not could also be implemented as: --- template not(T...) if (T.length == 1 && is(typeof(!T[0]) : bool)) { enum bool not = !T[0]; } alias PApply!(Compose, not) Not; --- I felt this would be somewhat over the top though… ;) David
Sep 03 2011
prev sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
Ooh ok. But how is it different from just using a bang? An example
would be nice there.
Sep 03 2011
prev sibling next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
I think `not` is already in std.functional, the others look very
interesting though!
Sep 03 2011
prev sibling next sibling parent reply "Simen Kjaeraas" <simen.kjaras gmail.com> writes:
On Sun, 04 Sep 2011 02:46:47 +0200, David Nadlinger <see klickverbot.at>=
  =

wrote:

 As we currently aren't reviewing anything (We still need a review  =

 manager for David's RegionAllocator or whatever we decide to receive  =

 next? Do you want to get things going Jonathan? Should I do it again? =

 Anybody else?), I thought I would take the opportunity to ask for  =

 comments on a few little template metaprogramming helpers:

 https://gist.github.com/1191885

 Besides a few helpers for manipulating/combining template predicates, =

 the above link contains three main:

 StaticFilter =E2=80=93 like std.algorithm.filter, but for type tuples =

 template predicates.
 PApply =E2=80=93 like the unluckily named std.functional.curry, but fo=

 parameters
 Compose - alias Compose!(A, B, C) Comp; // Comp!D is now A!(B!(C!D)).

 I had originally whipped these up on the fly while working on some  =

 metaprogramming-heavy code, but they have proven useful in other  =

 projects as well. What do you think? Would some of these be worthy  =

 additions to Phobos? Do you have similar stuff lying around in your ow=

 code?

StaticFilter definitely should be in Phobos. StaticReduce too, but you don't seem to have it on your list. I also often use StaticIota. For more handy templates I feel should be in Phobos, see Philippe Sigaud's dranges: http://www.dsource.org/projects/dranges -- = Simen
Sep 04 2011
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
I am back.

Simen Kjaeraas:

 I also often use StaticIota.

I suggest to not add StaticIota, and improve foreach instead: http://d.puremagic.com/issues/show_bug.cgi?id=4085 Bye, bearophile
Sep 04 2011
prev sibling next sibling parent David Nadlinger <see klickverbot.at> writes:
On 9/5/11 1:05 AM, Simen Kjaeraas wrote:
 StaticFilter definitely should be in Phobos. StaticReduce too, but you
 don't seem to have it on your list. I also often use StaticIota.

I have a StaticReduce lying around as well, but didn't include it in the snippet as I have used it exactly once so far, and wanted to keep the list short. It should probably be in Phobos though, even if only to compliment staticMap (the name of which really should be capitalized, I think); I'll add it to the Gist.
 For more handy templates I feel should be in Phobos, see
 Philippe Sigaud's dranges:

 http://www.dsource.org/projects/dranges

Wow, thanks for the tip, I vaguely remembered it being talked about here, but didn't know it includes so many metaprogramming goodies. From quickly skimming the code in templates.d, it seems like some of the templates unnecessarily rely on string mixins though, which considerably reduces their value. For example, Philippe's take on »Compose« will only work if the templates in question are from drange.template as well (resp. from modules imported by it), similar to the restrictions for std.functional string lambdas. David
Sep 04 2011
prev sibling parent dsimcha <dsimcha yahoo.com> writes:
== Quote from Simen Kjaeraas (simen.kjaras gmail.com)'s article
 StaticFilter definitely should be in Phobos. StaticReduce too, but you
 don't seem to have it on your list. I also often use StaticIota.
 For more handy templates I feel should be in Phobos, see
 Philippe Sigaud's dranges:
 http://www.dsource.org/projects/dranges
 -- =
    Simen

Seconded. StaticIota is extremely useful for loop unrolling optimizations, e.g.: T sum(T)(T[] nums) { enum nILP = 6; auto ilpTuple = StaticIota!nILP; T[nILP] ret = 0; for(size_t i = 0; i + nILP < nums.length; i += nILP) { foreach(j; ilpTuple) { // Static, automatically unrolled. ret[j] += nums[i + j]; } } foreach(i; nums.length / nILP * nILP..nums.length) { ret[0] += nums[i]; } foreach(i; 1..nILP) { ret[0] += ret[i]; } return ret[0]; }
Sep 04 2011
prev sibling next sibling parent reply kenji hara <k.hara.pg gmail.com> writes:
Shin Fujishiro's std.meta has the features.

https://github.com/sinfu/phobos-sandbox

I think that module has been almost completed, but the contact with
him has been interrupted.
(I want to merge it, and it is licensed under the Boost License, but I
doubt I will do it without his reply.)

Kenji Hara

2011/9/4 David Nadlinger <see klickverbot.at>:
 As we currently aren't reviewing anything (We still need a review manager
 for David's RegionAllocator or whatever we decide to receive next? Do you
 want to get things going Jonathan? Should I do it again? Anybody else?), =

 thought I would take the opportunity to ask for comments on a few little
 template metaprogramming helpers:

 https://gist.github.com/1191885

 Besides a few helpers for manipulating/combining template predicates, the
 above link contains three main:

 StaticFilter =96 like std.algorithm.filter, but for type tuples using tem=

 predicates.
 PApply =96 like the unluckily named std.functional.curry, but for templat=

 parameters
 Compose - alias Compose!(A, B, C) Comp; // Comp!D is now A!(B!(C!D)).

 I had originally whipped these up on the fly while working on some
 metaprogramming-heavy code, but they have proven useful in other projects=

 well. What do you think? Would some of these be worthy additions to Phobo=

 Do you have similar stuff lying around in your own code?

 Thanks,
 David

Sep 04 2011
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 09/05/2011 02:14 AM, kenji hara wrote:
 Shin Fujishiro's std.meta has the features.

 https://github.com/sinfu/phobos-sandbox

 I think that module has been almost completed, but the contact with
 him has been interrupted.
 (I want to merge it, and it is licensed under the Boost License, but I
 doubt I will do it without his reply.)

 Kenji Hara

And this will have to be fixed: "All members in this module are defined in the $(D meta) namespace and cannot be used without the $(D meta) qualifier:" Users can do the renamed import themselves if they wish to, the module should not enforce it.
Sep 04 2011
prev sibling parent reply David Nadlinger <see klickverbot.at> writes:
On 9/5/11 2:14 AM, kenji hara wrote:
 Shin Fujishiro's std.meta has the features.

 https://github.com/sinfu/phobos-sandbox

Oh, wow, so now (largely) the same functionality has been implemented at least three times, in Shin Fujishiro's std.meta, in Philippe Sigaud's dranges, and by myself – I guess we should really do something about this to avoid reinventing the wheel over and over again. Luckily, all the code is Boost-licensed, so I think I will just throw the best ideas from each implementation into a big bowl (for example, I really like Shin's approach to emulating template literals with strings) and cook up a module fit for submission to the Phobos review process. Thus, it would be great if you could let me know what you would like to see as far as metaprogramming is concerned, besides common higher-order templates like Map/Reduce/Filter, general helpers like Compose/PApply/Switch/Iota and the low-level helpers for working around quirks in the language (think checking identity for arbitrary symbols/types/ct values, being able to alias both types and values, …). High on my list of not yet implemented ideas is wrapping __traits: templates obviously won't be able to handle some of the strange semantics e.g. of the isArithmetic family of traits, but the »raw« __traits interface suffers from impedance mismatch with higher-order templates. David
Sep 04 2011
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 09/05/2011 03:31 AM, David Nadlinger wrote:
 On 9/5/11 2:14 AM, kenji hara wrote:
 Shin Fujishiro's std.meta has the features.

 https://github.com/sinfu/phobos-sandbox

Oh, wow, so now (largely) the same functionality has been implemented at least three times, in Shin Fujishiro's std.meta, in Philippe Sigaud's dranges, and by myself – I guess we should really do something about this to avoid reinventing the wheel over and over again. Luckily, all the code is Boost-licensed, so I think I will just throw the best ideas from each implementation into a big bowl (for example, I really like Shin's approach to emulating template literals with strings) and cook up a module fit for submission to the Phobos review process. Thus, it would be great if you could let me know what you would like to see as far as metaprogramming is concerned, besides common higher-order templates like Map/Reduce/Filter, general helpers like Compose/PApply/Switch/Iota and the low-level helpers for working around quirks in the language (think checking identity for arbitrary symbols/types/ct values, being able to alias both types and values, …).

Is that the correct level for addressing quirks in the language?
 High on my list of not yet implemented ideas is wrapping __traits:
 templates obviously won't be able to handle some of the strange
 semantics e.g. of the isArithmetic family of traits, but the »raw«
 __traits interface suffers from impedance mismatch with higher-order
 templates.

 David

Sep 04 2011
prev sibling parent reply "Robert Jacques" <sandford jhu.edu> writes:
On Sun, 04 Sep 2011 19:46:45 -0400, dsimcha <dsimcha yahoo.com> wrote:

 == Quote from Simen Kjaeraas (simen.kjaras gmail.com)'s article
 StaticFilter definitely should be in Phobos. StaticReduce too, but you
 don't seem to have it on your list. I also often use StaticIota.
 For more handy templates I feel should be in Phobos, see
 Philippe Sigaud's dranges:
 http://www.dsource.org/projects/dranges
 -- =
    Simen

Seconded. StaticIota is extremely useful for loop unrolling optimizations, e.g.:

vote++
Sep 04 2011
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Robert Jacques:

 Seconded.  StaticIota is extremely useful for loop unrolling optimizations,
e.g.:

vote++

vote-- StaticIota is not the good solution. I have explained why elsewhere: http://d.puremagic.com/issues/show_bug.cgi?id=4085 Bye, bearophile
Sep 05 2011
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 09/05/2011 07:31 PM, Simen Kjaeraas wrote:
 On Mon, 05 Sep 2011 13:05:23 +0200, bearophile
 <bearophileHUGS lycos.com> wrote:

 Robert Jacques:

 Seconded. StaticIota is extremely useful for loop unrolling

vote++

vote-- StaticIota is not the good solution. I have explained why elsewhere: http://d.puremagic.com/issues/show_bug.cgi?id=4085

Certainly we could sit in a corner and pray to almighty Walter that this be implemented, when he's done with the things he wants to do with D. Oooor - we could add StaticIota to Phobos, bypass the problem, and live happily ever after. Yes, static foreach would be nice, but the means to do what it would do, are easily implemented in the language as is.

That is some heavy C++ design style reasoning.
Sep 05 2011
prev sibling next sibling parent kennytm <kennytm gmail.com> writes:
bearophile <bearophileHUGS lycos.com> wrote:
 Robert Jacques:
 
 Seconded.  StaticIota is extremely useful for loop unrolling optimizations,
e.g.:

vote++

vote-- StaticIota is not the good solution. I have explained why elsewhere: http://d.puremagic.com/issues/show_bug.cgi?id=4085 Bye, bearophile

vote += 2; Who said staticIota is only used in static foreach? What if I want to supply staticMap!(staticToString, staticIota!('a', 'z'+1)) as the default argument of parameter names for 'naryFun'?
Sep 05 2011
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 09/05/2011 08:19 PM, kenji hara wrote:
 2011/9/6 Simen Kjaeraas<simen.kjaras gmail.com>:
 On Mon, 05 Sep 2011 13:05:23 +0200, bearophile<bearophileHUGS lycos.com>
 wrote:

 Robert Jacques:

 Seconded.  StaticIota is extremely useful for loop unrolling
 optimizations, e.g.:

vote++

vote-- StaticIota is not the good solution. I have explained why elsewhere: http://d.puremagic.com/issues/show_bug.cgi?id=4085

Certainly we could sit in a corner and pray to almighty Walter that this be implemented, when he's done with the things he wants to do with D. Oooor - we could add StaticIota to Phobos, bypass the problem, and live happily ever after. Yes, static foreach would be nice, but the means to do what it would do, are easily implemented in the language as is.

Agreed to Simen. The foreach statement already has loop unrolling feature. To use it, we can pass a compile-time sequence (like TypeTuple) as its aggregator. I think it is clear language design, and not need more. Then we need staticIota.

static foreach is part of the design. The only reason it is not in the compiler (and we have the kludgy foreach that works on tuples) is because Walter experienced implementation difficulties. How would you generate a number of declarations with the current foreach and StaticIota?
Sep 05 2011
parent reply zeljkog <zeljkog private.com> writes:
On 05.09.2011 21:55, Timon Gehr wrote:
 static foreach is part of the design. The only reason it is not in the
compiler (and we have the kludgy foreach that works on tuples) is because
Walter experienced implementation difficulties.

Before implementation somebody must precisely define static foreach, better to say static looping construct.
Sep 05 2011
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 09/05/2011 10:43 PM, zeljkog wrote:
 On 05.09.2011 21:55, Timon Gehr wrote:
 static foreach is part of the design. The only reason it is not in the
 compiler (and we have the kludgy foreach that works on tuples) is
 because Walter experienced implementation difficulties.

Before implementation somebody must precisely define static foreach, better to say static looping construct.

It works just like foreach, except that it does not introduce a new scope and can be used at module and aggregate scope. Eg: static foreach(x;0..5) { mixin("T!x var"~to!string(x)~";"); } is equivalent to T!0 var0; T!1 var1; T!2 var2; T!3 var3; T!4 var4; The aggregate to loop over is evaluated at compile time: int[] getAggregate(){return [1,2,3,];} static foreach(x;getAggregate()) { pragma(msg,x); } writes during compilation: 1 2 3
Sep 05 2011
parent reply zeljkog <zeljkog private.com> writes:
On 05.09.2011 23:06, Timon Gehr wrote:
 The aggregate to loop over is evaluated at compile time:

 int[] getAggregate(){return [1,2,3,];}
 static foreach(x;getAggregate()) {
 pragma(msg,x);
 }

Eh :) For me the only compile time agregate is tuple. We should talk about basic looping construct for compile time evolution.
Sep 05 2011
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 09/06/2011 12:36 AM, zeljkog wrote:
 On 05.09.2011 23:06, Timon Gehr wrote:
 The aggregate to loop over is evaluated at compile time:

 int[] getAggregate(){return [1,2,3,];}
 static foreach(x;getAggregate()) {
 pragma(msg,x);
 }

Eh :) For me the only compile time agregate is tuple.

foreach already works with any aggregate at compile time. int[] getAggregate(){return [1,2,3,];} mixin({ string r; foreach(x;getAggregate()) r~="pragma(msg,"~to!string(x)~");"; return r; }()); What is your point?
 We should talk about basic looping construct for compile time evolution.

In CTFE you can use any looping construct you like.
Sep 05 2011
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/5/11 13:31 EDT, Simen Kjaeraas wrote:
 On Mon, 05 Sep 2011 13:05:23 +0200, bearophile
 <bearophileHUGS lycos.com> wrote:

 Robert Jacques:

 Seconded. StaticIota is extremely useful for loop unrolling

vote++

vote-- StaticIota is not the good solution. I have explained why elsewhere: http://d.puremagic.com/issues/show_bug.cgi?id=4085

Certainly we could sit in a corner and pray to almighty Walter that this be implemented, when he's done with the things he wants to do with D. Oooor - we could add StaticIota to Phobos, bypass the problem, and live happily ever after. Yes, static foreach would be nice, but the means to do what it would do, are easily implemented in the language as is.

The problem is that StaticIota is not a replacement for static foreach due to scoping issues. We need a form of iteration that, just like static if, plants symbols in the current scope, not in a new scope. StaticIota is unable to help with that. Andrei
Sep 05 2011
parent bearophile <bearophileHUGS lycos.com> writes:
Andrei Alexandrescu:

 We need a form of iteration that, just like 
 static if, plants symbols in the current scope, not in a new scope. 
 StaticIota is unable to help with that.

A good static foreach works outside any functions too (as static if), at global scope. Bye, bearophile
Sep 05 2011
prev sibling next sibling parent reply "Simen Kjaeraas" <simen.kjaras gmail.com> writes:
On Mon, 05 Sep 2011 13:05:23 +0200, bearophile <bearophileHUGS lycos.com>  
wrote:

 Robert Jacques:

 Seconded.  StaticIota is extremely useful for loop unrolling  

vote++

vote-- StaticIota is not the good solution. I have explained why elsewhere: http://d.puremagic.com/issues/show_bug.cgi?id=4085

Certainly we could sit in a corner and pray to almighty Walter that this be implemented, when he's done with the things he wants to do with D. Oooor - we could add StaticIota to Phobos, bypass the problem, and live happily ever after. Yes, static foreach would be nice, but the means to do what it would do, are easily implemented in the language as is. -- Simen
Sep 05 2011
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Simen Kjaeraas:

 Yes, static foreach would be nice, but the means to do what it would do,  
 are easily implemented in the language as is.

Notes: - I am not asking for a real static foreach. The main point of bug 4085 is that that even half static foreach is better than the current situation. - "static foreach" is also a way to better document what the code is doing. I sometimes add /*static*/ before foreach to increase readability. - Some purposes/use cases of static foreach are not covered by a staticIota. Bye, bearophile
Sep 05 2011
prev sibling parent bearophile <bearophileHUGS lycos.com> writes:
Simen Kjaeraas:

 Certainly we could sit in a corner and pray to almighty Walter that this be
 implemented,

Walter did find problems in trying to implement a *full* static foreach. Walter is intelligent, quite experienced, and knows the DMD codebase well, but he's just one person. So maybe if he explains here what those problems were, someone else will find a partial solution... Bye, bearophile
Sep 05 2011
prev sibling next sibling parent kenji hara <k.hara.pg gmail.com> writes:
2011/9/6 Simen Kjaeraas <simen.kjaras gmail.com>:
 On Mon, 05 Sep 2011 13:05:23 +0200, bearophile <bearophileHUGS lycos.com>
 wrote:

 Robert Jacques:

 Seconded. =A0StaticIota is extremely useful for loop unrolling
 optimizations, e.g.:

vote++

vote-- StaticIota is not the good solution. I have explained why elsewhere: http://d.puremagic.com/issues/show_bug.cgi?id=3D4085

Certainly we could sit in a corner and pray to almighty Walter that this =

 implemented, when he's done with the things he wants to do with D. Oooor =

 we
 could add StaticIota to Phobos, bypass the problem, and live happily ever
 after.

 Yes, static foreach would be nice, but the means to do what it would do, =

 easily implemented in the language as is.

Agreed to Simen. The foreach statement already has loop unrolling feature. To use it, we can pass a compile-time sequence (like TypeTuple) as its aggregator. I think it is clear language design, and not need more. Then we need static= Iota. Kenji Hara
Sep 05 2011
prev sibling parent "Simen Kjaeraas" <simen.kjaras gmail.com> writes:
On Mon, 05 Sep 2011 19:49:43 +0200, Timon Gehr <timon.gehr gmx.ch> wrote:

 On 09/05/2011 07:31 PM, Simen Kjaeraas wrote:
 On Mon, 05 Sep 2011 13:05:23 +0200, bearophile
 <bearophileHUGS lycos.com> wrote:

 Robert Jacques:

 Seconded. StaticIota is extremely useful for loop unrolling

vote++

vote-- StaticIota is not the good solution. I have explained why elsewhere: http://d.puremagic.com/issues/show_bug.cgi?id=4085

Certainly we could sit in a corner and pray to almighty Walter that this be implemented, when he's done with the things he wants to do with D. Oooor - we could add StaticIota to Phobos, bypass the problem, and live happily ever after. Yes, static foreach would be nice, but the means to do what it would do, are easily implemented in the language as is.

That is some heavy C++ design style reasoning.

I disagree. I would heartily welcome static foreach, I'm only saying that rather than wait for the perfect solution (which might never appear) we should work with what we have. -- Simen
Sep 05 2011