What is scala's experimental virtual pattern matcher?

Question

I've seen quite a few mentions recently of the new "virtualized" pattern matcher for scala. I missed the memo explaining what it actually was...

Answer 1

The "virtualized" pattern matcher is a rewrite of the existing matcher. The motivation for doing this was to support virtualization of pattern matching for the polymorphic embedded DSLs, not relevant for 2.10.

As Iulian says in the comments below: It's very similar to how for-comprehensions are compiled: instead of directly generating code, they are translated to foreach, map, filter etc. Pattern matching could then be translated to a series of method calls, that DSLs could overwrite. The default implementation will respect the current semantics, and the challenge is to make it as efficient as the current one. It seems Adriaan is very close to this goal. The 'virtualized' implementation is simpler, and fixes several bugs in the current implementation.

The "polymorphic embedded DSLs" are the idea that one might write programs in scala that are not supposed to be run on the JVM. That is, scalac will produce an output which describes what the program is doing. This may then be re-compiled against a specific architecture. Such things have been talked about at ScalaDays 2011.

This rewrite will eventually become the standard scala pattern matcher. The old pattern matcher was (as I understand it) unmaintainable.

Answer 2

Sadly, the (sole) existing answer is low on juicy bits, and the links on the commentary are broken. So let me try to add some juice here, for, if no other reason, my own reference when I actually decide to do something with it in the future, seeing as this answer is on top of every google search I do.

The virtualized pattern matcher, as mentioned, is a rewrite of how the Scala compiler handles pattern matching. It served many purposes, with the "virtualization" part of it meaning it is part of the virtualized scala effort. That effort is a bit the opposite of macros: it takes things that are "run" at compile time, and move then to run time.

For example, given the presence of the proper definition in scope, a statement like this:

if (false) 1 else 2 

instead of being compiled to bytecode branches and literals, or even optimized to the literal "2", actually gets compiled as the following statement:

__ifThenElse(false, 1, 2) 

Please see the scala virtualized wiki for more information and some examples of what this can be useful for.

I said, however, that the pattern matcher rewrite served many purposes. One other very important goal was to turn the spaghetti code that was the old pattern matcher, full or special and corner cases and bugs, into something that can be reasoned with, extended and improved more easily. This rewrite fixed so many problems that people just went through the issues list running sample code for issues related to the pattern matcher and marking the issues as "fixed" as they worked. It does have new bugs of its own, but on a much, much smaller scale.

Now, there's very little information about how the new pattern matcher works, but, basically, it translates into a few method calls which are "implemented" in the compiler with the Option monad. That then goes into an optimization phase that produces optimal bytecode.

It is possible to introduce your own matcher, though that's locked behind an -Xexperimental flag. Try the following code, copied from Scala's test suite, with and without that flag:

trait Intf {  type Rep[+T]  type M[+T] = Rep[Maybe[T]]   val __match: Matcher  abstract class Matcher {    // runs the matcher on the given input    def runOrElse[T, U](in: Rep[T])(matcher: Rep[T] => M[U]): Rep[U]     def zero: M[Nothing]    def one[T](x: Rep[T]): M[T]    def guard[T](cond: Rep[Boolean], then: => Rep[T]): M[T]    def isSuccess[T, U](x: Rep[T])(f: Rep[T] => M[U]): Rep[Boolean] // used for isDefinedAt  }   abstract class Maybe[+A] {    def flatMap[B](f: Rep[A] => M[B]): M[B]    def orElse[B >: A](alternative: => M[B]): M[B]  }   implicit def proxyMaybe[A](m: M[A]): Maybe[A]  implicit def repInt(x: Int): Rep[Int]  implicit def repBoolean(x: Boolean): Rep[Boolean]  implicit def repString(x: String): Rep[String]   def test = 7 match { case 5 => "foo" case _ => "bar" } }  trait Impl extends Intf {  type Rep[+T] = String   object __match extends Matcher {    def runOrElse[T, U](in: Rep[T])(matcher: Rep[T] => M[U]): Rep[U] = ("runOrElse("+ in +", ?" + matcher("?") + ")")    def zero: M[Nothing]                                             = "zero"    def one[T](x: Rep[T]): M[T]                                      = "one("+x.toString+")"    def guard[T](cond: Rep[Boolean], then: => Rep[T]): M[T]          = "guard("+cond+","+then+")"    def isSuccess[T, U](x: Rep[T])(f: Rep[T] => M[U]): Rep[Boolean]  = ("isSuccess("+x+", ?" + f("?") + ")")  }   implicit def proxyMaybe[A](m: M[A]): Maybe[A] = new Maybe[A] {    def flatMap[B](f: Rep[A] => M[B]): M[B]                          = m + ".flatMap(? =>"+ f("?") +")"    def orElse[B >: A](alternative: => M[B]): M[B]                   = m + ".orElse("+ alternative +")"  }   def repInt(x: Int): Rep[Int] = x.toString  def repBoolean(x: Boolean): Rep[Boolean] = x.toString  def repString(x: String): Rep[String] = x }  object Test extends Impl with Intf with App {   println(test) } 

The result without the flag is just what you'd expect:

scala> Test.main(null) bar 

With -Xexperimental, however, the alternative matching "engine" gets compiled:

scala> Test.main(null) runOrElse(7, ?guard(false,?).flatMap(? =>one(foo)).orElse(one(bar))) 

See also, for more information, the scaladocs for PatternMatching and the MatchMonadInterface.

Disclaimer: the above was extract and ran from a Scala version on the master branch, after 2.10.0, so there may be differences. I find myself sadly lacking in a pure 2.10.0 or 2.10.1 environment to test it out, though.