Ranges and slices

I guess we’ve all seen Dijkstra’s famous argument that a range of natural numbers should be expressed using an inclusive lower bound and exclusive upper bound, and that, as a corollary, arrays should be indexed from 0. It’s a thought provoking little nugget of reasoning, though it fails to contemplate several objections, including that:
 
 
 
 
 
 
 

  • The inclusive lower bound/exclusive upper bound combination (let’s call that a Dijkstra range) isn’t natural for a range which includes negative integers. The range start<=i<=0 would be written as start<=i<1. Dijkstra ranges are nastily asymmetrical!
  • Zero-based indexing is infuriatingly inconvenient when accessing the last element of an array, or when indexing from the end of the array. Who here loves array[length-i-1]? This inconvenience, at least arguably, outweighs the convenience of being able to write0<=i<length instead of 1<=i<length+1, and thus substantially undermines Dijkstra’s case for zero-based indexing, even if we accept his argument for Dijkstra ranges!
  • Two endpoints isn’t the only way to specify a range of integers!

Ceylon doesn’t have a traditional for loop, and we don’t iterate list elements by looping over the indices of the list. Nevertheless, we still need a way to express ranges of integers. Our solution to this problem is a bit different to other languages, and amounts to a partial rejection of Dijkstra’s conclusions, so it’s worth explaining the reasoning behind it.

Ranges

Our design is premised on the observation that we almost never, in practice, naturally find ourselves with an inclusive lower bound/exclusive upper bound combination. What naturally arises in our program is almost always either:

  • two (inclusive) endpoints, or
  • an (inclusive) starting point and a length.

Using a Dijkstra range, we can express either case without too much discomfort:

  • start<=i<end+1
  • start<=i<start+length

Thus, we can view the traditional use of Dijkstra ranges as a sort of compromise between these two cases: a choice that makes neither option too painful.

But, of course, by clearly distinguishing these two common cases, it becomes clear that both case are amenable to further optimization. Thus, Ceylon provides two options for expressing a range of integers:

  • The spanned range operator expresses a range in terms of its two endpoints as start..end. In the case that end<start, the range is ofdecreasing values. In the case that end==start, the range has exactly one value.
  • The segmented range operator expresses a range in terms of its starting point and length as start:length. In the case of a nonpositive length, the range is empty.

Thus, a traditional C-style for loop of this form:

for (i=0; i<length; i++) { ... }

is written like this:

for (i in 0:length) { ... }

Now, since integers aren’t the only things we can form ranges of, the .. and : operators are generalized to any type T that satisfies the interfacesOrdinal & Comparable<T>. So, for example, we can iterate the letters of the English alphabet like this:

for (c in 'a'..'z') { ... }

Slices

A closely related problem is that of “slicing” lists. Python uses Dijkstra ranges to express a slice of a list, so list[start:end] contains the elements list[start], list[start+1], ..., list[end-1]. For the reasons already given above, this is a reasonable compromise.

Ceylon goes one better, giving you the choice between:

  • The span operator, written list[start..end] for the elements list[start], list[start+1], ..., list[end].
  • The segment operator, written list[start:length] for the elements list[start], list[start+1], ..., list[start+length-1].

The span and segment operators are defined in terms of the rather abstract interface Ranged and therefore apply to more than just Lists. For example, the platform module ceylon.collection lets you express subranges of a SortedMap or SortedSet using these operators.

 

Reference: Ranges and slices from our JCG partner Gavin King at the Ceylon Team blog blog.
Related Whitepaper:

Software Architecture

This guide will introduce you to the world of Software Architecture!

This 162 page guide will cover topics within the field of software architecture including: software architecture as a solution balancing the concerns of different stakeholders, quality assurance, methods to describe and evaluate architectures, the influence of architecture on reuse, and the life cycle of a system and its architecture. This guide concludes with a comparison between the professions of software architect and software engineer.

Get it Now!  

2 Responses to "Ranges and slices"

  1. John Bayko says:

    My preference for specifying ranges as first included, first excluded is to keep consistent with non-integer ranges. One end must be excluded, or it’s impossible to specify adjascent ranges which do not overlap (by whatever arbitrary measurement precision you’re using – and it might not even be clear how much they overlap by, for example seconds or nanoseconds). For integers this is less of a problem, but there’s also no problem just following the same convention, as Python does.

  2. Gavin King says:

    Hi John: like in most other programming languages, Ranges in Ceylon are always ranges of discrete values, since Ranges are Iterable. We’re not considering continuous ranges of real numbers or rational numbers or whatever, so this issue does not arise.

    One problem with the Python convention, as already pointed out, is how very common off-by-one errors are in code that uses the first included, last excluded convention. The convention is asymmetric, meaning that you have to apply a different reasoning pattern when you attempt to address elements from the end of the range.

Leave a Reply


8 − = two



Java Code Geeks and all content copyright © 2010-2014, Exelixis Media Ltd | Terms of Use | Privacy Policy
All trademarks and registered trademarks appearing on Java Code Geeks are the property of their respective owners.
Java is a trademark or registered trademark of Oracle Corporation in the United States and other countries.
Java Code Geeks is not connected to Oracle Corporation and is not sponsored by Oracle Corporation.

Sign up for our Newsletter

20,709 insiders are already enjoying weekly updates and complimentary whitepapers! Join them now to gain exclusive access to the latest news in the Java world, as well as insights about Android, Scala, Groovy and other related technologies.

As an extra bonus, by joining you will get our brand new e-books, published by Java Code Geeks and their JCG partners for your reading pleasure! Enter your info and stay on top of things,

  • Fresh trends
  • Cases and examples
  • Research and insights
  • Two complimentary e-books