How does Scala implement return from within an expression?

Question

For example, if we have a method like

def find[A](xs: Seq[A], p: A => Boolean): Option[A] = {
  xs.foreach(x => if (p(x)) return Some(x));
  None;
}

(of course there is a library function for this, this is just an example). How does the execution escape foreach when the inner function returns?

Or in

def foo(x: AnyRef): String =
  process(x match {
    case (s: String) => s;
    case _           => return "";
  })

how does the execution avoid running process when return "" is issued?

Answer 1

The foo example depends on which of

def process(s: String): String
def process(s: => String): String

it is. I'm assuming the former, since you suggest process isn't run. This is just the way it always works when passing an argument--you do the argument-creation work first, then call the method. Since you run into a return, it's easy: you just call the appropriate return from bytecode while creating the argument*, and never go on to invoke the method. So it is just a local return.

The find example is a little more involved. Let's try a maximally simple example motivated by a foo which requires a nonlocal return:

class Nonlocal {
  def pr(s: => String) = { println(s); "Printed" }

  def foo(x: AnyRef): String = pr(x match {
    case (s: String) => s;
    case _           => return "";
  })
}

The body of foo is equivalent to

import scala.runtime.NonLocalReturnControl
val temp = new AnyRef
try {
  pr(x match {
    case s: String => s
    case _         => throw new NonLocalReturnControl(temp, "")
  })
}
catch {
  case nlrc: NonLocalReturnControl[_] if (nlrc.key eq temp) =>
    nlrc.value.asInstanceOf[String]
}

The key things to notice is that a sentinel object is created so that these things can be arbitrarily nested without clobbering each other, and that NonLocalReturnControl carries the correct value back. Unsurprisingly, this isn't exactly cheap compared to just returning, say, an Int. But since it creates an exception without a stack trace (safe, because it can't escape: the catch block is guaranteed to catch it), it's not that bad--is about as bad as calling a trig function or summing an array with a few dozen entries.

Note also that pr only gets partly executed before the exception gets it. In this case, it doesn't print anything because the first thing it does is try to use s to fill in an actual string, but then it hits the exception which drops control back to foo. (So you get an empty string back from foo, but you don't print anything.)

* ^{Actually, in bytecode it tends to be a jump to the end of the method, with the load/return there. Irrelevant conceptually, though.}