Statically checked range types in Scala

I was showing off some Scala features earlier (specifically “Oh, hey, look. With proper singleton support + implicit arguments you can completely remove the need for a dependency injection container while losing none of the advantages”. More on that later…) and got to discussing the language with Craig, a coworker of mine (well, specifically our CTO. I work at a cool company. :-) ).

He asked me if Scala supported range types, to which my answer was something along the lines of “Well, no. But it should be possible to add as a library. Hmm. Might be hard to get it statically enforced though”.

Turns out it’s not. Here’s some code:

How do we use this?

scala> import ranges.Range;
import ranges.Range

scala> val myRange = new Range(0, 10);
myRange: ranges.Range = ranges.Range@10ae3fb

scala> val myRange2 = new Range(0, 20);
myRange2: ranges.Range = ranges.Range@c7014c

scala> val array = new myRange.CheckedArray[String]
array: myRange.CheckedArray[String] = ranges.Range$CheckedArray@280bca

scala> myRange.indices.foreach(x => array(x) = x.toString)

scala> array.mkString
res6: String = Index(0)Index(1)Index(2)Index(3)Index(4)Index(5)Index(6)Index(7)Index(8)Index(9)

scala> array(myRange.minIndex);
res8: String = Index(0)

scala> array(myRange.maxIndex);
res9: String = Index(9)

scala> array(myRange2.minIndex);
:8: error: type mismatch;
 found   : myRange2.Index
 required: myRange.Index
  val res10 = array(myRange2.minIndex);

scala> array(myRange.minIndex.mid(myRange.maxIndex));
res11: String = Index(4)

scala> array(myRange.minIndex + myRange.maxIndex);
:8: error: type mismatch;
 found   : myRange.Index
 required: String
  val res13 = array(myRange.minIndex + myRange.maxIndex);

scala> import myRange._;
import myRange._

scala> array(myRange.minIndex + myRange.maxIndex);
:11: error: type mismatch;
 found   : Int
 required: myRange.Index
  val res14 = array(myRange.minIndex + myRange.maxIndex);

scala> array(minIndex + maxIndex);
:11: error: type mismatch;
 found   : Int
 required: myRange.Index
  val res15 = array(minIndex + maxIndex);

CheckedArrays (and similarly ArraySlices) are scoped to a particular range object. You can only access them with indices from that same object. You can get Index objects by getting the minimum, the maximum, combining them with various operators, iterating over them or converting from an Integer (at which point it will either min/max it into bounds or throw an IndexOutOfBoundsException if the integer is out of bounds, depending on which method you call).

If you import the range (I’m thinking of separating that out into a separate object for convenience with working with multiple ranges) you’ll get an implicit convertion from indices to integers (*not* the other way around).

Currently nonexistent: Support for subranges, or working with multiple ranges (Update: See below). I think I know how to fix these in a niceish way.

Always going to be nonexistent: Can’t statically verify that two ranges are equal. This isn’t possible in principle, but even simple cases like knowing that new Range(0, 10) and new Range(0, 10) are equal types isn’t doable. I don’t think this is avoidable without special logic in the compiler or significantly more static resolution of objects than Scala is ever likely to have (e.g. I think we could do this using ML functors and sharing constraints, but it’s been so long since I’ve looked at those that I’m not really sure).

Update: Working with multiple ranges is always going to suck without language changes. There’s not enough sharing of values at compile time to express what it needs to. Subranges will probably still work though.

Update 2: It’s been observed that if you don’t know Scala then it’s non-obvious how this code works. Unlike Java, inner classes of different instances in Scala are actually different types. So given

val range1 = new Range(0, 10);
val range2 = new Range(0, 10);

range1.Index and range2.Index are different types, and may not be freely converted between. So this code works by having Range enforce that its Index elements are in bounds, and the compiler enforces that you can’t mix Index elements from different ranges.

This entry was posted in programming and tagged , on by .