Responses to “The Closure Of No Return”

I knew as soon as I wrote about implementing a simple prime number algorithm using Groovy that someone would find a more elegant way of solving the problem. In this post, I want to highlight some of the responses I received.

In my previous post, The Closure Of No Return, I discussed implementing an isPrime method that worked for relatively small integers. The algorithm is to try to divide the given number by all integers from two up to the square root of the number, rounded up.

My initial attempt, and the actual motivation for the blog post, was to demonstrate that if you use a return keyword inside a closure, you only return from the closure. So my initial implementation didn’t work:

// THIS DOESN'T WORK
boolean isPrime1(int x) {
    if (x == 2) return true
    int limit = Math.sqrt(x) + 1
    (2..limit).each { n ->
        // nice try, but a return in a closure
        // returns only from the closure
        if (x % n == 0) return false
    }
    return true
}

The each method takes a closure as an argument, which is like calling a completely separate method. The return statement inside the closure returns from that method, but not from the each loop itself.

In order to return the proper value, I introduced a local variable, called result, which I assigned inside the closure and then returned:

boolean isPrime2(int x) {
    if (x == 2) return true
    boolean result = true
    int limit = Math.sqrt(x) + 1
    (2..limit).each { n ->
        if (x % n == 0) {
            result = false
            // can't break out of the loop
        }
    }
    return result
}

Since I couldn’t use the break keyword inside the loop, this implementation was forced to check all the integers up to limit. I therefore switched at that point to Groovy’s for-in loop, which does allow the break:

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
        }
    }
    return result
}

That was my final implementation in the blog post. I posted that one the web and waited for the corrections to roll in.

One commenter, Eric Johansson, pointed out that once I switched to the for-in loop, I could go back to using return again and eliminate the local variable result. Of course that’s true, and I missed it because of the steps I went through to write the code. I wonder how often such hysteresis loops occur in practice.

Another person commenting on the post, identified at Tim but without an email address or a link, suggested using the any method:

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

The hope here is that the any method would stop at the first number that satisfied the closure. I wasn’t sure that was true, so I looked at the source code for Groovy, which can be found on GitHub. The any method is shown in the Groovy JDK as being part of the java.lang.Object class. One way methods are added to the Java standard library is through the metaprogramming methods in
org.codehaus.groovy.runtime.DefaultGroovyMethods. I looked in that class and found the any implementation, which adds the any method to the java.lang.Object class:

// from DefaultGroovyMethods
public static boolean any(Object self, Closure closure) {
    BooleanClosureWrapper bcw = new BooleanClosureWrapper(closure);
    for (Iterator iter = InvokerHelper.asIterator(self); iter.hasNext();) {
        if (bcw.call(iter.next())) return true;
    }
    return false;
}

If I’m interpreting this correctly, the iterator walks through each element one by one and returns true the first time an element satisfies the closure. In other words, yes, this approach would work and leave the loop at the proper time.

Soren (sorry, I don’t know how to put the line through the “o”) Berg Glasius (http://twitter.com/sbglasius) suggested using the every method instead, which would also probably do the job.

Both great developer Jochen Theodorou and the indefatigable Tim Yates immediately identified the obvious alternative that I missed. Here’s Tim’s solution (which is a slight variation on Jochen’s):

boolean isPrime5(int x) {
    int limit = Math.sqrt(x) + 1
    x == 2 || !(2..limit).find { n -> x % n == 0 }
}

I remembered the findAll method, which I used in my tests, but I forgot all about the find method, which returns the first element that satisfies the closure. That’s pretty ironic, too, because (in Grails especially) I normally accidentally use find when I meant findAll.

(As an aside, as soon as I saw Tim’s name, I assumed his solution was going to be both elegant and have the take method in there somewhere. I was half right.)

The only problem I have with these solutions is that while they work, they invalidate the real reason for my blog post, which was to emphasize that a return inside a closure returns only from the closure. Still, that last one feels like a really good way to solve the actual problem, so I’m going to use that in the future.

The best part is that everyone who suggested an alternative was quite friendly about it. I may have felt a bit foolish for missing these alternatives, but that’s my own pressure on myself. One of the best features about the Groovy community is how helpful and easy to work with everyone is, which I really like. Hopefully by posting those solutions here, I’m paying some of that forward.

(Thanks to everyone who responded, whether I quoted them here or not. I really appreciate the feedback.)

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.

Start With A Story

Way back in the early 90s, I decided to revisit a notion I’d toyed with for years, which was to become a science fiction writer. As part of that effort, I subscribed to Asimov’s Science Fiction Magazine, which was (and is) the best short story market available.

Back then, Isaac Asimov himself was semi-retired (he occasionally lamented that the science fiction world had “passed him by”), but he always introduced each issue with an essay. Though I always enjoyed his writing and, like so many budding writers of my generation, grew up on the Foundation and I, Robot series, I wasn’t really interested in reading the intros. I wanted to move on to the actual stories, especially given how little time I had available to do non-professional reading.

Yet, his essays were irresistible. I never missed one, and remember some to this day.

It turns out that he was using an excellent writer’s trick that he explained in one of his many books on writing: he started each one with a brief story.

He’d talk about some event that took place in his life, involving travel, or children, or a conference, or pretty much anything. He wouldn’t spend too much time on it, and ultimately he’d tie it into what he really wanted to talk about that issue. But the effect was immediate — you were pulled into the story and wanted to know how it all turned out.

(I’d quote some of them here, but my copies of the issues from back then, if they even exist anymore, are buried in boxes deep in my basement bearing giant “Danger! Here Be Daemons!” labels. Actually, if they really were marked that way, they’d be easier to find.)

While I never became a real sf writer (a story for another day), I definitely took that advice to heart. Whenever the form allows it, I start anything I’m writing with a tiny story. Most of my blog posts work that way. I do the same thing in my presentations.

The structure can be remarkably loose, and doesn’t actually have to be about me. The key requirements are only that the story has to be interesting and that it has to be short. Some I’ve used recently:

  • “My wife has an old car with over 225,000 miles on it. My son and I have been bugging her about getting a new one. You know how here in Canada my phone doesn’t work? Well, I just got an email from my insurance company with my ‘new’ insurance card.”
  • “I’ve been reading about Bayes’ Rule and statistics recently. Did you know that Pierre Simon Laplace, one of the greatest mathematicians of all time, was disowned by his father when he refused to go into the clergy? I’ve been thinking about what jobs my son could go into that would cause me to disown him. My short list includes patent troll, spammer, TSA groper, and any I.T. job that has the word ‘evangelist’ in it.”
  • “I saw a great tweet yesterday. Do you know why George R. R. Martin can’t use Twitter? Because he’s already killed off all 140 characters.”
  • “You know how you know you’ve been traveling too much? I’m ashamed to admit I drove over to the site today and sat in the parking lot for ten solid minutes trying to remember what state I was in. That’s not good.”
  • “Last night I was looking on the Internet for a list of palindromes for some code we’re going to write today. Did you know that ‘Flee to me, remote elf?’ is a palindrome? How about ‘Go hang a salami; I’m a lasagna hog’? Or even, ‘Sex at noon taxes’?”
  • “Way back in the 90s, I tried to become a science fiction writer…” (I see what you did there)

Those are pretty generic. I try to keep an eye on slashdot or reddit or related sites to see if there are any relevant news items, too. Like during an Android class, I’ll show people the latest information about the mobile marketplace, or how there’s a huge debate going on right now about the best way to introduce apps into cars. Or if I’m teaching anything related to Java (including Groovy and/or Grails) I talk about the Java 8 release and ask about any plans for adoption. Or, as I did last January, I’ll remind those students I met in St. Cloud, MN (temperature -24F before windchill) that in this country we’re allowed to live in warmer places.

It’s simple, but it has the effect of getting everyone’s attention. Try it out on your next article, or tech talk, or lunch-and-learn, or whatever. Next week I expect to open with “Hey, did you notice that the UConn men’s AND women’s basketball teams just won the NCAA Championship? Well, nyah, nyah, nyah.”

I’ll let you know how that goes over. 🙂

%d bloggers like this: