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

9 Aug 2009

      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 :
...
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