This somewhat overlaps with Universal Equatability, Hashability, and Comparability, but is more focused on functions.
There are also some connections to Pitch: Introduce (static) callables - that one enables calling structs as functions, while this post is about comparing functions as structs.
I'm working on a company's internal reactive programming framework. Framework heavily relies on comparing old values with new values to decide if computation did not change anything or updates should be propagated further. Which requires all the values framework operates with to be Equatable.
Actually, we even require them to be Hashable, because there is a handy AnyHashable, but there is no AnyEquatable. And since 99.9% of Hashable conformance is generated by the compiler, this comes for free from the source code perspective.
But we reached a point where some of the values need to be functions or structs containing functions. And here starts the fun part - now we need to compare functions.
Two values are equal if using either of them produces the same results (including side effects). For functions to be equal they should perform equal actions on equal captured values.
Comparing actions
Equality of actions in general case is an unsolvable problem, but if we could instead compare some token identifying the code site, that would be a reasonable proxy.
For example, given:
func makeFunc(cond: Bool, x: Int) -> () -> Void {
if (cond) {
return { print(X) }
} else {
return { print(x) }
}
}
expected result would be makeFunc(true, 42) != makeFunc(false, 42)
But given
func makeFunc(cond: Bool, x: Int) -> () -> Void {
if (cond) {
return makeFuncImpl(x: x)
} else {
return makeFuncImpl(x: x)
}
}
func makeFuncImpl(x: Int) -> () -> Void {
return { print(x) }
}
expected result would be makeFunc(true, 42) == makeFunc(false, 42)
Comparing captured values.
For structs and classes that conform to Equatable, we can assume that providers of the conformance took the responsibility of implementing proper equality semantics. That would also nicely expand to tuple, functions and metatypes, if structural types could conform to protocols.
If function captures references to shared mutable data structures it may potentially either make visible mutations or observe mutations done from outside.
So for two functions to have the same effect, all the references to shared mutable data structures should be the same. Current values of the mutable data are irrelevant. The same function may be called multiple times changing the value of mutable data, but function should remain equal to itself.
Interesting consequence from this is that in majority of cases every instance of a function which captures mutable local variables is unique. For example, every time this function is called, it produces a unique function:
func makeFunc() -> () -> Void {
var k = 0
return { k += 1 }
}
But that's not always the case. See counter example:
var k = 0
let funcs = (0..<1).map { _ in { k += 1 } }
funcs[0] == funcs[1] // true
It may be convenient to automatically compare captured class istances by identity. But also it may be a good idea to stay on the safe side and require all captured classes to explicitly conform to Hashable. Personally, I often use a helper protocol for this:
protocol HashableByIdentity: AnyObject, Hashable {}
extension HashableByIdentity {
static func == (lhs: Self, rhs: Self) -> Bool { return lhs === rhs }
func hash(into hasher: inout Hasher) { hasher.combine(ObjectIdentifier(self)) }
}
What we tried so far to implement this functionality using existing language features:
First of all, since function types themselves cannot conform to protocol because thay are not nominal, we are operating on functions wrapped into a generic structure which conforms to Hashable.
Our first attempt was to store custom comparison key together with a function. Ideally that comparison key should contain a token identifying a site where function was created, and a copy of every captured value. This turned out to be error-prone and very confusing for framework users - people were forgetting to include a captured value into the key or even passing useless dummy values.
Second approach - use custom protocol instead of function type and use hand-written hashable structs conforming to this protocol instead of functions. This is 100% reliable, but it was heavily critisized as being too verbose. Also we discovered that structs cannot be declared inside generic functions.
For the purposes of our framework we can tolerate false negatives - if two functions are doing the same but get compared as non equal, framework will perform redundant updates, but final result will be correct. But false positives are critical - if two functions which have different effects will compare as equal, newer one will not propagate, and old one may be called, leading to a bug.
So this leads to a third approach - unsafeBitCast'ing functions to a struct with two raw pointers and comparing those structs. Since in our framework we are comparing different generations of functions, in practise this always returns false. But that is still better than equality operator that always returns false - at least axiom of x == x holds.
And finally - currently I'm trying to use Swift metadata to inspect functions in runtime - Runtime/FunctionMirrorTests.swift at master · nickolas-pohilets/Runtime · GitHub. It does not work with functions created in a generic context. And for best results function literal should be immediately wrapped into the wraping structure to avoid problems like this - Why storing function in the Array produces a reabstraction thunk?.
All 4 approaches are poor man's solutions. Ideal solution would be to have this baked into the language.
Let's imagine how this could look like and work under the hood.
This feature places restrictions on values being captured, and is not needed in every case. So, I think this feature should be an opt-in. Similar to @escaping this could be an attribute:
typealias UsualFunc = (Int) -> Void
typealias EquatableFunc = @equatable (Int) -> Void
typealias HashableFunc = @hashable (Int) -> Void
The @equatable attribute probably is redudant. So far, I haven't encountered any example of type which conforms to Equatable, but has good reasons not to conform to Hashable.
If function captures a value that does not conform to Equatable/Hashable - this should produce an error. Note that currently it is not possible to conform tuples, other functions, metatypes and existential containers to a protocol. Technically it is possible to implement some ad-hoc solution limited to function comparison, but that sounds very hackish to me. Probably it is worth to return to the discussion of Universal Equatability, Hashability, and Comparability.
If function captures a mutable local variable - this should produce an warning/error. Equality with captured mutable variables is tricky and I think it is better to warn user about potential unexpected behaviour. It is always possible to box the value manually.
Protocol conformance for structural types would be very beneficial in this context. Otherwise Array's of @hashable functions are still not Hashable.
Function may be wrapped into an onion of the reabstraction wrappers. To perform the comparison, reabstraction wrappers should be followed until reaching the initial function. For this reabstraction wrapper should distinguishable from a regular funciton capturing another function. This can be achieved by adding a flag to the metadata of the function context, which would be set to 1 for reabstraction wrappers and to 0 for regular functions. Or it can be a separate kind of metadata.
I suspect actual code pointers stored inside a function may be not a reliable identifier of the function creation site because of optimizaions. Pointer to the medata of the context could be used instead.
And finally, pointer to witness table for Equatable/Hashable should be stored somewhere. It can be stored inside a function itself, making it a 3-word sized structure. Or inside the context, increasing value of the metadata field OffsetToFirstCapture from 2 words to 3. Or in the context metadata. The last option would minimize code bloat.