Virtual concepts (non-intrusive dynamic polymorphism)

[Andy Prowl]

Hello everyone,

I would like to ask for feedback concerning this idea I had about non-intrusive "dynamic" polymorphism:

https://www.dropbox.com/s/tg737sf8sj1p1ht/Virtual%20concepts%20for%20polymorphic%20types.pdf?dl=1

This is just a rough sketch, please do not expect any full-blown proposal. My goal is to find out whether it makes sense to invest more time on it, or if the idea is basically bull***t.

A few highlights:

1. The idea is about introducing non-intrusive support for dynamic polymorphism (similar to Haskell's typeclasses);
2. The idea is similar to the old C++0x "concept maps", but is *not* related to templates;
3. Code using a "virtual concept" can be compiled separately and does not need to see the definition of the instances of that concept.

Thank you,

Andy

[Brent Friedman]

Just a few thoughts:

The fact that it only works on polymorphic types makes sense based on your implementation, but is extremely limiting. Type erasure, an alternative that we already have access to, can operate on types that don't have a vtable and doesn't need the additional metadata.

What limitations are there to the kind of functions that you can define in a virtual concept? Can I create new constructors, or a destructor, or an operator= for a virtual concept? Can I pass an instance of a virtual concept by value, or by rvalue-reference? If so, it seems that each itable will at least need to include references to the various special member functions of the concrete type. Or is one only allowed to pass virtual concepts by pointer or lvalue-reference?

How does the compiler determine the size of a class's vtable when you might load a DLL that contains a virtual concept?

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposal...@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

[Andy Prowl]

Thank you for your valuable comments Brent.

As I mentioned, what I have so far is just a sketch, but I'll try to address your points. 

1. Concerning existing type erasure techniques, the only library solution I know of is Boost.TypeErasure. You're correct, it does work with non-polymorphic types, but it is not really easy to use, and it does not satisfy the assertion "&cx == &x" from the document I attached: my idea is to support reference semantics and allow accessing an object through a virtual concept without creating a proxy object (it must be *that* object which I pass around that gets referenced). Also, I believe (please correct me if I am wrong) that Boost.TypeErasure only supports duck-typing: I cannot specify, for instance, a concept (call it "C") such as "has member function foo()" and then pass to a function expecting a "C&" an object which only has a function "bar()", but for which an instantiation of C exists in which "foo()" delegates to "bar()". Unless I'm mistaken, that is basically how typeclasses work in Haskell. Finally, Boost.TypeErasure makes heavy use of templates, which is likely going to have a significant impact on compilation time;

2. The problem with supporting non-polymorphic classes, at least in the solution I have sketched so far, is that some sort of "ctable pointer" is necessary on every instance of an object to enable the caller to find the correct instantiation of a concept for the object at hand without knowing its type. For polymorphic types this is easy: we just reuse the vptr and extend the vtable with extra information. For non-polymorphic types we are in trouble, because if the compiler added a "ctable pointer" at the beginning of the in-memory representation of the object, client code which uses that object in a non-polymorphic way would be broken, because it would expect a different layout (I am not a compiler guy, so again, correct me if I'm wrong);

3. Defining destructors in a virtual concept is not meaningful as far as I can see: all types have a destructor, so "having a destructor" is a contract that all types satisfy - no need to make it explicit. An object referenced by a virtual contract will be destroyed when it goes out of scope (if it has automatic storage duration), or when it gets deleted (if it has dynamic storage duration);

4. Good point about constructors and other special member functions (except destructors). The main use case I can see for virtual concepts is indeed to access objects through references/pointers: after all, the idea is to support dynamic polymorphism the same way inheritance does, but non-intrusively, and inheritance-based polymorphism somehow forces us to use references and pointers. However, I am aware that polymorphic classes can be used with value semantics, and I do have a feeling that the same would be possible for virtual concepts, but honestly, I did not have this use case in mind when I started developing this idea. Definitely worth a deeper thought.

5. If a ctable is present as an extension of a vtable - as in the document I linked -, then its first field (the metadata) may contain information on its size.

Does this answer your questions, at least partly? If not, please let me know and I'll try to formulate better answers. Any feedback is welcome.

Kind regards,

Andy

[Brent Friedman]

Regarding 5, I may not have explained myself clearly.

Suppose I have a library called coollib which I distribute as a DLL. Coollib includes a polymorphic class X, whose ctable size needs to be known when I distribute the DLL. However, if a client program Funprog tries to make X implement a virtual concept (I understand this to be your primary motivation?) it won't work with your proposed implementation. Funprog needs to alter X's ctable in order to make X implement a virtual concept, and yet we can't do that without breaking coollib's ABI.

--

[Andy Prowl]

OK, I think I see what you mean. You're right, that would be a problem. 

I therefore propose an alternative implementation technique which - unless I'm overlooking something again - should work for non-polymorphic types too, including fundamental types, and does not require a ctable.

The idea is that any time a variable of virtual concept type (C*, C&, or plain C plus cv-qualification, where C is a virtual concept) is initialized, the storage that holds it is extended by the size of one pointer. The additional pointer points to the itable for the static type of the initializing expression. In other words, supposing there is an instantiation of type X for the virtual concept C, and given something like:

X x;
C* c = &x;
c.foo();

The compiler would initialize c with the address of x, and next to the location of c it would store an additional pointer to the itable of X for C. Same for references (the standard doesn't require references to occupy memory, but AFAIK compilers implement references as pointers). The case where c is not of reference/pointer type is handled similarly:

X x;
C c = x; // ASSUME X IS COPY-CONSTRUCTIBLE AND SATISFIES VIRTUAL CONCEPT C
c.foo();

The compiler here would copy-construct an object of type X from x and make it available through the virtual concept C by storing the itable pointer for C(X) next to the storage occupied by c.

A slightly more detailed, yet only sketched description is given here (see the "Implementation technique" section): http://bit.ly/ZgruFY.

I do realize there is much more to cover, but I'd like to know if this looks more promising or if the idea is fundamentally flawed.

Thank you,

Andy

[Brent Friedman]

I think this new version is definitely an improvement. Two pointers will be more feasible than one. I think there are some additional implementation complications to consider.

In order to build an object of virtual concept, we very much need information on the dynamic type of the object to be converted. Perhaps I have a function shave(Animal* a) which wants to convert a to the virtual concept Fuzzy. shave(Sheep*) might work if Sheep implements Fuzzy, and shave(Snake*) might not work. So, in order to even determine if we can convert the object to Fuzzy, we'll need to either add something to Animal's vtable or use RTTI, etc to determine if the conversion is possible. Repurposing dynamic_cast to work with virtual concepts makes sense for supporting this case where the conversion cannot be determined statically. Unless, of course, virtual concepts can only use the static type of an object (Animal in this case) but I don't get the impression that is the intent.

A perhaps more feasible implementation for performing the conversion would involve each virtual concept having a table where each entry is { typeid, itable* }. So the compiler uses RTTI to determine a unique id for the dynamic type of the object, finds the corresponding entry in the virtual concept's table, and dispatches the call into that corresponding itable entry. This allows us to augment a type without modifying it in any way (as long as we can do RTTI).

--

[Andy Prowl]

Thank you Brent.

Actually I believe it is the *static* type of the initializing expression that should be used rather than the dynamic type, otherwise we would break type-safety.

An Animal* can be provided when a Fuzzy* is expected if and only if there is a concept instantiation of Animal for Fuzzy (or of a class Animal derives from for Fuzzy). If not, passing a Snake* (for which we assume no instantiation exists) may result in a refused bequest at run-time.

The idea is to allow determining at compile-time that a function call through a virtual concept is going to be meaningfully implemented, while leaving the concrete binding at run-time - pretty much like classical dynamic polymorphism through inheritance: You don't know what will be called, but you know that something suitable will be called.

*** (PROBLEM) ***

Incidentally, I spotted a problem with the implementation technique I last proposed. In order to compile a function that uses a virtual concept with value semantics (e.g. a function that accepts an object of virtual concept type by value), the compiler needs to know the size of that object. So for instance, in order to compile the following:

void foo(C obj)
{
   std::cout << obj.bar();
}

The compiler needs to know the size of "obj". According to my current implementation technique, the size of "obj" is "one pointer + the size of the argument to foo()", but the latter is known only at call site - possibly in a different translation unit; so that won't work.

*** (SOLUTION) ***

I think it makes sense to always have objects of virtual concept type represented by a pair of pointers: the first pointer ("optr") is the pointer to the object which is being accessed polymorphically (and which is also the result of "&obj"), whereas the second pointer ("iptr") is the pointer to the itable. This gives "obj" a fixed size - twice a pointer size.

Then, when compiling a function call like the following:

int main()
{
    int x = 42;
    foo(x);
}

The compiler will copy-construct "x" into an unnamed object on the stack; the argument "obj" will have the "optr" pointing to that unnamed object, and the "iptr" pointing to the itable of "int" for C. The unnamed object will be destroyed when the call to foo() returns. Likewise, when copy-constructing an object:

int main()
{
    int x = 42;
    C obj = x;
    std::cout << obj.bar();
}

The "optr" of "obj" will point to an unnamed object copy-constructed from "x". That object will be destroyed when "x" gets destroyed.

Open issue: how to make this work for the initialization of non-static data members of non-reference, non-pointer concept type (we can't just create the unnamed object on the stack, because the embedding object might have dynamic storage duration)? How could the compiler do the magic? Or shall we forbid this (I'd rather allow it, for orthogonality)?

When the concept object being initialized has reference or pointer type, on the other hand, no copy-construction is involved and no "unnamed" object needs to be created.

I updated the draft accordingly: http://bit.ly/ZgruFY.

Kind regards,

Andy

[Vicente J. Botet Escriba]

Le 26/09/14 21:01, Andy Prowl a écrit :

Hi,

I think the idea is in general useful, and surely need a lot of refinements.
However the name virtual concept is not really good and the implementation can surely be improved, but I don't think the implementation is the most important part for the time been. Anyway a type erased implementation with an additional adaptor to do the mapping, seems more understandable to me.
What I think is important is what we want to be able to do.

Your virtual concept could be related to abstract data types (http://en.wikipedia.org/wiki/Abstract_data_type).
Type erasure usually has value semantics, but it is possible to give it reference or pointer semantics also.
 
Do you expect x to be deleted after a call to delete c in the following example?

X* xptr = new X;
C* c = xptr;
c->foo();
delete c

If this is the case, you need a way to state it explicitly on the virtual concept definition.

BTW, why do you need that

 C& cx = x;
 assert(&cx == &x);

?
Note that as C is not really a class, the assertion must not forcedly be implied.

Could virtual concepts inherit from other virtual concepts?



Vicente

[Andy Prowl]

Hi Vicente,

Thank you for sharing your thoughts. I will try to address your points in the following.

1. I am not particularly attached to the name "virtual concept". In Haskell there is something very similar which is called "typeclass", so I could have used that name. On the other hand, the old C++0x idea of "concept maps" was also something pretty similar, except for the fact that they were meant for template-based compile-time polymorphism (just like Concepts Lite), while my goal was to provide a mechanism for non-intrusive dynamic polymorphism. I picked the name "concept" to evoke the parallel with concept maps, and the adjective "virtual" to draw a connection with virtual call dispatch. But this is really a detail to me, so I'm open to suggestions for a better terminology.

2. In your example, I do expect "x" to be deleted when doing "delete c". My original idea was that all virtual concepts should implicitly support destruction as part of the interface they define, and the every itable would contain an entry for the corresponding type's instantiation pointing to that type's destructor. However, I could as well require the destructor to be explicitly mentioned in the virtual concept's definition as a prerequisite for writing "delete c" (but also for using objects of concept type with value semantics, since objects with automatic storage duration are implicitly destroyed when they go out of scope). For other special operations, like copy-construction, I require the corresponding special member function to be explicitly mentioned in the concept definition (see the draft I linked).

3. The reason why I think the assertion (&cx == &x) should not fail is that I want to enable reference semantics. Judging from what you write, I am now led to think that satisfying this assertion is not a necessary condition for achieving my goal. Anyway, my idea is that if a client stores a pointer to a virtual concept (say, "C* pc"), and later wants to figure out if the object pointed to by "pc" is the same object as another object pointed to by "px" (of type "T*", where "T" has an instantiation for "C"), it may do so by checking whether (pc == px). I thought special support from the compiler would be necessary to realize this, and that implementation would be the toughest obstacle - that's why I am trying to tackle it since the beginning. Please let me know if I am mistaken.

4. I do find it reasonable to allow virtual concepts to derive from other virtual concepts, but so far I haven't really thought through this in detail. In fact, when I opened this thread I considered it quite likely that my idea would be immediately classified as unfeasible by the experts, so I didn't want to invest time and effort on a full-blown proposal before getting some feedback.

Concerning the use of techniques based on type erasure (with which I am only mildly familiar from the technical viewpoint), one of my goals is to make code using virtual concepts compile fast (ideally as fast as code using traditional inheritance-based polymorphism). This is why I would avoid library solutions such as Boost.TypeErasure, because they will likely be heavily based on templates, and that does have a significant impact on build time - and readability as well, unless macros are used, but I personally dislike macros.

Kind regards,

Andy

[Andy Prowl]

BTW, some related literature:

 - Paper "Runtime Polymorphic Generic Programming [...]" by Mat Marcus, Jaakko Järvi, and Sean Parent: http://www.emarcus.org/papers/MPOOL2007-marcus.pdf

 - Slides of a presentation by Sean Parent on Adobe.Poly: http://stlab.adobe.com/wiki/images/c/c9/Boost_poly.pdf

 - Sean Parent's talk "Value Semantics and Concepts-based Polymorphism": https://www.youtube.com/watch?v=_BpMYeUFXv8

 - Sean Parent's talk "C++ Seasoning" @ GoingNative 2013: http://channel9.msdn.com/Events/GoingNative/2013/Cpp-Seasoning

 - Sean Parent's talk "Inheritance Is The Base Class of Evil" @ GoingNative 2013: http://channel9.msdn.com/Events/GoingNative/2013/Inheritance-Is-The-Base-Class-of-Evil

 - Poly library by Pyry Jahkola: https://github.com/pyrtsa/poly

Kind regards,

Andy

[Vicente J. Botet Escriba]

Le 27/09/14 17:39, Andy Prowl a écrit :

Hi Vicente,

Thank you for sharing your thoughts. I will try to address your points in the following.

Sorry if my replay is too long and not clear enough.

1. I am not particularly attached to the name "virtual concept". In Haskell there is something very similar which is called "typeclass", so I could have used that name. On the other hand, the old C++0x idea of "concept maps" was also something pretty similar, except for the fact that they were meant for template-based compile-time polymorphism (just like Concepts Lite), while my goal was to provide a mechanism for non-intrusive dynamic polymorphism. I picked the name "concept" to evoke the parallel with concept maps, and the adjective "virtual" to draw a connection with virtual call dispatch. But this is really a detail to me, so I'm open to suggestions for a better terminology.

What you are proposing (locking for) is close to Haskell type classes, but I don't think that it is possible to instantiate type classes (as objects) in Haskell, Type class instances are the data type for which there is a mapping. I believe that the user instantiate data types and use the operations of the type class via the data type -> type class mapping. Haskell type classes are much closer to concepts than what you propose.

I would not use the name Concept as a Concept is not limited to a set of functions. Abstract data types are more function oriented, this is way I suggested this name. ADA abstract data types provide something similar to what you are proposing IIRC. I don't know if we can take the address of an abstract data type instance in ADA :(

You could also take a look at Java Generics as the compiler uses type erasure to generate one compiled version of each generic class.

2. In your example, I do expect "x" to be deleted when doing "delete c". My original idea was that all virtual concepts should implicitly support destruction as part of the interface they define, and the every itable would contain an entry for the corresponding type's instantiation pointing to that type's destructor. However, I could as well require the destructor to be explicitly mentioned in the virtual concept's definition as a prerequisite for writing "delete c" (but also for using objects of concept type with value semantics, since objects with automatic storage duration are implicitly destroyed when they go out of scope). For other special operations, like copy-construction, I require the corresponding special member function to be explicitly mentioned in the concept definition (see the draft I linked).

I read the draft before posting. With value semantics, there is nothing to delete (at least at the user level), only to destroy. As the virtual concept knows exactly what type is stored (type erased) , I don't see why the stored types must define a virtual destructor. Am I missing something?

3. The reason why I think the assertion (&cx == &x) should not fail is that I want to enable reference semantics. Judging from what you write, I am now led to think that satisfying this assertion is not a necessary condition for achieving my goal.

I think that adding this requirement would make things more complex than needed.

Anyway, my idea is that if a client stores a pointer to a virtual concept (say, "C* pc"), and later wants to figure out if the object pointed to by "pc" is the same object as another object pointed to by "px" (of type "T*", where "T" has an instantiation for "C"), it may do so by checking whether (pc == px).

yes, this is tempting, an maybe desirable. The question is whether we want to check if the virtual concept pointer points to the same memory address as the pointer to the type or just to be able to compare them.  The operator== between pointers to virtual concept and a pointers to types can be defined, without forcing that they have the same physical address.

template <class M>
bool operator==(const C* x, const  M* y) {
  return __underlying_ptr(x) == y; // pointer semantics
}

where __underlying_ptr is an intrinsic that the compiler could reach to manage. Is if a C* was implemented as a smart pointer.

The operator& on virtual concepts could also be defined using the same intrinsic.

I'm not really happy with this however.

I thought special support from the compiler would be necessary to realize this, and that implementation would be the toughest obstacle - that's why I am trying to tackle it since the beginning. Please let me know if I am mistaken.

I really don't know.
If I were using a smart pointer approach to implement a virtual concept with pointer semantics let me call it virtual_concept_ptr<C>, I would expect the following

X x;;
X* px;;
px = &x;
virtual_concept_ptr<C> pc(px);
assertion (pc == px)

But if I have a virtual concept with value semantics, let me call it virtual_concept_value<C>,

virtual_concept_value<C> c(x);
virtual_concept_value<C>* pc = &c;

The following comparison has no sens as we are using value semantics.

assertion (pc == &x)

But the following would have a sense

assertion (*pc == x)


The difference between virtual_concept_ptr<C> and virtual_concept<C>*, is that the  virtual_concept_ptr<C> has pointer semantic, while  virtual_concept<C>* has value semantic, even if we are using a pointer. That is, virtual_concept_ptr<C> is not the same as virtual_concept<C>*

When we rewrite the previous using directly virtual concepts

X x;;
X* px;;
px = &x;
C* pc; // (1)
pc =px;


C c(x);
C* pc; // (2)
pc = &c;

The question is how do we interpret the C* pc; declaration. Has the concept C value or pointer semantics? I don't have a response. That could mean that, at the language level, we would need to consider different syntax to represent the different semantics. This wouldn't fit well with c++. So IMO, the type erased type must have value semantics. If we want a virtual concept with pointer semantics, the virtual concept must define the operations 'pointer' operations and accept only 'pointers' as a smart pointer.

4. I do find it reasonable to allow virtual concepts to derive from other virtual concepts, but so far I haven't really thought through this in detail. In fact, when I opened this thread I considered it quite likely that my idea would be immediately classified as unfeasible by the experts, so I didn't want to invest time and effort on a full-blown proposal before getting some feedback.

I believe that the experts have not talk yet ;-)

Concerning the use of techniques based on type erasure (with which I am only mildly familiar from the technical viewpoint), one of my goals is to make code using virtual concepts compile fast (ideally as fast as code using traditional inheritance-based polymorphism). This is why I would avoid library solutions such as Boost.TypeErasure, because they will likely be heavily based on templates, and that does have a significant impact on build time - and readability as well, unless macros are used, but I personally dislike macros.

I can understand that you want to avoid Boost.TypeErasure. For me type erasure is not associated to a library solution. It can be associated to the language and the compiler can do it better than a library. When I said that a type erasure implementation could be appropriated, I should said instead that your proposal fits naturally with a type erased model. Just you're locking for pointer semantics. Maybe it is worth considering a virtual concept (with value semantics) that is a pointer to another virtual concept.

Resuming, I believe that introducing in the language type erased types with value semantics will already be a good goal.
 
Vicente

[Klaim - Joël Lamotte]

​Hi, I think the initial idea have some merits but proposing to modify the class definitions to adhere to a "virtual concept" seems going backward to me.

In any way it made me realize the following, just pure ideas that might be useful to someone around here.

Let's assume that we have 
 1. concepts (as defined in the last proposals from Sutton & Stroustrup & others)

 2. reflection on concepts (at least ways to generate code from patterns depending on the properties of a concept)

 3. a way to ask for a concept in a template definition (not a type matching the concept, an actual concept)

Then it would be possible to build library types that can, for example, do the same work as proposed here. Something like:

   void some_work( C<Iterator> it ); // concrete function, C<Iterator> is a concrete type.

In this case C would be a template class which interface would look like:

    template< concept K >

    class C

    {

    public:

        // ...

        C( K&& value ); // actually a template constructor using the concept K

        C& operator=( K&& value );  /// actually a template assignment operator using the concept K

    private:

        /// code using reflection to generate the type-erasing code

        /// following the concept constraints to generate a type

    };

...

Now, thinking about this while writing it, having a way to just generate an anonymous type that would

follow the provided concept would be useful to generate type-erasure...

End of ideas.

[Ville Voutilainen]

On 28 September 2014 20:03, Klaim - Joël Lamotte <mjk...@gmail.com> wrote:
>
> Hi, I think the initial idea have some merits but proposing to modify the
> class definitions to adhere to a "virtual concept" seems going backward to
> me.
> In any way it made me realize the following, just pure ideas that might be
> useful to someone around here.
>
> Let's assume that we have
> 1. concepts (as defined in the last proposals from Sutton & Stroustrup &
> others)
> 2. reflection on concepts (at least ways to generate code from patterns
> depending on the properties of a concept)
> 3. a way to ask for a concept in a template definition (not a type matching
> the concept, an actual concept)
>
> Then it would be possible to build library types that can, for example, do
> the same work as proposed here. Something like:

I don't see why this idea needs concepts or reflection of concepts. If we have
reflection, it's quite simple to create an adapter template that derives from
the interface (aka the 'virtual concept', which we probably don't need to add
as a separate facility at all), and uses reflection to call the right signature
in the target class in the adapter's overrides of the interface
virtuals. The rest of it is
wrapping the objects of the target class type in the adapters where necessary.

[Andy Prowl]

@Vicente:

My post was long, so it's natural for your answer to be long as well. No need to apologize :)

Haskell is a very different language from C++, so analogies can only go that far. There are no "references" and "pointers" there, no modifiable "objects", so the parallel with type classes is mostly illustrative. However, I do believe that it makes sense to have objects "of virtual concept type" which, as I propose, would be represented in memory as pairs of pointers.

Honestly, the more I think about it, the more I believe the name "concept" is quite fitting. The analogy with compile-time concepts is very strong, and in fact I wrote another draft of the proposal that uses the same (or very similar) syntax. Accordingly, virtual concept instantiations are now introduced as "virtual concept maps".

Please have a look at the latest version, which you can find here: http://bit.ly/ZgruFY.

Concerning to value semantics: deletion is necessary "under the hood", because dynamic allocation is (often) required when passing type-erased objects by value (module SBO). Please refer to the latest draft for the details (section "Implementation technique").

I also considered the possibility of having a concept_ptr_ref<C> and a concept_ptr_value<C>, but I found this unnecessary and I could not foresee all the implications. Using C*, C&, or C is just more natural, and the implementation I propose seems to be relatively easy (I consulted this with a "compiler guy").
That would also allow performing pointer comparison, which (as you write) is tempting/desirable. It also does not require different syntax for supporting reference semantics vs. value semantics.

Kind regards,

Andy

[Andy Prowl]

@Ville:

Thank you for sharing your thoughts.

Due to my lack of knowledge I cannot say I understand your point about reflection, so I have a few questions:

1. Would the performance of a function call dispatch with a machinery involving reflection be comparable to that of a call through a vtable?

2. Given "concept" (or whatever we call it) C such that "x.foo()" is valid when "x" is instance of a model of C, would your approach allow writing something like this? 

X x;
C* c = &x;

c->foo();
assert(&c == &x);
C c = x;
c.foo();

3. Is the "adaptation" you write about something that could be written "once and for all" and made part of the standard library (provided we have reflection, of course), or is the user supposed to code it for their own types/concepts? Would it require fiddling with templates and/or macros? 

4. Do we have a proposal for reflection? The one I have seen one some time ago (http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2014/n3951.pdf) did not seem very mature to me.

Kind regards,

Andrea

[Andy Prowl]

@Joël:

Perhaps there has been a misunderstanding, I am not proposing to modify class definitions to adhere to a "virtual concept". In fact, what I am proposing is a non-intrusive mechanism for runtime polymorphism.

What possibly led you to think the mechanism was intrusive may have been the syntax I used for introducing concept instantiations. I have changed that in the last version of my draft to mirror the syntax of C++0x (compile-time) concept maps. You can find the last version here: http://bit.ly/ZgruFY.

For what concerns the rest of your post, I have trouble understanding the reflection-related logic in comments it due to my lack of knowledge about reflection, but in general I think that this feature does not require reflection and can be efficiently implemented without it (see the draft).

Kind regards,

Andy

[Ville Voutilainen]

On 28 September 2014 21:33, Andy Prowl <andy....@gmail.com> wrote:
> @Ville:
> Thank you for sharing your thoughts.
> Due to my lack of knowledge I cannot say I understand your point about
> reflection, so I have a few questions:
> 1. Would the performance of a function call dispatch with a machinery
> involving reflection be comparable to that of a call through a vtable?

The call of the interface/"virtual concept" function is virtual, the forwarding
of that from the adapter is a non-virtual call that may or may not be inlined
depending on whether the function called is inline.

> 2. Given "concept" (or whatever we call it) C such that "x.foo()" is valid
> when "x" is instance of a model of C, would your approach allow writing
> something like this?
>
> X x;
> C* c = &x;
> c->foo();
> assert(&c == &x);
> C c = x;
> c.foo();

Probably not. You would need to do something like
X x;
CWrap<X> cwx{x};
C* c = &cwx;
c->foo();
// the assertion for address equality would be false
C& c2 = cwx;

c.foo();

> 3. Is the "adaptation" you write about something that could be written "once
> and for all" and made part of the standard library (provided we have
> reflection, of course), or is the user supposed to code it for their own
> types/concepts? Would it require fiddling with templates and/or macros?

We don't have a facility for generating overrides for the
interface/virtual-concept
functions, so we can't make an adapter fully generic. You don't need any
macros, and you don't have to use templates if you don't want to, but making
such adapters more generic will benefit from templates. So, unless reflection
gains the capability of being able to generate overrides for base
class functions,
you would have to adapt your own types. Reflection helps with the adaptation
and can make it more generic when combined with templates, but at least in
its proposed form it can't make it fully generic/automatic.

> 4. Do we have a proposal for reflection? The one I have seen one some time
> ago (http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2014/n3951.pdf) did
> not seem very mature to me.

See
http://open-std.org/JTC1/SC22/WG21/docs/papers/2014/n4113.pdf

[Ville Voutilainen]

On 28 September 2014 22:10, Ville Voutilainen

<ville.vo...@gmail.com> wrote:
> Probably not. You would need to do something like
> X x;
> CWrap<X> cwx{x};
> C* c = &cwx;
> c->foo();
> // the assertion for address equality would be false
> C& c2 = cwx;
> c.foo();

That last bit should be c2.foo().

[Andy Prowl]

@Ville: Thank you for your explanation. Please find my comments below (I'm new to this forum so I hope I'm not screwing up formatting or something).

On Sunday, September 28, 2014 9:10:09 PM UTC+2, Ville Voutilainen wrote:

On 28 September 2014 21:33, Andy Prowl <andy....@gmail.com> wrote:
> @Ville:
> Thank you for sharing your thoughts.
> Due to my lack of knowledge I cannot say I understand your point about
> reflection, so I have a few questions:
> 1. Would the performance of a function call dispatch with a machinery
> involving reflection be comparable to that of a call through a vtable?

The call of the interface/"virtual concept" function is virtual, the forwarding
of that from the adapter is a non-virtual call that may or may not be inlined
depending on whether the function called is inline.

Are you not describing something similar to the concept/model approach outlined here (slide 24): http://stlab.adobe.com/wiki/images/c/c9/Boost_poly.pdf? I do realize that this mechanism requires one virtual dispatch + one regular function call (in fact, this is pretty much what my proposal boils down to for value semantics, except it's all done by the compiler), but I see no reflection involved. I am particularly concerned with run-time reflection, but perhaps it's compile-time reflection you are talking about. If that's the case, sorry for the misunderstanding. Always assuming we're talking about compile-time reflection, does it mean that reflection would be used to generate the concept/model types?

 

> 2. Given "concept" (or whatever we call it) C such that "x.foo()" is valid
> when "x" is instance of a model of C, would your approach allow writing
> something like this?
>
> X x;
> C* c = &x;
> c->foo();
> assert(&c == &x);
> C c = x;
> c.foo();

Probably not. You would need to do something like
X x;
CWrap<X> cwx{x};
C* c = &cwx;
c->foo();
// the assertion for address equality would be false
C& c2 = cwx;
c.foo();

OK, so it seems to me (no arrogance intended) that the solution based on reflection is not as powerful as the mechanism I am proposing, nor as natural/easy to use.
 

> 3. Is the "adaptation" you write about something that could be written "once
> and for all" and made part of the standard library (provided we have
> reflection, of course), or is the user supposed to code it for their own
> types/concepts? Would it require fiddling with templates and/or macros?

We don't have a facility for generating overrides for the
interface/virtual-concept
functions, so we can't make an adapter fully generic. You don't need any
macros, and you don't have to use templates if you don't want to, but making
such adapters more generic will benefit from templates. So, unless reflection
gains the capability of being able to generate overrides for base
class functions,
you would have to adapt your own types. Reflection helps with the adaptation
and can make it more generic when combined with templates, but at least in
its proposed form it can't make it fully generic/automatic. 

 
Same observation as above: this requires the user to write some boilerplate code. I can imagine the burden could be reduced by extracting a generic part of this boilerplate code into some template facility, but this affects both readability/maintainability and build times. One of the design goals for my proposal is to have build times comparable to those that interface-based polymorphism offers. Isn't this approach going to make build times rather comparable with those of using a library solution like Boost.TypeErasure?

> 4. Do we have a proposal for reflection? The one I have seen one some time
> ago (http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2014/n3951.pdf) did
> not seem very mature to me.

See
http://open-std.org/JTC1/SC22/WG21/docs/papers/2014/n4113.pdf

Thank you,

Andy 

[Ville Voutilainen]

On 28 September 2014 22:31, Andy Prowl <andy....@gmail.com> wrote:
> Are you not describing something similar to the concept/model approach
> outlined here (slide 24):
> http://stlab.adobe.com/wiki/images/c/c9/Boost_poly.pdf? I do realize that
> this mechanism requires one virtual dispatch + one regular function call (in
> fact, this is pretty much what my proposal boils down to for value
> semantics, except it's all done by the compiler), but I see no reflection
> involved. I am particularly concerned with run-time reflection, but perhaps

Correct, as things are now, there's no reflection involved. Chances are that
reflection will cut down on the boilerplate necessary and make things more
general.

> it's compile-time reflection you are talking about. If that's the case,

Compile-time, completely.

> OK, so it seems to me (no arrogance intended) that the solution based on
> reflection is not as powerful as the mechanism I am proposing, nor as
> natural/easy to use.

The example I showed can be written today, without reflection. It's not
as powerful as your proposal, but it's nowhere close as intrusive - it
needs no additions to the language at all. Yet it covers most of the
cases such "runtime concepts" are after, which are mostly post-hoc
adaptation of existing classes into new interfaces.

> Same observation as above: this requires the user to write some boilerplate
> code. I can imagine the burden could be reduced by extracting a generic part

Sure, but even your proposal is not free of boilerplate.

[Andy Prowl]

Thank you for your comments Ville.

You're right, my proposal is "intrusive" in the sense that it requires additions to the language, and the example you refer to can be written today with libraries like Adobe.Poly or Boost.TypeErasure; on the other hand, those libraries are not really easy to use, lead to higher build times due to the template machinery, and are not as powerful as the mechanism I am proposing.

Adobe.Poly is (AFAICT) only concerned with value semantics and not very well-documented, whereas Boost.TypeErasure only supports duck-typing. There is also Pyry Jahkola's Poly (https://github.com/pyrtsa/poly), which looks good, but as the author writes, it is "a proof-of-concept, probably too early or fragile for production use yet.".

Unless I'm overlooking something, my proposal does not suffer from these limitations, it provides a *simple* way for users to define their own concepts, generalizing things like std::function and std::any in a uniform and efficient way, and it draws a nice parallel with compile-time concepts. This is in principle a simple thing: we should have tools that make it simple.

As a final remark, I have troubles understanding your statement that "[my] proposal is not free of boilerplate": I think it is. The user has to provide only minimal information in order to define virtual concepts and their instantiations, and doesn't need to make use of anything like "concept_ptr<C>", "poly::self", "type_erasure::self", "wrap<C>", etc. No need to write adapters and wrappers either, no need to deal with templates, and (quite importantly) no need to deal with obscure compiler errors when they do something wrong.

Kind regards,

Andy

[Andy Prowl]

@Vicente:

As a further element in favor of adopting the name "concept", I found two references about "runtime concept" (pretty much the same idea). 

One is a wiki page from Adobe: http://stlab.adobe.com/wiki/index.php/Runtime_Concepts.

The other one is a paper by Bjarne Stroustrup, Sean Parent, and others: http://www.stroustrup.com/oops08.pdf.

Kind regards,

Andy

[Ville Voutilainen]

On 29 September 2014 00:14, Andy Prowl <andy....@gmail.com> wrote:
> Thank you for your comments Ville.
>
> You're right, my proposal is "intrusive" in the sense that it requires
> additions to the language, and the example you refer to can be written today
> with libraries like Adobe.Poly or Boost.TypeErasure; on the other hand,
> those libraries are not really easy to use, lead to higher build times due
> to the template machinery, and are not as powerful as the mechanism I am
> proposing.

The proposal might end up being more intrusive than just requiring a language
change; see the very end of this email.

> Adobe.Poly is (AFAICT) only concerned with value semantics and not very
> well-documented, whereas Boost.TypeErasure only supports duck-typing. There
> is also Pyry Jahkola's Poly (https://github.com/pyrtsa/poly), which looks
> good, but as the author writes, it is "a proof-of-concept, probably too
> early or fragile for production use yet.".
> Unless I'm overlooking something, my proposal does not suffer from these
> limitations, it provides a *simple* way for users to define their own
> concepts, generalizing things like std::function and std::any in a uniform
> and efficient way, and it draws a nice parallel with compile-time concepts.
> This is in principle a simple thing: we should have tools that make it
> simple.

No disagreement there - _as long as_ we are adding such tools for cases that
are commonly needed. I'm not sure whether run-time concepts of any kind are
so common. Note that there's nothing more to it - I'm not sure. I'm neither for
or against them, strongly, I'm just not sure. ;)

> As a final remark, I have troubles understanding your statement that "[my]
> proposal is not free of boilerplate": I think it is. The user has to provide
> only minimal information in order to define virtual concepts and their
> instantiations, and doesn't need to make use of anything like
> "concept_ptr<C>", "poly::self", "type_erasure::self", "wrap<C>", etc. No
> need to write adapters and wrappers either, no need to deal with templates,
> and (quite importantly) no need to deal with obscure compiler errors when
> they do something wrong.

The boilerplate comes in when I want to turn existing base classes that act
as abstract interfaces into these new virtual concepts. I have a
plethora of them,
and they are the things I want new classes to adapt to, somehow. So.. now I go
and turn them into virtual concepts. I have now modified the very fundamental
headers of many of my systems, and this causes a rebuild of "the
world". Furthermore,
these fundamental classes still need to work with pre-c++17 code, so I need
to macro them to be either the classes they used to be or virtual concepts.

*That* is very intrusive. With the current approaches, however less
powerful they may
be, I do not have to modify the base class at all, nor do I have to
modify the target
class, at all. All I need to write is external adaptation code. I
would much prefer a
solution that provides easy post-hoc adaptation while keeping the
adaptees intact,
without requiring intrusive modification to them.

[Andy Prowl]

OK, I think I need to put this in more concrete terms in order to understand your last example - please bear with me and forgive me if it's going to be a bit lengthy. Say we have an abstract interface IFoo and classes A and B which implement it:

class IFoo
{
public:
    virtual ~I() = default;
    virtual void foo() = 0;
};

class A : public IFoo
{
    virtual void foo() override { /* ... whatever ... */ }
    void bar() { /* ... something else ... */ }
};

class B : public IFoo
{
    virtual void foo() override { /* ... whatever ... */ }
    void bar() { /* ... something else ... */ }
};

And a polymorphic algorithm that works with objects of type IFoo:

void poly_foo(IFoo& obj)
{
    obj.foo();
}

Now say we want to write another polymorphic algorithm, poly_bar(), that needs to call bar() on its argument, and its argument may be an A or a B. We have a few options, but let's assume we decide to use virtual concepts. All we have to do is (1) define a new concept (say, "BarConcept"), (2) provide an instantiation of BarConcept for A and one for B, possibly using "= default" to minimize the work and enable duck-typing, and (3) let our new poly_bar() algorithm take a BarConcept&:

template<typename T>
virtual concept bool BarConcept()
{
    return requires(T obj)
    {
        { bar(); } -> void;
    };
}

virtual concept map BarConcept<A> = default;

virtual concept map BarConcept<B> = default;

void poly_bar(BarConcept& obj)
{
    obj.bar();
}

No need to touch or recompile any of the existing code so far.

Now of course if we wanted to modify our *existing* algorithm poly_foo() to work with concepts rather than with an abstract interface, then we will have to modify poly_foo() and recompile its clients.

Similarly, if we wanted to *turn* our existing IFoo into a virtual concept, we would have to modify IFoo as well as A and B and recompile all of their clients, but I do not see how any of the library solutions we've been referring to so far will help with that in general. Am I missing something?

Thank you,

Andy

[Andrzej Krzemieński]

Hi Andy,
The field of  your investigation is sure interesting and useful. This sort of thing is definitely needed. Even if it can be acheived by other means, adding a dedicated feature into the language might encourage people to use it.  I am not convinced if concept maps are that useful. What is the difference between defining a concept map and defining a "wrapper" class? Also, it looks from your paper that the binding of a type to a virtual concept does not work unless I explicitly declare it with a (possibly defaulted) concept map. Am I right? This would be a big inconvenience. This is what the original concepts were criticized for.

Also, inside the concept maps, how the visibility of names work? I mean, does normal ADL work? Which namespaces are accessible? Can I call other static member functions unqualified. Can I see fiunctions in the enclosing namespace scope?

The paper lists the following definition

template<typename T> virtual concept bool C() { return requires(T x) {
 { x.foo(C& obj) } -> void;
}; }

Should it not read:

template<typename T> virtual concept bool C() { return requires(T x) {
 { x.foo(obj) } -> void;
}; }

ALso, the examples only talk about member functions. In contrast, both Concepts Lite and other type erasure libraries allow to define the interface in terms of non-member functions:

requires(T v, T w)
{
  { transform(v) } -> T;
  { cmp(v, w) } -> bool;
}

Do you intend the above to be expressible with virtual concepts?

Regards,
&rzej

[Andy Prowl]

Hi Andrzej, 

Thank you for sharing your thoughts. This idea I'm working on is in a very preliminary state, and many things are still unclear to me - although I am convinced that we should have language support for making type erasure technically simple(r). The draft probably contains gross mistakes - like the one you spotted with "x.foo(C& c)", thank you for that - and/or other kinds of imprecision.

For instance, today I realized that the "requires-expression" I adopted for concept definitions won't work for run-time concepts, because the definitions of the satisfying types may not be visible at compile-time at the point where a concept is used, and therefore the dispatch mechanism requires knowing the exact signature of the concept's functions. So I made a step back and defined concepts as a list of (member) functions to be supported (the latest version is available here: http://bit.ly/ZgruFY).

Concerning free functions, yes I would definitely like to add support for them, but I haven't thought through this use case deep enough, and it is not clear to me at the moment how to implement them (I'm particularly scared by possible interplay with stuff like multi-methods, but I'm just hand-waving here). I would like to add support for data members too, but I'm not sure whether that's possible either.

Regarding ADL, I would say inside a concept map ADL should work just as it does outside of it, but I am aware that ADL is an extremely tricky topic, and its details keeps surprising me times and times again. So for the moment I'm making the arguably childish decision of ignoring those details and see how far I can get :)

Finally, I think concept maps can be either desirable or annoying depending on the use case. Duck-typing is definitely feasible and could be supported by decorating the concept definition with a [[ducktype]] attribute, or by any other means. That would make it unnecessary to define concept maps, and the modeling relation between a type and a concept would be inferred by syntactic matching of function signatures.

On the other hand, concept maps (like Haskell's type classes) allow for more flexibility: you can freely design your types without caring about syntactic requirements imposed by polymorphic algorithms (both the existing ones and the ones yet to come), since you can provide adaptation when needed. The difference between a concept map and an adapter class mostly comes into play when using reference semantics. Say I have a concept C and a type X that models it. My idea is to allow this:

X x;
C& c = x;
assert(addressof(c) == addressof(x));

The presence of an adapter class would make the assertion above fail, while it would succeed with concept maps (thanks to compiler magic). Some have commented that this is not a fundamental feature, and that might be true. But even without it, it seems to me that concept maps reduce the amount of boilerplate (especially template) code that users would have to write, and improve readability.

Kind regards,

Andy

[Vicente J. Botet Escriba]

Le 28/09/14 23:14, Andy Prowl a écrit :

> Thank you for your comments Ville.
>
> You're right, my proposal is "intrusive" in the sense that it requires
> additions to the language, and the example you refer to can be written
> today with libraries like Adobe.Poly or Boost.TypeErasure; on the
> other hand, those libraries are not really easy to use, lead to higher
> build times due to the template machinery, and are not as powerful as
> the mechanism I am proposing.

What do you find complex to use with Adobe.Poly?

>
> Adobe.Poly is (AFAICT) only concerned with value semantics and not
> very well-documented, whereas Boost.TypeErasure only supports
> duck-typing. There is also Pyry Jahkola's Poly
> (https://github.com/pyrtsa/poly), which looks good, but as the author
> writes, it is "a proof-of-concept, probably too early or fragile for
> production use yet.".
>

Well I'm sure that a Poly proposal will be welcome to the standard. It
is far easier to make a concrete proposal of a library than changing the
language.

> Unless I'm overlooking something, my proposal does not suffer from
> these limitations, it provides a *simple* way for users to define
> their own concepts, generalizing things like std::function and
> std::any in a uniform and efficient way, and it draws a nice parallel
> with compile-time concepts. This is in principle a simple thing: we
> should have tools that make it simple.

You proposal is far from been ready ;-). Usually languages proposals
have a probe of concept with a specific compiler in order to see if this
is doable and how this could improve the performances respect to a
library solution.

All this doesn't mean that I'm against the idea.

Vicente

[Vicente J. Botet Escriba]

Le 29/09/14 10:42, Andrzej Krzemieński a écrit :

W dniu czwartek, 25 września 2014 21:40:15 UTC+2 użytkownik Andy Prowl napisał:

Hello everyone,

I would like to ask for feedback concerning this idea I had about non-intrusive "dynamic" polymorphism:

https://www.dropbox.com/s/tg737sf8sj1p1ht/Virtual%20concepts%20for%20polymorphic%20types.pdf?dl=1

This is just a rough sketch, please do not expect any full-blown proposal. My goal is to find out whether it makes sense to invest more time on it, or if the idea is basically bull***t.

A few highlights:

1. The idea is about introducing non-intrusive support for dynamic polymorphism (similar to Haskell's typeclasses);
2. The idea is similar to the old C++0x "concept maps", but is *not* related to templates;
3. Code using a "virtual concept" can be compiled separately and does not need to see the definition of the instances of that concept.

Hi Andy,
The field of  your investigation is sure interesting and useful. This sort of thing is definitely needed. Even if it can be acheived by other means, adding a dedicated feature into the language might encourage people to use it.  I am not convinced if concept maps are that useful. What is the difference between defining a concept map and defining a "wrapper" class?

I would say that this it is the same as between type traits and a "wrapper" class.

Also, it looks from your paper that the binding of a type to a virtual concept does not work unless I explicitly declare it with a (possibly defaulted) concept map. Am I right? This would be a big inconvenience. This is what the original concepts were criticized for.

I'm absolutely for an explicit mapping. This doesn't mean that you couldn't say that given a type has a concept map for C1, a concept map for C2 can not be implied.

Also, inside the concept maps, how the visibility of names work? I mean, does normal ADL work? Which namespaces are accessible? Can I call other static member functions unqualified. Can I see fiunctions in the enclosing namespace scope?

These are all valid questions a proposal should answer.

ALso, the examples only talk about member functions. In contrast, both Concepts Lite and other type erasure libraries allow to define the interface in terms of non-member functions:

requires(T v, T w)
{
  { transform(v) } -> T;
  { cmp(v, w) } -> bool;
}

Do you intend the above to be expressible with virtual concepts?

Very good question. I don't think the proposal could take care of non-member functions in general, as the parameters of the non-member function could concern several types.


Vicente

[Andy Prowl]

Vicente,

You are right about my "proposal" being far from ready (in fact, I should rather call it an "idea"). However, with time I would like to grow it into a proposal, and I'm trying to collect useful comments, suggestions, and criticism through this discussion - which is happening. That helps me figuring out if it is worth investing some serious time on it.

You're also right about the necessity of backing up words with a prototype implementation, which is in fact one of the first things I thought of, and it is also the reason why I worried about possible implementation techniques since the beginning. At the moment, I believe hacking Clang would be the simplest way of coming up with a proof of principle. 

What I find complex about Adobe.Poly (apart from finding a good documentation and the latest version of the source code) is that (1) it requires defining boilerplate adaptation code (e.g. the PlaceableImplementation from the paper by Marcus, Jarvi, and Parent); (2) the user needs to deal with templates, just like with Boost.TypeErasure; (3) it does not allow for duck-typing (unless I'm missing something).

Kind regards,

Andy

[Vicente J. Botet Escriba]

Le 29/09/14 20:24, Andy Prowl a écrit :

> Vicente,
>
> You are right about my "proposal" being far from ready (in fact, I
> should rather call it an "idea"). However, with time I would like to
> grow it into a proposal, and I'm trying to collect useful comments,
> suggestions, and criticism through this discussion - which is
> happening. That helps me figuring out if it is worth investing some
> serious time on it.

I understand it perfectly.

>
> You're also right about the necessity of backing up words with a
> prototype implementation, which is in fact one of the first things I
> thought of, and it is also the reason why I worried about possible
> implementation techniques since the beginning. At the moment, I
> believe hacking Clang would be the simplest way of coming up with a
> proof of principle.
>

In case this can help. There is an old Signature feature project in gcc
[1,2] that is like your virtual concept, without mapping.

> What I find complex about Adobe.Poly (apart from finding a good
> documentation and the latest version of the source code) is that (1)
> it requires defining boilerplate adaptation code (e.g. the
> PlaceableImplementation from the paper by Marcus, Jarvi, and Parent);
> (2) the user needs to deal with templates, just like with
> Boost.TypeErasure; (3) it does not allow for duck-typing (unless I'm
> missing something).
>

Yes, Adobe::Poly, while ligther than Boost.TypeErasure on what concern
templates, it requires yet some boilerplate code. I guess that
compile-time reflection would help in genrating this boilerplate code.

I have found thatHaskell/Existentially quantified types [3] are quite
close to the virtual concept even it it needs to 'wrap an instance'
using a specific type contructor

Vicente

[1] http://bit.csc.lsu.edu/~gb/Signatures/index.html
[2] http://www.emerson.emory.edu/services/gcc/html/CPP_Signatures.html.
[3] http://en.wikibooks.org/wiki/Haskell/Existentially_quantified_types

[Andy Prowl]

Thank you for the references Vicente. I shall definitely look into Signatures. Agreed on existential types, which I should probably mention in the draft.

I am currently working on support for free functions, will link the next version here once I'm done (for some weak definition of "done").

Kind regards,

Andy

[Andrzej Krzemieński]

W dniu poniedziałek, 29 września 2014 20:24:02 UTC+2 użytkownik Andy Prowl napisał:

What I find complex about Adobe.Poly (apart from finding a good documentation and the latest version of the source code) is that (1) it requires defining boilerplate adaptation code (e.g. the PlaceableImplementation from the paper by Marcus, Jarvi, and Parent); (2) the user needs to deal with templates, just like with Boost.TypeErasure; (3) it does not allow for duck-typing (unless I'm missing something).

FWIW, I have compiled a short tutorial showing how to use Adobe.Poly and Boost.TypeErasure. They both support duck typing (as I understand it) and free functions:

http://akrzemi1.wordpress.com/2013/12/06/type-erasure-part-ii/

Regards,
&rzej

[Andy Prowl]

Hi Andzrej,

I read your (excellent) blog post, but judging from the use case you show, Adobe.Poly does not seem to support duck-typing: users have to write the adaptation logic for their types themselves (i.e. Counter and CounterImpl) - that's equivalent to using a concept map unless I'm missing something, just with more boilerplate code. 

Honestly, the more I look at the kind of sheganigans that are needed to work out type erasure using library solutions like Adobe.Poly and Boost.TypeErasure, the more I think that language support is fundamental.

I am now reworking my document into something more detailed, more formal, and closer to a draft. I think I have a solution that basically does what you suggest at the beginning of your blog post: take a concept definition (currently, from Concepts Lite) and let the compiler do the type-erasure magic. That means it will be possible to support free functions as well as static member functions. Not sure about data members at the moment.

I will link the draft here once I have a readable version of it.

Kind regards,

Andy

[Andrzej Krzemieński]

W dniu środa, 1 października 2014 21:42:26 UTC+2 użytkownik Andy Prowl napisał:

Hi Andzrej,

I read your (excellent) blog post, but judging from the use case you show, Adobe.Poly does not seem to support duck-typing: users have to write the adaptation logic for their types themselves (i.e. Counter and CounterImpl) - that's equivalent to using a concept map unless I'm missing something, just with more boilerplate code. 

No, you implement the two classes (Counter and CounterImpl) once per concept. The you can use just any type with this facility w/o any adaptation, as long as it has the operations defined in the concept.

Honestly, the more I look at the kind of sheganigans that are needed to work out type erasure using library solutions like Adobe.Poly and Boost.TypeErasure, the more I think that language support is fundamental.

I share your opinion. 

I am now reworking my document into something more detailed, more formal, and closer to a draft. I think I have a solution that basically does what you suggest at the beginning of your blog post: take a concept definition (currently, from Concepts Lite) and let the compiler do the type-erasure magic. That means it will be possible to support free functions as well as static member functions. Not sure about data members at the moment.

I wonder if it is even possible to do this for free functions that take two or more parameters of  type T. What do you do if the erased types mismatch. Boost.TypeErasure does it, but I have never enough patience to figure out how.

I will link the draft here once I have a readable version of it.

I can't wait to see it.

 

[Andy Prowl]

On Wednesday, October 1, 2014 10:06:36 PM UTC+2, Andrzej Krzemieński wrote:

W dniu środa, 1 października 2014 21:42:26 UTC+2 użytkownik Andy Prowl napisał:

Hi Andzrej,

I read your (excellent) blog post, but judging from the use case you show, Adobe.Poly does not seem to support duck-typing: users have to write the adaptation logic for their types themselves (i.e. Counter and CounterImpl) - that's equivalent to using a concept map unless I'm missing something, just with more boilerplate code. 

No, you implement the two classes (Counter and CounterImpl) once per concept. The you can use just any type with this facility w/o any adaptation, as long as it has the operations defined in the concept.

Oh, you're right. I overlooked that.
 

Honestly, the more I look at the kind of sheganigans that are needed to work out type erasure using library solutions like Adobe.Poly and Boost.TypeErasure, the more I think that language support is fundamental.

I share your opinion. 

I am now reworking my document into something more detailed, more formal, and closer to a draft. I think I have a solution that basically does what you suggest at the beginning of your blog post: take a concept definition (currently, from Concepts Lite) and let the compiler do the type-erasure magic. That means it will be possible to support free functions as well as static member functions. Not sure about data members at the moment.

I wonder if it is even possible to do this for free functions that take two or more parameters of  type T. What do you do if the erased types mismatch. Boost.TypeErasure does it, but I have never enough patience to figure out how.

Good point. I haven't thought about multimethods and possible implementations (I know there are some, at least Bjarne Stroustrup has a paper on that), but so far I was concerned mostly with situations where the two arguments of concept type are known to the compiler to be of the same instantiating type. 

When defining concepts I most often write this:

template<typename T>
virtual concept bool C()
{
    return requires(T x)
    {

        foo(x, x);
        // ...
    };
}

Here, function foo() is meant to accept instances of the same type. And if I write:

void bar(C& a, C& b)
{
    foo(a, b);
}

Then C would be bound to the same type, and I won't be able to call bar(x, y) if the compiler can't prove that x and y are of the same type.

Now if I have something like this (hypothetical template syntax for non-template functions, just to make sure a and b could refer to different types):

template<typename T, typename U>
virtual requires C<T>() && C<U>()
void bar(T& a, U& b)
{
    foo(a, b); // ERROR!
}

I will be able to call bar() with any pair of arguments that model C, but the compiler will stop me when trying to call foo(a, b).

At the moment I'm not able to come up with an example that would require multimethod-like dispatch, but I'm pretty sure there is. I shall definitely think about this. 

Thank you for your comments!

Andy

[Andy Prowl]

So I think I came up with a reasonably simple example. Say we have concepts C and D defined below:

template<typename T>
virtual concept bool D();

template<typename T>
virtual concept bool C()
{

    return requires(T x, D y)
    {
        foo(x, y);
        // ...
    };
}

template<typename T>
virtual concept bool D()
{
    return requires(C x, T y)
    {
        foo(x, y);
        // ...
    };
}

Also assume we have two classes, X (which models C), and Y (which models D). This means we have:

foo(X& x, D& d) { ... } // To make X a model of C

foo(C& c, Y& y) { ... } // To make Y a model of D

Now given the following function definition, supposing that x is bound to an X and y is bound to a Y:

void bar(C& x, D& y)
{
    foo(x, y); // WHAT TO CALL HERE?
}

Should we end up invoking foo(X, D) or rather foo(C, Y)? Clearly that depends on which argument we perform the dispatch through.

As it is, this call is ambiguous, and I tend to believe it should result in an error - another possibility would be to make an arbitrary choice and leave it up to the programmer to guarantee that foo(X, D) and foo(C, Y) do the same thing, otherwise UB will occur (but I don't like this option). 

I also wonder whether it makes sense to let the user disambiguate, and what would be a reasonable syntax.

[Andrzej Krzemieński]

Let's take a look like static polymorphism that uses templates solves this issue. Given the following three function templates:

template <typename T, typename U>

void fun(T t, U u);

template <typename T>
void fun(T t, int i);

template <typename U>
void fun(int i, U u);

If we try to pick one with two ints:

int i, j;
fun(i, j);

We get a compile-time ambiguity error. We can disambiguate by adding a yet another overload:

void fun(int i, int j);

Of course, in case of run-time polymorphism no compile-time error is possible, but I remember the investigation for the potential addition of multimethods (or open methods) showed that this ambiguity could be made a link-time error. I mean this doc: http://www.stroustrup.com/multimethods.pdf

Regards,
&rzej

[Andy Prowl]

The problem here is that we have to pick one argument according to which the dispatch is performed, which in the template case is not necessary. In the template case we can disambiguate by defining a method that specializes both fun(T, int) and fun (int, T), but how would the specializing function for virtual concepts end up in the itable for C and D? Requiring its presence would be a sort of inter-concept requirement.

Attempt at an answer: we could make the entry for "foo" in the itable for both C and D point to a compiler-generated function which would, at run-time, would inspect the types of the arguments and dispatch to the most specialized overload of "foo()" it finds. But is this most-specialized overload always guaranteed to exist? I would not like detecting ambiguities at run-time.

The example in Section 3.1 of the paper you link - which is the one I also had in mind - is not clear to me (especially the sentence "these overriders have a unique base-method through which the call can be dispatched – 2."), but that could just be my problem. What's objectively worrying me is that (referring to my original example again) the client code which calls "foo(x,y)", the code in which X is made a model of C (i.e. when the  corresponding itable is created), and the code in which Y is made a model of D, could all be linked separately - e.g. as DLLs. My impression is that link-time ambiguity detection wouldn't work in this case.

Anyway thank you very much for your help Andrzej.

Kind regards,

Andy

[Andy Prowl]

I created a GitHub repo for this idea/project/proposal: https://github.com/andyprowl/virtual-concepts.

Currently, the repository contains a draft of what is meant to become a larger document - either a proposal itself, or a document to be referenced from a proposal. The draft is at an early stage, containing only a motivating introduction to the problem and an overview of existing solutions for type erasure, including:

 - Adobe.Poly
 - Boost.TypeErasure
 - Pyry Jahkola's Poly
 - Boost.Interfaces
 - Signatures

The repository also contains code examples for the first three libraries (the last two projects have been abandoned).

Next, I plan to add one section stating the design goals and one section showcasing virtual concept in a nutshell. I also plan to hack on Clang and create a proof of pricinple, but this will take time - I have zero experience with writing compilers.

Any feedback is of course very welcome. I will keep posting further progress here.

Kind regards,

Andy

[Andy Prowl]

I added a "Design Goals" section (~5 pages) to the draft on the GitHub repo. Shortcut link (still work in progress): http://bit.ly/1CSmFRl.

Kind regards,

Andy

[mats.ta...@gmail.com]

As an ordinary C++ developer, I really like your proposal!

Is there a typo at p 29, 3.5?

auto r = Rectangle{{1.0, 2.0}, 5.0, 6.0};
Shape& s = r;
Shape const* p = &r;
std::unique_ptr<Shape> up = std::make_unique<Rectangle>(r);
std::shared_ptr<Shape> sp = std::move(up);
assert(up.get() == &r); // SHALL NEVER FIRE
assert(sp.get() == &s); // SHALL NEVER FIRE
assert(&r == &s); // SHALL NEVER FIRE

I might be missing something, but wouldn't the first assert fire because up has been moved from? Perhaps the line with the move and the first assert should be swapped?

[Вадим]

It may be interesting for you to look at traits in Rust, they are very similar to what you propose and serve as a tool for both static and dynamic polymorphism. Rust is much closer to C++ in its ideology, than Haskell, so its experience may somehow assist you with your proposal.

On Thursday, September 25, 2014 11:40:15 PM UTC+4, Andy Prowl wrote:

Hello everyone,

I would like to ask for feedback concerning this idea I had about non-intrusive "dynamic" polymorphism:

https://www.dropbox.com/s/tg737sf8sj1p1ht/Virtual%20concepts%20for%20polymorphic%20types.pdf?dl=1

This is just a rough sketch, please do not expect any full-blown proposal. My goal is to find out whether it makes sense to invest more time on it, or if the idea is basically bull***t.

A few highlights:

1. The idea is about introducing non-intrusive support for dynamic polymorphism (similar to Haskell's typeclasses);
2. The idea is similar to the old C++0x "concept maps", but is *not* related to templates;
3. Code using a "virtual concept" can be compiled separately and does not need to see the definition of the instances of that concept.

Thank you,

Andy

[Andy Prowl]

Hi Mats,

Thank you for your feedback! You're correct, I have now moved the assertion one line up and updated the document on the GitHub repo.

I am currently working on the next section of the draft, which should give a clearer idea of what the proposal is all about - what it allows, what it doesn't. I will keep posting progress here.

Kind regards,

Andy

[Andy Prowl]

Thank you for the tip Вадим, I do not know Rust but I shall definitely look into that.

Kind regards,

Andy

[Sean Middleditch]

On Friday, October 10, 2014 10:48:32 AM UTC-7, Вадим wrote:

It may be interesting for you to look at traits in Rust, they are very similar to what you propose and serve as a tool for both static and dynamic polymorphism. Rust is much closer to C++ in its ideology, than Haskell, so its experience may somehow assist you with your proposal.

Or in general look at structural typing: http://en.wikipedia.org/wiki/Structural_type_system

[Andy Prowl]

Thank you for the pointer Sean.

I do have some notes about structural vs. nominal typing. I also found this old proposal by Bjarne Stroustrup in which the two systems are analyzed in the context of generic programming and concepts: http://www.open-std.org/Jtc1/sc22/wg21/docs/papers/2009/n2906.pdf.

Soon I will upload the next section of the draft.

Kind regards,

Andy

[Andy Prowl]

I added another section ("Virtual concepts in a nutshell") to the draft. This new section demonstrates some practical applications of virtual concepts and provides an overview of what is allowed and what is not - e.g. generalize std::any and std::function, solve the Expression Problem, support freestanding functions as well as data members, support associated types/concepts, support concept refinement, and so on.

Section 4.3 ("Expression requirements and signature requirements") also discusses an important issue that (at least IMHO) has been overlooked in Concepts TS.

The next section I will add, which is about the algorithm used to extract interfaces from concept definitions, is the core of the work and probably the most challenging part. This will require some form of implementation and it will take time to complete it.

Apart from this, the document is getting quite long (~60 pages now without the bulk of the work), so I do not plan to use it as a proposal, but rather to reference it from a (much shorter) proposal as a source of more detailed information.

I would really appreciate any kind of feedback. Here are the pertinent links:

Draft: http://bit.ly/1CSmFRl
Bibliography: http://bit.ly/1CAuJEf

GitHub repo: https://github.com/andyprowl/virtual-concepts

Kind regards,

Andy

[mats.ta...@gmail.com]

I'm really exited by this feature now -- it looks like it could integrate elegantly/intuitively into C++. Also, I really like your writing style and thorough explanations. It makes the proposal/draft easy to understand and follow. :)

I spotted a typo: Introducing a new pair of expression templates times and divide is trivial: 

it should read Introducing a new pair of expression templates multiply and divide is trivial: 

[Andy Prowl]

Hi Mats,

Thank you for your positive feedback and for spotting the typo: fixed :)

Kind regards,

Andy

[Matthew Fioravante]

Hi Andy, I read your paper and I think a feature like this is a great direction for C++. Especially since it integrates so well with the syntax static concepts.

One limitation I don't quite understand, on page 33 of the paper you present a function like this:

void foo(virtual const Shape& l, virtual const Shape& r);

You state that l and r must bind to the same type, just like in static concepts. In otherwords I could not call foo(Circle(), Rectangle()). Can you elaborate on why this restriction is really necessary?

For static concepts, it makes sense because outside of the function "Shape" is a constrained template parameter (i.e. a static concept) but once inside the function "Shape" becomes a concrete type. If l and r could be different types then the meaning of Shape inside the function would become ambiguous and this clashes with the normal way we expect template parameters to work inside of template classes and functions. Because this restriction is maintained I can say sizeof(Shape), std::forward<Shape>(l), etc.. The way I use a constrained template parameter (i.e. concept) matches exactly the way I use a normal unconstrained template parameter T.

For dynamic concepts, no such ambiguity exists because "Shape" is already a type. Since the dynamic types have been erased there is no ambiguity when I reference "Shape" itself. Once I'm inside of foo(), all the compiler and I know is that we have 2 abstract Shapes. Also when using plain old inheritance I can have a function taking 2 pointers/references to base classes and pass them 2 different child classes. Why am I allowed to do easily do this inheritance but not dynamic concepts? A dynamic concepts feature should try to match the semantics of inheritance in this fashion since its really generalization of that type erasure technique. 

Also borrowing function template syntax to define a function which is not a template seems really confusing. Its a little bit scary that static concepts let us define things that look like normal functions which are actually templates. Being able to define things which look like templates but in reality aren't seems much worse. I can't imagine teaching all of these rules of when something is and is not a template to someone learning the language.

[Andrzej Krzemienski]

2016-03-11 1:10 GMT+01:00 Matthew Fioravante <fmatth...@gmail.com>:

One limitation I don't quite understand, on page 33 of the paper you present a function like this:

void foo(virtual const Shape& l, virtual const Shape& r);

You state that l and r must bind to the same type, just like in static concepts. In otherwords I could not call foo(Circle(), Rectangle()). Can you elaborate on why this restriction is really necessary?

[snip]
 

For dynamic concepts, no such ambiguity exists because "Shape" is already a type. Since the dynamic types have been erased there is no ambiguity when I reference "Shape" itself. Once I'm inside of foo(), all the compiler and I know is that we have 2 abstract Shapes. Also when using plain old inheritance I can have a function taking 2 pointers/references to base classes and pass them 2 different child classes. Why am I allowed to do easily do this inheritance but not dynamic concepts? A dynamic concepts feature should try to match the semantics of inheritance in this fashion since its really generalization of that type erasure technique. 

Hi Matthew.

I want to address one of the concerns you raised. Andy's paper forbids it, because it is not clear how the feature should behave in this case. It would be not implementable.

When you are performing an operation on two Shapes, you are in fact doing a dynamic-dispatch on two virtual tables. You need to solve the same problem as multi-methods solve.

With Andy's restriction, when you get two Shape-s, you extract their dynamic type:

```

void use(Shape s1, Shape s2)
{

  intersect(s1, s2);

}
```

You check that s1 is of type Circle, s2 is of type circle, so you know what to do: you call:

bool intersect(Circle const&, Circle const);

(which is probably part of the interface.) But if you figure out that s1's dynamic type is Library1::Polygon and s2's type is Library2::ShapeOfAustralia, to what function do you dispatch?

I hope this explanation helps.

Regards,

&rzej

[Andy Prowl]

Hi Matthew,

Thank you for your feedback.

Concerning your question about repeated occurrences of a (virtual) concept name, there's more than one reason that led me to this choice.

The main reason is that, in general, both scenarios are useful. Sometimes you want to express the fact that two erased objects must have the same type, and sometimes you want to allow them being independent. For example, imagine a concept SomeConcept modeling CopyConstructible and CopyAssignable (or just, say, Regular), and the following function:

    void foo(SomeConcept& c, SomeConcept& d)
    {
        auto e = c;
        c = d;
    }

The body of foo() makes sense only because "c" and "d" are known to be of the same (erased) type. Models of SomeConcept are only required to be CopyConstructible and CopyAssignable, i.e. constructible and assignable from another instance *of the same type*, not constructible/assignable from any instance of *any* other type modeling SomeConcept.

Let's also assume SomeConcept models DefaultConstructible, and consider this:

    void foo(SomeConcept& c)
    {
        SomeConcept d;
        // ...
    }

How do we know what type should be default-constructed in the first line? If all occurrences of the same concept name imply that the erased type is the same, then we know what to instantiate here: the same type erased by parameter "c". Otherwise, we're at a loss and the first line does not make sense (if you're wondering how can we achieve virtual dispatch on a default constructor, the latest version of the draft at https://github.com/andyprowl/virtual-concepts contains the answer in Section 5).

Certainly we also want to be able to specify that two concept variables may erase objects of different types (for the good parallel you draw with inheritance-based use cases). But what syntax to use? To me (but I see the controversy), the most natural choice was to use template syntax, where different type identifiers imply independent erasure:

    template<typename T, typename U>

        requires SomeConcept<T> && SomeConcept<U>
    void foo(SomeConcept& c, SomeConcept& d)
    {
        // ...
    }

Now I do understand your concern of this being counter-intuitive. I agree with it. However, defining syntax was not a priority for me. I liked the symmetry of this solution and my reasoning was sort of: "in Concepts TS non-template syntax can define function templates, which means syntax doesn't decide whether something is a template or not; but if that's the case, why not allowing template syntax to define non-function templates?". I do agree this is counter-intuitive and confusing: I just needed to pick some syntax and postpone bike-shedding (if we can call it like that).

Finally, consistency with Concepts TS just strengthened my decision of having repeated concept identifiers mean "same erased type".

Does this answer your question?

Andy

P.S.: People started to show interest for this proposal again, and there is now another thread in the SG8 - Concepts mailing list: https://groups.google.com/a/isocpp.org/forum/#!topic/concepts/241lmpRP28I.

[Andy Prowl]

Erm, I made a mistake in the example for independent erasure: the function parameters should have type T and U, obviously, and not SomeConcept. This is the correct snippet:

    template<typename T, typename U>
        requires SomeConcept<T> && SomeConcept<U>

    void foo(T& c, U& d)
    {
        // ...
    }