www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Bugs in template constraints

reply Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
There seem to be some bugs with template constraints. Here's a reduce example
(from TDPL) which will not compile:

import std.stdio;
import std.range;

 property bool empty(T)(T[] a) { return a.length == 0; }
 property ref T front(T)(T[] a) { return a[0]; }
void popFront(T)(ref T[] a) { a = a[1 .. $]; }


V reduce(alias fun, V, R)(V x, R range)
    if (is(typeof(x = fun(x, range.front)))
        && is(typeof(range.empty) == bool)
        && is(typeof(range.popFront())))
{
    //~ writeln(is(typeof(x = fun(x, range.front))));
    //~ writeln(is(typeof(range.empty) == bool));
    //~ writeln(is(typeof(range.popFront())));
    
    for ( ; !range.empty; range.popFront()) {
        x = fun(x, range.front);
    }
    return x;
}

unittest {
    int[] r = [10, 14, 3, 5, 23];
    
    // compute sum
    int sum = reduce!((a, b) { return a + b; })(0, r);
    assert(sum == 55);
    
    // compute minimum
    int min = reduce!((a, b) { return a < b ? a : b; })(r[0], r);
    assert(min == 3);
}

void main()
{
}

Errors:
reduce_original.d(28): Error: template reduce_original.reduce(alias fun,V,R) if
(is(typeof(x = fun(x,range.front))) && is(typeof(range.empty) == bool) &&
is(typeof(range.popFront()))) does not match any function template declaration
reduce_original.d(28): Error: template reduce_original.reduce(alias fun,V,R) if
(is(typeof(x = fun(x,range.front))) && is(typeof(range.empty) == bool) &&
is(typeof(range.popFront()))) cannot deduce template function from argument
types !(__dgliteral1)(int,int[])
reduce_original.d(28): Error: template instance errors instantiating template
reduce_original.d(32): Error: template reduce_original.reduce(alias fun,V,R) if
(is(typeof(x = fun(x,range.front))) && is(typeof(range.empty) == bool) &&
is(typeof(range.popFront()))) does not match any function template declaration
reduce_original.d(32): Error: template reduce_original.reduce(alias fun,V,R) if
(is(typeof(x = fun(x,range.front))) && is(typeof(range.empty) == bool) &&
is(typeof(range.popFront()))) cannot deduce template function from argument
types !(__dgliteral4)(int,int[])
reduce_original.d(32): Error: template instance errors instantiating template


If I comment out the constraints, and uncomment those writeln's - which are the
same as the constraints - like so:

V reduce(alias fun, V, R)(V x, R range)
    //~ if (is(typeof(x = fun(x, range.front)))
        //~ && is(typeof(range.empty) == bool)
        //~ && is(typeof(range.popFront())))
{
    writeln(is(typeof(x = fun(x, range.front))));
    writeln(is(typeof(range.empty) == bool));
    writeln(is(typeof(range.popFront())));
    
    for ( ; !range.empty; range.popFront()) {
        x = fun(x, range.front);
    }
    return x;
}

I will get all true results back:

true
true
true
true
true
true

I'm filing a bug unless something else is to blame here.
Aug 03 2010
next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Tue, Aug 3, 2010 at 20:59, Andrej Mitrovic <andrej.mitrovich gmail.com>wrote:


 There seem to be some bugs with template constraints. Here's a reduce
 example (from TDPL) which will not compile:


 V reduce(alias fun, V, R)(V x, R range)
    if (is(typeof(x = fun(x, range.front)))
        && is(typeof(range.empty) == bool)
        && is(typeof(range.popFront())))




 I'm filing a bug unless something else is to blame here.


I think that's because you cannot directly take the type of a statement. The
assignment in the first typeof() is to blame. To make a statement into an
expression, transform it into an anonymous void delegate(): put it in braces
(with a semicolon at the end) and call it like a function, like this:

V reduce(alias fun, V, R)(V x, R range)
    if (is({ typeof(x = fun(x, range.front);}()))
        && is(typeof(range.empty) == bool)
        && is(typeof(range.popFront())))
{...}

Or, more readable, wrap all the code you want to test into curly brackets
and evaluates its global return type:


V reduce(alias fun, V, R)(V x, R range)
   if (is(typeof({                              // I want to be able to do
that with an R and a V:
                 x = fun(x, range.front);
                 if (range.empty) {};
                 range.popFront();
   }())))

{...}

It's a D idiom you'll see in many places in the standard library. I
personally find it a _bit_ heavy on parenthesis, even though I like Lisp.


Philippe
Aug 03 2010
prev sibling next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On Tue, Aug 3, 2010 at 9:34 PM, Philippe Sigaud
<philippe.sigaud gmail.com>wrote:


 On Tue, Aug 3, 2010 at 20:59, Andrej Mitrovic
<andrej.mitrovich gmail.com>wrote:


 There seem to be some bugs with template constraints. Here's a reduce
 example (from TDPL) which will not compile:


 V reduce(alias fun, V, R)(V x, R range)
    if (is(typeof(x = fun(x, range.front)))
        && is(typeof(range.empty) == bool)
        && is(typeof(range.popFront())))




 I'm filing a bug unless something else is to blame here.


 I think that's because you cannot directly take the type of a statement.
 The assignment in the first typeof() is to blame. To make a statement into
 an expression, transform it into an anonymous void delegate(): put it in
 braces (with a semicolon at the end) and call it like a function, like this:

 V reduce(alias fun, V, R)(V x, R range)
     if (is({ typeof(x = fun(x, range.front);}()))
         && is(typeof(range.empty) == bool)
         && is(typeof(range.popFront())))
 {...}


The { comes after "typeof(" as in your second example, and then it compiles.



 Or, more readable, wrap all the code you want to test into curly brackets
 and evaluates its global return type:


 V reduce(alias fun, V, R)(V x, R range)
    if (is(typeof({                              // I want to be able to do
 that with an R and a V:
                  x = fun(x, range.front);
                  if (range.empty) {};
                  range.popFront();
    }())))

 {...}

 It's a D idiom you'll see in many places in the standard library. I
 personally find it a _bit_ heavy on parenthesis, even though I like Lisp.


 Philippe


Yeah, those paranthesis are getting a bit scary now. :) I guess this one
goes to the TDPL errata.

Thanks for your help Philippe.
Aug 03 2010
prev sibling next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
Oh and there's a shorter way to write this example, by using isInputRange
from std.range, like so:

if (isInputRange!R && is(typeof({x = fun(x, range.front);})))

This was in TDPL (except the {}'s which are missing).

On Tue, Aug 3, 2010 at 10:01 PM, Andrej Mitrovic <andrej.mitrovich gmail.com

 wrote:



 On Tue, Aug 3, 2010 at 9:34 PM, Philippe Sigaud <philippe.sigaud gmail.com

 wrote:



 On Tue, Aug 3, 2010 at 20:59, Andrej Mitrovic <andrej.mitrovich gmail.com

 wrote:



 There seem to be some bugs with template constraints. Here's a reduce
 example (from TDPL) which will not compile:


 V reduce(alias fun, V, R)(V x, R range)
    if (is(typeof(x = fun(x, range.front)))
        && is(typeof(range.empty) == bool)
        && is(typeof(range.popFront())))




 I'm filing a bug unless something else is to blame here.


 I think that's because you cannot directly take the type of a statement.
 The assignment in the first typeof() is to blame. To make a statement into
 an expression, transform it into an anonymous void delegate(): put it in
 braces (with a semicolon at the end) and call it like a function, like this:

 V reduce(alias fun, V, R)(V x, R range)
     if (is({ typeof(x = fun(x, range.front);}()))
         && is(typeof(range.empty) == bool)
         && is(typeof(range.popFront())))
 {...}


 The { comes after "typeof(" as in your second example, and then it
 compiles.



 Or, more readable, wrap all the code you want to test into curly brackets
 and evaluates its global return type:


 V reduce(alias fun, V, R)(V x, R range)
    if (is(typeof({                              // I want to be able to do
 that with an R and a V:
                  x = fun(x, range.front);
                  if (range.empty) {};
                  range.popFront();
    }())))

 {...}

 It's a D idiom you'll see in many places in the standard library. I
 personally find it a _bit_ heavy on parenthesis, even though I like Lisp.


 Philippe


 Yeah, those paranthesis are getting a bit scary now. :) I guess this one
 goes to the TDPL errata.

 Thanks for your help Philippe.
Aug 03 2010
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Tue, Aug 3, 2010 at 22:04, Andrej Mitrovic <andrej.mitrovich gmail.com>wrote:


 Oh and there's a shorter way to write this example, by using isInputRange
 from std.range, like so:

 if (isInputRange!R && is(typeof({x = fun(x, range.front);})))


Does this work, without the () after the } ?



 This was in TDPL (except the {}'s which are missing).



As I said, abstracting away common constraints is a common trick. Have a
look at std.range, you'll see a bunch of these.


Philippe
Aug 03 2010
prev sibling next sibling parent reply Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On Tue, Aug 3, 2010 at 10:23 PM, Philippe Sigaud
<philippe.sigaud gmail.com>wrote:


 On Tue, Aug 3, 2010 at 22:04, Andrej Mitrovic
<andrej.mitrovich gmail.com>wrote:


 Oh and there's a shorter way to write this example, by using isInputRange
 from std.range, like so:

 if (isInputRange!R && is(typeof({x = fun(x, range.front);})))


 Does this work, without the () after the } ?


I haven't even noticed those.

In the following, If I add the pair of ()'s I get void as a return type. If
I remove them, I get void delegate():

writeln(typeid(typeof( delegate void () {int x = 1;}())));    // writes void
writeln(typeid(typeof( delegate void () {int x = 1;})));      // writes void
delegate()

So I definitely need to add them. When not added the expression evaluates to
void delegate(), which is a valid type and the constraint then passes.

If I understood everything, this code in the constraint:

is(typeof({x = fun(x, range.front);}() )))

creates an anonymous function, the compiler sees it's trying to access x so
it makes it a delegate, and it infers that the function takes no arguments
and the return type is void. Did I get this right?


This was in TDPL (except the {}'s which are missing).

 As I said, abstracting away common constraints is a common trick. Have a
 look at std.range, you'll see a bunch of these.


 Philippe
Aug 03 2010
parent reply Pelle <pelle.mansson gmail.com> writes:
On 08/03/2010 11:07 PM, Andrej Mitrovic wrote:

 On Tue, Aug 3, 2010 at 10:23 PM, Philippe Sigaud
 <philippe.sigaud gmail.com <mailto:philippe.sigaud gmail.com>> wrote:



     On Tue, Aug 3, 2010 at 22:04, Andrej Mitrovic
     <andrej.mitrovich gmail.com <mailto:andrej.mitrovich gmail.com>> wrote:

         Oh and there's a shorter way to write this example, by using
         isInputRange from std.range, like so:

         if (isInputRange!R && is(typeof({x = fun(x, range.front);})))


     Does this work, without the () after the } ?


 I haven't even noticed those.

 In the following, If I add the pair of ()'s I get void as a return type.
 If I remove them, I get void delegate():

 writeln(typeid(typeof( delegate void () {int x = 1;}())));    // writes void
 writeln(typeid(typeof( delegate void () {int x = 1;})));      // writes
 void delegate()

 So I definitely need to add them. When not added the expression
 evaluates to void delegate(), which is a valid type and the constraint
 then passes.

 If I understood everything, this code in the constraint:

 is(typeof({x = fun(x, range.front);}() )))

 creates an anonymous function, the compiler sees it's trying to access x
 so it makes it a delegate, and it infers that the function takes no
 arguments and the return type is void. Did I get this right?


You only need to call it if you want to check the return type. You 
cannot create a function with content that can't compile, so in this 
case, the () isn't needed.

Correct me if I'm wrong, of course. :)
Aug 03 2010
parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
I guess that would make sense. With {}() I could add a comparison for the
return type if I ever needed that.

I did take a look in std.range, and pretty much all the templates there use
the {}() syntax.

On Tue, Aug 3, 2010 at 11:53 PM, Pelle <pelle.mansson gmail.com> wrote:


 On 08/03/2010 11:07 PM, Andrej Mitrovic wrote:


 On Tue, Aug 3, 2010 at 10:23 PM, Philippe Sigaud
 <philippe.sigaud gmail.com <mailto:philippe.sigaud gmail.com>> wrote:



    On Tue, Aug 3, 2010 at 22:04, Andrej Mitrovic
    <andrej.mitrovich gmail.com <mailto:andrej.mitrovich gmail.com>>
 wrote:

        Oh and there's a shorter way to write this example, by using
        isInputRange from std.range, like so:

        if (isInputRange!R && is(typeof({x = fun(x, range.front);})))


    Does this work, without the () after the } ?


 I haven't even noticed those.

 In the following, If I add the pair of ()'s I get void as a return type.
 If I remove them, I get void delegate():

 writeln(typeid(typeof( delegate void () {int x = 1;}())));    // writes
 void
 writeln(typeid(typeof( delegate void () {int x = 1;})));      // writes
 void delegate()

 So I definitely need to add them. When not added the expression
 evaluates to void delegate(), which is a valid type and the constraint
 then passes.

 If I understood everything, this code in the constraint:

 is(typeof({x = fun(x, range.front);}() )))

 creates an anonymous function, the compiler sees it's trying to access x
 so it makes it a delegate, and it infers that the function takes no
 arguments and the return type is void. Did I get this right?


 You only need to call it if you want to check the return type. You cannot
 create a function with content that can't compile, so in this case, the ()
 isn't needed.

 Correct me if I'm wrong, of course. :)
Aug 03 2010
prev sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Tue, Aug 3, 2010 at 23:07, Andrej Mitrovic <andrej.mitrovich gmail.com>wrote:


 If I understood everything, this code in the constraint:

 is(typeof({x = fun(x, range.front);}() )))

 creates an anonymous function, the compiler sees it's trying to access x so
 it makes it a delegate, and it infers that the function takes no arguments
 and the return type is void. Did I get this right?


Yes, that's it. If the enclosed statements are OK, then the whole delegate
compiles, gets a type (void delegate() ), and so on, though is(typeof()).

So, using it as a way to get template constraints to work on many statements
was not planned that way, I think. But it works :)

Basically any D block statement: { statements;} can be seen as a void
delegate().

see http://www.digitalmars.com/d/2.0/lazy-evaluation.html
and http://www.digitalmars.com/d/2.0/statement.html#ScopeStatement for an
example of this.

Philippe
Aug 03 2010