Sunday, March 15, 2009

Goto in Scala

Ever wished you could use goto in your Scala programs? :-) You'll be glad to know that a new compiler plugin, currently in development, makes it possible.

import Goto._

reset {
  var sum = 0
  var i = 0
  val beforeLoop = label // Create label for goto
  if (i < 10000) {
    println(i)
    sum += i
    i += 1
    goto(beforeLoop) // Jump to label
  }
  println(sum)
}

The new plugin brings delimited continuations to Scala. With continuation support, it becomes possible for end users to extend the language in new and interesting ways. For example, it is possible to write new control flow operations. Here's some code that implements the famous goto operation, which was for some reason omitted from the Scala language.

object Goto {

  case class Label(k: Label => Unit)

  private case class GotoThunk(label: Label) extends Throwable

  def label: Label @suspendable =
    shift((k: Label => Unit) => executeFrom(Label(k)))

  def goto(l: Label): Nothing =
    throw new GotoThunk(l)

  private def executeFrom(label: Label): Unit = {
    val nextLabel = try {
      label.k(label)
      None
    } catch {
      case g: GotoThunk => Some(g.label)
    }
    if (nextLabel.isDefined) executeFrom(nextLabel.get)
  }

}

To use this code, you would first call label to get a Label object. You could then jump to the label by calling goto and passing the Label object as an argument.

Here's how it works.

Calling label captures the continuation with shift. We store the continuation in a Label object. When we run the continuation, the Label is passed as an argument. This allows it to be used by code within the continuation—by calls to goto, for example.

Calling goto throws a GotoThunk that contains the Label. We then catch the thunk. We can catch it because we made sure to run our continuation in a try/catch block. Once we catch the thunk, we extract its Label and run the Label's continuation, starting the process all over again. In this way we can continue calling goto indefinitely…

Goto is only one of many control flow operations that we can construct with delimited continuations. For example, we can make conditionals, loops, generators, coroutines, etc.

If you're interested in playing with the plugin yourself, you can find some brief usage instructions in my previous blog entry. Remember that the plugin is still under development! You may also wish to read a description of the plugin's status that was posted to scala-user by Tiark Rompf, the plugin's author.

7 comments:

Channing Walton said...

NOOoooooooo.......

sadie said...

I second that NOOoooooo......

More important than what I want to use in my own code is what's available to other people. One of the blessings of a modern language like Scala is that when I'm handed code written by some spotty intern who isn't around to support it, I know it won't have mines like this hidden in it. Sure they can still write bad code, but with one less piece of rope to hang themself - and me - with.

Channing Walton said...

I should add to my 'NOOoooooooo.......' to avoid confusion.

I think its brilliant that scala can do this and it just goes to prove how flexible the language is. I just hope no one actually uses a goto ;)

grant rettke said...

When users utilize GOTO it might mean that an adquate control structure for their needs is missing from the language.

Nicolas Dasriaux said...

Yes, goto may be used appropriately in some rare cases, and bring more clarity.

But, 99% of the time, it is just a way for bad programmers who have not been abled to (and won't ever be able to) figure out structured programming with loops and alternatives.

I've maintained some Cobol at the very beginning of my career. And believe me, goto is the definition of hell. In Cobol, it allows jumping in the middle of a loop, or coding composite boolean expression with jumps.

Nicolas Dasriaux said...

This post clearly shows how continuations can actually be used to implement goto.

The code is very clear and well commented... provided that you already understood the continuation concept, continuation-passing style (CPS), and how CPS relates to reset and shift.

This post really helped me understood the purpose of continuations, which seems like a very abstract construction at first glance.

Rich Dougherty said...

Nicolas: Thanks for your comments. This post is partly a joke but partly an illustrative example. Glad it helped you!