www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Compile-Time Interfaces (Concepts)

reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
AFAIK there is no compile-time variant of interfaces right?

Why is that?

Wouldn't it be nice to say something like

     struct SomeRange realize InputRange
     {
         /* implement members of InputRange */
     }

and then the compiler will statically check that that all members 
are implemented correctly.

I guess this requires some new syntax to describe what an 
InputRange is.

Kind of like C++ Concepts.
Jul 17 2014
parent reply Justin Whear <justin economicmodeling.com> writes:
On Thu, 17 Jul 2014 22:49:30 +0000, Nordlöw wrote:


 AFAIK there is no compile-time variant of interfaces right?
 
 Why is that?
 
 Wouldn't it be nice to say something like
 
      struct SomeRange realize InputRange {
          /* implement members of InputRange */
      }
 
 and then the compiler will statically check that that all members are
 implemented correctly.
 
 I guess this requires some new syntax to describe what an InputRange is.
 
 Kind of like C++ Concepts.


What benefits would accrue from adding this?  Static verification that a 
structure implements the specified concepts?  If so, you can simply do 
this instead:

static assert(isInputRange!SomeRange);
Jul 17 2014
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Justin Whear:


 What benefits would accrue from adding this?  Static 
 verification that a structure implements the specified concepts?


Not just that, but also the other way around: static verification 
that a "Concept" is strictly sufficient for any instantiation of 
a specific template. This is what Haskell/Rust do.

Bye,
bearophile
Jul 17 2014
next sibling parent reply Justin Whear <justin economicmodeling.com> writes:
On Thu, 17 Jul 2014 23:06:30 +0000, bearophile wrote:


 Justin Whear:
 

 What benefits would accrue from adding this?  Static verification that
 a structure implements the specified concepts?


 
 Not just that, but also the other way around: static verification that a
 "Concept" is strictly sufficient for any instantiation of a specific
 template. This is what Haskell/Rust do.
 
 Bye,
 bearophile


By this do mean replacing the template constraint `if (isInputRange!R)` 
syntax?  If so, we need concept definition syntax, but we do not 
necessarily need a "struct realizes concept" syntax.  And, in fact, I 
would argue against it as a static assert would continue to be sufficient.
Jul 17 2014
parent "bearophile" <bearophileHUGS lycos.com> writes:
Justin Whear:


 By this do mean replacing the template constraint `if 
 (isInputRange!R)`
 syntax?  If so, we need concept definition syntax, but we do not
 necessarily need a "struct realizes concept" syntax.  And, in 
 fact, I
 would argue against it as a static assert would continue to be 
 sufficient.


I was not suggesting to put Concepts (or typeclasses) in D (and 
Andrei is against this idea), I was just trying to explain the 
basic difference between template constraints and concepts :-)

Bye,
bearophile
Jul 17 2014
prev sibling parent reply "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Thu, Jul 17, 2014 at 11:06:30PM +0000, bearophile via Digitalmars-d-learn
wrote:

 Justin Whear:
 

What benefits would accrue from adding this?  Static verification
that a structure implements the specified concepts?


 
 Not just that, but also the other way around: static verification that
 a "Concept" is strictly sufficient for any instantiation of a specific
 template. This is what Haskell/Rust do.


[...]

Right now, I'm still on the fence about the feasibility of implementing
concepts in D (esp. given our current direction to stabilize the
language with what we have), but I do see especially the following
strong benefit:

	/*
	 * Current implementation:
	 */
	template isInputRange(R) {
		// ... check for existence & types of .empty, .front,
		// .popFront
	}

	auto myFilter(R)(R range)
		if (isInputRange!R)
	{
		...
		if (range.length > 5) { // <---- uh oh
			...;
		}
		return result;
	}

	unittest
	{
		auto r = myFilter([1,2,3,4]);
		assert(r.equals(expectedResult));
		// N.B. error in myFilter's implementation not caught by
		// unittest because arrays just happen to have more
		// properties than pure input ranges.
	}

	/*
	 * Concepts implementation:
	 */
	concept InputRange(T) {
		bool empty;
		T front;
		void popFront();
	}

	auto myFilter(R : InputRange)(R range) // hypothetical syntax
	{
		...
		if (range.length > 5) { // <--- compile error:
					// InputRange doesn't have
					// .length property
			...
		}
		return result;
	}

Currently, there is no easy way to test if your range function is making
assumptions outside of the range API, because while signature
constraints are powerful, they also don't tell the compiler what
assumptions are granted to the function body -- the compiler has no way
to sanitize the function body until the template is actually
instantiated. But if your code wrongly depended on array-specific
properties, and your unittests only run tests with arrays, then the
problem won't be caught... until 3 months later when you ship your
library, and users complain that the function doesn't compile when
handed a non-array input range that doesn't have .length.

Using concepts, however, the compiler knows exactly what properties the
incoming type is assumed to have, and can therefore catch mistakes like
the above when you reference a property that isn't part of the concept.

This is a contrived example, of course. But it's a bit frightening how
many times I've come across Phobos code that makes wrong assumptions
like this.

A proper implementation of concepts would also catch more subtle errors,
such as the following:

	/**
	 * Checks that R is an input range according to the range API.
	 */
	enum isInputRange(R) = is(typeof(R.empty) : bool) &&
				is(typeof(R.front)) &&
				is(typeof(R.popFront()));

	auto myFilter(R)(R range)
		if (isInputRange!R)
	{
		...
		auto tmp = range.front; // <-- spot the bug
		...
		range.popFront();
		tmp = range.front; // <-- spot the bug
		...
		return result;
	}

What bug? I hear you say. Well, the problem is, input ranges as defined
by the isInputRange template above is under-specified. It merely asserts
that R.front has a type, but says nothing about whether the type is
assignable, or, indeed, whether it's ' property void front()', in which
case the first "spot the bug" line will fail to compile since you can't
instantiate a void type. And again, since sig constraints tell the
compiler nothing about what assumptions are granted to the function
body, such problems are left hidden until one day somebody comes along
and wants to use your function with an unusual input range.

Under a concepts implementation, you'd perhaps write something like
this:

	concept InputRange(T) {
		bool empty;
		T front;
		void popFront();
	}

The compiler will then reject both "spot the bug" lines in myFilter,
because, as written, the definition of InputRange says nothing about the
type T. Is it instantiable? Assignable? Since it's not specified, it's
illegal to attempt those operations in myFilter. This then forces us to
rewrite the definition of InputRange, perhaps something like this:

	concept InputRange(T : Assignable, Instantiable) {
		bool empty;
		T front;
		void popFront();
	}

	concept Assignable {
		void opAssign(typeof(this)); // tell compiler assignment is allowed
	}

So you see, this has forced us to be more precise about exactly what an
input range is, instead of the current imprecise definition which leads
to subtle, corner case bugs like std.algorithm not handling transient
ranges correctly, etc..


T

-- 
PNP = Plug 'N' Pray
Jul 17 2014
next sibling parent "Dicebot" <public dicebot.lv> writes:
..and call it "mixin interface" :P
Jul 17 2014
prev sibling next sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Thursday, 17 July 2014 at 23:44:56 UTC, H. S. Teoh via 
Digitalmars-d-learn wrote:

 So you see, this has forced us to be more precise about exactly 
 what an
 input range is, instead of the current imprecise definition 
 which leads
 to subtle, corner case bugs like std.algorithm not handling 
 transient
 ranges correctly, etc..


Great answer. Thanks alot!
Jul 19 2014
prev sibling parent reply bossfong <bossfong posteo.de> writes:
Could we possibly have a template like the following:

satisfiesInterface!(T, Interface);

that would return true when T satisfies Interface and otherwise gives 
descriptive error messages via __pragma(error, ...) ?

Then isInputRange could simply use satisfiesInterface under the hood and 
user code had a nice tool to check their very own requirements.
I'm not sure if such a template is possible though.
Jul 23 2014
parent reply "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Wed, Jul 23, 2014 at 04:21:16PM +0200, bossfong via Digitalmars-d-learn
wrote:

 Could we possibly have a template like the following:
 
 satisfiesInterface!(T, Interface);
 
 that would return true when T satisfies Interface and otherwise gives
 descriptive error messages via __pragma(error, ...) ?
 
 Then isInputRange could simply use satisfiesInterface under the hood
 and user code had a nice tool to check their very own requirements.
 I'm not sure if such a template is possible though.


We could, though it's not quite the same as a native concepts
implementation where the compiler can check templates for code that
wrongly makes assumptions about the incoming type that aren't defined by
the concept.


T

-- 
I think Debian's doing something wrong, `apt-get install pesticide', doesn't
seem to remove the bugs on my system! -- Mike Dresser
Jul 23 2014
parent reply bossfong <bossfong posteo.de> writes:
Am 23.07.2014 16:27, schrieb H. S. Teoh via Digitalmars-d-learn:

 We could, though it's not quite the same as a native concepts
 implementation where the compiler can check templates for code that
 wrongly makes assumptions about the incoming type that aren't defined by
 the concept.


 T


true.

Still, maybe compiler errors could be provided by a library that defines 
an "Concept(Interface)" UDA that you could use to annotate 
implementations of "Concepts"?

import concepts;

 Concept(InputRange)
struct MyInputRange
{
// ...
}

verifyConcepts();

Is it that what you mean?

Just thinking things through here...
Jul 23 2014
parent reply "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Wed, Jul 23, 2014 at 04:46:20PM +0200, bossfong via Digitalmars-d-learn
wrote:

 Am 23.07.2014 16:27, schrieb H. S. Teoh via Digitalmars-d-learn:

We could, though it's not quite the same as a native concepts
implementation where the compiler can check templates for code that
wrongly makes assumptions about the incoming type that aren't defined by
the concept.


T


 true.
 
 Still, maybe compiler errors could be provided by a library that
 defines an "Concept(Interface)" UDA that you could use to annotate
 implementations of "Concepts"?
 
 import concepts;
 
  Concept(InputRange)
 struct MyInputRange
 {
 // ...
 }
 
 verifyConcepts();
 
 Is it that what you mean?
 
 Just thinking things through here...


No, I'm talking about catching errors like this:

	auto myRangeAlgo(R)(R range)
		if (isInputRange!R)
	{
		...
		auto r = range.save;	// <--- oops
		...
		return Result(...);
	}

	unittest
	{
		auto testData = [1,2,3];
		auto result = myRangeAlgo(testData);

		// Test will pass, because arrays are also forward
		// ranges, which have a .save method. So we fail to
		// catch the bug in the code above.
		assert(result.equal(expectedResults));
	}


T

-- 
Bomb technician: If I'm running, try to keep up.
Jul 23 2014
parent reply "Bossfong" <Bossfong posteo.de> writes:
On Wednesday, 23 July 2014 at 15:28:34 UTC, H. S. Teoh via 
Digitalmars-d-learn wrote:

 On Wed, Jul 23, 2014 at 04:46:20PM +0200, bossfong via 
 Digitalmars-d-learn wrote:

 Am 23.07.2014 16:27, schrieb H. S. Teoh via 
 Digitalmars-d-learn:

We could, though it's not quite the same as a native concepts
implementation where the compiler can check templates for 
code that
wrongly makes assumptions about the incoming type that aren't 
defined by
the concept.


T


 true.
 
 Still, maybe compiler errors could be provided by a library 
 that
 defines an "Concept(Interface)" UDA that you could use to 
 annotate
 implementations of "Concepts"?
 
 import concepts;
 
  Concept(InputRange)
 struct MyInputRange
 {
 // ...
 }
 
 verifyConcepts();
 
 Is it that what you mean?
 
 Just thinking things through here...


 No, I'm talking about catching errors like this:

 	auto myRangeAlgo(R)(R range)
 		if (isInputRange!R)
 	{
 		...
 		auto r = range.save;	// <--- oops
 		...
 		return Result(...);
 	}

 	unittest
 	{
 		auto testData = [1,2,3];
 		auto result = myRangeAlgo(testData);

 		// Test will pass, because arrays are also forward
 		// ranges, which have a .save method. So we fail to
 		// catch the bug in the code above.
 		assert(result.equal(expectedResults));
 	}


 T


What about a small wrapper struct then:
A struct Concept that implements opdispatch and forwards all 
calls specified in the interface but for every other method do a 
pragma error.
Then take this struct as a parameter in the function instead of 
any type T.
Maybe, if that is possible, allow implicit conversion from any 
type to Concept, so the callsite doesnt change.
Is there something obvious im missing? Im justbrainstorming 
here...
Jul 23 2014
parent "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Wed, Jul 23, 2014 at 05:09:54PM +0000, Bossfong via Digitalmars-d-learn
wrote:

 On Wednesday, 23 July 2014 at 15:28:34 UTC, H. S. Teoh via
 Digitalmars-d-learn wrote:

On Wed, Jul 23, 2014 at 04:46:20PM +0200, bossfong via Digitalmars-d-learn
wrote:




[...]

Still, maybe compiler errors could be provided by a library that
defines an "Concept(Interface)" UDA that you could use to annotate
implementations of "Concepts"?

import concepts;

 Concept(InputRange)
struct MyInputRange
{
// ...
}

verifyConcepts();

Is it that what you mean?

Just thinking things through here...


No, I'm talking about catching errors like this:

	auto myRangeAlgo(R)(R range)
		if (isInputRange!R)
	{
		...
		auto r = range.save;	// <--- oops
		...
		return Result(...);
	}

	unittest
	{
		auto testData = [1,2,3];
		auto result = myRangeAlgo(testData);

		// Test will pass, because arrays are also forward
		// ranges, which have a .save method. So we fail to
		// catch the bug in the code above.
		assert(result.equal(expectedResults));
	}


T


 
 What about a small wrapper struct then:
 A struct Concept that implements opdispatch and forwards all calls
 specified in the interface but for every other method do a pragma
 error.
 Then take this struct as a parameter in the function instead of any
 type T.  Maybe, if that is possible, allow implicit conversion from
 any type to Concept, so the callsite doesnt change.
 Is there something obvious im missing? Im justbrainstorming here...


That's not a bad idea, and in fact something similar occurred to me as
well. Basically, my idea was to create dummy structs representing the
Concepts checked by the sig constraints, and have unittests instantiate
the algorithm with said structs. The structs will only have the methods
defined by the Concept, so this will catch any wrong code that tries to
access something outside of what the Concept defines.

Your idea is better, in fact, since you wouldn't have to rely on
programmer diligence to write such unittests. You wouldn't even need to
use pragma error; you just have opDispatch forward only the functions
implemented by the concept, and everything else will result in a "no
such field" error.

The only trouble is implicit conversion. I don't think the language
allows that right now, by design.


T

-- 
Question authority. Don't ask why, just do it.
Jul 23 2014
prev sibling next sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Thursday, 17 July 2014 at 22:52:37 UTC, Justin Whear wrote:

 static assert(isInputRange!SomeRange);


I'll use that for now.

Thx
Jul 19 2014
prev sibling parent reply "Atila Neves" <atila.neves gmail.com> writes:
On Thursday, 17 July 2014 at 22:52:37 UTC, Justin Whear wrote:

 On Thu, 17 Jul 2014 22:49:30 +0000, Nordlöw wrote:


 AFAIK there is no compile-time variant of interfaces right?
 
 Why is that?
 
 Wouldn't it be nice to say something like
 
      struct SomeRange realize InputRange {
          /* implement members of InputRange */
      }
 
 and then the compiler will statically check that that all 
 members are
 implemented correctly.
 
 I guess this requires some new syntax to describe what an 
 InputRange is.
 
 Kind of like C++ Concepts.


 What benefits would accrue from adding this?  Static 
 verification that a
 structure implements the specified concepts?  If so, you can 
 simply do
 this instead:

 static assert(isInputRange!SomeRange);


This is sufficient, but not adequate. Just as the built-in
unittest blocks with assertions, it's great when the assertion is
true but good luck finding out where the bug is when it's not.

The D Cookbook has an idiom to handle this by checking for __ctfe
but it's super hacky and there should be a better way.

I have lost count of how many times I wish the compiler would
help me with compile time interfaces as it does with runtime
code. static override and static interface? Yes please.

Atila
Jul 20 2014
parent "Vlad Levenfeld" <vlevenfeld gmail.com> writes:
On Sunday, 20 July 2014 at 15:45:37 UTC, Atila Neves wrote:

 On Thursday, 17 July 2014 at 22:52:37 UTC, Justin Whear wrote:

 On Thu, 17 Jul 2014 22:49:30 +0000, Nordlöw wrote:


 AFAIK there is no compile-time variant of interfaces right?
 
 Why is that?
 
 Wouldn't it be nice to say something like
 
     struct SomeRange realize InputRange {
         /* implement members of InputRange */
     }
 
 and then the compiler will statically check that that all 
 members are
 implemented correctly.
 
 I guess this requires some new syntax to describe what an 
 InputRange is.
 
 Kind of like C++ Concepts.


 What benefits would accrue from adding this?  Static 
 verification that a
 structure implements the specified concepts?  If so, you can 
 simply do
 this instead:

 static assert(isInputRange!SomeRange);


 This is sufficient, but not adequate. Just as the built-in
 unittest blocks with assertions, it's great when the assertion 
 is
 true but good luck finding out where the bug is when it's not.

 The D Cookbook has an idiom to handle this by checking for 
 __ctfe
 but it's super hacky and there should be a better way.

 I have lost count of how many times I wish the compiler would
 help me with compile time interfaces as it does with runtime
 code. static override and static interface? Yes please.

 Atila


+1, failing template constraints just gives a vague "couldn't 
match overload" type of error, and sometimes static assertions 
get suppressed. I've noticed that opDispatch is particularly bad 
about this. Even syntactic errors won't trigger compiler 
messages, and instead seems to behave like SFINAE which I was 
assured doesn't exist in D.
I have to use pragma (msg, ...) to get meaningful errors. Its so 
bad I generally avoid opDispatch despite its awesome potential 
and just generate template functions with mixins instead, because 
they are marginally easier to debug.

I wind up doing things like this to get the functionality I want:

static string assert_processing_stage_defined (string stage)()
{
	static immutable error_msg = `"Model must define processing 
stage: ` ~stage~ ` ()"`;

	return q{
		static assert (hasMember!(This, } `"`~stage~`"` q{), } 
~error_msg~ q{);
		static assert (isSomeFunction!(__traits(getMember, This, } 
`"`~stage~`"` q{)), } ~error_msg~ q{);
		static assert (ParameterTypeTuple!(__traits(getMember, This, } 
`"`~stage~`"` q{)).length == 0, } ~error_msg~ q{);
		static assert (is (ReturnType!(__traits(getMember, This, } 
`"`~stage~`"` q{)) == void), } ~error_msg~ q{);
	};
}

mixin(``
	~assert_processing_stage_defined!`initialize`
	~assert_processing_stage_defined!`update`
);

I'm sure theres worse ways to do it but I still find this ugly 
and overly specific. I would much rather use something like what 
Nordlöw suggested. Something that is standardized across the 
language and generates meaningful error messages.
Jul 20 2014