An alternative approach to TypeErasure
Hi all, I was quite impressed by Sean Parent's Friday talk in C++Now! 2012 (see slides in [1], code in [2]) and was left wondering whether the generation of his polymorphic object wrapper could be made simple somehow in C++11. [1]: https://github.com/boostcon/cppnow_presentations_2012/raw/master/fri/value_s... [2]: https://github.com/boostcon/cppnow_presentations_2012/blob/master/fri/value_... What I ended up with is tricking ADL into allowing the overloading of arbitrary (specifically crafted) function objects that I call _callables_, and then letting the user define interfaces by specifying sets of ("member") function signatures with a callable. You can find the code, and my rambling introductory README file, in GitHub: https://github.com/pyrtsa/poly Comments are welcome! * * * Here's a somewhat shorter intro: 1) Create a callable F by simply deriving it from poly::callable<F>: struct draw_ : poly::callable<draw_> {}; constexpr draw_ draw = {}; 2) Or use the convenience macro POLY_CALLABLE(name) to do the same: POLY_CALLABLE(to_string); // type `to_string_` and object `to_string` 3) Overload your callables by overloading the function named `call`, with the callable as first argument: template <typename T> void call(draw_, T const & x, std::ostream & out, std::size_t position) { out << std::string(position, ' ') << x << std::endl; } std::string call(to_string_, int i) { return std::to_string(i); } template <typename T> std::string call(to_string_, std::vector<T> const & xs) { std::ostringstream s; s << '['; auto i = begin(xs), e = end(xs); if (i != e) s << *i++; while (i != e) s << ", " << *i++; s << ']'; return s.str(); } Now you can call ::draw(x, o, p) and ::to_string(x) for several different types of x: ::draw(123, std::cout, 2); // prints " 123" to stdout ::to_string(std::vector<int>(1, 2, 3)); // "[1, 2, 3]" But you can likewise extend ::draw and ::to_string further by overloading them for your own types too. 4) Define an interface by specifying the set of function signatures as template arguments to poly::interface: using drawable = poly::interface< void(draw_, poly::self const &, std::ostream &, std::size_t, std::string(to_string_, poly::self const &)>; Now, the following calls got automatically defined, and forwarded to whatever type you successfully construct a `drawable` from: void call(draw_, drawable const &, std::ostream &, std::size_t); std::string call(to_string_, drawable const &); * * * I am aware that Steven Watanabe has put some astonishing work on his proposed Boost.TypeErasure. I'm open for discussion whether and how his or mine is a better approach, or if we could combine these into an eventual Boost.Interface library or such! * * * PS. Like I mention in my GitHub page, this kind of type erasure is common in functional languages like Haskell or Clojure. The problem they are solving there is known as the Expression Problem. IMO it makes very much sense to have the corresponding construct in C++ too, as we're moving towards a more and more functional style with parallelism and such. Best Regards, -- Pyry Jahkola pyry.jahkola@iki.fi https://twitter.com/pyrtsa
Hi, On Sun, Jun 24, 2012 at 7:34 PM, Pyry Jahkola <pyry.jahkola@iki.fi> wrote:
I was quite impressed by Sean Parent's Friday talk in C++Now! 2012
The slides are interesting, but I can't find the video on boostcon youtube account. Is it not online yet or there is no video? Joel Lamotte
On Jun 24, 2012, at 6:57 AM, Klaim - Joël Lamotte wrote:
On Sun, Jun 24, 2012 at 7:34 PM, Pyry Jahkola <pyry.jahkola@iki.fi> wrote:
I was quite impressed by Sean Parent's Friday talk in C++Now! 2012
The slides are interesting, but I can't find the video on boostcon youtube account. Is it not online yet or there is no video?
I just uploaded Sean's video last night. http://www.youtube.com/watch?v=_BpMYeUFXv8 -- Marshall Marshall Clow Idio Software <mailto:mclow.lists@gmail.com> A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait). -- Yu Suzuki
AMDG On 06/24/2012 03:34 AM, Pyry Jahkola wrote:
I am aware that Steven Watanabe has put some astonishing work on his proposed Boost.TypeErasure. I'm open for discussion whether and how his or mine is a better approach, or if we could combine these into an eventual Boost.Interface library or such!
I don't think your approach is fundamentally very different from mine. Consider: template<class T = _self> struct to_string { static std::string apply(T const&) { return std::to_string(t); } }; typedef boost::type_erasure::any< mpl::vector<copy_constructible<>, to_string<> > > x(...); call(to_string<>(), x); vs. POLY_CALLABLE(to_string); template<class T> std::string call(to_string_, T const& t) { return std::to_string(t); } poly::interface<std::string(to_string_, poly::self)> x(...); to_string(x); The changes are: 1) replace a static member apply, with a free function call 2) copy_constructible<> is implicit 3) The concept is deduced from the signature, instead of the signature being deduced from the concept. 4) replace call(to_string<>, x) with to_string(x) The transformation is basically 1-to-1. In principle, every feature of my library could be implemented with yours and vice versa, just changing the base definitions. There's only one real difference in capability. Compare: call(to_string<>(), x) with to_string(x). My library knows from the signature of to_string<>, that it should dispatch on the first (and only) argument, while yours has to deduce this from the arguments. This can only cause an unresolvable ambiguity for mutually recursive anys like this: template<class T1, class T2> struct aconcept { static void apply(const T1&, const T2&); }; struct concept1; struct concept2; struct concept1 : boost::mpl::vector< copy_constructible<>, aconcept<_self, any<concept2> > > {}; struct concept2 : boost::mpl::vector< copy_constructible<>, aconcept<any<concept1>, _self> > {}; The way you handle template arguments to poly::interface makes it impossible to create this kind of mutually recursive any. In Christ, Steven Watanabe
On 2012-06-24 14:21:32 +0000, Steven Watanabe said:
I don't think your approach is fundamentally very different from mine.
Not fundamentally. But what do you think about the API of my library? I found it easier to understand when you see the "member" functions almost as is in the template arguments, and you don't have to invent names like ostreamable for some more domain-specific functions.
The way you handle template arguments to poly::interface makes it impossible to create this kind of mutually recursive any.
Hmm, that's right. But I'm a bit puzzled by not being able to think of a good real-world example of such problem. -- Pyry Jahkola pyry.jahkola@iki.fi https://twitter.com/pyrtsa
AMDG On 06/24/2012 03:55 PM, Pyry Jahkola wrote:
On 2012-06-24 14:21:32 +0000, Steven Watanabe said:
I don't think your approach is fundamentally very different from mine.
Not fundamentally. But what do you think about the API of my library? I found it easier to understand when you see the "member" functions almost as is in the template arguments, and you don't have to invent names like ostreamable for some more domain-specific functions.
I believe that it should be possible to give a decent name to any top-level concept. Of course, if your main concept has multiple functions, it may not be possible to give a good name to each one. In this case, I think a convention like has_push_back<void(int)> would be good enough. Overall, I'd say that I like the way your interface looks, but I wouldn't choose to do it that way, just because I'm pedantic about the overload resolution and ADL issues that I pointed out in another post. One of the things I dislike about your interface is that it's necessarily based on individual functions. With mine, composite concepts like copy_constructible<> and forward_iterator<> are used in exactly the same way as the base single-function concepts. Finally, I'm beginning to consider the details of the definitions less important, since I think the cleanest interface for defining new members will end up having to use macros. // A concept called custom::has_push_back // for a member function called push_back // that takes 1 argument. Example usage: // has_push_back<void(int)>. BOOST_TYPE_ERASURE_MEMBER((custom)(has_push_back), push_back, 1); (I have an initial implementation of this macro, but I still need to finish the tests and documentation. With variadic templates I can eliminate the "1" argument.)
The way you handle template arguments to poly::interface makes it impossible to create this kind of mutually recursive any.
Hmm, that's right. But I'm a bit puzzled by not being able to think of a good real-world example of such problem.
This kind of situation should happen very rarely if ever. I was just pointing it out for the sake of completeness. In Christ, Steven Watanabe
on Sun Jun 24 2012, Pyry Jahkola <pyry.jahkola-AT-iki.fi> wrote:
https://github.com/pyrtsa/poly
Comments are welcome!
After a quick skim: Very cool! Reminds me a bit of something I did, entirely in the static polymorphism space: http://article.gmane.org/gmane.comp.lib.boost.devel/120408... But I guess your work is fundamentally different from what I was doing. One thing I didn't see you mention there is that since your generic functions are first-class objects, they can be passed and returned, thereby supporting higher-order functional programming.
* * *
I am aware that Steven Watanabe has put some astonishing work on his proposed Boost.TypeErasure. I'm open for discussion whether and how his or mine is a better approach, or if we could combine these into an eventual Boost.Interface library or such!
Very interesting. Does either approach support operator overloading?
PS. Like I mention in my GitHub page, this kind of type erasure is common in functional languages like Haskell or Clojure. The problem they are solving there is known as the Expression Problem.
Is that different in essence from the Binary Method Problem?
IMO it makes very much sense to have the corresponding construct in C++ too, as we're moving towards a more and more functional style with parallelism and such.
Well, it's not as though we can't already do functional programming in C++... I think you might be conflating issues here. Isn't this really about a way to do runtime polymorphism with value semantics? -- Dave Abrahams BoostPro Computing http://www.boostpro.com
AMDG On 06/24/2012 08:13 AM, Dave Abrahams wrote:
on Sun Jun 24 2012, Pyry Jahkola <pyry.jahkola-AT-iki.fi> wrote:
* * *
I am aware that Steven Watanabe has put some astonishing work on his proposed Boost.TypeErasure. I'm open for discussion whether and how his or mine is a better approach, or if we could combine these into an eventual Boost.Interface library or such!
Very interesting. Does either approach support operator overloading?
Yes. I put quite a bit of effort into making sure that operator overloads would work correctly. In Christ, Steven Watanabe
On 2012-06-24 18:34:13 +0000, Steven Watanabe said:
On 06/24/2012 08:13 AM, Dave Abrahams wrote:
Very interesting. Does either approach support operator overloading?
Yes. I put quite a bit of effort into making sure that operator overloads would work correctly.
I started the work on operator overloading, as you might guess when seeing the file include/poly/operators.hpp (names in this file will definitely change) I didn't get so far that poly::interface would actually recognize these callables and create the corresponding operators for itself, but that sure is possible. More importantly, I'm still kind of missing the point of why the feature of operator overloading is really needed. In essence: How should binary operators behave? Steven's TypeErasure defines binary operators such that only when the wrapped types of a and b are the same, can you sum them up: "a + b". But where would you use this kind of an "any", where only some of the instances can be added up, and others cause undefined behavior? Wouldn't you actually do the addition on the side where you know the types, and not on the type-erased side? Do we really have a real world use case that would prompt us to implement features like operator overloading? * * * Before releasing more worms from the can of type-erased operators, I must confess that I know still too little about the possible uses for type erasure / expression problem / what you name it. What I propose is we should look into how e.g. Haskell and Clojure programmers use their type classes and protocols. For one thing, I could only think of few examples where the interface would have mutating functions. (Anybody care to throw in more examples?) More typical use cases (that I could think of) are functions which read the wrapped type (as const reference), and then either (1) return a value, or (2) cause a side effect: std::string(to_html_, self const &); // (1) "pure" function void(print_, self const &, std::ostream &); // (2) side effect Maybe if the whole interface is about wrapping some sort of computation or side effect, it might make sense to have some non-const functions too: using progress = interface< std::size_t(total_progress_, self const &), std::size_t(current_progress_, self const &), void(run_for_, self &, std::chrono::microseconds)>; Or maybe it's modeling a kind of a container and you can insert items into it: using container = interface< void(insert_, self &, std::size_t, content), void(remove_, self &, std::size_t), content &(at_, self &, std::size_t), content const &(at_, self const &)>; -- Pyry Jahkola pyry.jahkola@iki.fi https://twitter.com/pyrtsa
on Sun Jun 24 2012, Pyry Jahkola <pyry.jahkola-AT-iki.fi> wrote:
More importantly, I'm still kind of missing the point of why the feature of operator overloading is really needed. In essence: How should binary operators behave? Steven's TypeErasure defines binary operators such that only when the wrapped types of a and b are the same, can you sum them up: "a + b".
But where would you use this kind of an "any", where only some of the instances can be added up, and others cause undefined behavior? Wouldn't you actually do the addition on the side where you know the types, and not on the type-erased side?
Do we really have a real world use case that would prompt us to implement features like operator overloading?
Well, it's interesting; this type erasure can be viewed/used two different ways: 1. Runtime polymorphism 2. Static polymorphism with separate compilation of generic functions Approach 1 admits a runtime type error when the types don't match in a+b. Approach 2 doesn't. Haskell actually takes approach 2. Prelude> :t (+) (+) :: (Num a) => a -> a -> a That's why, for example, it isn't possible to make a list of a given type class and store two different types that conform to that type class in the list. *Your* type erased things do runtime polymorphism, so they're very different from Haskell's typeclasses in that sense. For dynamic polymorphism in Haskell, you need something like http://hackage.haskell.org/trac/ghc/wiki/PolymorphicDynamic
Before releasing more worms from the can of type-erased operators, I must confess that I know still too little about the possible uses for type erasure / expression problem / what you name it. What I propose is we should look into how e.g. Haskell and Clojure programmers use their type classes and protocols.
It's probably a good idea to learn as much as possible from other languages, but that said, we *do* have plenty of prior art in C++ for type erasure. Just making those use cases better is a worthy goal on its own. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
AMDG On 06/24/2012 02:53 PM, Pyry Jahkola wrote:
On 2012-06-24 18:34:13 +0000, Steven Watanabe said:
On 06/24/2012 08:13 AM, Dave Abrahams wrote:
Very interesting. Does either approach support operator overloading?
Yes. I put quite a bit of effort into making sure that operator overloads would work correctly.
I started the work on operator overloading, as you might guess when seeing the file
include/poly/operators.hpp (names in this file will definitely change)
I didn't get so far that poly::interface would actually recognize these callables and create the corresponding operators for itself, but that sure is possible.
If you have to create special cases for these in the core library, you're doing it wrong.
More importantly, I'm still kind of missing the point of why the feature of operator overloading is really needed. In essence: How should binary operators behave? Steven's TypeErasure defines binary operators such that only when the wrapped types of a and b are the same, can you sum them up: "a + b".
But where would you use this kind of an "any", where only some of the instances can be added up, and others cause undefined behavior? Wouldn't you actually do the addition on the side where you know the types, and not on the type-erased side?
Binary operators like this require you to have a coherent set of objects. You can't just take two random objects from two different sources and combine them. There are also a few special cases where binary operators can have a reasonable default behavior when the types don't match. For example, equality_comparable<> and less_than_comparable<> can test the stored /types/ first before testing the value.
Do we really have a real world use case that would prompt us to implement features like operator overloading?
any_iterator. Also, you're confusing two separate issues. Operator overloading is a separate issue from binary methods. Some operators, like ostreamable<> or incrementable<>, would normally only take one any argument.
* * *
Before releasing more worms from the can of type-erased operators, I must confess that I know still too little about the possible uses for type erasure / expression problem / what you name it. What I propose is we should look into how e.g. Haskell and Clojure programmers use their type classes and protocols.
For one thing, I could only think of few examples where the interface would have mutating functions. (Anybody care to throw in more examples?)
More typical use cases (that I could think of) are functions which read the wrapped type (as const reference), and then either (1) return a value, or (2) cause a side effect:
std::string(to_html_, self const &); // (1) "pure" function void(print_, self const &, std::ostream &); // (2) side effect
Maybe if the whole interface is about wrapping some sort of computation or side effect, it might make sense to have some non-const functions too:
using progress = interface< std::size_t(total_progress_, self const &), std::size_t(current_progress_, self const &), void(run_for_, self &, std::chrono::microseconds)>;
Or maybe it's modeling a kind of a container and you can insert items into it:
using container = interface< void(insert_, self &, std::size_t, content), void(remove_, self &, std::size_t), content &(at_, self &, std::size_t), content const &(at_, self const &)>;
In Christ, Steven Watanabe
On 2012-06-24 15:13:28 +0000, Dave Abrahams said:
After a quick skim: Very cool!
Kiitos!
Reminds me a bit of something I did, entirely in the static polymorphism space: http://article.gmane.org/gmane.comp.lib.boost.devel/120408... But I guess your work is fundamentally different from what I was doing.
Interesting. Segmented ranges actually was one potential use case I was thinking when implementing poly::interface. Btw, has there been any work on the front of segmented ranges since in Boost? Or are we just waiting for Boost.SIMD currently?
One thing I didn't see you mention there is that since your generic functions are first-class objects, they can be passed and returned, thereby supporting higher-order functional programming.
Good point! I definitely need to add that note to my README.
PS. Like I mention in my GitHub page, this kind of type erasure is common in functional languages like Haskell or Clojure. The problem they are solving there is known as the Expression Problem.
Is that different in essence from the Binary Method Problem?
No, it's about (I'm paraphrasing somewhat) being able to both (1) "easily" make more types implement an interface, and (2) "easily" add more functions to an interface. Easily in (1) would mean, "without having to modify and recompile the whole interface (meaning the existing function implementations)". In (2), "without having to modify (and recompile) all the classes". If I'm not missing a point, both of these are relatively easy with my library, especially where templates can be used in defining the callable functions. The Binary Method Problem seems to be about what I criticized in the operator overloading discussion of this thread an hour ago. What I'm saying is, I don't think the Binary Method Problem is the right problem to solve with type erasure, but I'm happy to hear any counter-arguments!
IMO it makes very much sense to have the corresponding construct in C++ too, as we're moving towards a more and more functional style with parallelism and such.
Well, it's not as though we can't already do functional programming in C++... I think you might be conflating issues here. Isn't this really about a way to do runtime polymorphism with value semantics?
Hmm, you are be right that I went too far in saying that. But one nice property in both mine and (if I've understood correctly) Steven's libraries is that the functions remain external to the data structures, and can be easily composed (with higher order functions). Obviously we all have been able to do FP in C++ for years without these new constructs. -- Pyry Jahkola pyry.jahkola@iki.fi https://twitter.com/pyrtsa
Pyry Jahkola wrote:
Hi all,
I was quite impressed by Sean Parent's Friday talk in C++Now! 2012
I didn't see the talk but I did skim through the slide deck. One HUGE thing jumped out at me. I don't remember the exact quote - but I think it was something like: "C++ is now way too large for any single person to understand all of it" I believe: a) This is true, b) This is a problem. c) That as a problem it's under appreciated by us C++ fans d) That we have to explicitly address it in some way in order to keep C++ from being a victim of it's own success. Robert Ramey
On Mon, Jun 25, 2012 at 1:31 AM, Robert Ramey <ramey@rrsd.com> wrote:
I didn't see the talk but I did skim through the slide deck.
One HUGE thing jumped out at me.
I don't remember the exact quote - but I think it was something like:
"C++ is now way too large for any single person to understand all of it"
I think Pyry was talking about a different talk as the slides are not these from the talk you mention... Joel Lamotte
On 2012-06-24 15:48:17 +0000, Klaim - Joël Lamotte said:
I think Pyry was talking about a different talk as the slides are not these from the talk you mention...
That's correct. I've been waiting for that talk to appear to YouTube, so I could show it to my colleagues, but no luck so far. You can browse through the thoughtwork in the slides, but there was more to it in the talk than just the slides. IIRC, his view was that inheritance-based polymorphism never solved more problems at Adobe than it caused; borrowing one feature (in code) from another software product always meant having to pull in another heap of foreign class hierarchies. Because those classes only talked to class hierarchies they already knew about. And the rest of the talk was kind of proving that concepts-based polymorphism might help solving this problem. PS. Of course, I agree with Robert Ramey that his keynote speech from Thursday did have its point too! But that's off-topic. -- Pyry Jahkola pyry.jahkola@iki.fi https://twitter.com/pyrtsa
On 24 June 2012 11:31, Robert Ramey <ramey@rrsd.com> wrote:
"C++ is now way too large for any single person to understand all of it"
I believe:
a) This is true, b) This is a problem. c) That as a problem it's under appreciated by us C++ fans d) That we have to explicitly address it in some way in order to keep C++ from being a victim of it's own success.
I am unclear what this has to do with Boost specifically. (I also don't believe it is solvable since it is diametrically opposed to the C++ Committee goal of backwards compatibility [which is a two edged sword: a huge strength from a language adoption point of view, but a liability from a language design point of view], but if you have concrete ideas on how to solve it, I'm all ears in a more appropriate forum.) -- Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> (847) 691-1404
AMDG On 06/24/2012 03:34 AM, Pyry Jahkola wrote:
Here's a somewhat shorter intro:
1) Create a callable F by simply deriving it from poly::callable<F>:
struct draw_ : poly::callable<draw_> {}; constexpr draw_ draw = {};
2) Or use the convenience macro POLY_CALLABLE(name) to do the same:
POLY_CALLABLE(to_string); // type `to_string_` and object `to_string`
3) Overload your callables by overloading the function named `call`, with the callable as first argument:
template <typename T> void call(draw_, T const & x, std::ostream & out, std::size_t position) { out << std::string(position, ' ') << x << std::endl; }
Some thoughts on this interface: a) It's a bit more concise than my interface, but the difference isn't major. b) ADL is less robust than class template specialization, since it can accidentally pull in unrelated functions that happen to have the same name. c) Your function objects won't overload properly with ordinary functions, if, for example, someone has a function called draw or to_string that operates on his own type. In Christ, Steven Watanabe
participants (7)
-
Dave Abrahams -
Klaim - Joël Lamotte -
Marshall Clow -
Nevin Liber -
Pyry Jahkola -
Robert Ramey -
Steven Watanabe