In Swift 3, what is a way to compare two closures?

Question

Suppose you have two closures of type (Int)->() in Swift 3 and test to see if they are the same as each other:

typealias Baz = (Int)->()
let closure1:Baz = { print("foo \($0)") }
let closure2:Baz = { print("bar \($0)") }

if(closure1 == closure2) {
    print("equal")
}

This fails to compile, giving the message:

Binary operator '==' cannot be applied to two '(Int)->()' operands

OK, well, how then can we compare two closures of the same type, to see if they are the same?

How would you determine if two closures are equal? Equality implies substitutability, so does that mean you'd expect `{ print("hi") } == { sayHi() }` to be `true` if `func sayHi() { print("hi") }`? What about captured variables – what if the variable is not of `Equatable` type? I don't see how there's any sensible way you could determine equality between two closures. — Hamish, Jul 23 '17 at 22:38
It's also worth noting that Swift doesn't support referential equality between closures (compare https://stackoverflow.com/q/24111984/2976878) due to various thunks they can get put through, and optimisations, such as specialisations & method body sharing, that would make the results unpredictable. — Hamish, Jul 23 '17 at 22:38
In what situation would it even make sense do compare closures? — Alexander, Jul 23 '17 at 23:20
@Hamish "Equality implies substitutability" -- yes it does. I would say that == would mean they return the same results always. And === means they are exactly exactly the same. As far as variables that are not of `Equatable` type, well in my opinion, there should be no such variables! If there are, they should be eliminated from the language systematically as a top priority. All vars should be equatable—why are some not? As for captured variables, they only get captured once a function has run. Comparing closures would be easy: just see if they contain the same instructions or not. — CommaToast, Jul 24 '17 at 09:23
@Alexander See Middleware in ReSwift... lol... just be ready to have your face melted off. — CommaToast, Jul 24 '17 at 09:27
@CommaToast "I would say that == would mean they return the same results always" OK, so how would you go about writing the code to test for that with respect to closures? — JeremyP, Jul 24 '17 at 10:09
@CommaToast But checking to see if they contain the same instructions does *not* check whether they "return the same results always". In the example I gave above, one closure makes a call to `print`, the other makes a call to `sayHi`. In an -Onone build, those closures won't contain the same instructions, but they'll always do the same thing. Furthermore, the level of optimisation would affect the results you get (w/ inlining, specialisation etc.). As JeremyP says, determining equality by "they always do the same thing" would require a solution to the halting problem. — Hamish, Jul 24 '17 at 10:09
"As for captured variables, they only get captured once a function has run" This is not correct. The captures happen at the time when the closure is instantiated, not when it runs. — JeremyP, Jul 24 '17 at 10:11
Omg, this is plain horrible. What is the stuff that swift designers are smoking? It;s destroying everyone's sanity. ALL they needed was comparing the pointers to functions. That's it. Is it THAT difficult to bridge? — Anton Tropashko, Oct 21 '20 at 12:39
@anton-tropashko The question is not, "How to compare pointers," but rather, how to compare two actual closures (which could be from different places in code). If I was the Swift team, I might accomplish this by having a SHA of each compiled closure in a table. If the SHA's are different then the closures cannot be the same. — CommaToast, Oct 23 '20 at 01:05
Now you have it: https://stackoverflow.com/questions/64496302/in-swift-5-what-is-a-way-to-compare-pointers-to-two-closures — Anton Tropashko, Oct 23 '20 at 08:11

JeremyP · Answer 1 · 2017-07-24T10:33:30.573

11

I'm pretty sure there is no way to determine if two closures are equal.

Obviously, a logical equality check is out of the question. That would be equivalent to finding an answer to the halting problem. (Just test to see if your code is equivalent to a piece of code that loops forever. If it is, it doesn't halt. If it isn't, it does halt.)

In theory you might expect the === operator to test if two closures are the exact same piece of code, but that gives an error when I try it in Playground.

Playground execution failed: error: MyPlayground.playground:1:20: error: cannot check reference equality of functions; operands here have types '(Int) ->  ()' and '(Int) -> ()'
let bar = closure1 === closure2
          ~~~~~~~~ ^   ~~~~~~~~

Having thought about it, I'm sure the reason why that doesn't work is because you can't be sure that the closures really are equal. A closure is not just the code, but also the context in which it was created including any captures. The reason you can't check for equality is that there is no meaningful way in which two closures are equal.

To understand why thew captures are important, look at the following code.

func giveMeClosure(aString: String) -> () -> String
{
     return { "returning " + aString }
}

let closure1 = giveMeClosure(aString: "foo")
let closure2 = giveMeClosure(aString: "bar")

Are closure1 and closure2 equal? They both use the same block of code

print(closure1()) // prints "returning foo"
print(closure2()) // prints "returning bar"

So they are not equal. You could argue that you can check the code is the same and the captures are the same, but what about

func giveMeACount(aString: String) -> () -> Int
{
    return { aString.characters.count }
}

let closure3 = giveMeACount(aString: "foo")
let closure4 = giveMeACount(aString: "bar")

print(closure3()) // prints 3
print(closure4()) // prints 3

Apparently these closures are equal. It's not possible to implement any reasonable definition of equality that will work in every case, so Apple has instead not even tried. This is safer than providing an incomplete implementation that is wrong in some cases.

edited Jul 24 '17 at 10:33

answered Jul 23 '17 at 23:00

JeremyP

84,577
15
123
161

Well, I appreciate the attempt, but that's just not correct. In the example I gave in my question, we have two closures that are *quite clearly not equal*. However if they both said "foo" then they would be perfectly well equal, in the most meaningful possible way. Sure, if there were captured variables that were different between them, then they would be different -- why is that confusing? If the contexts are different the the closures are different. Seems straightforwards to me. The real reason they can't do it, evidently, has to do with compiler optimizations or some such voodoo... – CommaToast Jul 24 '17 at 09:35
@CommaToast The fact that you can tell if two closures are not equal in some trivial cases has no bearing on the general answer to the question. You can't compare closures in Swift (with good reason) and that is the end of the story. – JeremyP Jul 24 '17 at 09:59
1

@CommaToast In simplified instances, determining if two pieces of code behave the same *is possible*. In the general case, this is a transformation of the Halting problem, and is undecidable. Completely partitioning the set of all possible closures into those that do and don't fall into the "determinably equivalent" category is also a transformation of the Halting problem, and also undecidable. – Alexander Jul 24 '17 at 15:23
1

You cannot compare closures in Swift, at all, @JeremyP? You can compare their types, which narrows it down very far. The 2nd new example you added has 2 closures that are obviously not the same (they have different input values). It is precisely this aspect of equality—the ability to check, knowing two closures are the same type, whether their input value and the parts of their captured scope that they access equate—that is sorely lacking. A closure is a black box; you cannot even get read-only access into their state. You cannot say `closure1.$0` and see its first arg, or `closure1.scope`... – CommaToast Jul 25 '17 at 00:37
@Alexander Why then does git know if two pieces of code are the same or different, when I paste them over each other, having normalized whitespace and symbols? How can I reliably assign `closure1 = closure2` if the system has no way to guarantee they are the same? Clearly the type of closures can be compared, as can the machine instructions therein, so all that remains is to compare the scope and captures, right? We could easily wall off the questions relating to Halting problem simply by imposing reasonable restrictions on the definition of Equatable. – CommaToast Jul 25 '17 at 00:50
Besides I don't see how the Halting problem is relevant. We don't need to know whether each closure will loop infinitely or not, to be able to tell that whatever it is they do, it will be the same or different between the two. – CommaToast Jul 25 '17 at 00:54
@CommaToast Many problems are transformations in the halting problem. By the same elements of reflection and negation, you can write proofs that state that it's impossible to determine if two arbitrary pieces of code behave the same, in the general case. – Alexander Jul 25 '17 at 01:15
@CommaToast Closures having the same type is necessary for them to be equivalent, but it's definitely not sufficient. Closures with different instructions can behave the same. Also, captured variables might be non-equatable. – Alexander Jul 25 '17 at 01:16
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/150038/discussion-between-alexander-and-commatoast). – Alexander Jul 25 '17 at 01:16
Well your link is broken but I've been thinking about this again recently. For one thing, the halting problem is really not proven to be impossible to solve, people just think it is, because of some papers from the 1930s that few people actually read in detail. If you read Turing's paper for example, the "proof" assumes that no computer program can ever be able to recognize itself. That is dumb because it can be done. It just has to be smart enough. – CommaToast Oct 23 '20 at 01:15
As for the question of closures, the compiler must be able to tell if two are the same, because the optimizer removes duplicate code from your app. The runtime has to be able to tell things apart or it would not even be able to run at all because it would have no way at all to distinguish whether it was running the correct code. Lastly, clearly any compiled closure is stored somewhere on disk, which means, it's just ones and zeroes. Are you telling me you can't compare two binary integers? – CommaToast Oct 23 '20 at 01:19
Consider also that if you alter the binary of some app, then your Mac won't run it anymore because now the code signature will be invalid. That means it can tell whether one app is the same as another app. Well, if this logic can apply to an entire app, why can't it apply to a closure? Of course... it can. But the people who made Swift simply didn't bother to implement it yet. – CommaToast Oct 23 '20 at 01:21
1

@CommaToast First, I don't agree with you about Turing's proof. For a start, he isn't the only person to have done it. Alonzo Church came up with the same result using the lambda calculus. Secondly, even if it's theoretically possible to determine if two arbitrary pieces of code are the same, it's not been done in practice. – JeremyP Oct 23 '20 at 07:05
@CommaToast You can't tell if two closures are the same just by comparing the code byte for byte. You also need to account for the captured variables. You also can't rely on code signing. That's just same as comparing the code byte for byte but knowing the code can't be changed. You still have the problem of the captures. – JeremyP Oct 23 '20 at 07:09
It's an interesting problem to be sure. Seems like Church/Turing problem is just about how to know if some code would run forever or stop, and this relates to Godel's incompleteness theorem since what if you feed a function into itself? But I'd be happy just to compare if two references to a closure have the same code and captures, if the captures used are all equatable too. Maybe it's impossible though. – CommaToast Nov 17 '20 at 23:32

score 11 · Answer 2 · answered Jul 24 '17 at 15:24

In the case where you want to track your own closures, uses them as Dictionary keys, etc., you can use something like this:

struct TaggedClosure<P, R>: Equatable, Hashable {
    let id: Int
    let closure: (P) -> R

    static func == (lhs: TaggedClosure, rhs: TaggedClosure) -> Bool {
        return lhs.id == rhs.id
    }

    var hashValue: Int { return id }
}

let a = TaggedClosure(id: 1) { print("foo") }
let b = TaggedClosure(id: 1) { print("foo") }
let c = TaggedClosure(id: 2) { print("bar") }

print("a == b:", a == b) // => true
print("a == c:", a == c) // => false
print("b == c:", b == c) // => false

In Swift 3, what is a way to compare two closures?

2 Answers2

Linked

Related