www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - of "Conditional Implementation" vs "Assertive Input Validation"

reply "monarch_dodra" <monarchdodra gmail.com> writes:
I've been putting my nose in std.algorithm recently, 
specifically, requirements of algorithms.

I must say I'm a big fan of conditional implementations. Given 
the genericity of templates (!), it can be very hard to overload 
them correct without conditional implementation. It is a really 
useful language feature

That said, more often than not, they are also used to validate 
input. While this is a good thing, when a developer DOES try to 
call an algorithm with invalid input, he is greeted with the 
cryptic:
"Error: template foo does not match any function template 
declaration"
Followed by the (potentially long) list of candidates.
More often than not, the conditional implementations are actually 
quite complicated, and contain up to 5 or 6 different conditions.

The worse part is that the developer has no idea _which_ 
condition he has violated.

This is a shame, since most of the time, the conditions are not 
necessary for disambiguation, and a static assert would work just 
as well, and be more verbose.

Simple example:
minPos doesn't shouldn't operate on infinite ranges. compare:
Range minPos(Range)(Range R1) if (is(inputRange!Range) && 
!isInfinite!Range) {...}
vs
Range minPos(Range)(Range R1) if (is(inputRange!Range)
{
     static assert(!isInfinite!Range, "minPos cannot operate on 
infinite ranges.")
     ...
}

Now, if a developer ever accidentally calls minPos with an 
infinite range, he gets slapped in the face with a very explicit 
compilation warning. This (I think) is great, because the 
"isInfinite" test is really just an implementation detail.

inputRange is really the input condition of the range, and should 
stay conditional.

--------
How do you feel about "assertive input validation" vs 
"conditional implementation"?

Is this something you'd like to see more of in algorithm?
Jul 23 2012
next sibling parent "Tobias Pankrath" <tobias pankrath.net> writes:
On Monday, 23 July 2012 at 11:10:39 UTC, monarch_dodra wrote:


 Is this something you'd like to see more of in algorithm?


Yes! Improving error messages is very important. Maybe we find a 
better solution on compiler level but in the meantime [not only] 
std.algorithm will benefit from your solution.
Jul 23 2012
prev sibling next sibling parent Jacob Carlborg <doob me.com> writes:
On 2012-07-23 13:10, monarch_dodra wrote:

 I've been putting my nose in std.algorithm recently, specifically,
 requirements of algorithms.

 I must say I'm a big fan of conditional implementations. Given the
 genericity of templates (!), it can be very hard to overload them
 correct without conditional implementation. It is a really useful
 language feature

 That said, more often than not, they are also used to validate input.
 While this is a good thing, when a developer DOES try to call an
 algorithm with invalid input, he is greeted with the cryptic:
 "Error: template foo does not match any function template declaration"
 Followed by the (potentially long) list of candidates.
 More often than not, the conditional implementations are actually quite
 complicated, and contain up to 5 or 6 different conditions.


I think this is really a problem with std.algorithm.

-- 
/Jacob Carlborg
Jul 23 2012
prev sibling next sibling parent reply "Chris NS" <ibisbasenji gmail.com> writes:
It certainly makes sense.  Maybe the long term solution would be 
a way to embed those assertions in the conditions, but in the 
meantime the proposal would alleviate the error message issue.  I 
know I've often enough stared long and hard at a volume of 
template instantiation errors waiting for the real mistake to 
jump out at me.

----------

And for the curious, what I mean by embedding assertions in the 
conditions is quite literally what it sounds like:

Range minPos ( Range ) ( Range R1 )
if( is( inputRange!Range ) )
assert( !isInfinite!Range, "minPos cannot operate on infinite 
ranges." )
{
     ...
}

In which case the compiler would merge the condition expressions 
of the assertions into the if-condition, and remember the message 
strings associated with them.
Jul 23 2012
parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Mon, Jul 23, 2012 at 1:44 PM, Chris NS <ibisbasenji gmail.com> wrote:


 And for the curious, what I mean by embedding assertions in the conditions
 is quite literally what it sounds like:

 Range minPos ( Range ) ( Range R1 )
 if( is( inputRange!Range ) )
 assert( !isInfinite!Range, "minPos cannot operate on infinite ranges." )


Would it be possible to create a If / Assert template that returns
(er, becomes) true if the condition is true, and static asserts if not
?

template Assert(bool condition, string message)
{
    static if (condition)
        enum Assert = true;
    else
        static assert(false, message);
}

void foo(T,U)(T t, U u) if (is(T == int) && Assert!(isIntegral!U, "U
must be an integer type"))
{}


void main()
{
    foo(1,"a");
}

Seems to work (tm).
Jul 23 2012
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 23-Jul-12 17:29, Philippe Sigaud wrote:

 On Mon, Jul 23, 2012 at 1:44 PM, Chris NS <ibisbasenji gmail.com> wrote:


 And for the curious, what I mean by embedding assertions in the conditions
 is quite literally what it sounds like:

 Range minPos ( Range ) ( Range R1 )
 if( is( inputRange!Range ) )
 assert( !isInfinite!Range, "minPos cannot operate on infinite ranges." )


 Would it be possible to create a If / Assert template that returns
 (er, becomes) true if the condition is true, and static asserts if not
 ?


Will explode every time a constraint is tested?
After all constraints do fail so that other function is picked up and 
they are supposed to.


 template Assert(bool condition, string message)
 {
      static if (condition)
          enum Assert = true;
      else
          static assert(false, message);
 }

 void foo(T,U)(T t, U u) if (is(T == int) && Assert!(isIntegral!U, "U
 must be an integer type"))
 {}


 void main()
 {
      foo(1,"a");
 }

 Seems to work (tm).



-- 
Dmitry Olshansky
Jul 23 2012
next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Mon, Jul 23, 2012 at 3:39 PM, Dmitry Olshansky <dmitry.olsh gmail.com> wrote:


 Will explode every time a constraint is tested?
 After all constraints do fail so that other function is picked up and they
 are supposed to.


Damn, you're right.
Jul 23 2012
prev sibling parent reply "Simen Kjaeraas" <simen.kjaras gmail.com> writes:
On Mon, 23 Jul 2012 15:49:43 +0200, Philippe Sigaud  
<philippe.sigaud gmail.com> wrote:


 On Mon, Jul 23, 2012 at 3:39 PM, Dmitry Olshansky  
 <dmitry.olsh gmail.com> wrote:


 Will explode every time a constraint is tested?
 After all constraints do fail so that other function is picked up and  
 they
 are supposed to.


 Damn, you're right.


To be fair, it explodes as often as the if (isInputRange!T){static  
assert(!isInfinite!T);} does.

-- 
Simen
Jul 23 2012
parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 23-Jul-12 18:07, Simen Kjaeraas wrote:

 On Mon, 23 Jul 2012 15:49:43 +0200, Philippe Sigaud
 <philippe.sigaud gmail.com> wrote:


 On Mon, Jul 23, 2012 at 3:39 PM, Dmitry Olshansky
 <dmitry.olsh gmail.com> wrote:


 Will explode every time a constraint is tested?
 After all constraints do fail so that other function is picked up and
 they
 are supposed to.


 Damn, you're right.


 To be fair, it explodes as often as the if (isInputRange!T){static
 assert(!isInfinite!T);} does.


Right. It's just I did something similar to Philippe stuff previously 
and this somehow was an unpleasant surprise for me.

-- 
Dmitry Olshansky
Jul 23 2012
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/23/12 7:10 AM, monarch_dodra wrote:
[snip]

 --------
 How do you feel about "assertive input validation" vs "conditional
 implementation"?

 Is this something you'd like to see more of in algorithm?


The assertive input validation has the problem it prevents an overload 
outside of std.algorithm from working.

I think we should focus here on the compiler giving better information 
about which part of the Boolean constraint failed.


Andrei
Jul 23 2012
parent reply Jacob Carlborg <doob me.com> writes:
On 2012-07-23 16:47, Andrei Alexandrescu wrote:


 The assertive input validation has the problem it prevents an overload
 outside of std.algorithm from working.

 I think we should focus here on the compiler giving better information
 about which part of the Boolean constraint failed.


I would like to have something like this:

constraint InputRange (Range)
{
     alias ElementType!(Range.init) E;

      property bool empty ();
     void popFront ();
      property E front ();
}

constraint ForwardRange (Range) : ForwardRange!(Range)
{
     E save ();
}

constraint BidirectionalRange (Range) : ForwardRange!(Range)
{
     void popBack ();
      property E back ();
      property E front ();
}

It would be even better if the Range parameter and the ElementType could 
be handled automatically:

constraint BidirectionalRange : ForwardRange
{
     void popBack ();
      property ElementType back ();
      property ElementType front ();
}

And then to use the constraints, like this:

auto filterBidirectional (alias pred, Range : 
BidirectionalRange!(Range)) (Range range);

Or even better if this would be possible:

auto filterBidirectional (alias pred) (BidirectionalRange range);

I know that others have had similar ideas. In these cases I think the 
compiler should be able to give clear and proper error messages when 
something fails to match because now the range constraints/interfaces 
have names. Something like "Foo doesn't match BidirectionalRange" or 
similar.

-- 
/Jacob Carlborg
Jul 23 2012
next sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Monday, 23 July 2012 at 19:57:42 UTC, Jacob Carlborg wrote:

 [snip]
 I know that others have had similar ideas. In these cases I 
 think the compiler should be able to give clear and proper 
 error messages when something fails to match because now the 
 range constraints/interfaces have names. Something like "Foo 
 doesn't match BidirectionalRange" or similar.


My fear is that no matter how you look at it, the compiler just 
doesn't know which overload you want to call. If the compiler 
could generate messages about why each overload was not 
satisfactory, and it would have then to generate messages about 
each and every possible overload, including the ones that you 
obviously didn't want. Things would be better, but probably 
over-verbose :/

My thought was not to remove conditional implementations 
entirely, but rather to compliment them:

I think, for example, this would be perfect for equal:
"Takes two input ranges, and compares them with pred":
Notice that the english input condition here is merely "two input 
ranges". If the range elements don't actually compare, it does 
not mean you did not fulfill the "input contract", but rather 
that you did not fulfill the "implementation requirements".

equal(alias pred = "a == b", R1, R2)(R1 range1, R2 range2)
   if (isInputRange!R1 && isInputRange!R2)
{
   assert(is(typeof(BinaryPred!pred(r1.front, r2.front))), "equal: 
elements are not predicate comparable");
   ...
}

On Monday, 23 July 2012 at 14:47:50 UTC, Andrei Alexandrescu 
wrote:

 The assertive input validation has the problem it prevents an 
 overload outside of std.algorithm from working.

 I think we should focus here on the compiler giving better 
 information about which part of the Boolean constraint failed.


 Andrei


That is true, but then again, a certain level of ambiguity is "a 
good thing"®. The compiler choosing too eagerly which function 
you want to call based on obscure conditional implementations is 
dangerous (IMO).

For example, if somebody else provided an "equal" which operated 
on two input ranges, and took a unary predicated, and then used 
the result of the unary predicate to compare the elements, I sure 
as hell wouldn't it to be disambiguated without my explicit 
consent.

If somebody writes a "fill" that can operate on input 
(non-forward, non-infinite) ranges, I WANT the ambiguity.

----
I think the above gives a good balance of both approaches: The 
conditional implementation is enough to *roughly* define what the 
function operates on, while giving enough leeway for 
non-ambiguous overloads. Once the compiler has *chosen* the 
implementation though, then more thorough input validation can 
kick in.

That's my take on it anyways.
Jul 23 2012
parent Jacob Carlborg <doob me.com> writes:
On 2012-07-23 22:28, monarch_dodra wrote:


 My fear is that no matter how you look at it, the compiler just doesn't
 know which overload you want to call. If the compiler could generate
 messages about why each overload was not satisfactory, and it would have
 then to generate messages about each and every possible overload,
 including the ones that you obviously didn't want. Things would be
 better, but probably over-verbose :/

 My thought was not to remove conditional implementations entirely, but
 rather to compliment them:

 I think, for example, this would be perfect for equal:
 "Takes two input ranges, and compares them with pred":
 Notice that the english input condition here is merely "two input
 ranges". If the range elements don't actually compare, it does not mean
 you did not fulfill the "input contract", but rather that you did not
 fulfill the "implementation requirements".

 equal(alias pred = "a == b", R1, R2)(R1 range1, R2 range2)
    if (isInputRange!R1 && isInputRange!R2)
 {
    assert(is(typeof(BinaryPred!pred(r1.front, r2.front))), "equal:
 elements are not predicate comparable");
    ...
 }


That looks even more horrible then the current std.algorithm. We 
shouldn't have to add _more_ of these checks, rather remove. The 
compiler should help the developer, not the other way around.

I think the signatures in std.algorithm are already too complicated and 
verbose and they still don't protect from the horrible template errors 
that template constraints were supposed to help avoid.

-- 
/Jacob Carlborg
Jul 23 2012
prev sibling parent reply "xenon325" <1 mail.net> writes:
On Monday, 23 July 2012 at 19:57:42 UTC, Jacob Carlborg wrote:

 constraint BidirectionalRange (Range) : ForwardRange!(Range)
 {
     void popBack ();
      property E back ();
      property E front ();
 }

  [snip]

 I know that others have had similar ideas.


I remember this was discussed recently and Don Clugston suggested 
something like this:

if there is no match for:

     void foo(T)(T t) if( !conditionA!T ){}
     void foo(T)(T t) if( conditionA!T && conditionB!T ){}

the error will be:

template foo does not match any function template, constraints 
values are:
     conditionA: true
     conditionB: false

(note that `conditionA` is listed only once)

And given who Don is, I'm pretty sure he have an idea how to 
implement this.
Jul 24 2012
parent reply Jacob Carlborg <doob me.com> writes:
On 2012-07-24 10:37, xenon325 wrote:


 I remember this was discussed recently and Don Clugston suggested
 something like this:

 if there is no match for:

      void foo(T)(T t) if( !conditionA!T ){}
      void foo(T)(T t) if( conditionA!T && conditionB!T ){}

 the error will be:

 template foo does not match any function template, constraints values are:
      conditionA: true
      conditionB: false

 (note that `conditionA` is listed only once)

 And given who Don is, I'm pretty sure he have an idea how to implement
 this.


That will be just a little better. The problem is it will leak 
implementation details. For this to be useful you really need to create 
a template for every condition:

template isFoo (T)
{
     enum isFoo = is(T == Foo);
}

void foo (T) (T t) if (isFoo!(T));

If you just do it like this:

void foo (T) (T t) if (is(T == Foo));

Then it will leak the "raw" condition. With my approach the constraint 
will have a name which should result in a lot better error messages.

Think of it like this. You have a function, "foo", taking an interface 
parameter, "Foo":

interface Foo
{
     void a ();
     void b ();
     void c ();
}

void foo (Foo f);

You then call the function with an object that does _not_ implement the 
function, then you get a proper easily understandable error message:

foo(new Object);

Error: Object doesn't implement Foo

What would you think if the error message look like this instead:

Error: Object doesn't have the methods:
     void a ();
     void b ();
     void c ();

Now imagine that with a bunch of conditions instead.

void foo (T) (T t) if (__traits(compiles, { T t; t.foo; t.bar; }) || 
is(T : Foo));

Error: template foo does not match any function template, constraints 
values are:
      __traits(compiles, { T t; t.foo; t.bar }) false
      is(T : Foo) false

-- 
/Jacob Carlborg
Jul 24 2012
parent reply "xenon325" <1 mail.net> writes:
On Tuesday, 24 July 2012 at 12:50:08 UTC, Jacob Carlborg wrote:


 That will be just a little better. The problem is it will leak 
 implementation details. For this to be useful you really need 
 to create a template for every condition:

 template isFoo (T)
 {
     enum isFoo = is(T == Foo);
 }

 void foo (T) (T t) if (isFoo!(T));

 If you just do it like this:

 void foo (T) (T t) if (is(T == Foo));

 Then it will leak the "raw" condition.


hmm, yeah that could be hard for novices



 With my approach the constraint will have a name which should 
 result in a lot better error messages.


How is it different from creating a template for every condition 
? ;)

Honestly, I don't quite get what's the difference between current 
template constraints and ones you're proposing:

// yours
constraint InputRange (Range)
{
     alias ElementType!(Range.init) E;

      property bool empty ();
     void popFront ();
      property E front ();
}

// std.range
// 
https://github.com/D-Programming-Language/phobos/blob/master/std/range.d#L549
template isInputRange(R)
{
     enum bool isInputRange = is(typeof(
     (inout int _dummy=0)
     {
         R r = void;       /*** how would you express this b.t.w. 
? ***/
         if (r.empty) {}
         r.popFront();
         auto h = r.front;
     }));
}

on the call site it's as convenient and clear as yours.
On the definition site, yes, syntax maybe is a tad worse,
but it's not *that* bad to require introduction of a new
language construct.

Actually the only thing constraint writer needs to know is that
     `is(typeof(<code>))`
means "compiles". All the rest is perfectly clear.



 Think of it like this. You have a function, "foo", taking an 
 interface parameter, "Foo":

 interface Foo
 {
     void a ();
     void b ();
     void c ();
 }

 void foo (Foo f);

 You then call the function with an object that does _not_ 
 implement the function, then you get a proper easily 
 understandable error message:

 foo(new Object);

 Error: Object doesn't implement Foo

 What would you think if the error message look like this 
 instead:

 Error: Object doesn't have the methods:
     void a ();
     void b ();
     void c ();

 Now imagine that with a bunch of conditions instead.

 void foo (T) (T t) if (__traits(compiles, { T t; t.foo; t.bar; 
 }) || is(T : Foo));

 Error: template foo does not match any function template, 
 constraints values are:
      __traits(compiles, { T t; t.foo; t.bar }) false
      is(T : Foo) false


I think I've addressed these points, let me know if
I can explain it better.
Jul 24 2012
parent reply Jacob Carlborg <doob me.com> writes:
On 2012-07-25 07:30, xenon325 wrote:


 How is it different from creating a template for every condition ? ;)


As long as you actually _do_ that, it might not be so much different.


 Honestly, I don't quite get what's the difference between current
 template constraints and ones you're proposing:

 // yours
 constraint InputRange (Range)
 {
      alias ElementType!(Range.init) E;

       property bool empty ();
      void popFront ();
       property E front ();
 }

 // std.range
 //
 https://github.com/D-Programming-Language/phobos/blob/master/std/range.d#L549

 template isInputRange(R)
 {
      enum bool isInputRange = is(typeof(
      (inout int _dummy=0)
      {
          R r = void;       /*** how would you express this b.t.w. ? ***/
          if (r.empty) {}
          r.popFront();
          auto h = r.front;
      }));
 }

 on the call site it's as convenient and clear as yours.
 On the definition site, yes, syntax maybe is a tad worse,
 but it's not *that* bad to require introduction of a new
 language construct.


Well it depends on that syntax is used. It's clearer if this syntax 
would be possible:

void foo (InputRange range);

I think it's very little chance of a new language construct being added. 
It's more like I don't necessarily think the way the template 
constraints were implemented was the best way.


 Actually the only thing constraint writer needs to know is that
      `is(typeof(<code>))`
 means "compiles". All the rest is perfectly clear.


And why is "(inout int _dummy=0)" there? I would guess that 
std.algorithm and other parts of Phobos is filled with strange things 
like this.


 I think I've addressed these points, let me know if
 I can explain it better.


Then the conclusion would at least be that std.algorithm could use some 
enhancement how these template constraints are written.

-- 
/Jacob Carlborg
Jul 25 2012
parent "xenon325" <1 mail.net> writes:
On Wednesday, 25 July 2012 at 07:23:51 UTC, Jacob Carlborg wrote:

 On 2012-07-25 07:30, xenon325 wrote:


 For this to be useful you really need to create a template 
 for every condition






[snip]

 With my approach the constraint will have a name which should 
 result in a lot better error messages.


 How is it different from creating a template for every 
 condition ? ;)


 As long as you actually _do_ that, it might not be so much 
 different.


But you would have to create a constraint for every condition as 
well!
And if someone implements Don's idea, error messages would be as 
good.



 Honestly, I don't quite get what's the difference between 
 current
 template constraints and ones you're proposing:




[snip]

 on the call site it's as convenient and clear as yours.
 On the definition site, yes, syntax maybe is a tad worse,
 but it's not *that* bad to require introduction of a new
 language construct.


 Well it depends on that syntax is used. It's clearer if this 
 syntax would be possible:

 void foo (InputRange range);


1. How would you signify `foo` is generic ?
    For complier it's probably possible - by type of `InputRange`,
      but that will be one more special case
    What about user ?

2. How would you put 2 constraints on `range` ?

3. Also you forgot to address:


 template isInputRange(R)
 {
      enum bool isInputRange = is(typeof(
      (inout int _dummy=0)
      {
          R r = void;       /*** how would you express this 
 b.t.w. ? ***/




    range.d comment on this line is "can define a range object".



 I think it's very little chance of a new language construct 
 being added. It's more like I don't necessarily think the way 
 the template constraints were implemented was the best way.


Sorry, but I still fail to see how you way is (significantly) 
better.



 Actually the only thing constraint writer needs to know is that
     `is(typeof(<code>))`
 means "compiles". All the rest is perfectly clear.


 And why is "(inout int _dummy=0)" there? I would guess that 
 std.algorithm and other parts of Phobos is filled with strange 
 things like this.


Yeah :) My thoughts (have really little D experience):
1. why is it lambda
2. why does it have argument
3. why is arg `inout`
4. why is *dummy* arg initialized

I would think it's some kind of temporary compiler workaround.
But if it's something smart, it could definitely use
better syntax, no objections here (__traits( compiles, ..) ?).



 Then the conclusion would at least be that std.algorithm could 
 use some enhancement how these template constraints are written.


Agree, `(inout int _dummy=0)` is confusing. There well may be 
other (as confusing) examples but probably there are easy ways to 
fix them.
Maybe you should create enhancement request or discuss it with 
community ?


Wait! We were talking about how to make compiler error messages 
better.
Jul 25 2012