Implement systems for flavor, pointwise extensions, default bound and rounding mode

[Kolaru]

This PR is my latest take on solving #237 and is a replacement #254. The main reason for a new PR and the closing of the previous one is that #254 relied heavily on macro and was thus hard to maintain and even harder to extend. Moreover the discussion around #254 arrived at the conclusion that what we want is really what the standard call a "flavor", and thus trying to come up with a flavor system seems the way to go.

In summary my first try in #254 was both misguided and overcomplicated.

The new trick is simpler and is essentially contained in the following lines:

abstract type AbstractRealFlavor{T} <: Real end
abstract type AbstractNonRealFlavor{T} end

const AbstractFlavor{T} = Union{AbstractRealFlavor{T}, AbstractNonRealFlavor{T}}

Concrete interval types must subtype either AbstractRealFlavor or AbstractNonRealFlavor and will benefit from all methods defined for AbstractFlavor. Thus this system should be extensible and relatively easy to maintain as for the most part we can treat AbstractFlavor as the common supertype of all intervals (it is however not as it can not be directly subtyped).

Currently this is still a work in progress, but the package compile, thanks to the definition of a default interval type named Interval. Thus most old definitions work but are only defined for the default flavor (note that some functionnality like the .. syntax will always only be defined for the default interval type).

What remain to be done is

• [ ] Separate the functionnalities common for all flavors from the flavor dependant ones and redefined them accordingly.
• [ ] Implement all required functions for the IEEE standard "set based flavor".
• [ ] For each function in the IEEE standard, add ref. to where it is defined in the IEEE standard.
• [ ] Add all relevant flavors.
• [ ] Fix all the bugs.

I do not forget the problem of boolean functions that were at the core of #254 and solutions to these problems to them will be implemented in the corresponding flavors.

PS: Since this requires to review more or less the whole codebase I'm also trying to clean up the code along the way.

List of issues that should be fixed by this PR or that this PR will help solve:

• [ ] #237 Core issue tackled here.
• [ ] #264 Division by 0 will be handled differently depending on the flavor used.
• [ ] #272 Kaucher arithmetic could be one of the supported flavors.
• [ ] #168 Behavior of isinf() will be flavor dependant.
• [ ] #165 Boolean operations will be flavor dependant.
• [ ] #2 Oldest issue about interval being subtype of Real.
• [ ] #209 Some flavor (Kaucher arithemtic ?) have [∞, ∞] as a valid interval.
• [ ] #56 Tightness vs. speed may be managed through the choice of flavor.
• [ ] #129 Behavior of mod may be flavor dependant.

Issues I will probably fix along the way as they are minor and I'll need to review related part of the code, but that are tangential to the core concerns:

• [x] #270 Move every special symbol to a separate file.
• [x] #212
• [x] #285
• [ ] #170
• [x] #8
• [x] #127 and #228 Easier to get rid of the global precision rather than adapt it to the new flavor system.

[Kolaru]

While reviewing the files arithmetic.jl and functions.jl I noticed an inconsistent way of comparing numbers to zero:

1. In arithmetic.jl by first getting the zero of the right type, typically x >= zero(x).
2. In functions.jl by comparing to literal, without any conversion, typically x >= 0.

Is there any known performance gain to the former? I play a bit with it and wasn't able to see any difference (I assume the compiler may be smart enough to give correct type to literals).

Unifying that will either have a good impact on performance or on readability, so I thing it's worth looking into.

@dpsanders @lbenet I assume one of you wrote this files in the first place, so any idea?

[lbenet]

Please, ping us when this is ready for review...

[dpsanders]

This looks really fantastic, thanks!

Will it mess you up too much if we merge a few of the latest prs?

[dpsanders]

As far as the comparisons with zero go, I think they are equivalent, but yes we should be consistent. I think comparing with the literal zero is sufficient.

[Kolaru]

Of course this PR is not yet ready for review (forgot to comment after pushing), I pushed these changes to show my current progress (they include a TODO and changelog.txt files if you want to have a quick look at the state of affair).

Also most basic functionality should work (constructing and arithmetic with intervals), yet many tests fail or error. Reasons for this include the new system 100% breaking the old promotion mechanism and some crucial functions for test changing names, like == becoming isidentical for intervals.

@dpsanders I think you should not hesitate, most of them have a well defined scope and I should be able to adapt this PR to them without too much fuss (hopefully). Moreover I can't give an estimation of the time it will take to finish this PR, promotion is tricky and the test suite to which I should comply (for each provided flavor) is huge.

[Kolaru]

I have encountered a problem deeper that what I had anticipated:

julia> @which 2*(1..2)
*(x::Number, y::Number) in Base at promotion.jl:314

This means that if we allow flavor that are not subtype of at least Number, they won't be able to use the built-in promotion mechanism. Unless we are willing to reimplement a promotion ourselves (I don't volunteer for that), I think it forces us to have Flavor <: Number for any flavor (and probably Flavor <: Real would make sense since interval are as much number are they are real... that is they are not).

While not immediatly blocking for the developpement of the this PR, I think it's worth discussing as removing <: Real was the main issue tackled by this PR.

[gwater]

This means that if we allow flavor that are not subtype of at least Number, they won't be able to use the built-in promotion mechanism.

Can you elaborate? To me it seems consistent, that something which is not a Number should not go through the normal promotion rules. How non-Number objects interact among themselves and with numbers naturally depends on the underlying mathematical structure of those objects.

[dpsanders]

You don't need to reimplememt promotion, just provide methods like +(x::Interval, y::Real), which is not too onerous.

[Kolaru]

I'll answer here to @dpsanders about the comment I made in #335 about "being overdramatic about a minor setback":

The setback to which I referred is the promotion mechanism (or lack thereof for Intervals that are not Numbers) I mentioned in my previous comment here. While I now agree that it would not be too hard to play around it, it still feels a bit like reinventing the wheel. In some sense being a Number mainly means accessing to that mechanism (the problematic comparisons operators for example aren't defined at that level).

But at the end of the day, it is more a philosophical matter, as the code base won't looks very different either way (and may even looks cleaner not using the Number promotion mechanism since the promotion rule stuff is kind of a mess).

[dpsanders]

These days I would definitely say to not use the promotion mechanism. Just define all the functions explicitly.

[Kolaru]

Note that getting rid of the promotion mechanism also means removing conversion between number and interval with the convert function (since it is automatically called for arithmetic operations otherwise and it messes up everything).

I'm perfectly fine with that, it simply forces the conversion to go through an interval constructor. It is worth noting however since some of the oldest issues mention the implementation of new convert methods.

[lbenet]

Is it possible that you rebase this to current master?

[Kolaru]

nervous laughter Yeah sure, ha ha, no problem...

Truth is, since I pretty much change every file in this PR and reorganize many of them, rebasing will mean erasing everything and reintegrating manually all changes in master on top of it, which is a rather consequent work.

Is there a reason you wish to have a rebased version before the PR is ready for review/merging ?

[lbenet]

Just thinking about this comment:

Will it mess you up too much if we merge a few of the latest prs?

and how should we all proceed in a constructive way...

[Kolaru]

In many cases new PR would need to be adapted to the new architecture (including a new file organization to match the IEEE standard) developped there. While rebasing will be serious work, it will mostly be a matter putting the changes in the right file together with some renaming.

So considering that this PR still needs a lot of work, I think it makes more sense to not block other PRs and deal with the rebase problem at the end.

I'll make sure to ask for review and merging as soon as the full current test suite pass for a single flavor though, to allow to constructively build future change on top of this PR (including among other new flavors).

[lbenet]

So considering that this PR still needs a lot of work, I think it makes more sense to not block other PRs and deal with the rebase problem at the end.

This what I had precisely in mind...

[dpsanders]

I'm wondering if some of the pieces can be gradually introduced, such as the changes to the abstract base types, without much disruption.

Or maybe it would be better to develop a separate package like IntervalArithmetic2, which when it is ready can just completely replace the current package.

[lbenet]

I'm in favor of the first option.

[Kolaru]

What I'm doing here is:

1. Implementing a new type hierarchy.
2. Extend the type hierarchy to support new flavors.
3. Review each file to put the definition at the right level (AbstractFlavor, specific flavor or default Interval). 3a. Check what the standard require for 3. 3b. Since I review each file anyway, restructure the file system and add docstring according to the standard.
4. Fix all tests that gets broken along the way.

It doesn't make sense to split the process in between these steps, but what I can do to make this incremental is to make smaller PR for each chunk of the codebase I review, the rest of the package should not be broken as everything will still be defined for the default Interval flavor.

First chunk would be everything I've done until now (most basics functionnalities), because my commit history has been to messy to have nice smaller chunks ^^'. I still need to fix all the failing tests I currently have and rebase it and we would be good to go, if you think that's the way to do it.

[dpsanders]

That sounds great.

We should also set up some benchmarks to make sure there are no performance regressions.

[coveralls]

Coverage decreased (-32.4%) to 57.71% when pulling 9b46da75c3cb5d2bdea8e5b53b414b691ea8ec15 on Kolaru:interval_flavors into d3a318c6356515ee2d2a0c47ab7af419dea106ea on JuliaIntervals:master.

[Kolaru]

So I got a bit carried away after the juliacon IA workshop and decided to finally rebase it so that we can try to bring this to a conclusion. Maybe not the best timing to get quick feedback, but hey, at least this is going forward. All tests are passing so it should be possible to try this out (which was the reason of this rebase before the PR is ready to begin with).

Note however than still a bunch of methods are defined only for the default Interval type and not for generic AbstractFlavor. To see the exact extend of how far I got, please refer to the TODO file in the src dir. A good example of final quality files are all those in src/intervals/common/arithemetic.

The tests mostly pass, except on the x86 appveyor windows build. And the doc is somehow broken. But these should not have consquence on immediate testing.

For a more general description of this PR, the head message of this PR and in my last comment (https://github.com/JuliaIntervals/IntervalArithmetic.jl/pull/271#issuecomment-565217079) still hold. The short version is that it define new abstract type for flavors, but in fact most of the work was to check and document the correspondance to the standard (and refactor according to it), as well as determining what behaviors are flavor dependent. The latter has mostly not yet been implemented, except for the default set-based flavor described in the standard.

The framework should allow flavors that are not subtype of Real (following the beautiful work done in NumberIntervals.jl, the consensus on whether we should support them may have changed though). The amount of stuff still broken for them is unkown, since the tests currently only run on the default flavor, which subtype Real.

Finally, in no particular order, a bunch of stuff I changed along the way:

• File structure changed to match the IEEE standard
• Symbols that alias another function moved to symbols.jl
• Removed global precision
• make_interval renamed wrap_literals (because that's what is actually done)
• Removed pi_interval(T) in favor of Interval{T}(π)
• Renamed multiply_by_positive_constant to scale
• @round now take the flavor of the returned interval as first argument
• Removed find_quadrants_tan as it was a duplicate of find_quadrants
• Renamed mid(a, α) -> scaled_mid(a, α) (to avoid discrepency with default parameter)
• Functions returning intervals based on bound type now required a flavor type as parameter
• Renamed entireinterval -> RR (and aliased to symbol ℝ i.e. \bbR<TAB>)
• Added check of the "IA_DEFAULT_FLAVOR" and "IA_DEFAULT_BOUND_TYPE" keys in ENV to get the flavor (Interval) and bound type (DefaultBound). The default interval type is thus Interval{DefaultBound}.
• Transfer the behavior of == (interval equality as defined in the standard) to the function isidentical and reserve the == symbol for flavor dependent pointwise equality.

[dpsanders]

What is the status on this? I can try to look at it in the next few days.

Does it make any sense to make a separate package, in a similar way to NumberIntervals.jl (unreleased for the moment)? With the idea that at some point we will replace the current codebase with the new one?

[Kolaru]

The flavor system not done yet, but the refactoring of the codebase is close to be finished. I think that first finishing the refactor in this PR and implementing the actual flavor system in a future PR is the way to go (especially so since I am still only half convinced by the system presented here).

As for separate packages, I do not currently see much benefit with it.

[lbenet]

I agree with @Kolaru; let's have patience with this PR, and then in another one implement a flavor system. I also see no benefit in having another package for the new flavor, but leave the idea as worth considering.

[codecov-commenter]

Codecov Report

Merging #271 (d8e71bb) into master (db9202c) will decrease coverage by 16.16%. The diff coverage is 87.86%.

@@             Coverage Diff             @@
##           master     #271       +/-   ##
===========================================
- Coverage   90.94%   74.78%   -16.17%     
===========================================
  Files          25       33        +8     
  Lines        1789     1594      -195     
===========================================
- Hits         1627     1192      -435     
- Misses        162      402      +240     

Impacted Files	Coverage Δ
src/IntervalArithmetic.jl	50.00% <0.00%> (-50.00%)	:arrow_down:
src/intervals/complex.jl	0.00% <0.00%> (-93.94%)	:arrow_down:
src/intervals/rounding_macros.jl	0.00% <0.00%> (ø)
src/bisect.jl	57.69% <26.66%> (-42.31%)	:arrow_down:
src/intervals/arithmetic/hyperbolic.jl	66.66% <66.66%> (ø)
src/intervals/rounding.jl	67.14% <71.18%> (-4.29%)	:arrow_down:
src/decorations/decorations.jl	75.00% <75.00%> (ø)
src/multidim/intervalbox.jl	86.66% <76.47%> (-2.81%)	:arrow_down:
...rc/intervals/interval_operations/set_operations.jl	80.00% <80.00%> (ø)
src/intervals/interval_operations/boolean.jl	84.21% <84.21%> (ø)
... and 30 more

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update db9202c...d8e71bb. Read the comment docs.

[Kolaru]

This is now essentially ready for review @dpsanders @lbenet @lucaferranti

I still need to implement some tests and revamp the documentation, but otherwise the changes I planned for the codebase are done.

In particular I will need to restore the IEEE test suite, in a way compatible with the new way of doing everything (in particular interval equality).

I have included the changelog below (also in changelog.md). Hopefully it is exhaustive and I haven't forgotten anything major.

Anyway, I expect the review to take some serious time since I have essentially modified... well everything. If you'd we could organize a call to discuss all that too.

Changelog

Structure

Changed to match the IEEE standard, with corresponding docstring to every function when it is in the standard.

Overall restructuring of the files to try to be more organized.

Symbols that alias another function moved to symbols.jl

Only minimal changes to multdim/.

Global precision

Removed. It was causing problems and was agreed upon at some point.

Rounding

Removed setrounding(Interval, mode) and redefinition of function to change the rounding mode.

Instead the default rounding is given by the (not exported) function IntervalArithmetic.rounding_mode() and can be changed by redefining the function.

This allow to simplify the management of the rounding mode.

@round now take the interval type of the returned interval as first argument. The old fallback to the default bound still exists.

Flavors

Only Cset flavor is available.

The mechanism for more flavor is however introduced, in a similar way to the new rounding mechanism. The current flavor is given by the (not exported) IntervalArithmetic.current_flavor() and can be overwritten to change flavor.

Default bound

Introduced the same mechanism as rounding and flavor, with the default bound given and possible changed through the not exported IntervalArithmetic.default_bound().

Pointwise politic

Introduced the concept of pointwise politic, that is what to do with the pointwise extension of boolean function like == to intervals.

Uses the same mechanism as rounding, flavor and default bounds, using the function IntervalArithmetic.pointwise_politic() to define the current mode.

By default uses ternary logic, similar to what is done in NumberIntervals.jl.

Also implemented boolean intervals (always erroring in conditional) and the old behavior (often silently breaking if .. else clauses).

Identity of intervals now use the \stareq infix operator, == being reserved for pointwise equality test.

Promotion and conversion

Removed all promotion and conversion involving intervals.

This makes the tracking of correctness easier as generic Number or Real methods now errors with intervals if they are not redefined in the package.

Construction

The constructors definitions have been overall and, to an extend, redesigned.

Now only @interval is trying to be smart and widen decimal inputs to guarantee their inclusion, leading to 2 eps wide interval built from single decimal literals. Guaranteeing inclusion is still better done by using either the I"" string macro or parse(Interval, str).

All others constructors take floating point at face value.

Consequently, atomic has been massively simplified.

Introduced the alias checked_interval to be more specific than just lowercase interval. Both are now equivalent to ...

Interval(::Irrational) works with generated function and is tight and correct.

Complex and Rational

Support drop as it caused problems. It could be restored.

Parser

Rewritten using CombinedParsers.jl.

It is now much simpler and also slightly tighter.

Unfortunately the new dependency seems to error on nightly, which is what causes the CI to fail.

Some extension of parsing that are not in the standard still need to be restored.

Docstrings

Added a ton of docstrings.

Others

• Removed widen and wideinterval.
• Removed interval_from_midpoint_radius. It is implemented by ±.
• Removed force_interval
• Removed find_quadrants_tan as it was a duplicate of find_quadrants
• make_interval renamed wrap_literals
• Removed pi_interval(T) in favor of Interval{T}(π)
• Renamed multiply_by_positive_constant to scale
• Renamed mid(a, α) -> scaled_mid(a, α) to avoid discrepancy with default parameter.
• Tests that seemed to have been tailored to the behavior of the old @interval have been modified or marked as @test_broken when the expected value can not be easily derived
• @interval changed to Interval in tests as much as possible.

[lbenet]

Truly impressive @Kolaru ! I'll try to begin a review this week. Perhaps, due the length of the PR, the best is send individual comments, rather than a thorough single-body review. Would that be ok for you?

[Kolaru]

@lbenet Sure, sounds good.

[dpsanders]

This sounds fantastic @Kolaru, many thanks for taking this on! I will also review as soon as possible.