Tuesday, April 20, 2010

Breaks

Scala 2.8 added the break control flow option. It is not implemented as a special language feature. Rather it is simply implemented as an object/trait using standard Scala mechanisms. If you are interested in creating a control flow object similar to this look at the Defining Custom Control Structures post.

The Break functionality is works basically how you would expect:
  1. // Import the control flow methodsmethods
  2. scala> import util.control.Breaks._
  3. import util.control.Breaks._
  4. // pass a function to the breakable method
  5. scala> breakable {
  6.      | for (i <- 1 to 10 ) {
  7.      | if(i > 5) break  // call break when done
  8.      | println(i)
  9.      | }
  10.      | }
  11. 1
  12. 2
  13. 3
  14. 4
  15. 5

Pretty intuitive but beware, break only breaks out to the first enclosing breakable. Here is an example of the issue:
  1. scala> def loop(f : Int => Boolean) = breakable {
  2.      | for (i <- 1 to 300) if (f(i)) break else println(i)
  3.      | }
  4. loop: (f: (Int) => Boolean)Unit
  5. // This never ends because break is caught by breakable in the loop method
  6. scala> breakable {
  7.      | while(true) {
  8.      | loop{ i => break; true }
  9.      | }
  10.      | }

Fortunately the implementers provide an elegant way to handle these sorts of cases. The Breaks object extends the Breaks class. By instantiating other instances of Breaks it is possible to control which breaks capture
  1. scala> import scala.util.control._
  2. import scala.util.control._
  3. scala> 
  4. scala> def loop(f : Int => Boolean) = {
  5.      |   val Inner = new Breaks
  6.      |   Inner.breakable {
  7.      |     for (i <- 1 to 4) if (f(i)) Inner.break else println(i)
  8.      |   }
  9.      | }
  10. loop: (f: (Int) => Boolean)Unit
  11. scala> 
  12. scala> val Outer = new Breaks
  13. Outer: scala.util.control.Breaks = scala.util.control.Breaks@1ba4806
  14. scala> Outer.breakable {
  15.      |   while(true) {
  16.      |     loop{ i => if(i==4) Outer.break; false}
  17.      |   }
  18.      | }
  19. 1
  20. 2
  21. 3

9 comments:

  1. I was interested in the implementation, so I checked out the source for Breaks. It seems it uses exceptions to achieve the "break" effect. This means that the performance of this construct is far from optimal.

    ReplyDelete
  2. I am far from an expert here but from the discussions I have read the performance should not be much of an issue. Creating an exception is supposedly a light weight action so that will not create a lot of overhead. The main cost of exceptions occur when filling the exception with a stack trace. The stack trace is never obtained so from what I understand it is never calculated.

    I do not know how much of a performance issue it is to throw an exception but again from what I have read that is not particularly expensive either.

    Finally I do not see many situations where the performance is an issue. Or if it is I think there should be fairly simple ways to work around it. One of the most commons ways to use break is within a loop. In that case the break is called once per loop. So unless the break happens very quickly and the loop is called very often there should be little performance problems even if break is very slow (which I don't think it is).

    my 2 cents.

    ReplyDelete
  3. Except if the break is surrounded by an outer loop, which is I think a very common case. Most use of break is when there are many nested loops. It would be interesting to see a microbenchmark against a traditional Java break.

    ReplyDelete
  4. I think it won't work if break call is surrounded by try-catch clause. Like:

    scala> breakable {
    | for (i <- 1 to 5) {
    | try {
    | println(i)
    | if ( i > 2 ) break
    | } catch { case e => println("break caught") }
    | }
    | }
    1
    2
    3
    break caught
    4
    break caught
    5
    break caught


    I know it is not a good practive but, unfortunately, I still see code like that.

    ReplyDelete
  5. >@Anonymous said...
    >I was interested in the implementation, so I >checked out the source for Breaks. It seems it >uses exceptions to achieve the "break" effect. >This means that the performance of this construct >is far from optimal.

    Run some tests and put up some proof please!

    The exception thrown is defined by object Breaks as a val. Its instatiated exactly once for your entire application. Furthermore the expensive part of instantiating exceptions is the population of the stack trace. The BreakException mixes in the NoStackTrace trait which means that NO STACK TRACE is populated for this singleton exception.
    That leaves the actually throw catch mechanism which I believe is pretty efficient.

    So please! Run some tests and post your results as proof of your assertion that this is inefficient.

    ReplyDelete
  6. I would be very interested to see Scala's break benchmarked against Java's break as well.

    Also, are there any clever designs in the works to implement continue using some combination of language features as well?

    ReplyDelete
  7. @Daniel: In order to implement a continue, you can use the following:

    val continue = new Breaks
    Breaks.breakable {
    for (i <- 1 to 10)
    continue.breakable { if (i % 2 == 0) continue.break; println(i); if (i == 7) Breaks.break }
    }

    Produces:
    1
    3
    5
    7

    Unfortunately, I haven’t seen a way to return a value with a break, so that one could use it together with yield.

    ReplyDelete
  8. I am new to Scala. The first time I discovered that Scala had no built-in break and continue, my instinct was "bug in the language". I've had a lot of programming experience and so my instincts are often correct ...

    Indeed, I see in this case one of the enormous problems with Scala-style break: It's **dynamically** scoped. Your example of the loop() function shows exactly the problem, and it shows clearly why dynamic scoping sucks so badly. There's a reason why modern programming languages are lexically scoped.

    ReplyDelete
  9. I find that the actual need for break is virtually non-existent. I have been programming in scala for almost 4 years now and I have only had the need for it once and the implementation was sufficient for that use-case.

    So I would say that in my experience this is a non-issue

    ReplyDelete