C++ lambda operator ==

Question

How do I compare two lambda functions in C++ (Visual Studio 2010)?

std::function<void ()> lambda1 = []() {};
std::function<void ()> lambda2 = []() {};
bool eq1 = (lambda1 == lambda1);
bool eq2 = (lambda1 != lambda2);

I get a compilation error claiming that operator == is inaccessible.

EDIT: I'm trying to compare the function instances. So lambda1 == lambda1 should return true, while lambda1 == lambda2 should return false.

Are you trying to compare the result of evaluating the lambdas, or the lambdas themselves? — Joshua Rodgers, Oct 21 '10 at 15:03
What do you MEAN by == ? What do you test equal ? And if you ever don't know, how could the compiler know by itself, and chose an operator== which would do what you don't know ? — Stephane Rolland, Oct 21 '10 at 15:03
@Joshua: He's obviously trying to compare the lambdas themselves. Which is a perfectly reasonable thing to do for anyone coming from a language with “proper” first class function object, in lambda or any other notation. Although those languages may or may not agree on whether `labda1` and `lambda2` in the code above would be equal, so Stephane probably pointed out why C++0x left out `operator==` for lambdas. — Christopher Creutzig, Oct 21 '10 at 15:15
@Christopher That's why I asking if that's what he was wanting to do. It doesn't make sense in terms of C++ (although it does in other languages) and I wanted to get a better sense of what was actually trying to be compared. — Joshua Rodgers, Oct 21 '10 at 15:18
@Christopher: is it a reasonable thing to do in languages with first class functions? There are still a lot of questions your comparison has to consider: are two functions which do the same thing equal? What if they have different implementations? What if the actual logic in the code is the same, but the values in their respective closures are different? It's not trivial to determine if two functions are "equal", and many languages with first-class functions don't allow equality testing of functions for that exact reason. — jalf, Oct 21 '10 at 21:20
@jalf: Obviously, I have no chance of knowing all languages with first-class function objects, and I'm not surprised to see you referring to “many languages” not allowing that. The other points you mentioned – I thought I had said pretty much the same thing above. But in some cases, it is a reasonable thing to do, yes. For example, in a computer algebra system, checking if the functor of an expression you got as input is *the* `sin` function (of which the system only has one) is reasonable, useful, and well supported in the systems I am familiar with. — Christopher Creutzig, Oct 22 '10 at 06:38
Which is to say that I'm quite happy with having lambdas be very similar to function pointers with closures – and one useful option of defining equality of lambdas is to treat lambdas from the same definition as equal. This option requires working out some details of whether the compiler should be allowed to fold equivalent lambdas into equal ones and what that means for comparison, but in the end, that is more or less just an arbitrary decision someone would have to make. — Christopher Creutzig, Oct 22 '10 at 06:51
@Christopher: I'm not sure how a definition of equality which depends on *arbitrary decisions* would be considered useful. By the way, your `sin` example is interesting. Should `sin(float)` compare equal to `sin(double)` What about the C `sin` and C++ `std::sin`, are they equal? What about a `sin` implemented via a lookup table versus one that computes its result in software versus one that does it using the hardware sin instruction? Most systems have many `sin` functions. — jalf, Oct 22 '10 at 09:41
@jalf: As I said, I was talking about systems that have exactly one `sin` function. And in these systems, the expression `sin(2*x)` would be an ordinary object to pass around, not necessarily meant to receive a numerical value for `x`. But I guess we do agree that this would be much less useful in C or C++, which simply has a different view on what a function really is. — Christopher Creutzig, Oct 29 '10 at 07:00

score 17 · Accepted Answer · edited May 23 '17 at 12:09

You can't compare std::function objects because std::function is not equality comparable. The closure type of the lambda is also not equality comparable.

However, if your lambda does not capture anything, the lambda itself can be converted to a function pointer, and function pointers are equality comparable (however, to the best of my knowledge it's entirely unspecified whether in this example are_1and2_equal is true or false):

void(*lambda1)() = []() { };
void(*lambda2)() = []() { };
bool are_1and1_equal = (lambda1 == lambda1); // will be true
bool are_1and2_equal = (lambda1 == lambda2); // may be true?

Visual C++ 2010 does not support this conversion. The conversion wasn't added to C++0x until just before Visual C++ was released.

score 2 · Answer 2 · answered Oct 21 '10 at 15:27

2

You cannot compare functions, end of.

You can at most compare pointers to functions in languages that have that concept (this is also what, for example, EQ does in Lisp. And it fails for equivalent functions that do not occupy the same place in memory.)

answered Oct 21 '10 at 15:27

nowayjose

37
1

3

+1. Comparing lambdas might work in some languages on the basis of hashing their parse trees (or accomplishing the same "by accident" through memoization and comparing their addresses), but there's little mathematical basis for such an operation. Determining that two arbitrary functions do the same thing is impossible. Empty functions are a very special case. – Potatoswatter Oct 21 '10 at 16:19
3

There are two notions of equality for functions: equality of definition and equality of behavior. The first could be done by comparison of program text in some sense (comparison of implementation address is a variation on this) but the second is impossible; full intentional comparison is in exactly the same computational marsh as the Halting Problem. – Donal Fellows Oct 21 '10 at 20:51
1

@Potatoswatter But the compiler knows the type of the lambda, and lambdas have unique types, so it could provide `operator==` for lambdas of the same type--because they're the *same lambda*. The operator itself would return `true` IFF the same values (bitwise, presumably) are captured by each lambda. – Kyle Strand May 04 '16 at 16:43

score -1 · Answer 3 · answered Oct 21 '10 at 20:25

-1

This is impossible.

Proof sketch: if it were possible to compute

f1 == f2

then it would also be possible to compute

f == infiniteLoop

and solve the Halting Problem.

answered Oct 21 '10 at 20:25

Jörg W Mittag

363,080
75
446
653

3

I don't know if you're serious, but this is nonsense. Two sources/binaries/scripts/function bodies/... can be easily compared (say in the normalized/optimized IR of the compiler), but this does not solve the halting problem. You may at most check if the given source/function/... is equal to one that is known to halt. – Matteo Italia Oct 21 '10 at 20:30
1

While I'll agree that it's impossible to determine that two functions are the same function *in the general case*, a weaker equality, two functions having the same code (Turing State Table, if you like) are equal. An even weaker equivalence (which could leave the OP's example inequal) would be that they compare equal if they are the same function object, which is basically the same as comparing function pointers. – SingleNegationElimination Oct 21 '10 at 20:34
2

@Matteo Italia, @TokenMacGuy: The OP doesn't specify what kind of equality he is looking for, so I am assuming extensional equality, which seems to be the usual definition. If the OP wants an *unusual* definition, he should probaby provide one. – Jörg W Mittag Oct 21 '10 at 20:39
1

@Jörg W Mittag: in your definition, are `for(;;);` and `for(unsigned int i=0;;i=(i+1)%20) cout< – Matteo Italia Oct 21 '10 at 21:04
@TokenMacGuy: But if only the code has to be identical, then, in any language which supports closures, you can have two functions be equal, and yet return different values when you call them. Not very intuitive. – jalf Oct 21 '10 at 21:22
@jalf: the captured variables in the closure are a part of the function's code/body. You can either view it in terms of the captured variables must be equal for the function to be equal, or else the captured variables are implicit arguments, and only when *all* arguments are identical are the functions the same. To take it a step further, is `std::time()` equal to itself? after all, each time you call it you get a different answer! – SingleNegationElimination Oct 21 '10 at 23:30
@TokenMacGuy: Captured variables aren't usually part of the functions *code*, which was what you originally said. As for `std::time`, that's a good question too, which just underlines what I said: defining equality for functions isn't straightforward. :) – jalf Oct 21 '10 at 23:59
@jalf: If `std::time()` is not equal to itself, then functions are not values, and cannot support the `==`. That might be unconscionable. I would prefer for `std::time()` to be equal to itself, because it is the same object, ie `&std::time() == &std::time()`. Weather `[](){} == [](){}` is similar to `typeid(std::vector) == typeid(std::vector)`, supposing one side of the equality appears in a separate compilation unit. The compiler may make separate instances, but for various reasons, they are defined as and must be equal. – SingleNegationElimination Oct 22 '10 at 00:21

Eric Towers · Answer 4 · 2015-09-25T03:09:45.317

-3

Simplest answer: All of template<> class function's operator==()s are private.

Followup question: Which if the following did you expect:
- compare address of functions
- compare two distinct objects (of type std::function<void ()>
- compare two abstract functions

Edit (nearly 5 years later):

I find it amusing that there are downvotes without comments. If the downvotes are because C++11 changed the access level for std::function::operator==(), then I say the voter doesn't understand how time works. If the downvotes are because the question asker did not clarify what he imagined operator==() would compare, perhaps the voter should see the multi-hour discussion via comments immediately under the question, which the OP answered only in the comments to my answer.

edited Sep 25 '15 at 03:09

answered Oct 21 '10 at 15:23

Eric Towers

4,175
1
15
17

The first one: compare address of functions. – Randy Voet Oct 22 '10 at 13:00
1

C++11 didn't change the access level for `std::function::`, because `std::function` didn't exist in C++03. Also, `operator==` *isn't* private (in any version of the standard); it's *not even a member function*. And it doesn't compare function addresses; it only permits comparison against `nullptr`. – Kyle Strand May 04 '16 at 16:47
Then I must have been psychic since I referenced it about 10 months before C++11 was finalized. Alternatively, it's a reference to TR1 (2007) and you are confirming the content of my edit: you don't understand how time works. – Eric Towers Oct 22 '16 at 23:09

C++ lambda operator ==

4 Answers4