Equality of functions

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 - https://github.com/nickolas-pohilets/Runtime/blob/master/Tests/RuntimeTests/FunctionMirrorTests.swift. 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.

3 Likes

Also, since all reabstraction thunks have the same layout, there can be one metadata record shared for all reabstraction contexts. And regular functions could be distinguished from reabstraction wrappers by comparing pointer to context metadata against pointer to that shared metadata.

Hi, so you want arbitrary(pure) functions to be equatable? Or do you want the functions which are basically the copies to have a notion of identity and thus being able to determine which function is the one you care about?

I can't speak for the author, but for a very long time I have wanted functions to be Equatable and Hashable based on source code identity iff everything in the capture is Equatable and Hashable. I am not knowledgeable enough about the implementation to comment on the approach described here, but that is the semantics I am interested in.

2 Likes

Well let's start from the notion of equality of the functions, in algebra two functions are considered equal if for each input it produces the same output. As you can feel this one is tricky to implement in programming terms because some spaces are infinite, like all the possible strings, and then there comes a tuple of two strings and oh well... that's why they called product types.
Btw, to read more about searching the uncountably infinite spaces in programming, start from here: https://www.fewbutripe.com/2018/12/05/seemingly-impossible.html. This gem precedes Pointfree and for sure is a must read.

2 Likes

Also functional programming languages exist for much longer than Swift and already tried to figure this problem, so reading this is a good start as well: https://stackoverflow.com/questions/9906628/equality-of-functions-in-haskell

1 Like

Not sure if I understood your question correctly, because we might have different understanding of the terms 'pure', 'copy' and 'identity', but probably the first one.

+1 to @anandabits.

Let me explain it with examples to be clear:

class Mutable: HashableByIdentity {
  var data: [Int]
}

func makeA(x: Int) -> () -> Void {
    return { print(x + 1) }
}
func makeB(x: Int) -> () -> Void {
    return { print(x + 1) }
}
func makeC(x: Int) -> () -> Void {
   return { print(x - 1) }
}
func makeD(x: Int) -> () -> Int {
    return { x * x }
}

func makeE(ref: Mutable) -> (Int) -> Void {
  return { ref.data.append($0) }  
}

makeA(x: 1) == makeA(x: 1) // true
makeA(x: 1) == makeA(x: 2) // false
makeA(x: 1) == makeB(x: 1) // false, developer explicitly wanted those to be different
makeA(x: 1) == makeC(x: 1) // false
makeA(x: 1) == makeD(x: 1) // compilation error
AnyHashable(makeA(x: 1)) == AnyHashable(makeD(x: 1)) // false

let obj1 = Mutable()
let obj2 = Mutable()
makeE(ref: obj1) == makeE(ref: obj1) // true
makeE(ref: obj1) == makeE(ref: obj2) // false
makeE(ref: obj1)(42)
makeE(ref: obj1) == makeE(ref: obj1) // still true

This is the notion of extensional equality. You are correct that this is effectively impossible to implement in a programming language. On the other hand, it is possible to implement intensional equality, which is what I am interested in. (Note: functions do not need to be pure to be compared for intensional equality)

So seems like an identity more like.

Intensional equality is a well established notion. It is sufficient for the use cases I am aware of and is the only notion of equality that is feasible for functions.

I mean like as a way of achieving intensional equality of function we could add function identity so we could use === operator.
It is probably impossible to factor in captured variables, only captured constants. What about side effects, what do we do about them?
@Nickolas_Pohilets makeA(x: 1), makeB(x: 3) this two functions produce the same side effects, but are they equal?

No.

Treat every captured variable as a constant reference to a mutable data structure. Two functions are equal as long they mutate or observe mutations of the same data structure. See peculiar examples in my original post.

Can you please elaborate on how you see intensional equality being applied to functions? Is it something like source code equality? Or maybe like comparing actual machine codes?

  1. Compare some token that identifies source code location
  2. If token matches - compare all the captured values.

The first candidate for such token is the code address of the partial apply forwarder. This might be not very reliable because of optimisations. I think context metadata pointer would serve this role beter.

No, not actually comparing source code. Each function body would be assigned an identity by the compiler one way or another. @Nickolas_Pohilets has been exploring ways to do that.

What do you guys think about the suggested syntax - @equatable/@hashable attributes? Do you think @equatable is needed?

I don't have a strong opinion on the syntax as I am not sure what factors should drive a decision about that.

I do think we should support equatable independently of hashable. There are types that do not provide a Hashable conformance but do provide an Equatable conformance and we would want to be able to capture them in an equatable closure.

Could you give couple examples of such types?

I don't have anything concrete handy and don't have time to look this morning, but if it was expected that every Equatable type also conform to Hashable we would have one protocol instead of two.

Why I then only AnyHashable, but no AnyEquatable?

Terms of Service

Privacy Policy

Cookie Policy