How bad is it if x < y doesn't return a Bool?

[gdalle]

Suppose I define a number type T for which order comparison is not meaningful: <(x::T, y::T) doesn’t make any mathematical sense, because T actually contains a set. There are good reasons why I’m doing this, see SparseConnectivityTracer.jl, but that’s not the topic of today.

My problem is that I still want to allow control flow with ifelse. In my scenario, ifelse(x < y, a, b) should ignore the comparison result and just return some function f(a, b) (essentially taking both branches at once).
How bad is it if I define something like the following?

struct T <: Real
    s::Set{Int}
end

f(a::T, b::T) = T(union(a.s, b.s))
Base.:<(x::T, y::T) = missing
Base.ifelse(::Missing, a::T, b::T) = f(a, b)

It works:

julia> a, b = T(Set([1, 2, 3])), T(Set([3, 4, 5]));

julia> ifelse(a < b, a, b)
T(Set([5, 4, 2, 3, 1]))

But I’m afraid it might lead to invalidations or other bad behavior. How criminal is it to break the convention that < must return a Bool?

[Datseris]

I would say at least 10 years in prison level of criminal. But it doesn’t have to be.

Why don’t you make a singleton type so

struct MyTIsLess end
Base.:<(x::T, y::T) = MyTIsLess()

so that you extend the method

Base.ifelse(::MyTIsLess, a::T, b::T) = f(a, b)

? There is no type piracy in this approach. Is there any meanigful reason you chose Missing initially?

[Datseris]

In any case though, I would choose a different symbol than <. You can use many of the supported unicode infix operators.

[gdalle]

@Datseris

There is no type piracy in this approach.

There is no type piracy in the initial approach either because I overload ifelse(::Missing, ::T, ::T) and I own T.
However you’re right: returning a singleton type that I own would allow me to overload ifelse(::MyTIsLess, ::Any, ::Any), which is even better.

Sadly, in both cases, we might cause invalidations if already-compiled methods assume that < should return a Bool.

@Datseris

In any case though, I would choose a different symbol than <. You can use many of the supported unicode infix operators.

The point is to use this in an operator overloading approach, so that it works with pre-existing code (à la ForwardDiff). If I need to introduce new symbols, I destroy this hope.

[lrnv]

If I understand you correctly, your code implies that (x < y) === (y < x), which seems pretty bad.

Maybe a type holding the two parts of the comparison would make more sense :

struct MyCompare{T}
  x::T
  y::T
end
Base.:<(x::T, y::T) = MyCompare(x,y)
Base.ifelse(C::MyCompare, a::T, b::T) = f(C.x,C.y, a, b)

?

Otherwise, you better ensure that f(a,b) == f(b,a) !

[gdalle]

@lrnv

If I understand you correctly, your code implies that (x < y) === (y < x), which seems pretty bad.

In my case that’s exactly what I want. Essentially, I need a way to take both branches of ifelse and so the comparison result doesn’t matter.

The context is sparsity detection for Jacobians. I’m trying to determine which input variables x_j influence which output variables y_i, because they will correspond to nonzeros in the Jacobian matrix \partial y / \partial x. If I have control flow in my function y(x), I need to consider both branches, because they may lead to different sparsity patterns depending on the value of x. That’s what the sets are about in the struct T (they are sets of input indices j), and that’s why I take f to be the union operation.

[lrnv]

Ok so the union of sets part is actually what you are doing and not a mock-up ? In which case it seems resonable to use a singleton type as DatSeries proposed with ifelse(::CompareIsUnion, a, b) = union(a,b) directly and then union(a::T,b::T) = T(union(a.set,b.set))

[gdalle]

This will probably lead to method invalidations, right? Are those avoidable?

[Elrod]

To answer the initial question of “had bad is it”, there are precedents. For example, Symbolics.jl:

julia> using Symbolics

julia> @variables w x y z;

julia> x < y
x < y

julia> ifelse(x < y, w, z)
ifelse(x < y, w, z)

The answer of ifelse also contains the union of inputs (i.e., both w and z), but if you’re only interested in the incidence, you can be more efficient by not preserving the structure.

As an aside, I’d also suggest numbering your inputs and using BitSets for much faster set operations.

The other packages that immediately come to mind which don’t return Bool iare the SIMD packages, VectorizationBase.jl and SIMD.jl.

[gdalle]

Thanks! And indeed, BitSet is used under the hood

[Sukera]

@Elrod

To answer the initial question of “had bad is it”, there are precedents. For example, Symbolics.jl:

To be fair though, Symbolics.jl is much closer to being its own language with its own semantics than just a regular julia package. It using Julia semantics as a sort-of semi-CAS is not a good example for why subverting expectations on logical operations is a good idea, especially since that has already led to friction in the past.

@gdalle since you want to have ifelse(foo, a, b) mean sort-of foo(a,b), why use ifelse at all? That operation sounds like a very different one than ifelse.

[ericphanson]

BTW in terms of precedent, Convex.jl also returns constraint objects from ==, <=, and >= between its expression objects and numbers/matrices (and between expressions and other expressions), and has done so for ~10 years. I don’t think it’s caused severe issues, but I wouldn’t be surprised if there were some invalidations or such.

[gdalle]

@Sukera

To be fair though, Symbolics.jl is much closer to being its own language with its own semantics than just a regular julia package. It using Julia semantics as a sort-of semi-CAS is not a good example for why subverting expectations on logical operations is a good idea, especially since that has already led to friction in the past.

@Sukera do you have examples of such friction? The comparison actually makes sense because what we’re coding with @hill is an alternative to Symbolics for Jacobian and Hessian sparsity pattern detection.

@Sukera

@gdalle since you want to have ifelse(foo, a, b) mean sort-of foo(a,b), why use ifelse at all? That operation sounds like a very different one than ifelse.

Because I’m not writing the code that will be subjected to operator overloading, my users are writing it. And I want my new (set-containing) types to flow freely through existing code that uses comparisons or ifelse.

[Sukera]

@gdalle

@Sukera do you have examples of such friction?

Generalize `==` Documentation to not be Statistics-Specific by ChrisRackauckas · Pull Request #53024 · JuliaLang/julia · GitHub for one, or the whole Static{Int} debate for another.

@gdalle

The comparison actually makes sense because what we’re coding with @hill is an alternative to Symbolics for Jacobian and Hessian sparsity pattern detection.

What you’re describing sounds to me like abstract interpretation, i.e. a static analysis pass like the kind of thing JET.jl is doing. Not execution under Julia semantics and bending/breaking the expected API of a set of functions.

[gdalle]

@Sukera

What you’re describing sounds to me like abstract interpretation, i.e. a static analysis pass like the kind of thing JET.jl is doing. Not execution under Julia semantics and bending/breaking the expected API of a set of functions.

Abstract interpretation is a common technique in autodiff, which is the intended application of our code. Except that here we implement it with simple operator overloading, instead of a more sophisticated compiler-hooked machinery like JET. It’s a similar distinction as between ForwardDiff (operator overloading AD) and e.g. Zygote or Enzyme (source transformation AD).

[Sukera]

@gdalle

Abstract interpretation is a common technique in autodiff,

Abstract interpretation is a compiler technique to reason about some syntax (in this case, julia syntax) with some semantics (in your case, non-julia semantics, since ifelse is not actually supposed to branch). What you’re describing is doing exactly that, but you’re trying to do that inside of the semantics of julia and its type system. By necessity, that means breaking the contract of e.g. == or <, since those are (generally) expected to return a Bool.

@gdalle

Except that here we implement it with simple operator overloading, instead of a more sophisticated compiler-hooked machinery like JET. It’s a similar distinction as between ForwardDiff (operator overloading AD) and e.g. Zygote or Enzyme (source transformation AD).

It’s my understanding that this is already how Symbolics.jl works under the hood, with all the problems that entails. As such, I think those problems also apply to your approach Maybe I’m misunderstanding something?

[gdalle]

@Sukera

Abstract interpretation is a compiler technique

In the autodiff literature, this term refers to a wide array of techniques, not all of which hook into the compiler. It’s more of a broad synonym for “changing the semantics of your code”. Minor terminology quirk, which @oxinabox could probably clarify better than me.

@Sukera

It’s my understanding that this is already how Symbolics.jl works under the hood, with all the problems that entails. As such, I think those problems also apply to your approach Maybe I’m misunderstanding something?

I think you’re right. It’s also the same paradigm that ForwardDiff.jl and Measurements.jl follow. Changing semantics by operator overloading is dangerous, and there’s a compromise to find on how disruptive you wanna be. This topic is about placing the needle correctly

[Elrod]

@Sukera

To be fair though, Symbolics.jl is much closer to being its own language with its own semantics than just a regular julia package. It using Julia semantics as a sort-of semi-CAS is not a good example for why subverting expectations on logical operations is a good idea, especially since that has already led to friction in the past.

FWIW, I don’t really care about Symbolics as a CAS.
I care about Symbolics as a means of tracing Julia code for use by packages like ModelingToolkit, which is quite similar to what gdalle wants to do here.

[Sukera]

@gdalle

It’s more of a broad synonym for “changing the semantics of your code”.

Yes, that’s exactly what I said in the sentences following the one you quoted You can substitute “compiler” for “interpreter” or “static analyser” in my post above and the intended meaning would not change - for the purposes of this discussion, they are equivalent.

@gdalle

Changing semantics by operator overloading is dangerous, and there’s a compromise to find on how disruptive you wanna be. This topic is about placing the needle correctly

Ultimately, the question that you’ll have to answer is what you do about code that ends up doing the equivalent of <(a,b)::Bool, be it for type stability or some other reason. Since you can’t overload ::, overloading ifelse will get you stuck with an assertion. That’s why I’m saying that what you want to do goes outside of the semantics of julia-the-language.

You can either ignore that kind of code and consider it out of scope for your project, or suggest to your users that they shouldn’t assume functions return what they’re documented to return (which sounds much more dangerous to me). The only “perfect”/nondisruptive solution is an actual abstract interpreter that can properly handle these situations, by operating on the level of an actual compiler/interpreter handling :: natively.

[gdalle]

@Sukera

Ultimately, the question that you’ll have to answer is what you do about code that ends up doing the equivalent of <(a,b)::Bool, be it for type stability or some other reason. Since you can’t overload ::, overloading ifelse will get you stuck with an assertion.

In that case an error will be thrown, and I guess that’s coherent with what I want to do