This post originated from an RSS feed registered with Scala Buzz
by Daniel Sobral.
Original Post: Strict Ranges?
Feed Title: Algorithmically challenged
Feed URL: http://dcsobral.blogspot.com/feeds/posts/default
Feed Description: Random thoughts of an IT worker in the stone age of computer science.
A common mistake newcomers to Scala usually make is to treat Scala ranges as strict. It's easy to see why they make such mistake, because the very expression "strict", though relatively easy to find in the Scala API documentation, is unfamiliar to them.
So, before getting into the problem, I'll make a brief detour. In functional languages, there is a concept of "strict functions" and "non-strict functions". Informally, a "strict function" is one which always evaluates its argument. For programmers from a non-functional background, that's most of the functions they ever saw, but not all. For instance, the trinary operator, "test ? f1 : f2", does not evaluate all its arguments, f1 and f2, even though it always evaluate at least one of them.
Now, to see where that can lead to trouble, let's first see an example of non-strictness in action:
scala> object X { | val x = -10 to 10 map (2 / _) | } defined module X
scala> object Y { | val y = List.range(-10, 10) map (2 / _) | } defined module Y
scala> Y.y(0) java.lang.ArithmeticException: / by zero at Y$$anonfun$1.apply(<console>:5) at Y$$anonfun$1.apply(<console>:5) at scala.List.map(List.scala:812) at Y$.<init>(<console>:5) at Y$.<clinit>(<console>) at .<init>(<console>:6) at .<clinit>(<console>) at RequestResult$.<init>(<console>:3) at RequestResult$.<clinit>(<console>) at RequestResult$result(<console>) at sun.reflect.Nativ... scala> X.x(0) res2: Int = 0
We see an error happens when the map on the list is applied, but not when the map on the range is applied. That's because the function "map" for Range (the result of "x to y" or "x until y" expressions) is non-strict. I can get the value for any part of that Range, except the eleventh element, without throwing an exception.
But let say we have a function expensiveComputation, which takes quite a while to process. What happens, then, if I do this:
If you haven't seen it before, the "future" function uses threads to compute the function you passed to it. Your program can go on to do other stuff, while all that work is being done concurrently.
Except, of course, that's not what's happening. No computation is being done, because Range's non-strict map hasn't evaluated its arguments. In fact, each time I call "apply" to get the result of the computation, the function I passed to map (the future) will be computed again! For example:
scala> def expensiveComputation(n: Int) = { | println("Starting expensive computation") | val x = n * 2 | println("Finished expensive computation") | x | } expensiveComputation: (Int)Int
scala> val m = 1 to 10 map (i => future(expensiveComputation(i))) (output from "m.toString" skipped)
To see where that can be a problem to beginners, take a look at the code in this question at Stack Overflow:
def ttest() = { val threads = for (i <- 1 to 5) yield new Thread() { override def run() { println("going to sleep") Thread.sleep(1000) println("awake now") } }
Well, gladly, Scala 2.8 should have a strict Range, so newcomers will be spared the trouble and lost debugging time. Here's what this will look like with Scala 2.8:
And, if we want the previous behavior, we can just call the "view" method. It will work not only on Range, but on pretty much all standard collections, as it is defined on the class IterableLike.
And, speaking of Scala 2.8 changes, there is one that is also likely to reduce confusion among newcomers, and is related to what we spoke of. It's related to how guards on for-comprehensions work. For instance, take a look at this code:
scala> def find(n: Int, l: List[Int]) = { | var found = false | for (el <- l; if !found) found = el == n | found | } find: (Int,List[Int])Boolean
This code doesn't work as expected because of how for-comprehensions are translated:
l.filter(el => !found).foreach(el => found = el == n)
Since "filter" for List is a strict method, this just doesn't work, as "filter" evaluates before "foreach". However, Range's "filter" on Scala 2.7 is non-strict. Does it work? Yes:
scala> def findR(n: Int, l: Range) = { | var found = false | for (el <- l; if !found) found = el == n | found | } findR: (Int,Range)Boolean
scala> findR(5, 1 to 10) res17: Boolean = true
But, back to the first example, as of Scala 2.8 the for-comprehension code will translate like this:
l.withFilter(el => !found).foreach(el => found = el == n)
This new function, "withFilter", will be non-strict for standard Scala collections. There's no way, however, to ensure that third-party collections will preserve the non-strictness. Hopefully, people will act in a sensible manner! :-) At any rate, the "find" function, as written, will work on Scala 2.8.
I hope this helps people working with Scala 2.7, and hope even more for Scala 2.8 to arrive soon! As a parting thought, though, I'd like to briefly speak of "<-", seen in for-comprehensions. I have seen people calling it many things. Martin Odersky's (et al) Programming in Scala book, however, calls it "in". So "for (el <- l)" ought to read "for el in l". So, if you weren't sure what to call it, now you know! Happy coding!
Previous Topic
