The Closure Of No Return

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.

9 responses to “The Closure Of No Return”

  1. Jochen Theodorou Avatar
    Jochen Theodorou

    you can actually keep the open block, if you replace the usage of “each” with find. You have to reverse the booleans a bit, but the following works:
    boolean isPrime1(int x) {
    if (x == 2) return true
    int limit = Math.sqrt(x) + 1
    return (2..limit).find { x % it == 0 } == null
    }

  2. You could replace return with throw and wrap the function in try-catch.

  3. A good way to challenge students is to define the general, lazy prime stream (https://gist.github.com/mperry/10878344):

    @Grab(“org.functionaljava:functionaljava:3.1”)

    import fj.F
    import fj.data.Stream
    import groovy.transform.Memoized

    @Memoized
    Stream primes() {
    Stream.cons(2, { ->
    Stream.range(3).filter { Integer i ->
    primes().takeWhile({ Integer j -> j * j i % k != 0 }
    }
    })
    }

    println primes().takeWhile { it <= 20 }

  4. Since you changed the each-loop to a for-loop, you no longer need the ‘break’, you can use ‘return’ as you did first. Since the for-loop isn’t a closure, a ‘return’ will return the method just as expected.

  5. Ah, of course. That didn’t occur to me, and it probably should have. 🙂 Thanks for the info.

  6. Have you tried using the any function rather than each? I am making the assumption it breaks out of checking each value when it gets a true value.

    boolean isPrime3(int x) {
    if (x == 2) return true
    int limit = Math.sqrt(x) + 1
    !(2..limit).any { n ->
    x % n == 0
    }
    }

    assert (2..20).findAll { isPrime3(it)} == [2, 3, 5, 7, 11, 13, 17, 19] // works

  7. My go at making it even more Groovy:

    boolean isPrime(int x) {
    int limit = Math.sqrt(x) + 1
    x == 2 || (2..limit).every { n ->
    x % n
    }
    }

  8. i like the ‘any’ solution .. here is a slight variation for 3..n primes and trying to keep it in a single line 🙂 http://vasya10.wordpress.com/2012/01/10/groovy-olc-1/

  9. […] blogged about that before, and even submitted a variation to Baruch Sadogursky as a Groovy Puzzler, but this is where I first […]

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.