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:

// 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??

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.

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

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.

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

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:

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]

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.

About Ken Kousen
I teach software development training courses. I specialize in all areas of Java and XML, from EJB3 to web services to open source projects like Spring, Hibernate, Groovy, and Grails. Find me at Google+ on Google+ I am the author of "Making Java Groovy", a Java / Groovy integration book published by Manning in the Fall of 2013.

8 Responses to The Closure Of No Return

  1. Jochen Theodorou says:

    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. Jens R says:

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

  3. Mark Perry says:

    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. Ken Kousen says:

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

  6. Tim says:

    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. vasya10 says:

    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/

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,377 other followers

%d bloggers like this: