Equality comparison of boost::function<>
Is this possible? I always get ambiguities when I try it. Here's some sample code: class foo { public: typedef enum { lost, reset } device_event; typedef boost::function<void (window&, device_event)> device_listener; void add_listener(const device_listener& listener) { std::list<device_listener>::const_iterator iter = std::find(listeners_.begin(), listeners_.end(), listener); if (iter == listeners_.end()) listeners_.push_back(listener); } private: std::list<device_listener> listeners_; }; The above is slightly simplified from my actual code, but when I do this I get the following: I'm using Visual C++ 9.0 SP1 1>f:\dev\testing\window.h(42) : error C2666: 'operator ==' : 4 overloads have similar conversions 1> q:\include\boost\1.39.0\boost\function\function_template.hpp(995): could be 'void boost::operator ==<R,T0,T1>(const boost::function2<R,T0,T1> &,const boost::function2<R,T0,T1> &)' [found using argument-dependent lookup] 1> with 1> [ 1> R=void, 1> T0=zg::window &, 1> T1=zg::window::device_event 1> ] 1> q:\include\boost\1.39.0\boost\function\function_base.hpp(791): or 'bool boost::operator ==<zg::window::device_listener>(Functor,const boost::function_base &)' [found using argument-dependent lookup] 1> with 1> [ 1> Functor=zg::window::device_listener 1> ] 1> q:\include\boost\1.39.0\boost\function\function_base.hpp(782): or 'bool boost::operator ==<zg::window::device_listener>(const boost::function_base &,Functor)' [found using argument-dependent lookup] 1> with 1> [ 1> Functor=zg::window::device_listener 1> ] 1> or 'built-in C++ operator==(void (__thiscall boost::function2<R,T0,T1>::dummy::* )(void), void (__thiscall boost::function2<R,T0,T1>::dummy::* )(void))' 1> with 1> [ 1> R=void, 1> T0=zg::window &, 1> T1=zg::window::device_event 1> ] 1> while trying to match the argument list '(const zg::window::device_listener, const zg::window::device_listener)' 1
On Sat, Aug 8, 2009 at 12:30 AM, Zachary Turner<divisortheory@gmail.com> wrote:
Is this possible? I always get ambiguities when I try it. Here's some sample code:
Disregard, I did some more searching around and found out that it's a known issue and it's not possible. So I'm already working on another solution. Out of curiosity, is it impossible due to technical limitations, or is it just not implemented because it's either difficult or nobody's ever gotten around to it?
2009/8/7 Zachary Turner <divisortheory@gmail.com>:
Out of curiosity, is it impossible due to technical limitations, or is it just not implemented because it's either difficult or nobody's ever gotten around to it?
Undecidable by reduction to the halting problem in general, though apparently possible for straight-line code (no loops/recursion) through the brute-force method of generate all paths and send them to a theorem prover to prove equivalence.
On 8 Aug 2009, at 07:30, Scott McMurray wrote:
2009/8/7 Zachary Turner <divisortheory@gmail.com>:
Out of curiosity, is it impossible due to technical limitations, or is it just not implemented because it's either difficult or nobody's ever gotten around to it?
Undecidable by reduction to the halting problem in general, though apparently possible for straight-line code (no loops/recursion) through the brute-force method of generate all paths and send them to a theorem prover to prove equivalence.
That sounds very unnecessary. Surely it would be sufficient, and what most people would expect, to check if the two function objects point to the same function (in the sense of location in memory), as opposed to logically equivalent functions? I wrote some code that compares instances of the SAT problem, of course I didn't do the NP-hard job of checking if they had the same set of solutions, just if they were actually the same problem. Chris
Christopher Jefferson wrote:
On 8 Aug 2009, at 07:30, Scott McMurray wrote:
2009/8/7 Zachary Turner <divisortheory@gmail.com>:
Out of curiosity, is it impossible due to technical limitations, or is it just not implemented because it's either difficult or nobody's ever gotten around to it?
Undecidable by reduction to the halting problem in general, though apparently possible for straight-line code (no loops/recursion) through the brute-force method of generate all paths and send them to a theorem prover to prove equivalence.
That sounds very unnecessary. Surely it would be sufficient, and what most people would expect, to check if the two function objects point to the same function (in the sense of location in memory), as opposed to logically equivalent functions?
I wrote some code that compares instances of the SAT problem, of course I didn't do the NP-hard job of checking if they had the same set of solutions, just if they were actually the same problem.
Chris
Comparing two SAT-instances actually is NP-hard, too. Given any SAT formula F, you could just check if (not F) is the same problem as the trivial formula (true). If (not F) is equivalent to (true), F is unsatisfiable and otherwise F is satisfiable. Tobi
On 8 Aug 2009, at 17:45, Tobias Columbus wrote:
Christopher Jefferson wrote:
2009/8/7 Zachary Turner <divisortheory@gmail.com>:
Out of curiosity, is it impossible due to technical limitations, or is it just not implemented because it's either difficult or nobody's ever gotten around to it?
Undecidable by reduction to the halting problem in general, though apparently possible for straight-line code (no loops/recursion) through the brute-force method of generate all paths and send them to a theorem prover to prove equivalence. That sounds very unnecessary. Surely it would be sufficient, and what most people would expect, to check if the two function objects
On 8 Aug 2009, at 07:30, Scott McMurray wrote: point to the same function (in the sense of location in memory), as opposed to logically equivalent functions? I wrote some code that compares instances of the SAT problem, of course I didn't do the NP-hard job of checking if they had the same set of solutions, just if they were actually the same problem.
Chris
Comparing two SAT-instances actually is NP-hard, too. Given any SAT formula F, you could just check if (not F) is the same problem as the trivial formula (true). If (not F) is equivalent to (true), F is unsatisfiable and otherwise F is satisfiable.
As I thought I implied, I know comparing if two SAT instances have the same set of solutions is NP-hard. However when I wrote a comparison function, I considered (for example) the problems "X" and "X \/ (Y /\ not Y)" to be different problems with the same set of solutions. Similarly, I wouldn't expect an implementation of boost::function to say that, given: int f() { return 2; } and int g() { return 2; } to say that f and g are the same function, in the same way C++ would not say that f == g either. But, this is very off-topic I think. Sorry. Chris
Christopher Jefferson wrote:
On 8 Aug 2009, at 17:45, Tobias Columbus wrote:
Christopher Jefferson wrote:
On 8 Aug 2009, at 07:30, Scott McMurray wrote:
2009/8/7 Zachary Turner <divisortheory@gmail.com>:
Out of curiosity, is it impossible due to technical limitations, or is it just not implemented because it's either difficult or nobody's ever gotten around to it?
Undecidable by reduction to the halting problem in general, though apparently possible for straight-line code (no loops/recursion) through the brute-force method of generate all paths and send them to a theorem prover to prove equivalence. That sounds very unnecessary. Surely it would be sufficient, and what most people would expect, to check if the two function objects point to the same function (in the sense of location in memory), as opposed to logically equivalent functions? I wrote some code that compares instances of the SAT problem, of course I didn't do the NP-hard job of checking if they had the same set of solutions, just if they were actually the same problem.
Chris
Comparing two SAT-instances actually is NP-hard, too. Given any SAT formula F, you could just check if (not F) is the same problem as the trivial formula (true). If (not F) is equivalent to (true), F is unsatisfiable and otherwise F is satisfiable.
As I thought I implied, I know comparing if two SAT instances have the same set of solutions is NP-hard. However when I wrote a comparison function, I considered (for example) the problems "X" and "X \/ (Y /\ not Y)" to be different problems with the same set of solutions.
Similarly, I wouldn't expect an implementation of boost::function to say that, given:
int f() { return 2; } and int g() { return 2; }
to say that f and g are the same function, in the same way C++ would not say that f == g either.
But, this is very off-topic I think. Sorry.
Yes, you're right! I agree, that function-pointer comparison would suffice for some (many?) use-cases of boost::function, but actually I just wanted to point out that theoretical ( and off-topic! ) complication with formula-comparison. Sorry. Tobi
Chris _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
2009/8/8 Christopher Jefferson <chris@bubblescope.net>:
That sounds very unnecessary. Surely it would be sufficient, and what most people would expect, to check if the two function objects point to the same function (in the sense of location in memory), as opposed to logically equivalent functions?
But what about this? less<int> f; function<bool(int,int)> g = f; function<bool(int,int)> h = f; Checking based on address won't be able to tell that g == h, since copies of f will be taken for lifetime reasons.
Scott McMurray wrote:
But what about this?
less<int> f; function<bool(int,int)> g = f; function<bool(int,int)> h = f;
Checking based on address won't be able to tell that g == h, since copies of f will be taken for lifetime reasons.
That's not a problem at all. Boost.function holds its content by copy. The real issue is that function objects aren't equality comparable. Function pointers are, but not function objects.
On Sun, Aug 9, 2009 at 5:32 PM, Mathias Gaunard<mathias.gaunard@ens-lyon.org> wrote:
Scott McMurray wrote:
But what about this?
less<int> f; function<bool(int,int)> g = f; function<bool(int,int)> h = f;
Checking based on address won't be able to tell that g == h, since copies of f will be taken for lifetime reasons.
That's not a problem at all. Boost.function holds its content by copy.
The real issue is that function objects aren't equality comparable. Function pointers are, but not function objects.
This is probably just my ignorance on the issue of boost::function implementation details, but I don't see why function objects can't be equality comparable. I mean I understand that in general it's impossible to determine the equivalence of two arbitrary functions, but I don't think those are necessarily the semantics that a function equality test would need to provide. For example if I created a boost::function object and bound it to a named recursive implementation of fibonacci, and then created another boost::function object and bound it to an implementation of fibonacci using a lambda function in conjunction with boost::egg in the vault to get the Y-combinator, I would fully expect function equality to return false in this case. In the example above, however:
less<int> f; function<bool(int,int)> g = f; function<bool(int,int)> h = f;
I see no reason why it should be impossible, or at the very least no reason why it should be undecidable that g and h are the same function. For example, less<T> contains no state, so every instance of less<N> is always equal to every other instance of less<M> if and only if N == M. Again I don't know much about the details of boost::function implementation, but somewhere down there it has to have a typed copy of f otherwise it wouldn't be able to invoke operator(), so why couldn't it just compare typeids of those two instances? For function objects that contain state, it seems like it could just use deep equality testing of members. It's true that functors like std::less<> don't provide equality operators, but honestly for two instances of boost::function<> that both contain function objects, I'd be satisfied if boost::function just had an equality operator like this: template<class Sig> bool operator==(const boost::function<Sig>& func1, const boost::function<Sig>& func2) { return (typeid(func1.internal_func_obj) == typeid(func2.internal_func_obj)) && (memcmp(&func1.internal_func_obj, &func2.internal_func_obj, sizeof(func1.internal_func_obj)) == 0); } with internal_func_obj replaced with whatever, since again I'm not familiar with the implementation details. It seems like even lambda expressions should be equality comparable provided they are exactly the same function object. So that two lambda functions both specified as (_1 + _2)(x, y) for example would be the same, but (_2 + _1)(x, y) would be different (even though they're actually the same provided + is commutative). I'm assuming that the construction of a boost::function<> object is deterministic given a lambda expression, but I think that's a reasonable assumption. Even given void foo(int a, int b, int c) {} boost::function<void (int, int, int)> f = bind(foo, _1, _2, _3); boost::function<void (int, int, int)> f = foo; I'd be fine if equality returned false. So in short, what is the flaw in just testing the way two function objects are represented internally?
AMDG Zachary Turner wrote:
This is probably just my ignorance on the issue of boost::function implementation details, but I don't see why function objects can't be equality comparable.
They can be, but they don't have to be. Please see http://www.boost.org/doc/html/function/faq.html#id1877737
Again I don't know much about the details of boost::function implementation, but somewhere down there it has to have a typed copy of f otherwise it wouldn't be able to invoke operator(), so why couldn't it just compare typeids of those two instances?
If you want to compare typeids you can do it explicitly, since boost::function allows access to the typeid of the contained function object.
For function objects that contain state, it seems like it could just use deep equality testing of members. It's true that functors like std::less<> don't provide equality operators, but honestly for two instances of boost::function<> that both contain function objects, I'd be satisfied if boost::function just had an equality operator like this:
template<class Sig> bool operator==(const boost::function<Sig>& func1, const boost::function<Sig>& func2) { return (typeid(func1.internal_func_obj) == typeid(func2.internal_func_obj)) && (memcmp(&func1.internal_func_obj, &func2.internal_func_obj, sizeof(func1.internal_func_obj)) == 0); }
with internal_func_obj replaced with whatever, since again I'm not familiar with the implementation details.
This is problematic because it doesn't match normal C++ semantics.
It seems like even lambda expressions should be equality comparable provided they are exactly the same function object. So that two lambda functions both specified as (_1 + _2)(x, y) for example would be the same, but (_2 + _1)(x, y) would be different (even though they're actually the same provided + is commutative). I'm assuming that the construction of a boost::function<> object is deterministic given a lambda expression, but I think that's a reasonable assumption.
Even given
void foo(int a, int b, int c) {}
boost::function<void (int, int, int)> f = bind(foo, _1, _2, _3); boost::function<void (int, int, int)> f = foo;
I'd be fine if equality returned false.
This ought to return false because the types are different.
So in short, what is the flaw in just testing the way two function objects are represented internally
It would be surprising, because nothing else works that way. In Christ, Steven Watanabe
On Mon, Aug 10, 2009 at 10:51 AM, Steven Watanabe<watanabesj@gmail.com> wrote:
This ought to return false because the types are different.
So in short, what is the flaw in just testing the way two function objects are represented internally
It would be surprising, because nothing else works that way.
I agree it might be surprising from an implementation standpoint. But are there examples of functors such that equality implemented this way would return a surprising result? If the result isn't surprising, then I don't think the implementation should matter much, as long as it relies only on standards conformant language aspects. Again I could just be overlooking something due to lack of understanding of the implementation details of boost::function<>, but at least on the surface it seems to me that the behavior would always produce expected results.
AMDG Zachary Turner wrote:
On Mon, Aug 10, 2009 at 10:51 AM, Steven Watanabe<watanabesj@gmail.com> wrote:
This ought to return false because the types are different.
So in short, what is the flaw in just testing the way two function objects are represented internally
It would be surprising, because nothing else works that way.
I agree it might be surprising from an implementation standpoint. But are there examples of functors such that equality implemented this way would return a surprising result?
boost::lambda::_1 == std::string() The result of memcmp depends on the implementation details of std::string.
If the result isn't surprising, then I don't think the implementation should matter much, as long as it relies only on standards conformant language aspects.
memcmp is not guaranteed to produce sensible results in this context. I don't know that it is even guaranteed to work for POD types, when padding is added for alignment reasons.
Again I could just be overlooking something due to lack of understanding of the implementation details of boost::function<>, but at least on the surface it seems to me that the behavior would always produce expected results
In Christ, Steven Watanabe
Comparing the types and internal memory of objects is a non-starter - an empty class is absolutley not the same as a stateless class. Take a look at this example of an empty class with state. //empty_class.hpp class empty_class { public: empty_class(); empty_class(empty_class& other); int operator()()const; }; //empty_class.cpp namespace { static std::map<const empty_class*const,int> map_; static int next_ = 0; } empty_class::empty_class() { map_[this] = next_++; } empty_class::empty_class(const empty_class& other) { map_[this] = next_++; } int empty_class::operator()()const { return map_[this]; }
participants (3)
-
Christopher Jefferson -
Joseph Gauterin -
Mathias Gaunard -
Scott McMurray -
Steven Watanabe -
Tobias Columbus -
Zachary Turner