Julia standard library for interval type

Internals & Design Internals
1

I see the interval type, represented by e.g. 0..100 used in a few different areas. One is obviously for interval arithmetic. But using this notation/type/syntax also seems very usefor for e.g. setting plot limits. Another use is to give a domain on which to specify an optimization problem.

In seeing unrelated use-cases for this IMO excellent syntax, I started wondering - is the concept of an interval not generally useful enough, and the syntax good enough, that this should be added as a standard library to the base language?

EDIT:
I created this post talking about “the core language” and “base library”. I realized later that I meant a stanard library, and have made edits to fix the wording.

2 Likes
2

What’s wrong with 0:100 (i.e. a range)?

1 Like
3

Sometimes, the intermediate values are not known/important. 0:100 is 101 discrete values with a span from 0 to 100. But an interval is continuos, and says nothing about intermediate values. The two concepts are quite distinct.

In e.g. plotting, I find it convenient to not think about what resolution is needed, and letting the plotting package figure it out under-the-hood. This can be done based on for example numerical derivatives. The only thing I know when I first create the plot is the interesting span, or interval.

4 Likes
4

Ah, I see what you mean.

Well, generally, things in Base are mostly there if they’re needed by Base itself. While the two (range and intervals) are semantically different, I’m not sure the extended semantics for intervals are needed in Base. Since e.g. plotting is not provided by Base, I’m not sure what additional benefit would be had by having those types in Base? Putting them there only makes it harder to update them after all, since they aren’t updated as frequently as a package can be.

2 Likes
5

A tuple (a,b) is often used for setting plot limits, which is pretty concise.

There could be a string macro

interval"[a,b)"

but a..b is supported by Home ¡ Intervals.jl

2 Likes
6

A touple is a very functional and okay way to do it, but the interval notation feels more natural to me, both in terms of look and in concept.

I realize that I meant a Standard Library Implementation. My bad. My thought was that the concept of an interval is general and useful enough that it should be available without a third-party package dependency. But after taking a closer look at Intervals.jl, I can see that it is pretty minimal. So maybie having the dependency is a low price to pay, and works just fine.

I’m not sure what the best solution is, but I am still leaning towards that the interval-type is, to repeat myself, general and useful enough to warrant being included in the language itself. As a standard library seems like a good solution.

7

Current evidence suggests that it is not.
Our idea of what an interval is and how it should act is demonstratably still evolving since we have multiple competing packages.

Hopefully at some point those will converge, either to one package, or to a common shared API (like Tables.jl), but til then we need to keep them flexible.

Changing anything in a standard library is hard.
You can’t make any breaking changes.
and even adding new features is annoying since people on old versions of julia can’t benifit from them.
Where as a package can be updated independently of the julia version.

Standard libraries are basically second class packages.
There are to my mind 2 reasons to put things in standard library.

  1. It is needed for some other part of the standard library. (e.g. we introduce some missing methods for some specialized matrix factorization, but that needs say some new method for factorizing numbers into primes or something to implement efficently.)
  2. Not having it in the standard library causes people to use an inferior solution that is in the standard library (a good example is only which is like first but also checks that there is only one element. WIthout it people will use first and their code will be a bit less robust to programmer mistakes)

Julia is not a language where everything you need is in the standard library (unlike say Mathematica).
Julia is more like LaTeX: noone uses LaTeX in a nontrivial way without installing a few dozen packages.

21 Likes
8

Thanks a lot for the high quality reply. If it is advantageous to be a package as opposed to a part of the language, which you have convinced me that it is, then things are just fine :slight_smile:

2 Likes
9

There are good reasons to keep things in a 3rd party package, but it also means that, unfortunately, the syntax a..b will probably not see widespread use. There is a tradeoff, not just an upside.

2 Likes
10

I hope a..b doesn’t become standard syntax to only mean intervals. MonteCarloMeasurements.jl uses it to define uniformly distributed uncertainty and it would have to choose some less nice syntax if intervals were a standard thing.

1 Like
11

That was kind of what I was hoping for, so that is a shame. But due to reasons mentioned, along with stuff like

, the status quo seems like a good place to be :slight_smile:

2 Likes
12

Note .. is defined in EllipsisNotation.jl and is shared between several different packages included IntervalSets.jl

5 Likes
13

I have used interval arithmetic in a couple of projects, though I wouldn’t call myself an expert, and here are my 2 cents: when you look at the problem more closely, the ‘intervals’ from interval arithmetic are not the right tool to represent domains. They are meant to represent uncertainty on quantities; the two concepts are orthogonal.

Illuminating example: you wish to solve the optimization problem

\min_{x\in [\sqrt2, \sqrt3]} x^2.

Neither \sqrt2 nor \sqrt3 are exact Float64 numbers, and should be represented themselves by an interval if you want a rigorous result; for instance, 1.4141..14142. So passing this domain to an optimization function becomes impossible if you want to use an interval type for that. You can do the following

using IntervalArithmetic

a = sqrt(@interval(2))
b = sqrt(@interval(3))
D = hull(a, b)   # this returns the interval [a.lo, b.hi]
y = minimise(x -> x^2, D)  # this will return an interval containing (D.lo)^2

but it is a subtly different thing: for instance, the length of your domain is the uncertain quantity b-a, i.e., [b.lo-a.hi, b.hi-a.lo], which is not diam(D) and is in fact impossible to retrieve from D, since information about a.hi and b.lo has disappeared. And the call in the last line returns an interval containing a.lo^2; this is not guaranteed to contain the exact solution to your problem, 2.0.

In my humble opinion, when doing rigorous computations with interval arithmetic the notation a..b should be used to represent a single real number whose value is not known exactly as a Float64, and not the thing that you call “intervals” in a calculus course. Do not let the name mislead you. I have done that mistake before, and can advise against it.

Maybe you want a parametric type for this job

struct Domain{T}
  a::T
  b::T
end

but at this point the benefits over a tuple are unclear.

1 Like
14

Even for a contiguous interval of integers, one might not want UnitRange, since it is an AbstractArray, and therefore e.g.

julia> UnitRange(1, 3) == [1, 2, 3]
true

For consistency, hash on UnitRange cannot be an O(1) operation:

julia> @time hash(0:(2^62))
  0.002515 seconds
0x62935834bd81dfd0

julia> @time hash((0, 2^62))
  0.000000 seconds
0xa0892713c4d761dc
15

IntervalSets.jl is designed for intervals as domains (even has an abstract type Domain ). There’s also the companion package DomainSets.jl

3 Likes
16

I disagree: The intervals from IntervalArithmetic do represent domains, and the two concepts (domains and “uncertainty on quantities”) are the same.

Your example

\min_{x\in [\sqrt2, \sqrt3]} x^2

is an interesting one.

The difficulty here has nothing to do, per se, with interval arithmetic; it is just the usual problem of not being able to represent sqrt(2) exactly using floating-point arithmetic.

You are asking for the minimum over a larger set, so you should expect a lower value.

The correct way to solve your problem is as a constrained optimisation problem:

minimise x^2, subject to 2 \le x^2 \le 3

(I say “the correct way” since this allows you to exactly specify the correct set using numbers that are exactly representable.)

This is a significantly harder problem to solve in a guaranteed way using interval arithmetic than unconstrained optimisation, and we are (still) working on it; hopefully this will be doable soon, and will return an interval that is guaranteed to contain the true result.

7 Likes
17

Thanks for the feedback; you are one of the most knowledgeable people on interval arithmetic and I value your opinion.

However I think we are looking at slightly different problems here. Here, I want to find a rigorous inclusion for the solution of the problem \min_{x \in [\sqrt2, \sqrt3]} x^2. This is not a problem (and a domain) that I can represent in exact arithmetic, but I can work with the family of minima

y_{ab} = \min_{x \in [a,b]} x^2

and write a function my_minimize(f, (a, b)) that computes an inclusion interval \mathbf{y} \supset \{y_{ab}: a \in \mathbf{a}, b \in \mathbf{b} \}. Then, y = my_minimize(x->x^2, (sqrt(@interval(2)), sqrt(@interval(3))) solves the problem. I expect the interval \mathbf{y} returned by this line of code to always contain 2, otherwise this would not be a correct implementation. This is not exactly what minimize from your IntervalOptimization.jl package does, but it is still a legitimate problem that one may want to formalize and solve using interval arithmetic. And if we try to conflate the two concepts and use IntervalArithmetic’s intervals as domains, then we cannot solve it anymore.

I hope this explanation makes sense. :slight_smile:

1 Like
18

Yes I agree that it’s a legitimate problem; the difficulty is in writing my_minimize that actually does this!
The problem here really is “just” in how you correctly represent the exact end points.

I don’t see how to do that without formulating it as a constrained minimisation problem, as in my previous post.

Alternatively you could also use higher and higher precision BigFloats. This will give you an increasing sequence of lower bounds that will converge to the correct answer, but will still not give you a guaranteed inclusion.

1 Like
19

Well, this specific case is easy because the function f(x) = x^2 is monotonic, so we can just return f(\mathbf{a}), which will contain 2. More generally, one could split the domain into intervals in which f is guaranteed to be monotonic and (hopefully small) intervals in which the sign of its derivative is undetermined, and then work with that representation.

But my point here is that if we conflate the two concepts then we lose the possibility of even formulating this problem and writing a function that solves it. And with it possibly also other problems. Maybe one can regard these “intervals with uncertain endpoints” as a sort of higher-order concept and exclude them from the syntax, but this is restricting the number of problems that we have a language for.

20

I guess the problem here is simply that the minimum occurs at an endpoint.
This should then be explicitly checked for and the endpoint interval itself returned in this case.

A PR for that would be welcome.

2 Likes