Range API

[Olexandr Rotan]

>
> but I also don't sense people beating down the doors for that (even if the
> language had range literals, like `0..<100`).


True, that what I was thinking also: "is iteration over numeric range is so
important to challenge general versatility of API?", but

for (int j=index; j<index+target.length(); j++)


is the use case that I haven't even thought of. After some research, I
found a family of methods across jdk that could benefit from ranges. Their
names match X::indexOf(X) or X::indexOfSubX(X) or similar patterns. I did
some research and found it surprising that the only young language, which
all now have first-class support for ranges, that takes advantage of range
return types is Swift and its string::range(of: substring) (maybe there is
similar methods for sublists in Swift, I think it is not that significant).
Others either return an optional int or int itself.

Much more languages, though, have adapted ranges as input parameters for
slicing and other range-specifying operations, not lastly due to issues like

Similarly, I see errors in API usage because sometimes we specify range by
> (start, end) and sometimes by (start, length)


Though, there are some differences with the vast majority of languages and
this API currently, mostly with the fact that almost all languages do not
support any range algebra out-of-the-box (closest I have seen were
itertools in Rust), and, subsequently, there is nowhere to emerge for unios
from, unlike current implementation. Adapting return types for being
three-state algebraic data types (i.e. result of passing empty range,
result of passing uninterrupted and result of passing union) is not that
hard, but just another work to do in case similar APIs would be adopted in
jdk.

My research about iterability of ranges in other languages showed that
there is, unfortunately, no magic pill invented. Basically, there are two
approaches to making range iterable:

1) Implement iterator
2) Implement increment/decrement

The concrete way might vary from traits in Rust (and something like this in
Haskell I suppose) to operator overloading in c++, but concepts are the
same. Most languages also provide out-of-the-box support for integer
ranges.

And that is what I concluded on, at least for now. I think that API should
provide support for any custom iteration strategy using something like
Collector/Gatherer wrappers over a functional interface that will transform
increment/decrement function into iterator. Besides that, I think that it
makes sense to create separate Range.OfInts(int, int) or just
Range.of(int,int) overload, that will return thin extension of
Range<Integer> (noone convinces me to create new specialized class), that
implements iterable using simple int increments, which would both benefit
the performance and address most of the use cases for "obviously iterable"
ranges. I also think there is no need for open iterable ranges, even if
start-closed. I think it is better to have some method to return Stream
than implement Iterable, since this might lead to unexpected problems.

Best regards

On Thu, Sep 26, 2024 at 4:30 PM Brian Goetz <brian.goetz at oracle.com> wrote:

> Sorry for the not-good news, but I'm not too surprised.  Computational
> domains like "32 bit integers" seem like they should have a lot in common
> with algebraic structures like groups and rings, but when you start poking
> at them, the compromises we make to fit them into hardware registers start
> to bite.  (And let's not get started on floating point...)  Lots of
> research into numeric towers in various languages, or capturing fundamental
> properties in type classes like Haskell's `Eq` and `Ord`, offers plenty of
> compromise to go with its promise.
>
> I think a big part of what you are running into is that you've started
> with a _concept_ (a deceptively simple one, at that), rather than
> _requirements_.  And it is the open-endedness of this concept (discrete vs
> continuous, bounded vs half-open, including endpoints or not, etc) that
> resists abstraction.  Plus, without clear requirements, you will be subject
> to an endless barrage of "what about my pet use case" (e.g., "what about
> the numbers zero to ten, advancing by two").  Meanwhile, domain-specific
> libraries such as java.time will invent their own domain-specific answers,
> like Interval.
>
> Rather than starting from the algebraic properties, perhaps start from the
> other end: what are the use cases where the lack of a range abstraction is
> problematic.  I get that
>
>     for (int i=0; i<100; i++) { ... }
>
> is uglier and less abstract than
>
>     for (int i : Range.of(0, 100)) { ... }
>
> but I also don't sense people beating down the doors for that (even if the
> language had range literals, like `0..<100`).
>
> Where I do see people having trouble is that many range computations are
> error prone.  For example, `String::indexOf` returns the starting index of
> a match; if you want to actually iterate over the characters of such a
> match, you have to do something like
>
>     for (int j=index; j<index+target.length(); j++)
>
> and you are at risk for fencepost errors when recreating the range.
> Whereas an indexOf method (under a more suitable name) that returned a
> range, would be more amenable to downstream processing.  Similarly, I see
> errors in API usage because sometimes we specify range by (start, end) and
> sometimes by (start, length), and since both are ints, we get no type
> checking when you pass the wrong kinds of ints to such a method.
>
> But, the mere existence of a Range type would do little to help String,
> Arrays, and other range-happy APIs, because we would have to update them to
> include new overloads that dispense and consume ranges.  So that's a big
> project.
>
> Still, I think investigating use cases involving libraries that work
> intensively with ranges like this would likely yield useful information for
> what a Range type would want to provide.
>
> HTH,
> -Brian
>
>
>
>
>
>
> On 9/26/2024 9:07 AM, Olexandr Rotan wrote:
>
> Researching the of deriving some iterable representations from ranges, and
> I am not here with the good news.
>
> Unlike range algebra and boolean operations, which generalize
> extremely well, iterability of ranges... Well, it's safe to say it
> doesn't generalize at all. Analyzing key features people expect iterable
> ranges to have, I ended up concluding there are basically two groups / two
> use cases for them. First is plain and simple, arguably the most popular
> one: iterating over a range of integer numbers, i.e. `for (i : Range.of(1,
> 10))`. Another use case is for more complex iterations over ranges of
> reference types, most commonly dates/time.
>
> There are two groups of values by their nature: discrete and continuous.
> Most of the types belong to the second group, as there is no direct
> increment AND decrement for them (we will omit hardware limitations for
> simplicity), such as floating point values. What is the increment of 1,3?
> 1.31 or 1.30000000001, or maybe something even more unreadable? On the
> other hand, the increment of LocalDate in context of range iteration that
> represents today is rather obvious - it is tomorrow.
>
> There is a pretty limited number of discrete types in jdk. Dates, whole
> numbers and basically that's it. The discrete types that are not present in
> jdk can be really various. For example, users can define a comparable
> type "F1Team" and compare them based on their position in the last race.
> There, increment would most likely be the next team in rating. There are
> many domain-specific cases like this.
>
> This is where the problem comes from. If the user would always have to
> pass a comparator to create a range, it would be consistent to make the
> user define increment/decrement as well. But we don't want users to pass a
> comparator if the type is already comparable. Similarly, we don't want
> users to define increment/decrement if there is already one in the
> language! I think defining increments for dates (say LocalDate.plusDays(1))
> would be acceptable, even defining increments for floats in context of
> ranges might be acceptable, but making people define increments for
> integers is, in my opinion, completely not. Besides performance impact,
> this is a terrible user experience.
>
> There are a few solutions to this:
> 1) Define ton of overrides for factory methods and specialized types for
> this (uhh, sounds awful)
> 2) Introduce new interface, say Discrete<T>, that defines T increment()
> (and possible T decrement()) methods. From now on, there are 2 branches:
> 2.1) Leave things as is, allow users to define incrementation logic for
> their types, but don't touch integers and other built-ins.I see this option
> as extremely inconsistent and not solving the main issue, which is
> iterability of integers.
> 2.2) Retrofit (scary) existing types to implement this interface. This
> should not have any compatibility nor security implications, but still
> sneaking into java.lang every time we need some new API to be more
> user-friendly is obviously not a way to go. This basically comes down to a
> question about how deep we want to integrate ranges into language, and is
> range  generalization even worth the invasion into the core of
> language (imo yes).
> 3) Leave things as they are, just let users derive iterables using
> something like range.asIterableWithStep(IncremetStartegy increment). I
> think this would make an API too narrow as no one will use it for routine
> tasks the same way people do in Rust, Kotlin and other languages.
>
> I would love to hear community opinion on this matter. Which option is the
> most preferable, maybe some compromise between a few of them, or maybe
> there is a better way to go that I didn't mention here?
>
> Best regards
>
> On Tue, Sep 24, 2024 at 5:11 PM Alan Snyder <javalists at cbfiddle.com>
> wrote:
>
>> I have another example: I have a datatype that represents a region of an
>> audio track, for example, one tune in a medley of tunes. I allow the region
>> to
>> specify both a start and end time, but the end time is optional (and
>> mostly not used). When the end time is not specified, the region ends at
>> the start of the next region, or at
>> the end of the track if there is no next region. The latter case is
>> useful because the exact track length may not be known. The optionality of
>> the end time
>> is not represented in the type system.
>>
>> Having said that, I’m not sure that a general abstract interface would be
>> useful for this example.
>>
>> On Sep 24, 2024, at 2:13 AM, Olexandr Rotan <rotanolexandr842 at gmail.com>
>> wrote:
>>
>> As part of the redesigning  process , I am researching whether or not
>> there are use cases that require asserting that the range is exactly
>> half-bounded. This is important because I plan to switch to
>> BoundedAtEnd/BoundedAtStart sealed interfaces instead of flags and runtime
>> checks: Here is what I gathered for now.
>>
>>
>>    - *Date/Time Handling (Historical or Forecast Data)*: When dealing
>>    with events that started at a specific time but have no known end (e.g.,
>>    open-ended employment contracts or ongoing subscriptions)
>>    - *Stream Processing (Real-time Event Streams)*: In real-time
>>    systems, you might process data that has a start time but no defined end,
>>    such as monitoring a live video feed or logging system. The range is
>>    bounded at the start and unbounded at the end as more data will
>>    continuously arrive.
>>    - *Data Pagination (Fetch Until Condition)*: When implementing
>>    pagination, sometimes you might want to fetch items starting from a
>>    specific index up to an unbounded limit (e.g., fetching all items after a
>>    certain point until memory runs out or a condition is met).
>>    - *Auditing and Monitoring*: In systems where audit trails or logging
>>    data should capture all events after a certain point (bounded start) with
>>    no foreseeable end (unbounded end), such as monitoring changes to records
>>    in a database starting from a fixed timestamp.
>>    - *Scientific or Statistical Ranges*: When modeling physical systems
>>    or statistical ranges, you might want to capture measurements that begin at
>>    a known threshold but theoretically have no upper or lower bound. For
>>    example, recording temperature data starting at absolute zero and
>>    increasing without any known upper limit.
>>    - *Inventory or Resource Allocation*: Resource allocation policies,
>>    such as those for virtual machines, may be based on known minimum
>>    allocation thresholds but have flexible or unbounded resource caps,
>>    depending on availability.
>>
>>    I am writing to ask whether anyone who worked with such systems could
>>    confirm/deny that those are real use cases. If so, would it be satisfying
>>    enough to assert one-way unboundness with instanceof checks, i.e. range
>>    instanceof UnboundedEndRange && !(range instanceof UnboundedStartRange).
>>    Would appreciate any feedback.
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/core-libs-dev/attachments/20240926/6c6e334f/attachment-0001.htm>