Uniqueness types in Scala

I’ve recently read about the Clean programming language and got interested in it’s uniqueness typing system. The main idea is that if at some point in the program we have a link to a mutable object, and we are sure, that at the same moment there is no other links to this object, we can safely mutate it, and this will still be a pure operation.

Can we have a similar thing in scala? The way, I would like to see this is an optional annotation for the compiler. Much the same way as compiler tries to optimize tail calls and fails the compilation, if it fails to do so for a function, that is explicitly annotated with the @tailrec annotation. Here’s an example of how I see this:

import scala.collection.mutable._
def fillList(n: Int) = {
    @unique val list = new ListBuffer[Int]()
    for (i  0 to n) list += i
    list.toList
}

Here the compiler would see that there’s only one link to the list variable at any time and this would compile successfully. Now consider another example:

import scala.collection.mutable._
def swapFirstTwo[A](arr: Seq[A]) = {
    @unique val array = new ListBuffer[Int](arr:_*)
    lazy val fst = array(0)
    lazy val snd = array(1)
    array(0) = snd // here we have two links to array: array(0), which we're mutating and snd
    array(1) = fst // and here again
    array.toSeq
}

This should not compile: there are two links to the list in one expression. Although, in this particular case it is ok (from the point of view that it works correctly, of course it looks ugly and is not an idiomatic scala in any way). The code will of course still compile and work without annotation.

Anyway, we all sometimes do scala code optimization, that requires using an internal mutable state to speed things up. Although we usually cover it as much as we can, we’re still not happy with this code. Having the @unique annotation could give some compile-time guarantees, that we’re still pure and not doing anything wrong.

The idea can be extended to having a @pure annotation for functions: ask the compiler to fail the compilation if the function calls a function that does not pass the @pure check (library functions, performing IO can be explicitly marked @impure), or has non-@unique mutable state. I, of course, don’t have any idea, if scala compiler has enough information to make this possible.

Thoughts?

Comments

blog comments powered by Disqus