How is equality of anonymous function closures checked?

Internals & Design
, ,
1

I was wondering how equality of functions works in Julia, and eventually stumbled on this example, which I can’t quite explain:

julia> f = x -> y -> x + y
#1 (generic function with 1 method)

julia> g = f(1); h = f(1); g == h
true

So far, so good. Both g and h are the increment function.

julia> f = x -> y -> x = y
#5 (generic function with 1 method)

julia> g = f(1); h = f(1); g == h
false

Here things get a bit hairy. Why are g and h not equal?

And lastly, is it standard for variables in a function closure g to change after g has been declared, just by calling g?

julia> f = x -> y -> (print(x, "\n"); x = y)
#65 (generic function with 1 method)

julia> g = f(1); g(1); g(2); g(3); g(4);
1
1
2
3
1 Like
2

Can you explain more about what you believe these functions should do? It seems natural to me that x is mutated in your final example, but you seem to not think that should happen if I understand you correctly.

4

I think I expected the second example to return true. I haven’t called either g or h, so the value of x should still be 1 in both of them.

Also, I’m wondering how Julia checks equality without getting trapped in an infinite loop. In particular, it’s conceivable to put a pointer to g inside g by calling g(g) in the last example. Then the obvious way of checking equality would go in an infinite loop.

5

This is not close to a complete explanation, but this long snippet using a debugger is how I’d go about exploring a question like that:

julia> using Debugger

julia> f = x -> y -> x + y
#1 (generic function with 1 method)

julia> g = f(1); h = f(1);

julia> @enter g == h
In ==(x, y) at operators.jl:83
>83  ==(x, y) = x === y

About to run: (===)(var"#2#4"{Int64}(1), var"#2#4"{Int64}(1))
1|debug> n
In ==(x, y) at operators.jl:83
>83  ==(x, y) = x === y

About to run: return true
1|debug> n
true

julia> f = x -> y -> x = y
#5 (generic function with 1 method)

julia> g = f(1); h = f(1);

julia> @enter g == h
In ==(x, y) at operators.jl:83
>83  ==(x, y) = x === y

About to run: (===)(var"#6#8"(Core.Box(1)), var"#6#8"(Core.Box(1)))
1|debug> n
In ==(x, y) at operators.jl:83
>83  ==(x, y) = x === y

About to run: return false
1|debug> n
false

julia> Core.Box(1) === Core.Box(1)
false

julia> 1 === 1
true

The big contrast is between:

(===)(var"#2#4"{Int64}(1), var"#2#4"{Int64}(1))

and

(===)(var"#6#8"(Core.Box(1)), var"#6#8"(Core.Box(1)))
5 Likes
6

Note that in general comparing two functions is not possible (aka decidable: math - Is finding the equivalence of two functions undecidable? - Stack Overflow).

What Julia does here is falling back to === (as John showed) which compares the memory-address of the function definition. This is apparently not the same in your second example, because of the Box. But I don’t think there is any guarantee that future Julia versions will compare the first example equal.

3 Likes
7

Closures are just “anonymous” functors, i.e. the first case translates roughly to

struct ClosureX{T}
    inner::T
end

(f::ClosureX)(x) = f.inner(x)

struct ClosureY{T}
    x::T
end

(f::ClosureY)(y) = f.x + y

f = ClosureX(ClosureY)

As such, f(1) is always ClosureY{Int}(1) and, as it is an immutable struct, instances are compared by value by default.

In the second case, ClosureY must be a mutable struct because of the assignment:

mutable struct ClosureY
    x
end

(f::ClosureY)(y) = f.x = y

Mutable structs are compared by reference by default, so, multiple calls to f return different objects.

Keep in mind that in the first example, g and h are equal only because they are created as identical structs, not because they “do the same thing”. If you define another function ff in the same way as f, f(a) and ff(a) would not be equal:

julia> f = x -> y -> x + y
#5 (generic function with 1 method)

julia> ff = x -> y -> x + y
#9 (generic function with 1 method)

julia> f(1) == ff(1)
false
6 Likes
8

I’m not sure this is quite right since the boxing enables mutation without using mutability at the struct level. I’m not 100% confident I know the implementation well enough to say, but I think there’s some evidence that the struct equivalent for the mutation-supporting closure is itself an immutable struct:

julia> f = x -> y -> x = y
#1 (generic function with 1 method)

julia> g = f(1)
#2 (generic function with 1 method)

julia> h = f(1)
#2 (generic function with 1 method)

julia> typeof(g).mutable
false

julia> mutable struct ClosureY
           x
       end

julia> ClosureY.mutable
true
1 Like
9

It’s not because of mutable type declarations.

1) Meta.@lower x -> y -> x = y 
:($(Expr(:thunk, CodeInfo(
    @ none within `top-level scope'
1 ─      $(Expr(:thunk, CodeInfo(
    @ none within `top-level scope'
1 ─      global var"#38#40"
│        const var"#38#40"
│   %3 = Core._structtype(Main, Symbol("#38#40"), Core.svec(), Core.svec(:x), false, 1)
│        var"#38#40" = %3
│        Core._setsuper!(var"#38#40", Core.Function)
│        Core._typebody!(var"#38#40", Core.svec(Core.Box))
└──      return
)))
│        $(Expr(:thunk, CodeInfo(
    @ none within `top-level scope'
1 ─      global var"#37#39"
│        const var"#37#39"
│   %3 = Core._structtype(Main, Symbol("#37#39"), Core.svec(), Core.svec(), false, 0)
│        var"#37#39" = %3
│        Core._setsuper!(var"#37#39", Core.Function)
│        Core._typebody!(var"#37#39", Core.svec())
└──      return
)))
│   %3 = Core.svec(var"#38#40", Core.Any)
│   %4 = Core.svec()
│   %5 = Core.svec(%3, %4, $(QuoteNode(:(#= REPL[20]:1 =#))))
│        $(Expr(:method, false, :(%5), CodeInfo(quote
    y
    Core.getfield(#self#, :x)
    Core.setfield!(%2, :contents, %1)
    return %1
end)))
│   %7 = Core.svec(var"#37#39", Core.Any)
│   %8 = Core.svec()
│   %9 = Core.svec(%7, %8, $(QuoteNode(:(#= REPL[20]:1 =#))))
│        $(Expr(:method, false, :(%9), CodeInfo(quote
    x@_4 = x@_2
    x@_4 = Core.Box(x@_4)
    #38 = %new(var"#38#40", x@_4)
    return #38
end)))
│        #37 = %new(var"#37#39")
└──      return #37
))))
2) Meta.@lower x -> y -> x+y 
julia> Meta.@lower x -> y -> x + y
:($(Expr(:thunk, CodeInfo(
    @ none within `top-level scope'
1 ─      $(Expr(:thunk, CodeInfo(
    @ none within `top-level scope'
1 ─      global var"#42#44"
│        const var"#42#44"
│        Core.TypeVar(:x, Core.Any)
│   %4 = Core._structtype(Main, Symbol("#42#44"), Core.svec(%3), Core.svec(:x), false, 1)
│        var"#42#44" = %4
│        Core._setsuper!(var"#42#44", Core.Function)
│        Core._typebody!(var"#42#44", Core.svec(%3))
└──      return
)))
│        $(Expr(:thunk, CodeInfo(
    @ none within `top-level scope'
1 ─      global var"#41#43"
│        const var"#41#43"
│   %3 = Core._structtype(Main, Symbol("#41#43"), Core.svec(), Core.svec(), false, 0)
│        var"#41#43" = %3
│        Core._setsuper!(var"#41#43", Core.Function)
│        Core._typebody!(var"#41#43", Core.svec())
└──      return
)))
│   %3 = Core.svec(var"#42#44", Core.Any)
│   %4 = Core.svec()
│   %5 = Core.svec(%3, %4, $(QuoteNode(:(#= REPL[21]:1 =#))))
│        $(Expr(:method, false, :(%5), CodeInfo(quote
    Core.getfield(#self#, :x)
    %1 + y
    return %2
end)))
│   %7 = Core.svec(var"#41#43", Core.Any)
│   %8 = Core.svec()
│   %9 = Core.svec(%7, %8, $(QuoteNode(:(#= REPL[21]:1 =#))))
│        $(Expr(:method, false, :(%9), CodeInfo(quote
    var"#42#44"
    Core.typeof(x)
    Core.apply_type(%1, %2)
    #42 = %new(%3, x)
    return #42
end)))
│        #41 = %new(var"#41#43")
└──      return #41
))))
3) Meta.@lower mutable struct A end 
julia> Meta.@lower mutable struct A end
:($(Expr(:thunk, CodeInfo(
    @ none within `top-level scope'
1 ─       global A
│         const A
│   %3  = Core.svec()
│   %4  = Core.svec()
│         #16#A = Core._structtype(Main, :A, %3, %4, true, 0)
│         Core._setsuper!(#16#A, Core.Any)
│   %7  = $(Expr(:isdefined, :A))
└──       goto #6 if not %7
2 ─ %9  = A
│   %10 = Core._equiv_typedef(%9, #16#A)
└──       goto #4 if not %10
3 ─       #16#A = %9
└──       goto #5
4 ─       A = #16#A
5 ┄       goto #7
6 ─       A = #16#A
7 ┄ %17 = #16#A
│   %18 = Core.svec()
│         Core._typebody!(%17, %18)
│         global A
│         $(Expr(:method, :A))
│   %22 = Core.Typeof(A)
│   %23 = Core.svec(%22)
│   %24 = Core.svec()
│   %25 = Core.svec(%23, %24, $(QuoteNode(:(#= REPL[22]:1 =#))))
│         $(Expr(:method, :A, :(%25), CodeInfo(quote
    A
    %new(%1)
    return %2
end)))
└──       return
))))
4) Meta.@lower struct A end 
julia> Meta.@lower struct A end
:($(Expr(:thunk, CodeInfo(
    @ none within `top-level scope'
1 ─       global A
│         const A
│   %3  = Core.svec()
│   %4  = Core.svec()
│         #17#A = Core._structtype(Main, :A, %3, %4, false, 0)
│         Core._setsuper!(#17#A, Core.Any)
│   %7  = $(Expr(:isdefined, :A))
└──       goto #6 if not %7
2 ─ %9  = A
│   %10 = Core._equiv_typedef(%9, #17#A)
└──       goto #4 if not %10
3 ─       #17#A = %9
└──       goto #5
4 ─       A = #17#A
5 ┄       goto #7
6 ─       A = #17#A
7 ┄ %17 = #17#A
│   %18 = Core.svec()
│         Core._typebody!(%17, %18)
│         global A
│         $(Expr(:method, :A))
│   %22 = Core.Typeof(A)
│   %23 = Core.svec(%22)
│   %24 = Core.svec()
│   %25 = Core.svec(%23, %24, $(QuoteNode(:(#= REPL[23]:1 =#))))
│         $(Expr(:method, :A, :(%25), CodeInfo(quote
    A
    %new(%1)
    return %2
end)))
└──       return
))))

Note the difference between 3 & 4 - it’s just the fifth field of the call to Core._structtype, which (I think) stands for mutability. Neither 1 nor 2 have that set to true, so they’re not mutable structs (ismutable works on instances, that’s the reason for the call):

julia> f = x -> y -> x + y
#45 (generic function with 1 method)

julia> ismutable(f(1))
false

julia> g = x -> y -> x = y
#49 (generic function with 1 method)

julia> ismutable(g(1))
false

The Box the second one is capturing is though:

julia> f(1) |> dump
#46 (function of type var"#46#48"{Int64})
  x: Int64 1

julia> f(1).x |> ismutable
false

julia> g(1) |> dump
#50 (function of type var"#50#52")
  x: Core.Box
    contents: Int64 1

julia> g(1).x |> ismutable
true
4 Likes
10

it looks like we need undecidable value as new possible output for predicate functions (true false)

11

Note that generally, if you cannot decide a == b, returning false is harmless, which is why it is the fallback.

== of anything nontrivial should be defined by the programmer, not the language.

1 Like
12

generally you can also express a predicate by negating its opposite

13

Sure — that’s why that is the general fallback for !=.

1 Like
14

Ok, I don’t get the confusion. The default for == and isequal is ===.

The ===-operator cannot be overridden, it is a core language built-in. The rough idea is: Two objects are === if and only if the compiler is permitted to replace one by the other, i.e. if their difference is unobserveable (without unsafe pointer arithmetic). If you can distinguish the objects without invoking UB / poking at memory / breaking the language, then they are not ===.

The meaning of === for mutable types is pointer equality. For primitives, it is equality of bit-patterns. For immutable struct, it is recursive, i.e. === for each field.

Note that you cannot attach finalizers to immutable objects, nor take their address (pointer_from_objref) – because that would potentially allow you to distinguish === objects, and the compiler doesn’t like that.

There is one impure, ugly and very pragmatic exception: String. Strings are immutable and === iff their contents are equal. However, pointer_from_objref("aaa") is still permissible, for more pragmatic C interop.

So the true rule is more like: If objects are considered identical, then the language/compiler can guarantee/prove that they can only be distinguished by pointer-slinging and pointer_from_objref(x::String).

It does not matter how deep you hide the mutability – i.e. whether the closure itself is mutable, or whether it is immutable and contains a mutable (Box) field. Either way, you can write a distinguisher between the closures, and it would be a serious bug if they were considered ===.

(another exception is malformed booleans: If you unsafe_load or unsafe_store! a bitpattern that is not 0x00 or 0x01 into a Bool, then equality/identity is somewhere between undef/poison/UB. Structure padding is ignored by ===.)

3 Likes
15

I don’t think you can use the value of pointer_from_objref to distinguish objects, so this is not “ugly” or inconsistent.

1 Like
16

The inconsistent thing is that pointer_from_objref of String is allowed, even though it is ignored by === – so you can, in this one instance, distinguish objects that are jl_egal. Irregardless of debatable consistency, I’m very happy with the pragmatic behavior!

1 Like