On 8 Aug 2009, at 07:30, Scott McMurray wrote:

2009/8/7 Zachary Turner :

...

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

On 8 Aug 2009, at 17:45, Tobias Columbus wrote:

Christopher Jefferson wrote:

...

...

2009/8/7 Zachary Turner :

...

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

2009/8/8 Christopher Jefferson :

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 g = f; function 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.

On Sun, Aug 9, 2009 at 5:32 PM, Mathias Gaunard wrote:

Scott McMurray wrote:

...

But what about this?

less<int> f; function g = f; function 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 g = f; function 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 f = bind(foo, _1, _2, _3); boost::function 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?

On Mon, Aug 10, 2009 at 10:51 AM, Steven Watanabe 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.

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 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]; }