Remove Interval <: Real ?

[dpsanders]

Since ForwardDiff now no longer requires types to be <: Real (JuliaDiff/ForwardDiff.jl#369, although not yet in a released version), maybe it is time to make Intervals no longer be subtypes of Real.

cc @gwater

[gwater]

As discussed earlier, I would strongly support that. (So far I have not been able to resolve the constructor issues in #181; I think for now it is a dead end.)

[Kolaru]

I am currently looking into that issue and complex numbers appear to be problematic. Complex{T} requires T <: Real, which means our current definition of complex intervals (Complex{Interval{Float64}}) would no longer be valid.

Even if the requirement to have Real components was removed from Base, it would kind of be awkward to have (0.1..0.5) not be a Real while (0.1..0.5) * im is a Complex (which is inavoidable to reuse the definitions from Base).

So I think we will have to keep Interval as Real.

[gwater]

it would kind of be awkward to have (0.1..0.5) not be a Real while (0.1..0.5) * im is a Complex (which is inavoidable to reuse the definitions from Base).

I'm not exactly sure how Complex{Interval} currently behaves. In mathematical terms it should be equivalent to a 2-dimensional IntervalBox, no? Or is it more like a straight line on the complex plane? In either case, it raises the same questions as the real case: Are complex intervals sets of numbers or do they each represent one specific (but uncertain) number? In the latter case subtyping makes sense; in the former it's problematic.

[Kolaru]

I'm not exactly sure how Complex{Interval} currently behaves.

A Complex{Interval} is simply an object A + B*im with A and B intervals, so it is like an 2-dimensional IntervalBox.

Are complex intervals sets of numbers or do they each represent one specific (but uncertain) number? In the latter case subtyping makes sense; in the former it's problematic.

While I agree with this analysis (and prefer the former interpretation), it lefts out the following practical concern: all Base complex functions for a complex number a + b*im are defined in term of operation on a and b and as a consequence, the current definition of complex interval can reuse all the definitions from Base (with the exception of some functions doing branching as in #245 ). Not subtyping complex interval to Complex implies to either redefine all these functions, or to remove the requirement for Complex to have Real components and have Complex{T} not always be a subtype of Complex. Both solution require a lot of work that I am not sure is worth for the sake of mathematical purity.

[gwater]

the current definition of complex interval can reuse all the definitions from Base (with the exception of some functions doing branching as in #245 ). […] Both solution require a lot of work that I am not sure is worth for the sake of mathematical purity.

I disagree with your premise: The subtyping question is not about mathematical purity but about very practical concerns. The implementations in Base all assume that they are handling objects representing specific numbers and that operations on their real components behave like operations on real numbers. However, real Intervals in IntervalArithmetic.jl don't behave like numbers; they behave like sets. (That is why this issue exists.) Therefore, which implmeentation is used is not a question of convenience but of meaningful results. Currently it is impossible to predict when a complex interval does what it's supposed to and when it silently breaks.

The problem isn't that Intervals are a subtype of Real; it's that they are a subtype of Number (either via Real or via Complex) while at the same time behaving like sets in many operations.

[Kolaru]

I think I get your point (and mainly agree with it). However I feel like it may be kind of tangential to the question of keeping or not Interval <: Real: in both cases we have to to handle ambiguous situations with intervals, by choosing if the process should error or not. As far as I can see, removing Interval <: Real does not help from a programming point of view (it would definitively be less confusing for the user in many case though).

[gwater]

As far as I can see, removing Interval <: Real does not help from a programming point of view

I think it would be helpful because it would a) prevent silent failures when people try to use set-like intervals as drop-ins for numbers and b) open up the way to actually implementing a number-like interval which could be used like that. The current subtyping is an anti-feature: It suggests compatibility where there actually isn't any and introduces catastrophic bugs like JuliaIntervals/IntervalRootFinding.jl#86

[Kolaru]

I think it would be helpful because it would a) prevent silent failures when people try to use set-like intervals as drop-ins for numbers

That is where I get confused by your reasonning. All basic functions are redefined in this package for intervals (otherwise Julia would not know how to handle the new type, even if it is a subtype of Real, and it would error).

Therefore if a method silently fails it is because it has been defined to do so in this package and having Real as a supertype does not seems to have any influence here.

[lbenet]

I am coming too late to the party, though I've spent some fair amount of time thinking about this. In my opinion, the discussion here reflects the discussion of the Interval community itself: is an Interval a set of numbers or a number? I think the usual opinion (with many disadvantages!) is to think it as an unknown number which lies inside a given set; there are other approaches that take it as the set of those possibilities. Both options have advantages and disadvantages.

In my specific case, I do need that Interval{T} is a subtype of something below Number, so being a subtype of Real is fine. The reason is that Taylor1{U} or TaylorN{U} (both subtypes of Number) require U<:Number. My interest is building rigorous Taylor expansions of a given function, which then requires interval coefficients for the expansion and for the remainder. Clearly, I am in favor of keeping Interval{T} at least as a subtype of Real. Yet, there are good arguments not to have it as a subtype of Real.

My proposal here is then pragmatical: let's provide another (new!) struct which is not a subtype of Real. In terms of the jargon of the IEEE standard, this amounts to define another flavor.

[gwater]

I have to admit I'm a little frustrated with this topic because I know we have discussed all of this before (eg. in #168 and #165): I completely understand that it seems practical to use Intervals with packages that expect Numbers. The problem is that currently methods like iszero() and isinfinite() as well as all comparisons are defined based on the IEEE standard which decidedly treats intervals as sets. Please look at these methods, look at the standard, and look at JuliaArrays/StaticArrays.jl#450 to see it all explodes. What we actually need for the Julian convenience drop-in Interval is a flavor which does not follow IEEE in its definitions (but builds on the IEEE methods internally). Since it was made clear in #181 that the Interval implementation in this package is meant to follow IEEE removing the Number supertype or splitting set-like and number-like Intervals is the only way to resolve this.

I will not draw this fruitless discussion out further. If you want, close this bug report and move on. I guess, if you redefine ldiv() internally you can even avoid JuliaArrays/StaticArrays.jl#450 . But you can be sure that bugs like that one will keep popping up, as long as you define set-like behaviors on a Number subtype.

[dpsanders]

I have to say that I have come round to @gwater's arguments here. I suggest we make a branch where we remove <: Real and see how much actually breaks.

As regards the knock-on effects of this, there is already a type called Compl defined, I think in IntervalRootFinding.jl, which redoes some of Complex; it should not be too hard to flesh out the rest. ForwardDiff.jl already allows types that are not <: Real.

Also, @Kolaru has a very interesting PR for defining these different "flavours", if I remember correctly.

[Kolaru]

I have to admit I'm a little frustrated with this topic because I know we have discussed all of this before (eg. in #168 and #165)

Sorry to hear that and to have appeared stubborn (well I may even actually be stubborn, as the next sentence may indicate x_x). I precisely think that the discussion here is different to #165 and #168, but won't draw this further either.

As regards the knock-on effects of this, there is already a type called Compl defined, I think in IntervalRootFinding.jl, which redoes some of Complex; it should not be too hard to flesh out the rest.

My main concern here is that base/complex.jl is about 1000 lines long, so it is definitely a serious amount of work (highlighting that I am getting closer and closer to have written 1000 lines in the different issues relating to this problem would be a valid point though). Quite a big amount of the file however seems to be about having the most precise implementation which may be adressed at a latter time.

Also I realised that if we ever want to support complex number in polar form rho * exp(im*arg), redefining everything will be pretty much inavoidable.

Also, @Kolaru has a very interesting PR for defining these different "flavours", if I remember correctly.

You probably refer to this comment in @gwater PR. It is not directly applicable to a situation with one flavour being subtype of Real (let name this PseudoNumberInterval) and not the other (say SetInterval), because they will not be able to have a common supertype.

A possible workaround is to have something like

abstract type IntervalMode end
struct Strict <: IntervalMode end
struct Silent <: IntervalMode end

struct ConcreteInterval{T, M <: IntervalMode}
    lo::T
    hi::T
end

struct PseudoNumberInterval{T, M} <: Real
    interval::ConcreteInterval{T, M}
end

struct SetInterval{T}
    interval::ConcreteInterval{T, Strict}
end

AnyInterval{T, M} = Union{PseudoNumberInterval{T, M}, SetInterval{T}}

and to define most functions for ConcreteInterval{T, M} and make functions for AnyInterval{T, M} refer to it (may be done at once using some some macro magic).

Strict mode should error in ambiguous cases (e.g. 0 > (-1..1)), while Silent returns false silently. There are 3 possibilities at the end as SetInterval are always Strict (they will error anyway on any function defined on Real having them Strict simply allows to provide more helpful error messages), while PseudoNumberInterval may have both modes.

There should be no performance penalty as long as struct avoid having AnyInterval as member variables. However which one to use should in general be clear for example, @lbenet needs one flavour of PseudoNumberInterval while IntervalRootFinding should probably use SetInterval in its Root object.

Finally, note that different flavour will need to be able to interact, as for example you search the roots of a TaylorSeries from @lbenet you will work with at least two flavours (I have a use case which is actually conceptually similar to that problem).

[Kolaru]

Since most problems seem to come from functions returning booleans, ConcreteInterval in the draft proposition above could use correct three way logic (true/false/unconclusive) and the wrapper is responsible for deciding what to do with the unconclusive value. Silent intervals would turn it into either true or false (currently it is always false I think) while Strict intervals should raise an error.

(Silent is a terrible name by the way, the point of this mode is not being Silent it is returning true only if the test is true for all element in the interval.)

[ajkeller34]

I admit I don't have much bandwidth to contribute here, but it would be great if the end result of the WIP PR is that I could use Unitful.Quantity types with Interval.

[lbenet]

Thanks for your comment @ajkeller34. I guess the problem in your case is the limitation that Interval{T} <: Real imposes; is this correct? Other cases, however, do need it, e.g., for the validated integration of ODEs, where the coefficients are supposed to be "numbers".

I think the discussion here made clear that we need another type that mimics all the functionality of Interval but assuming them as "set"s rather as "number"s.

[ajkeller34]

That is likely a problem, yes; also, the type parameter T is restricted to Real. My use case is for validated math with Unitful quantities, so correspondingly I would also like my intervals to be "numbers."

In Unitful, after some long discussion, it was decided that Unitful.Quantity{T} <: Number, rather than Real. Note that T is unrestricted. For complex quantities we have Unitful.Quantity{<:Complex}.

I see echoes of those discussions here, in that there is a tension between choosing a subtype that is practical for coding in the near term, and choosing an accurate subtype. Even if you have an interval type that is to be treated as a number, I am not sure strictly speaking that the interval is a real number. Some of the discussion surrounding this comment may be interesting.

[lbenet]

So your point is actually to relax Real and consider Intervals as a subtype of Number, right?

While I agree with the essence of the comment, I'd like to listen what is the (design) reason for Unitful.Quantity{T} <: Number?

[ajkeller34]

I am not sure I could pin it down to one particular design reason, but here are a few arguments in addition to the comment I linked above.

One argument specific to Unitful would be that adding two real numbers is well-defined, whereas 1meter + 1 is not well defined, so typeof(1meter) better not be a subtype of Real. Another argument might be to ask why Quantity{<:Integer} !<:Integer. If it is a subtype of Real, well surely it should be a subtype of Integer, right? But that way leads to problems as you go down a rabbit hole of defining types like IntegerQuantity{<:Integer} <: Integer and so on. I can understand wanting to restrict to real numbers if you can think of other types a user might conceivably try where your design assumptions are violated, but of course that comes at the cost of restricting other types that might just work fine.

[Kolaru]

That would indeed be good. The current idea is to have the type allowed as interval to be determined by a trait (see #185). The rational for this is that is the nature of interval arithmetic: we can't promise correct results for just any number type (also an Interval can not be allowed to be bounds of Intervals, because it may cause unexpected infinite recursion, most operation on intervals being lowered to operation on their bounds).

With a trait system, we will be able to allow any type as bound, as long as the user takes the responsability to use type with good rounding capabilities (documenting what that means exactly will be kind of hard though, but the baseline idea is they should be wrapper for some kind of Float).

[Kolaru]

@ajkeller34 After thoughts: while Interval{Quantity{T}} is not available, Quantity{Interval} already seems to work fine (note the parentheses):

julia> using IntervalArithmetic

julia> using Unitful

julia> a = (100..110)u"g"
[100, 110] g

julia> b = (1.25..3.1)u"kg"
[1.25, 3.10001] kg

julia> a + b
[1.34999, 3.21001] kg

julia> b / 2.2u"m^2"
[0.568181, 1.4091] kg m^-2

[ajkeller34]

That's true, and certainly helpful in many cases. (Measurements.jl also works in this way, but not the other way around, if I remember right.) However, if a package defines a struct like the following, I don't see an easy solution:

struct Something{T}
   x::Interval{T}
   other_fields
end

In such a case I guess the package author would have to change Interval{T} to T and enforce some constructor checks but it seems like it would be unnecessarily complicated this way.

[goretkin]

There are some issues with Quantity{Interval}:

using IntervalArithmetic: IntervalArithmetic, interval
using Unitful: Unitful, m

a = interval(0, 0)
b = interval(0, 1)
@assert a <= b
@assert a*m <= b*m  # assertion failure here

Without having given it too much thought, the source of the problem is the assumption made at https://github.com/PainterQubits/Unitful.jl/blob/47d131be92eefae1b49cd02b0a9f9a55b74be97f/src/quantities.jl#L324

<=(x::AbstractQuantity, y::AbstractQuantity) = <(x,y) || x==y

Although this problem wouldn't be prevented/fixed by removing the Real supertype (since Unitful.jl works with ::Number), one could argue that anything that calls itself <:Real should not behave as such:

julia> a <= b
true

julia> a < b
false

julia> a == b
false

[goretkin]

Perhaps this is not the place to collect violations of the interface informally suggested by <: Real, but rem not defined for IntervalArithmetic.Interval{Float64} might be another one (from #423)

[gwater]

I really like this idea of actually collecting the implicit interface Base defines for subtypes of Real. Maybe it could even become part of the Julia manual (since a lot of packages subtype Real)

EDIT: Opened a discussion over on Julia Discourse

[OlivierHnt]

In the 1.0-dev branch, we made several changes to improve reliability, at the cost of convenience. In this regard, the removal of Interval <: Real certainly has its appeal.

I have made a local branch to experiment with removing Interval <: Real; I now believe this may not be as daunting as I initially expected. Of course, beside Base functionalities, this impacts how Interval interacts with the rest of the Julia ecosystem. As mentioned above, this may be good in the long term to ensure that people do not just rely on some generic code written for Real which may silently fail because it does not satisfy the interval arithmetic specifications.

That being said, we talked about TaylorSeries.jl. In particular, it defines

abstract type AbstractSeries{T <: Number} <: Number end

What would be the cost of having

abstract type AbstractSeries{T} <: Number end

instead? So the Taylor1 and TaylorN can have coefficients that may not be subtypes of Real. @lbenet perhaps you have tried this already?

[lbenet]

That being said, we talked about TaylorSeries.jl. In particular, it defines

abstract type AbstractSeries{T <: Number} <: Number end

What would be the cost of having

abstract type AbstractSeries{T} <: Number end

instead? So the Taylor1 and TaylorN can have coefficients that may not be subtypes of Real. @lbenet perhaps you have tried this already?

Good point! I must admit that I haven't tried it, so I'll give it a try. Perhaps, as we do it here, we should define a union type to restrict a little bit the parameter type of Taylor1 and TaylorN...

[OlivierHnt]

I think that we still need to have Interval <: Number, for a better compatibility with LinearAlgebra. For instance we would want UniformScaling(interval(1)) to work.
Then the question is whether changing Interval <: Real to Interval <: Number really worth it?

[timholy]

xref #585