Re: [Boost-users] Equality comparison of boost::function<>

Subject: Re: [Boost-users] Equality comparison of boost::function<>
From: Zachary Turner (divisortheory_at_[hidden])
Date: 2009-08-10 09:55:44

On Sun, Aug 9, 2009 at 5:32 PM, Mathias
Gaunard<mathias.gaunard_at_[hidden]> 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?