How is pattern matching in Scala implemented at bytecode level?

Question

How is pattern matching in Scala implemented at bytecode level? Is it like a series of if (x instanceof Foo) constructs, or something else? What are its performance implications?

For example, given the following code (from Scala By Example pages 46-48), how would the equivalent Java code for the eval method look like?

abstract class Expr
case class Number(n: Int) extends Expr
case class Sum(e1: Expr, e2: Expr) extends Expr

def eval(e: Expr): Int = e match {
  case Number(x) => x
  case Sum(l, r) => eval(l) + eval(r)
}

P.S. I can read Java bytecode, so a bytecode representation would be good enough for me, but probably it would be better for the other readers to know how it would look like as Java code.

P.P.S. Does the book Programming in Scala give an answer to this and similar questions about how Scala is implemented? I have ordered the book, but it has not yet arrived.

Answer 1

The low level can be explored with a disassembler but the short answer is that it's a bunch of if/elses where the predicate depends on the pattern

case Sum(l,r) // instance of check followed by fetching the two arguments and assigning to two variables l and r but see below about custom extractors 
case "hello" // equality check
case _ : Foo // instance of check
case x => // assignment to a fresh variable
case _ => // do nothing, this is the tail else on the if/else

There's much more that you can do with patterns like or patterns and combinations like "case Foo(45, x)", but generally those are just logical extensions of what I just described. Patterns can also have guards, which are additional constraints on the predicates. There are also cases where the compiler can optimize pattern matching, e.g when there's some overlap between cases it might coalesce things a bit. Advanced patterns and optimization are an active area of work in the compiler, so don't be surprised if the byte code improves substantially over these basic rules in current and future versions of Scala.

In addition to all that, you can write your own custom extractors in addition to or instead of the default ones Scala uses for case classes. If you do, then the cost of the pattern match is the cost of whatever the extractor does. A good overview is found in http://lamp.epfl.ch/~emir/written/MatchingObjectsWithPatterns-TR.pdf

Answer 2

James (above) said it best. However, if you're curious it's always a good exercise to look at the disassembled bytecode. You can also invoke scalac with the -print option, which will print your program with all Scala-specific features removed. It's basically Java in Scala's clothing. Here's the relevant scalac -print output for the code snippet you gave:

def eval(e: Expr): Int = {
  <synthetic> val temp10: Expr = e;
  if (temp10.$isInstanceOf[Number]())
    temp10.$asInstanceOf[Number]().n()
  else
    if (temp10.$isInstanceOf[Sum]())
      {
        <synthetic> val temp13: Sum = temp10.$asInstanceOf[Sum]();
        Main.this.eval(temp13.e1()).+(Main.this.eval(temp13.e2()))
      }
    else
      throw new MatchError(temp10)
};