Meta Scala (2) – Matchmaking in the world of Scala

Update (21.04.12): Fixed some html issues with code listing
Update (21.04.12): Added example of or operation in simple pattern matching (very useful for keeping your code concise)

While the better part of me is making her way through the Dollhouse – the 5th chapter of what I find to be a really disturbing game – Alice – Madness returns, I decided to dive into one of Scala’s most powerful features – pattern matching.

Part 2 – Pattern matching

The Basics

Test(!) and implementation

  test("Simple pattern matching") {
    checkThreatLevelOf(Deathclaw()) should be ("you are dead")
    checkThreatLevelOf(Radscorpion()) should be ("run!")
    checkThreatLevelOf(FireGecko()) should be ("run!")
    checkThreatLevelOf(SuperMutant()) should be ("unless you got a big gun, run!")
    checkThreatLevelOf(Raider()) should be ("steady now. shoot!")
    checkThreatLevelOf(BigRat()) should be ("get him! it's only a BigRat()!")
    checkThreatLevelOf(Yeti()) should be ("wtf is Yeti()?")

    sealed abstract case class Enemy(attack:Int,  defense:Int)
    case class Deathclaw() extends Enemy(10,10)
    case class Radscorpion() extends Enemy (10,9)
    case class FireGecko() extends Enemy (10,8)
    case class SuperMutant() extends Enemy(8, 7)
    case class Raider() extends Enemy(4, 3)
    case class BigRat() extends Enemy(1, 1)
    case class Yeti() extends Enemy(0, 0)

    def checkThreatLevelOf(enemy:Enemy) =
      enemy match {
        case Enemy(10, 10) => "you are dead"
        case Enemy(10, 9) | Enemy(10,8) => "run!"
        case Enemy(a, d) if (a > 5 || d > 5) => "unless you got a big gun, run!"
        case enemy if (enemy.attack > 1 || enemy.defense > 1) => "steady now. shoot!"
        case enemy@Enemy(1, 1) => "get him! it's only a %s!" format enemy
        case wtf => "wtf is %s?" format wtf
      }
  }

So what exactly happened there?

Well as you can see is that I’ve been playing Fallout: New Vegas too often lately. And oh, of course, there is also the pattern matching. The simplest way to understand pattern matching is to treat it as a series of nested if-else statements (because that’s what it is under the hood) – as soon as the match is found, the match value is returned, so the order of matching plays a big role here. Also, somewhat confusing for Java devs, because of that if-else structure, there is no fall-through.

The structure of match

  test("Simple pattern matching") {
   ...
      enemy match {
        case Enemy(10, 10) => "you are dead"
        case Enemy(10, 9) | Enemy(10,8) => "run!"
        case Enemy(a, d) if (a > 5 || d > 5) => "unless you got a big gun, run!"
        case enemy if (enemy.attack > 1 || enemy.defense > 1) => "steady now. shoot!"
        case enemy@Enemy(1, 1) => "get him! it's only a %s!" format enemy
        case wtf => "wtf is %s?" format wtf
      }
   ...
}

As you can see it’s simple as saying someValue match (line 3) and then in the body of matching have a rule for every case you want to match:
– (line 4) You can match on almost any value – primitives, complex types, unlike in Java which allows you to switch only on few primitive type, Strings, Enums and few special extensions of primitive wrappers. Scala’s case classes perfectly fit pattern matching.
– (line 5) You can apply the same result to multiple cases with | (pipe).
– (line 6) Also, it’s really about the patterns – whereas in Java the cases have to be final (literals) in Scala you can describe how your pattern should look like by matching values of case classes (see line 5) and you can limit the pattern using so called guards (the if statement).
– (line 7) You can match the whole value and use it straight in the guards, as opposed to matching the values in the case class.
– (line 8) You can match the case class pattern and assign it to local value using @.
– (line 9) In the end you can resolve all unknown matches into one default match by assigning to local value or simply use the magic _ if you don’t want to do anything with it on right side of the =>.

A peek under the hood

The compiler does few tricks to optimize the if-else experience. If you scalac our example with -print option you will get a really nice output of what is going on when using pattern matching. In general, the compiler will first assign your value to some temp on which it continues all ifs. Also, if it recognizes you are matching a case class by it’s constructing values, it will extract those values from your matched value and assign those to another set of temporary values to use them in further comparisons. The guards are simply turned into private predicates to which the values are applied in the if-elses.
To help you understand I included the compilation output below. The MyTest is just an object I put the code into to be able to compile only the implementation. Also remember that the compiler makes a lot of optimizations along the way, so the code is never a straight one-to-one translation of your cases.
Notice the enemy being assigned to temp26 and its attack and defense being extracted to temp27 and temp28. Also the guards are turned into private defs gd2$1 and gd3$1 respectively. The rest is just a lot of if-else logic.

    def checkThreatLevelOf(enemy: MyTest$Enemy): java.lang.String = {
       val temp26: MyTest$Enemy = enemy;
      if (temp26.ne(null))
        {
           val temp27: Int = temp26.attack();
           val temp28: Int = temp26.defense();
          if (temp27.==(10))
            {
              if (temp28.==(10))
                {
                  "run!"
                }
              else
                {
                  if (MyTest.this.gd2$1(10, temp28))
                    "unless you got a big gun, run!"
                  else
                    {
                      if (MyTest.this.gd3$1(temp26))
                        "steady now. shoot!"
                      else
                        {
                          val wtf: MyTest$Enemy = temp26;
                          body%41(wtf){
                            scala.this.Predef.augmentString("wtf is %s?").format(scala.this.Predef.genericWrapArray(Array[java.lang.Object]{wtf}))
                          }
                        }
                    }
                }
            }
          else
            {
              if (MyTest.this.gd2$1(temp27, temp28))
                "unless you got a big gun, run!"
              else
                {
                  if (MyTest.this.gd3$1(temp26))
                    "steady now. shoot!"
                  else
                    if (temp27.==(1).&&(temp28.==(1)))
                      {
                        scala.this.Predef.augmentString("get him! it\'s only a %s!").format(scala.this.Predef.genericWrapArray(Array[java.lang.Object]{temp26}))
                      }
                    else
                      {
                        body%41(temp26)
                      }
                }
            }
        }
      else
        {
          if (MyTest.this.gd3$1(temp26))
            "steady now. shoot!"
          else
            {
              body%41(temp26)
            }
        }
    };
    final  private[this] def gd2$1(x$1: Int, x$2: Int): Boolean = x$1.>(5).||(x$2.>(5));
    final  private[this] def gd3$1(x$1: MyTest$Enemy): Boolean = x$1.attack().>(1).||(x$1.defense().>(1));

Type matching

Test(!) and implementation

  test("Type Case") {
    shoot(PlasmaRifle()) should be("zooooom")
    shoot(LaserRifle()) should be("peeuuww")
    shoot(HuntingRifle()) should be("kapooww")

    sealed abstract class Rifle()
    case class PlasmaRifle() extends Rifle()
    case class LaserRifle() extends Rifle()
    case class HuntingRifle() extends Rifle()

    def shoot(rifle:Rifle) = rifle match {
      case _:PlasmaRifle => "zooooom"
      case _:LaserRifle => "peeuuww"
      case _:HuntingRifle => "kapooww"
    }
  }

So what exactly happened there?

As you can see I make some noise depending on the type of Rifle I shoot. Easy as it is, you simply use : (colon) to match types in pattern matching. The usual form would be:

  value match {
    case value_assignment1:TypeToMatch1 => doSomething1
    case …
    case value_assignmentN:TypeToMatchN => doSomethingN
    case _ => doSomethingElse
  }

Under the hood

Under the hood, compiler interprets : in case statement as isInstanceOf call. Our example above will be changed into the compiler specific equivalent of the following:

def shoot(rifle:Rifle) … {
  val temp: Rifle = rifle;
  if (temp.$isInstanceOf[PlasmaRifle]())
    {
     "zooooom"
    }
  else
    if (temp.$isInstanceOf[LaserRifle]())
    …
}

Type matching considered harmful?

Type matching (or Type Case) is a widely used paradigm, which at the same time stirs a lot of emotions in the programming world. If you ever found yourself typing something along the lines of instanceof in any language, then you know (as a good programmer) that it’s a bit of a code smell. In example above you will quickly recognize that polymorphism is a better answer to solving the problem of shooting a rifle. However there are times where you should simply be pragmatic and fine-tune the balance of readability, complexity, good practice, etc., especially in cases where the input is external. One of such examples is Scala’s interoperability with Java:

test("Exception Type Case") {
    debug(new EmptyRifle) should be ("You're out of ammo!")
    debug(new JammingRifle) should be ("It's jammed!")
    debug(new HuntingRifle) should be ("nice shot!")

    sealed abstract class Rifle { def shoot }
    class JammingRifle extends Rifle { def shoot = throw new JammedRifleException }
    class EmptyRifle extends Rifle { def shoot = throw new OutOfAmmoException }
    class HuntingRifle extends Rifle { def shoot = "kapooww" }

    class JammedRifleException extends RuntimeException
    class OutOfAmmoException extends Exception

    def debug(rifle:Rifle) = {
      try {
        rifle.shoot
        "nice shot!"
      } catch {
        case e: JammedRifleException => "It's jammed!"
        case e: OutOfAmmoException => "You're out of ammo!"
        case e: Exception => "You're screwed! %s happened." format e
      }
    }
  }

Putting aside any discussions about Java’s exception mechanism – how cool is that? I mean, as Java programmer you would definitely benefit from such statement to clean your code (why are you catching so many exceptions anyway? 😉 ). As you can see, the try-catch is implemented as a function, thus returning value – that approach allows you to get rid of those pesky temporary variables initiated outside of the try statement.
Btw – Scala is not forcing you to catch checked exception – how cooler is that?

When considering Type Case, another problem is type erasure – a process in which all useful information about the type that was needed during compilation-time to ensure type consistency is removed at run-time, thus leaving you in a situation where Type Case approach is useless. Consider example below. Can you spot the problem?

  test("Erasure makes it complicated") {
    checkAmmo(Rifle(new HollowPoint308)) should be ("Hollow point .308 loaded")
    checkAmmo(Rifle(new Standard308)) should be ("Standard .308 loaded.")

    def checkAmmo[T](rifle:Rifle[T]) = rifle match {
      case _:Rifle[Standard308] => "Standard .308 loaded."
      case _:Rifle[HollowPoint308] => "Hollow point .308 loaded."
    }

    sealed abstract class Ammo
    class Standard308 extends Ammo
    class HollowPoint308 extends Ammo

    case class Rifle[T](ammo:T)

    class JammedRifleException extends RuntimeException
    class OutOfAmmoException extends Exception
  }

Right. So this test does not pass (“Standard .308 loaded.” was not equal to “Hollow point .308 loaded”). Why? Because at run-time all information about Rifle having this or that type is lost and so you will always fall into the first scenario – no matter what.

So if you find yourself Type Caseing – think twice – if you still need it – hey, who am I to judge, at least you know it inside and out.

Pattern matching anonymous function

Test(!) and implementation

  test("Pattern matching anonymous function") {
    fight(List(Deathclaw(), Raider(), BigRat(), SuperMutant())) should be (List(5, 1, 0, 2))

    def fight(enemies:List[Enemy]) = {
      val useRifle:PartialFunction[Enemy, Int] = {case Enemy(_, d) if d > 3 && d < 6 => d - 3 }
      val useKnife:PartialFunction[Enemy, Int] = {case Enemy(_, d) if d <= 3 => d - 1 }
      val useGrenade:PartialFunction[Enemy, Int] = {case Enemy(_, d) if d >= 6 => d - 5 }
      enemies.foldLeft(List[Int]()) {
        (enemyWounds, enemy) =>
             enemyWounds :+ (useRifle orElse useKnife orElse useGrenade)(enemy)
      }
    }

    sealed abstract case class Enemy(attack:Int,  defense:Int)
    case class Deathclaw() extends Enemy(10,10)
    case class SuperMutant() extends Enemy(8, 7)
    case class Raider() extends Enemy(4, 4)
    case class BigRat() extends Enemy(1, 1)
  }

So what exactly happened there?

Let’s imagine you’re going into combat and for each weapon you have, there is a function defined (partial – but we’ll get to that in a minute), which tells you when and how effectively you can use each weapon (how much damage it does). Now look at lines 8-10 and, if you’re a careful reader, you will notice immediately that there is pattern matching. Well, it’s actually pattern matching anonymous function. How is that different you ask? Well, for once you have a single case defined, which limits the domain of your input values. A function, which is defined only for a subset of its input domain, is called partial function (for example division is a partial function in domain of integers, as it barfs on 0) and (surprise! surprise!) our single case statements are implemented as such. When compiler sees case pattern matching statements without match clause it’s simply defines new PartialFunction for each of them. So the above is equivalent to:

    test("PartialFunction") {
    fight(List(Deathclaw(), Raider(), BigRat(), SuperMutant())) should be (List(5, 1, 0, 2))

    def fight(enemies:List[Enemy]) = {
      val useRifle:PartialFunction[Enemy, Int] = new PartialFunction[Enemy,  Int] {
        def apply(enemy:Enemy) = enemy.defense - 3
        def isDefinedAt(enemy:Enemy) = enemy.defense > 3 && enemy.defense < 6
      }
      val useKnife:PartialFunction[Enemy, Int] = new PartialFunction[Enemy,  Int] {
        def apply(enemy:Enemy) = enemy.defense - 1
        def isDefinedAt(enemy:Enemy) = enemy.defense <= 3
      }
      val useGrenade:PartialFunction[Enemy, Int] = new PartialFunction[Enemy,  Int] {
        def apply(enemy:Enemy) = enemy.defense - 5
        def isDefinedAt(enemy:Enemy) = enemy.defense >= 6
      }
      enemies.foldLeft(List[Int]()) {
        (enemyWounds, enemy) =>
          enemyWounds :+ (useRifle orElse useKnife orElse useGrenade)(enemy)
      }
    }

    sealed abstract case class Enemy(attack:Int,  defense:Int)
    case class Deathclaw() extends Enemy(10,10)
    case class SuperMutant() extends Enemy(8, 7)
    case class Raider() extends Enemy(4, 4)
    case class BigRat() extends Enemy(1, 1)
  }

As you probably got it by now, using case statements is the easiest and a very elegant way to define PartialFunctions in your code as you can use the full power of pattern matching. But wait, there’s more!
Line 22 shows you how you can inflict enemy wounds by combining partial functions using orElse operator, which produces new combined PartialFunction from its left and right operands. At the end, you apply such chain to each enemy and a proper weapon will be selected. As with the full pattern matching – the order of the combination is important as the first PartialFunction, for which isDefinedAt holds will be used.

Even more on PartialFunctions

There are some slick things you can do with PartialFunction. For once, the fact that they have the validation of the input (isDefinedAt) nicely separated from the function itself (apply) makes it really easy to make your code really dynamic without a need to define and handle obscure exception hierarchy. Another thing is andThen – operation which combines the partial function with transformation function. The latter takes the output of partial function. I modified our latest example to have some more fun (with Raiders it’s more personal, so you have to finish them off with a knife):

  test("Now it's personal") {
    case class Enemy(defense:Int)
    val raider = Enemy(4)
    val deadEnemy = Enemy(0)

    val useRifle:PartialFunction[Enemy, Enemy] = {case Enemy(d) if d > 3 && d < 6 => Enemy(d - 3) }
    val useKnife:PartialFunction[Enemy, Enemy] = {case Enemy(d) if d <= 3 => Enemy(d - 1) }

    (useRifle andThen useKnife)(raider) should be (deadEnemy)

  }

Easiest way to read this is useKnife(useRifle(raider)). The great part is that useRifle guards the input domain for the whole operation – useKnife does not have to be a PartialFunction.

If you think about it, partial function guarantees some values for part of the domain and none for the rest. Given that reasoning, you can lift (lifting is a whole separate topic, just remember the name for now) your PartialFunction to become a Function, which yields Option values and is defined for the whole domain of the input.
This operation may come in handy, when you do not validate against isDefinedAt and still want to get rid of those pesky exceptions and such. Also – it’s a lot easier to define such function:

  test("Bringing knife to a deathclaw fight") {
    case class Enemy(defense:Int)
    val bigRat = Enemy(3)
    val deathclaw = Enemy(10)
    val notEvenAScratch = None

    val useKnife:PartialFunction[Enemy, Int] = {case Enemy(d) if d <= 3 => d - 1 }

    (useKnife.lift)(bigRat) should be(Some(2))
    (useKnife.lift)(deathclaw) should be(notEvenAScratch)

  }

So now you know – never ever use melee weapons on a Deathclaw.

More official and less lethal usage of PartialFunction can be found here

In the next episode we will take a look at some detailed usage of Pattern matching, namely Regex pattern matching, List Pattern Matching and Tuples pattern matching as they are at the heart of your daily work with Scala.
Stay tuned!

End Scene

You’re now level 12 PatternMatcher!
Advertisements

2 Comments Add yours

  1. erikvanoosten says:

    Nice post! Didn’t know about lift on partial functions.

    There are some typo’s in the useKnife functions (caused by those pesky <‘s).

    I was also wondering about the semantics of the return value of the first fight method.

    1. useresu says:

      Thanks for feedback and glad you found something new 😉
      I will update the post shortly with your suggestions and also I got feedback from @pmaas to extend the partial functions bit with inline cases and extending isDefinedAt with multiple cases, so stay tuned!

      Oh – and I omitted compose function of PartialFunction – will add it as well 😉

Leave a reply after the beep...

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s