Split Interval into separate package?

[ssfrr]

As you mention in JuliaLang/julia#12624, several people have implemented interval types in their packages. I know at least of @dcjones's IntervalTree package. I'm also looking at intervals for a package that I'm working on. Would you be interested in splitting out the interval type into a separate package? It seems like your implementation is useful pretty generally.

[mbauman]

Perhaps. I'm still not entirely happy with how they behave, and I've slowly been tinkering with their definition (I'll probably propose something along these lines soon: https://github.com/mbauman/AxisArrays.jl/compare/repeatedintervals).

There are two ways to define intervals, and I don't think there's one correct answer here, so I hesitate to grab the obvious Intervals.jl name.

I've made them kinda-sorta Range-like, where they can feasibly support any ordinal type. They're not subtypes of Number, so they don't really act like true numbers. I've just defined a few arithmetic operations that I need for this package and kept things relatively simple. The other trick is that I want to delay some operations until I use them in indexing to avoid fencepost and numerical accuracy problems… but in the repeatedintervals branch above I'm using a custom operator for this and so it could easily be an AxisArrays addition to the base Interval type. This probably isn't going to be a common concern in other domains.

The other option is to only allow intervals between Numbers, and make intervals themselves a subtype of Number. This allows them to be used much more extensively as a computational type. This is what @dpsanders' ValidatedNumerics.jl package does.

[ssfrr]

My use case is pretty straightforward and I think pretty similar to your needs. I'm working on some common types for DSP (streams, buffers, processing nodes) and just want to use SIUnit-valued intervals for indexing multi-channel, uniformly-sampled signals in the time or frequency domain. I haven't thought through the semantics fully yet, and at first will probably just quantize the given interval endpoints to the nearest sample values. It's mostly a convenience so you can say "give me the first 500ms of audio from this buffer"

I'm definitely not familiar enough with interval arithmetic to evaluate which semantics are more generally useful, but do you think that the common core of a parameterized tuple (maybe with the A..B operator) could serve as a common-enough scaffold that it could be shared and extended by other packages?

I could just write some getindex handlers that take 2tuples, or cut-paste one of the other Interval implementations, but it seems like they're used in enough places that it might be useful to have the basics shared.

I could just be overthinking it though, and would definitely defer to your expertise here.

[mbauman]

It's mostly a convenience so you can say "give me the first 500ms of audio from this buffer"

Oh man, yes, that's exactly what I want to express, too.

I definitely think we can work towards a registered Intervals package. In order to do so, I'd like to see if we can get a consensus from all the Interval stake-holders around here on a package name, home, and behavior. Ideally, we'd all manage to find some implementation that most of us are happy with and can use in our respective packages.

Here are the important parts that I'd like to have in an intervals implementation:

• It's an immutable type that has two concretely-typed fields of the same type, lo and hi (actual field names are irrelevant).
• It should be able to support types that are Number or AbstractTime. Maybe more, too, but at least those.
• It isn't itself a subtype of Number. This is somewhat negotiable, but I've found that this makes life a lot easier. See: this comment for details.
• A non-interval x can promote and convert to an interval with lo == hi == x.
• Basic arithmetic and comparisons are implemented in a consistent manner, allowing both homogenous arithmetic/comparison (between two Intervals) and heterogeneous arithmetic/comparison (an Interval against a "scalar", via promotion).

An implementation I'm fairly happy about is at https://github.com/mbauman/AxisArrays.jl/blob/18532bef6d9825f493d651c606f766abbaf217d1/src/intervals.jl#L1-L115, but this certainly isn't the way it must be.

On the Intervals-as-computable-numbers front, there's:

• @dpsanders' ValidatedNumerics.jl: Interval{T<:Real} <: Real. Only supports Real numbers, and is itself Real. Uses careful rounding modes to guarantee that the result is within the interval, and is carefully designed to deal with floating point inaccuracies. I'm afraid that our use-cases don't line up. Do you mind if we register a general-purpose package called Intervals.jl?
• @andrioni's Intervals.jl: Interval{T<:Union(Float32, Float64, BigFloat)} <: Number. This interfaces with MPFI, and probably can't use a shared Interval type. Would you feel pushed aside if we registered a package called Intervals.jl?

On the Intervals-as-storage-type-with-limited-computation front, there's:

• AxisArray's Interval{T<:Union{Number, AbstractTime}}
• @sjkelly's Intervals.jl: Interval{T} <: AbstractInterval{T}. I think your current work is fairly consistent with what I'm proposing, but I'd like to extend it with the .. operator and arithmetic/comparisons with scalars. Would you be interested in collaborating? Would you like to host or officially maintain the result? Or would you prefer this to be a separate work?
• @scheinerman's ClosedIntervals.jl: ClosedInterval{T<:Real}. Would you be interested in the above definitions? Your work is a little farther from what I have proposed, but we may be able to find some middle ground.

And then there are a bunch of domain-specific implementations that may not get any advantages from a common package:

• @zenna's AbstractDomains.jl: Interval{T<:Real} <: Domain{T}
• @TheBB's NURBS.jl: Interval{T<:Real}
• @dlfivefifty's ApproxFun.jl: Interval{T} <: IntervalDomain{T}
• @dcjones' BioJulia/IntervalTrees.jl: immutable Interval{T} <: AbstractInterval{T}

Y'all are welcome to join in - what do you think about an officially registered Intervals package?

[dlfivefifty]

ApproxFun’s Interval is a subtype of Domain.  Other Domains include Circles, Arcs, etc.  So I could only imagine ApproxFun taking advantage of a common package if the package was more general: “Domains.jl” or “Sets.jl”.

This may be worthwhile for interval arithmetic for Complex numbers, where you want to work with "Disk"s, not “Interval”s.

On 15 Sep 2015, at 8:13 am, Matt Bauman notifications@github.com wrote:

It's mostly a convenience so you can say "give me the first 500ms of audio from this buffer"

Oh man, yes, that's exactly what I want to express, too.

I definitely think we can work towards a registered Intervals package. In order to do so, I'd like to see if we can get a consensus from all the Interval stake-holders around here on a package name, home, and behavior. Ideally, we'd all manage to find some implementation that most of us are happy with and can use in our respective packages.

Here are the important parts that I'd like to have in an intervals implementation:

It's an immutable type that has two concretely-typed fields of the same type, lo and hi (actual field names are irrelevant).
It should be able to support types that are Number or AbstractTime. Maybe more, too, but at least those.
It isn't itself a subtype of Number. This is somewhat negotiable, but I've found that this makes life a lot easier. See: this comment https://github.com/mbauman/AxisArrays.jl/blob/e27bc5342a7d66c345ca491ac831ab1781730300/src/intervals.jl#L55-L77 for details.
A non-interval x can convert to an interval with lo == hi == x.
Basic arithmetic and comparisons are implemented in a consistent manner, allowing both homogenous arithmetic/comparison (between two Intervals) and heterogeneous arithmetic/comparison (an Interval against a "scalar", via promotion).
An implementation I'm fairly happy about is at https://github.com/mbauman/AxisArrays.jl/blob/e27bc5342a7d66c345ca491ac831ab1781730300/src/intervals.jl#L1-L115 https://github.com/mbauman/AxisArrays.jl/blob/e27bc5342a7d66c345ca491ac831ab1781730300/src/intervals.jl#L1-L115, but this certainly isn't the way it must be.

On the Intervals-as-computable-numbers front, there's:

@dpsanders https://github.com/dpsanders' ValidatedNumerics.jl https://github.com/dpsanders/ValidatedNumerics.jl: Interval{T<:Real} <: Real. Only supports Real numbers, and is itself Real. Uses careful rounding modes to guarantee that the result is within the interval, and is carefully designed to deal with floating point inaccuracies. I'm afraid that our use-cases don't line up. Do you mind if we register a general-purpose package called Intervals.jl?
@andrioni https://github.com/andrioni's Intervals.jl https://github.com/andrioni/Intervals.jl: Interval{T<:Union(Float32, Float64, BigFloat)} <: Number. This interfaces with MPFI, and probably can't use a shared Interval type. Would you feel pushed aside if we registered a package called Intervals.jl?
On the Intervals-as-storage-type-with-limited-computation front, there's:

AxisArray's Interval{T<:Union{Number, AbstractTime}}
@sjkelly https://github.com/sjkelly's Intervals.jl https://github.com/sjkelly/Intervals.jl: Interval{T} <: AbstractInterval{T}. I think your current work is fairly consistent with what I'm proposing, but I'd like to extend it with the .. operator and arithmetic/comparisons with scalars. Would you be interested in collaborating? Would you like to host or officially maintain the result? Or would you prefer this to be a separate work?
@scheinerman https://github.com/scheinerman's ClosedIntervals.jl https://github.com/scheinerman/ClosedIntervals.jl: ClosedInterval{T<:Real}. Would you be interested in the above definitions? Your work is a little farther from what I have proposed, but we may be able to find some middle ground.
And then there are a bunch of domain-specific implementations that may not get any advantages from a common package:

@zenna https://github.com/zenna's AbstractDomains.jl https://github.com/zenna/AbstractDomains.jl: Interval{T<:Real} <: Domain{T}
@TheBB https://github.com/TheBB's NURBS.jl https://github.com/TheBB/NURBS.jl: Interval{T<:Real}
@dlfivefifty https://github.com/dlfivefifty's ApproxFun.jl https://github.com/ApproxFun/ApproxFun.jl: Interval{T} <: IntervalDomain{T}
@dcjones https://github.com/dcjones' BioJulia/IntervalTrees.jl https://github.com/BioJulia/IntervalTrees.jl: immutable Interval{T} <: AbstractInterval{T}
Y'all are welcome to join in - what do you think about an officially registered Intervals package?

—
Reply to this email directly or view it on GitHub #20 (comment).

[sjkelly]

@mbauman @ssfrr I'm up for extending Intervals.jl however needed and maintaining forward compatibility. My initial motivation was to use it as a rigorous basis for HyperRectangles and DistanceFields. I have moved the package to JuliaGeometry so collaboration will be easier. I really like your Interval implementation, especially the .. notation!

@dpsanders and I talked about JuliaCon and IIRC my arithmetic implementations are not congruent with the IEEE proposal. It might take some time to integrate with the needs of ValidatedNumerics, but it doesn't seem impossible.

[ssfrr]

One thing to consider with the A..B syntax is that it may get used for the non-overloadable getfield, so that syntax might become unavailable. Also the precedence is rather low, so currently 1..4 + 7..1 doesn't do what you'd want. I think that with a consensus of a few people though it's a lot easier to get that sort of thing changed (or a new operator added to the parser).

[zenna]

I think:

• Intervals are a kind of set representation and it makes sense for them to be a subtype of set representations. Hence Domain{T} in AbstractDomains.
• When you take this perspective some operations such as X = Interval(0,1); X>0.5 have multiple, natural answers. Natural because it's a set operation; the answer should be a set. Multiple because it depends on what domain you want the answer to be in.
• Interval bounds (closed vs open) should be explicit (I haven't done this in Abstract Domains). Possibly it could be done with no cost using types.
• Intervals being a subtype of Number has slightly more pros than cons. Fundamentally, they do not fit into the type-hierarchy. OTOH there is a lot of existing code designed for numbers that we would like to be able to use with intervals.
• Interval arithmetic is more useful when you can go both forwards and backwards. Otherwise you will get overapproximation errors which renders it useless for complicated functions.

[dlfivefifty]

AbstractDomains.jl seems very useful for ApproxFun. I’d be in favour of using that as the base for “Interval”, and happy to contribute.

Zenna: Either way, maybe I should at some point port ApproxFun’s lists of domains ("Circle", "Disk”, “Line”, “Ray”, “Arc”) over to AbstractDomains.jl?

On 15 Sep 2015, at 9:54 am, Zenna Tavares notifications@github.com wrote:

I think:

Intervals are a kind of set and it makes sense for them to be a subtype of sets hence Domain{T} in AbstractDomains.
When you take this perspective some operations such as X = Interval(0,1); X>0.5 have multiple, natural answers. Natural because it's a set operation; the answer should be a set. Multiple because it depends on what domain you want the answer to be in.
Interval bounds (closed vs open) should be explicit (I haven't done this in Abstract Domains). Possibly it could be done with no cost using types.
Intervals being a subtype of Number has slightly more pros than cons. Fundamentally, they do not fit into the type-hierarchy. OTOH there is a lot of existing code designed for numbers that we would like to be able to use with intervals.
Interval arithmetic is more useful when you can go both forwards and backwards. Otherwise you will get overapproximation errors which renders it useless for complicated functions.
—
Reply to this email directly or view it on GitHub #20 (comment).

[mbauman]

Wow, this is great everyone. Thanks for the feedback and being so willing to collaborate!

My use case is very pragmatic — I just want intervals to make an API simpler. If being part of a larger InfiniteSet/Domain hierarchy means that more of us can work together then I'm all for it.

Some specific responses:

@ssfrr One thing to consider with the A..B syntax is that it may get used for the non-overloadable getfield, so that syntax might become unavailable

One of my goals is to present a strong case for an alternative… and make sure that it doesn't get wasted on a rarely used syntax. I don't mind the low precedence all that much — it behaves like :, which has some nice qualities once you get used to it.

@zenna - AbstractDomains.jl is much more general that I had first thought. I agree that it could make for a great basis here.

some operations such as X = Interval(0,1); X>0.5 have multiple, natural answers. Natural because it's a set operation; the answer should be a set. Multiple because it depends on what domain you want the answer to be in.

I disagree on this point. I think that the primary comparison operators in base should always return a Bool, which limits the choices we can make. In that vein, I think the base comparison operators should behave as though they were ∀ values in the interval/domain. This has some very cool advantages:

julia> r = cumsum(rand(100));

julia> idxs = searchsorted(r, 5..8) # With AxisArray's repeatedinterval branch
12:17

julia> r[idxs]
6-element Array{Float64,1}:
 5.43329
 6.04483
 6.07484
 6.68762
 7.47311
 7.85931

Edit: perhaps the set-like comparisons that you currently have could be extensions of .< and .==?

Interval bounds (closed vs open) should be explicit

I wouldn't be against supporting it, but for Intervals I'd prefer a closed default.

Intervals being a subtype of Number has slightly more pros than cons.

My two biggest cons are that I really want the ability to form intervals between dates/DateTime (today()-Day(5) .. today()) and that it causes ambiguities with every other Number wrapper that is also a Number (DualNumbers, SIUnits, ForwardDiffNumbers, Compose measurements, and so on). For each of these that you'd like to interoperate with, you need to explicitly choose who wins in a promotion or get tons of ambiguity warnings. But I do understand that this does make the type much more powerful for general use. Maybe someday we'll get ambiguity warnings deferred to runtime errors, which would make this more amenable.

If Interval{T<:Number} <: Number, then perhaps we could also use the .. operator to form a TimeInterval{T<:AbstractTime} (like how : forms different kinds of ranges). It'd mean a lot of code duplication, but it's one solution. But since we don't have multiple inheritance, it may be tough to have all Domains also be a subtype of Number, so this may be limited by that in any case.

Interval arithmetic is more useful when you can go both forwards and backwards

I'm afraid I don't understand what you mean by this, could you explain a little further?

[ssfrr]

I wonder if the split is that:

1. Intervals can be used to represent uncertainty, where you want to start with bounds on your inputs and define operations that propagate that uncertainty (preferably keeping the bounds tight). From this perspective the answer to 4 < 3..5 is the set {true, false}, as is 3..5 == 3..5 as in AbstractDomains. In general operations are defined as if you're doing the operation elementwise on the cartesian product and then returning the Interval bounding the results.
2. Intervals can be used to represent known contiguous spans in a domain. From this perspective 4 < 3..5 is false and 3..5 == 3..5 is true. It's not as clear to me that most arithmetic operations make sense here, though maybe I'm thinking too narrowly. Set operations like union and intersection seem to make sense, though I'm not sure what the union of disjoint intervals should be.

Just to throw the idea out there, if there isn't enough common ground for these to be represented with the same underlying type I wonder if Interval and Span could represent the two cases? I do think it's better if we can find a common basic type though.

@mbauman would you mind giving a concrete example of where ambiguity warnings pop up with Interval <: Number and not otherwise?

[mbauman]

would you mind giving a concrete example of where ambiguity warnings pop up with Interval <: Number and not otherwise?

Sure. On a hand-wavy level: Is (1..2)*Second an SIQuantity{Interval} ((1 to 2) seconds) or is it an Interval{SIQuantity} (1 second to two seconds)? Julia needs to be told what to do in each and every case you want to support. And even in cases you don't care to support, it will complain loudly.

On a concrete level: You hit ambiguities in promote_rule and any non-promoting operators you both want to support, like comparison operators and (IIRC) array arithmetic, because you both want to define:

Base.isless(::Number, ::Interval) = …
Base.isless(::SIQuantity, ::Number) = …

This is ambiguous for the case isless(::SIQuantity, ::Interval) since they're both Number. Base.promote_rule is even trickier, since it can effectively hide the ambiguities by it trying things in both orders for you, and can surprisingly be a hang in ambiguous combinations without warning:

immutable SIQuantity{T<:Number} <: Number; end
immutable Interval{T<:Number} <: Number; end
Base.promote_rule{T, S}(::Type{SIQuantity{T}}, ::Type{SIQuantity{S}}) = SIQuantity{promote_type(T,S)}
Base.promote_rule{T, S<:Number}(::Type{SIQuantity{T}}, ::Type{S}) = SIQuantity{promote_type(T,S)}
Base.promote_rule{T, S}(::Type{Interval{T}}, ::Type{Interval{S}}) = Interval{promote_type(T,S)}
Base.promote_rule{T, S<:Number}(::Type{Interval{T}}, ::Type{S}) = Interval{promote_type(T,S)}
# Above methods aren't ambiguous!  But in Base we have:
# promote_type{T,S}(::Type{T}, ::Type{S}) =
#     promote_result(T, S, promote_rule(T,S), promote_rule(S,T))
# So when we promote_type(Interval, SIQuantity), we get:
# promote_type(Interval, SIQuantity) => promote_result(Interval, SIQuantity, Interval, SIQuantity)
# And in Base we have
# promote_result(t,s,T,S) = promote_type(T,S)
# So we end up with a recursive loop, but it's so slow it doesn't hit a stack overflow:
julia> promote_type(Interval{Int}, SIQuantity{Int})
# …

Making Interval not a Number solves this — its methods win.

[dlfivefifty]

For the question about disjoint intervals: ApproxFun has a type UnionDomain that has a Vector of subdomains, which can be of different types.

Sent from my iPhone

On 16 Sep 2015, at 2:05 am, Spencer Russell notifications@github.com wrote:

I wonder if the split is that:

1. Intervals can be used to represent uncertainty, where you want to start with bounds on your inputs and define operations that propagate that uncertainty (preferably keeping the bounds tight). From this perspective the answer to 4 < 3..5 is the set {true, false}, as is 3..5 == 3..5 as in AbstractDomains. In general operations are defined as if you're doing the operation elementwise on the cartesian product and then returning the Interval bounding the results.
2. Intervals can be used to represent known contiguous spans in a domain. From this perspective 4 < 3..5 is false and 3..5 == 3..5 is true. It's not as clear to me that most arithmetic operations make sense here, though maybe I'm thinking too narrowly. Set operations like union and intersection seem to make sense, though I'm not sure what the union of disjoint intervals should be.

Just to throw the idea out there, if there isn't enough common ground for these to be represented with the same underlying type I wonder if Interval and Span could represent the two cases? I do think it's better if we can find a common basic type though.

@mbauman would you mind giving a concrete example of where ambiguity warnings pop up with Interval <: Number and not otherwise?

—
Reply to this email directly or view it on GitHub.

[JeffBezanson]

+1. I'll also put in a vote for @mbauman -style intervals (where they are not Numbers, and act mostly like sets). It would be good to have a standard type for expressing range queries.

[dpsanders]

In ValidatedNumerics.jl, the fact that Intervals "are numbers" (i.e. have a number-type trait, which currently must be expressed as Interval <: Real) is important. Having said that, maybe it would not be too much work to get rid of this (though I distinctly remember that there is always a crucial moment when it is much more natural to have it).

I would propose that the simple interval type under discussion in this issue could be called literally a SimpleInterval.