www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - D2's std.algorithm

reply Bill Baxter <dnewsgroup billbaxter.com> writes:
   sort!("a > b")(array);


I just wanted to say that this is BRILLIANT!  Zero call overhead, zero 
syntax overhead, compile-time lambda functions!

All the algorithms should support this syntax so we can do sexy 
compile-time lambda one-liners like:

    find!("a.some_member > 10")(array);

or

    partition!("a.call_something() !is null")(array);

etc.

And probably those should allow a data arg passed as 'b' to the lambda 
function so you could do something like
    find!("a.some_member > b")(array, 10);

Or even use template varargs and number the args automatically to allow:

    find!("a.x > b && a.w < c")(array, 10, 20);

It would just sequentially name the arguments b,c,d,e... etc.


can be processed before mixing it in.
    find!("a.x > {1} && a.w < {2}")(array, 10, 20);

That would be excellent.  Take that boost::lambda!

--bb
Dec 10 2007
next sibling parent reply "Craig Black" <cblack ara.com> writes:
"Bill Baxter" <dnewsgroup billbaxter.com> wrote in message 
news:fjl4fo$8am$1 digitalmars.com...

   sort!("a > b")(array);


 I just wanted to say that this is BRILLIANT!  Zero call overhead, zero 
 syntax overhead, compile-time lambda functions!

 All the algorithms should support this syntax so we can do sexy 
 compile-time lambda one-liners like:

    find!("a.some_member > 10")(array);

 or

    partition!("a.call_something() !is null")(array);

 etc.

 And probably those should allow a data arg passed as 'b' to the lambda 
 function so you could do something like
    find!("a.some_member > b")(array, 10);

 Or even use template varargs and number the args automatically to allow:

    find!("a.x > b && a.w < c")(array, 10, 20);

 It would just sequentially name the arguments b,c,d,e... etc.


 can be processed before mixing it in.
    find!("a.x > {1} && a.w < {2}")(array, 10, 20);

 That would be excellent.  Take that boost::lambda!

 --bb


Yes very cool!  Would be even better if the parens could be removed. 
Ideally, the compiler would be able to do CTFE with some lambdas.

-Craig
Dec 11 2007
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Craig Black wrote:

 "Bill Baxter" <dnewsgroup billbaxter.com> wrote in message 
 news:fjl4fo$8am$1 digitalmars.com...

   sort!("a > b")(array);


 I just wanted to say that this is BRILLIANT!  Zero call overhead, zero 
 syntax overhead, compile-time lambda functions!

 All the algorithms should support this syntax so we can do sexy 
 compile-time lambda one-liners like:

    find!("a.some_member > 10")(array);

 or

    partition!("a.call_something() !is null")(array);

 etc.

 And probably those should allow a data arg passed as 'b' to the lambda 
 function so you could do something like
    find!("a.some_member > b")(array, 10);

 Or even use template varargs and number the args automatically to allow:

    find!("a.x > b && a.w < c")(array, 10, 20);

 It would just sequentially name the arguments b,c,d,e... etc.


 can be processed before mixing it in.
    find!("a.x > {1} && a.w < {2}")(array, 10, 20);

 That would be excellent.  Take that boost::lambda!

 --bb


 
 Yes very cool!  Would be even better if the parens could be removed. 
 Ideally, the compiler would be able to do CTFE with some lambdas.


There's that idea of creating "static" parameters from DCon07.

With that you should be able to stick the string in as a regular 
parameter.  But I don't actually find the template syntax too bad.  It's 
a good reminder that the argument must be a compile-time constant.

When/if we get static parameters it's going to be harder to tell from 
looking at code what's compile-time and what's not.  I anticipate 
wasting lots of time in this manner: "why did I/they write this function 
like this?  thats silly <rewrite rewrite> -- oh damn, I see why now. 


--bb
Dec 11 2007
next sibling parent reply "Craig Black" <cblack ara.com> writes:
"Bill Baxter" <dnewsgroup billbaxter.com> wrote in message 
news:fjmol3$1f71$1 digitalmars.com...

 Craig Black wrote:

 "Bill Baxter" <dnewsgroup billbaxter.com> wrote in message 
 news:fjl4fo$8am$1 digitalmars.com...

   sort!("a > b")(array);


 I just wanted to say that this is BRILLIANT!  Zero call overhead, zero 
 syntax overhead, compile-time lambda functions!

 All the algorithms should support this syntax so we can do sexy 
 compile-time lambda one-liners like:

    find!("a.some_member > 10")(array);

 or

    partition!("a.call_something() !is null")(array);

 etc.

 And probably those should allow a data arg passed as 'b' to the lambda 
 function so you could do something like
    find!("a.some_member > b")(array, 10);

 Or even use template varargs and number the args automatically to allow:

    find!("a.x > b && a.w < c")(array, 10, 20);

 It would just sequentially name the arguments b,c,d,e... etc.


 can be processed before mixing it in.
    find!("a.x > {1} && a.w < {2}")(array, 10, 20);

 That would be excellent.  Take that boost::lambda!

 --bb


 Yes very cool!  Would be even better if the parens could be removed. 
 Ideally, the compiler would be able to do CTFE with some lambdas.


 There's that idea of creating "static" parameters from DCon07.

 With that you should be able to stick the string in as a regular 
 parameter.  But I don't actually find the template syntax too bad.  It's a 
 good reminder that the argument must be a compile-time constant.

 When/if we get static parameters it's going to be harder to tell from 
 looking at code what's compile-time and what's not.  I anticipate wasting 
 lots of time in this manner: "why did I/they write this function like 
 this?  thats silly <rewrite rewrite> -- oh damn, I see why now. Argument 


 --bb


First I've heard about static parameters  Very good idea.

You may be right about all that, but I still prefer a syntax without double 
quotes.
Dec 12 2007
parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 12/12/07, Craig Black <cblack ara.com> wrote:

   sort!("a > b")(array);


 I still prefer a syntax without double quotes.


How about

    sort!(q{a > b})(array);

? D2 rocks!
Dec 12 2007
parent reply bearophile <bearophileHUGS lycos.com> writes:
Janice Caron:

 sort!(q{a > b})(array);


Please explain :-)

Bye,
bearophile
Dec 12 2007
next sibling parent "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"bearophile" <bearophileHUGS lycos.com> wrote in message 
news:fjpcqv$1uio$1 digitalmars.com...

 Janice Caron:

 sort!(q{a > b})(array);


 Please explain :-)

 Bye,
 bearophile


q{ ... } is a "token string".  Its contents are lexed and have to conform to 
D's lexicography, but it is then turned into a string literal.  It goes well 
with string mixins and the like.
Dec 12 2007
prev sibling parent "Janice Caron" <caron800 googlemail.com> writes:
On 12/12/07, bearophile <bearophileHUGS lycos.com> wrote:

 Janice Caron:

 sort!(q{a > b})(array);


 Please explain :-)


It's just another way of writing strings. You can write "..." or you
can write q{...}. It's slightly different - escape strings aren't
expanded, and the string contents have to be valid D, but it's still
just a string. The cool thing is that your text editor doesn't know
that, and so will still syntax-highlight the string contents!
Dec 12 2007
prev sibling parent Matti Niemenmaa <see_signature for.real.address> writes:
Bill Baxter wrote:

 When/if we get static parameters it's going to be harder to tell from
 looking at code what's compile-time and what's not.  I anticipate
 wasting lots of time in this manner: "why did I/they write this function
 like this?  thats silly <rewrite rewrite> -- oh damn, I see why now.



The way I figure they should be used only when overloading between "known at
compile time" and "not known at compile time". For instance, precompiling stuff
like formatting strings and regexps. If a parameter is only for compile time use
in that it doesn't compile with a non-const argument, it should be a template
parameter as currently.

But then, I think using CTFE for something that is used only at compile time is
completely wrong, so I might be alone with my opinions. :-)

-- 
E-mail address: matti.niemenmaa+news, domain is iki (DOT) fi
Dec 12 2007
prev sibling parent reply Sean Kelly <sean f4.ca> writes:
Bill Baxter wrote:

  >   sort!("a > b")(array);
 
 I just wanted to say that this is BRILLIANT!  Zero call overhead, zero 
 syntax overhead, compile-time lambda functions!
 
 All the algorithms should support this syntax so we can do sexy 
 compile-time lambda one-liners like:
 
    find!("a.some_member > 10")(array);
 
 or
 
    partition!("a.call_something() !is null")(array);
 
 etc.


This is a pretty neat trick that has the benefit of providing a succinct 
syntax that works for both runtime and for CTFE.  However, the overall 
utility of the approach seems less than is offered by more traditional 
means.  Complex comparisons could render the function call largely 
unreadable by requiring a multi-line string to be passed as a template 
argument, and there is also no means of supplying a comparator at 
run-time using this method.  For comparison, consider this find routine:

     template find( Elem, Pred = IsEqual!(Elem) )
     {
         size_t find( Elem[] buf, Elem pat, Pred pred = Pred.init )
         {
             for( size_t pos = 0; pos < buf.length; ++pos )
             {
                 if( pred( buf[pos], pat ) )
                     return pos;
             }
             return buf.length;
         }
     }

With this support comparator:

     struct IsEqual( T )
     {
         static bool opCall( T p1, T p2 )
         {
             static if( is( T == class ) || is( T == struct ) )
                 return (p1 == p2) != 0; // opEquals returns an int
             else
                 return p1 == p2;
         }
     }

Because the function used for comparison is static, this code complies 
and works perfectly with CTFE.  At the same time, the predicate may also 
be a more complex struct, anonymous delegate, function pointer, named 
delegate, and so on.  With this in mind, I would be inclined to do 
something like this to add string predicate support to existing routines:

     template find( char[] oper )
     {
         size_t find(Elem)( Elem[] buf, Elem pat )
         {
             return .find!(Elem, Encode!(Elem, oper))( buf, pat );
         }
     }

     struct Encode( T, char[] exp )
     {
         static bool opCall( T a, T b )
         {
             return mixin(exp);
         }
     }

Thus allowing:

     const posA = find( "abcdefg", 'c' );            // uses IsEqual
     const posB = find!("a == b")( "abcdefg", 'c' ); // uses Encode

     void main()
     {
         // uses anonymous delegate at run-time
         auto posC = find( "abcdefg",
                           'c',
                           (char a, char b){ return a == b; } );
     }

So I guess what I'm saying is that the string version is a cool idea to 
be used in addition to the classic approach, but I see little utility in 
having it replace the classic approach.  And it's easy enough to add the 
string encoding as a facade over existing functions that nearly anything 
that accepts a predicate can use the string approach for free.


Sean
Dec 18 2007
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Sean Kelly wrote:

 Bill Baxter wrote:

  >   sort!("a > b")(array);

 I just wanted to say that this is BRILLIANT!  Zero call overhead, zero 
 syntax overhead, compile-time lambda functions!

 All the algorithms should support this syntax so we can do sexy 
 compile-time lambda one-liners like:

    find!("a.some_member > 10")(array);

 or

    partition!("a.call_something() !is null")(array);

 etc.


 
 This is a pretty neat trick that has the benefit of providing a succinct 
 syntax that works for both runtime and for CTFE.  However, the overall 
 utility of the approach seems less than is offered by more traditional 
 means.  Complex comparisons could render the function call largely 
 unreadable by requiring a multi-line string to be passed as a template 
 argument, and there is also no means of supplying a comparator at 
 run-time using this method.  For comparison, consider this find routine:
 
     template find( Elem, Pred = IsEqual!(Elem) )
     {
         size_t find( Elem[] buf, Elem pat, Pred pred = Pred.init )
         {
             for( size_t pos = 0; pos < buf.length; ++pos )
             {
                 if( pred( buf[pos], pat ) )
                     return pos;
             }
             return buf.length;
         }
     }
 
 With this support comparator:
 
     struct IsEqual( T )
     {
         static bool opCall( T p1, T p2 )
         {
             static if( is( T == class ) || is( T == struct ) )
                 return (p1 == p2) != 0; // opEquals returns an int
             else
                 return p1 == p2;
         }
     }
 
 Because the function used for comparison is static, this code complies 
 and works perfectly with CTFE.  At the same time, the predicate may also 
 be a more complex struct, anonymous delegate, function pointer, named 
 delegate, and so on.  With this in mind, I would be inclined to do 
 something like this to add string predicate support to existing routines:
 
     template find( char[] oper )
     {
         size_t find(Elem)( Elem[] buf, Elem pat )
         {
             return .find!(Elem, Encode!(Elem, oper))( buf, pat );
         }
     }
 
     struct Encode( T, char[] exp )
     {
         static bool opCall( T a, T b )
         {
             return mixin(exp);
         }
     }
 
 Thus allowing:
 
     const posA = find( "abcdefg", 'c' );            // uses IsEqual
     const posB = find!("a == b")( "abcdefg", 'c' ); // uses Encode
 
     void main()
     {
         // uses anonymous delegate at run-time
         auto posC = find( "abcdefg",
                           'c',
                           (char a, char b){ return a == b; } );
     }
 
 So I guess what I'm saying is that the string version is a cool idea to 
 be used in addition to the classic approach, but I see little utility in 
 having it replace the classic approach.  And it's easy enough to add the 
 string encoding as a facade over existing functions that nearly anything 
 that accepts a predicate can use the string approach for free.


D2 std.algorithm.sort actually does come in two flavors, the string kind 
and an alias kind.

And in fact the string kind just creates a function that's passed to the 
alias kind.  So it probably doesn't actually eliminate the call overhead 
despite the comparison function being available at compile time.  I was 
a little surprised when I saw that implementation, actually.

Anyway, I just like the idea of using a string literal for comparisons 
for the simple cases.  I tried to use boost::functional once and was 
totally incapable of writing something as trivial as an expression that 
used .member of the argument thingy rather than the argument itself. 
But the string expression makes it completely obvious how to do that. 
And it *should* be inline-able and CTFE-able if you write your templates 
carefully, even if the current implementation is not*.

--bb

* Note that I'm not sure if the std.algorithm implementation is 
CTFE-able or not.  Haven't tried it.  Doesn't look like it would be 
though. Not by DMD at least.
Dec 18 2007
parent Sean Kelly <sean f4.ca> writes:
Bill Baxter wrote:

 
 D2 std.algorithm.sort actually does come in two flavors, the string kind 
 and an alias kind.
 
 And in fact the string kind just creates a function that's passed to the 
 alias kind.  So it probably doesn't actually eliminate the call overhead 
 despite the comparison function being available at compile time.  I was 
 a little surprised when I saw that implementation, actually.


If I had to guess I'd say it's to make the routines CTFE-able.  But I 
don't feel it's as flexible as the method used by Tango (and roughly 
illustrated in my previous post).


 Anyway, I just like the idea of using a string literal for comparisons 
 for the simple cases.  I tried to use boost::functional once and was 
 totally incapable of writing something as trivial as an expression that 
 used .member of the argument thingy rather than the argument itself. But 
 the string expression makes it completely obvious how to do that. And it 
 *should* be inline-able and CTFE-able if you write your templates 
 carefully, even if the current implementation is not*.


I very much agree.


 * Note that I'm not sure if the std.algorithm implementation is 
 CTFE-able or not.  Haven't tried it.  Doesn't look like it would be 
 though. Not by DMD at least.


The routines in tango.core.Array are CTFE-able but for the issue 
described here:

http://d.puremagic.com/issues/show_bug.cgi?id=1742

So I imagine those in std.algorithm are as well, or could be made so 
with little effort.


Sean
Dec 18 2007