Stuff I've learned recently…

Even in a language like Groovy that is normally so clean and intuitive, there are traps for the unwary. I fell into one again today (in front of a room full of students), and I think it’s high time I documented it, at least so I’ll remember it for next time.

I’m teaching a Groovy / Grails class this week, and one of the problems I posed to the students was to write an isPrime method that worked for integers less than, say, 1000. The easiest brute force way to solve the problem is to divide the given number by every integer from 2 up to the square root of the number, rounded up.

Here’s a first try:
[sourcecode language=”groovy”]
// NOTE: THIS DOESN’T WORK
boolean isPrime1(int x) {
if (x == 2) return true
int limit = Math.sqrt(x) + 1
(2..limit).each { n ->
if (x % n == 0) return false // Danger, Will Robinson!
}
return true
}

assert (2..20).findAll { isPrime1(it) } == (2..20) // Wait, what??
[/sourcecode]
In other words, the method returns true for every number, whether it’s prime or not.

The problem is the return statement inside the each loop. The argument to the each method is a closure, and returning from a closure returns only from the closure, not the whole method.

I should emphasize that, so maybe next time I’ll remember it:

A return inside a closure returns only from the closure, not from the method that called it.

It’s actually not that hard to understand, when I think it through. Calling the closure is like calling another method. When I use the return keyword inside the closure, it’s like returning from that method, so it only returns from there and not from the each method itself.

So, how do I fix this? One way is to define a boolean variable outside the closure and then set it inside, but that leads to a minor problem as well.
[sourcecode language=”groovy”]
boolean isPrime2(int x) {
if (x == 2) return true
boolean result = true // local var to set in closure
int limit = Math.sqrt(x) + 1
(2..limit).each { n ->
if (x % n == 0) {
result = false
// don’t you wish you could break here?
}
}
return result
}

assert (2..20).findAll { isPrime2(it) } ==
[2, 3, 5, 7, 11, 13, 17, 19] // works, but no break
[/sourcecode]
I defined a boolean variable called result and initialized it to true. Then, inside the closure, if a number is not prime, I set the variable to false, and returned the variable at the end.

As the comment shows, however, I can’t break out of the loop. You can only use break inside loops, and some reason (I don’t know why), each loops don’t qualify. I’m forced to follow the loop to the end.

There is a way to solve that problem, too. I just need to replace the each loop with Groovy’s for-in loop.
[sourcecode language=”groovy”]
boolean isPrime3(int x) {
if (x == 2) return true
boolean result = true
int limit = Math.sqrt(x) + 1
for (n in 2..limit) {
if (x % n == 0) {
result = false
break // yay!
}
}
return result
}

assert (2..20).findAll { isPrime3(it)} ==
[2, 3, 5, 7, 11, 13, 17, 19] // works
[/sourcecode]
Now it works. This is also one reason to sometimes favor the for-in loop over the each iterator, but usually they’re interchangeable.

As usual, I couldn’t leave well enough alone. A common idiom in the Groovy JDK is to use metaprogramming to replace a static method in one class with an instance method in another. For example, java.lang.Math has the static abs method, but the Groovy JDK adds abs as an instance method to java.lang.Number. It’s not hard to do the same thing here:
[sourcecode language=”groovy”]
Number.metaClass.isPrime = { ->
Integer x = delegate as Integer
if (x == 2) return true
boolean result = true
int limit = Math.sqrt(x) + 1
for (n in 2..limit) {
if (x % n == 0) {
result = false
break
}
}
return result
}

assert (2..20).findAll { it.isPrime() } == [2, 3, 5, 7, 11, 13, 17, 19][/sourcecode]
The delegate of the closure is the number the isPrime method was called on, so if I assign it to x I can copy and paste my implementation from above.

The truly fun part was that I assigned this problem to the students, and then decided to live code the implementation in front of them. Of course I went for the each implementation, falling right into the trap. Since I’ve seen this problem many times, I recognized it pretty quickly and therefore wrote the other two implementations after that. I’d like to believe that the students got some value out of seeing me mess it up and then fix it. If nothing else, they learned the value of test cases. Without those assert statements, I probably wouldn’t have noticed the error in the first place.

Baruch Sadogursky (@jbaruch on Twitter) is doing a presentation on Groovy and Grails Puzzlers at Gr8conf in Minneapolis at the end of July, and he’s always interested in issues like this, so I made sure to send it along to him. If you know of any others, I’m sure he’d appreciate them as well.