A Conversation with Martin Odersky, Part IV

Scala is an emerging general-purpose, type-safe language for the Java Platform that combines object-oriented and functional programming. It is the brainchild of Martin Odersky, a professor at Ecole Polytechnique Fédérale de Lausanne (EPFL). In this multi-part interview series, Artima's Bill Venners and Frank Sommers discuss Scala with Martin Odersky. In Part I, The Origins of Scala, Odersky gives a bit of the history that led to the creation of Scala. In Part II, The Goals of Scala, he discusses the compromises, goals, innovations, and benefits of Scala's design. In Part III, The Purpose of Scala's Type System, he dives into the design motivations for Scala's type system. In this fourth and final installment, Odersky discusses pattern matching.

What is pattern matching?

Bill Venners: Scala has pattern matching, a functional programming technique that hasn't been seen before in mainstream languages. Can you explain what it is, and why we need it?

Martin Odersky: Pattern matching is not very new. It has been in languages from the mid-seventies. One of the first languages that I know had it is ML, but probably it existed in languages before that. It is a standard feature of many functional languages, including ML, Caml, Erlang, and Haskell.

So what does pattern matching do? It lets you match a value against several cases, sort of like a switch statement in Java. But instead of just matching numbers, which is what switch statements do, you match what are essentially the creation forms of objects.

For example, a list in Scala is one of two cases: either the empty list, which is written Nil, or a list that consists of a single element, the head of the list, followed by another list, the tail. In pattern matching, you can ask: given a list, is it the empty list? You write case Nil, an arrow (=>), and then some expression:

  case Nil => // some expression

Or you can ask: is it a non-empty list? You write case x :: xs, an arrow, and some expression:

  case x :: xs => // some expression

The double colon (::) is the cons operator; x represents the head of the list, and xs the tail. So the pattern match will first make a distinction as to whether the list is empty. But if the list was not empty, it will also name the head of the list x and the tail of the list xs. These variables can then be used in the expression to the right of the arrow. (See Listing 1.)

list match {
  case Nil => "was an empty list"
  case x :: xs => "head was " + x + ", tail was " + xs
}

That's a very simple pattern. Patterns actually nest, just like expressions nest, so you can have very deep patterns. Generally the idea is that a pattern looks just like an expression. It is basically exactly the same sort of thing. It looks like an expression that constructs a potentially complicated tree of objects, only you leave out the news. You don't need them. In fact in Scala, when you construct the same objects you don't need the news either. Then you can in some places have variables that are placeholders for what actually is in that tree of objects. (See Listing 2.)

object match {
  case Address(Name(first, last), street, city, state, zip) => println(last + ", " + zip)
  case _ => println("not an address") // the default case
}

The purpose of pattern matching

So why do you need pattern matching? We all have complicated data. If we adhere to a strict object-oriented style, then we don't want to look inside these trees of data. Instead, we want to call methods, and let the methods do the right thing. If we have the ability to do that, we don't need pattern matching so much, because the methods do what we need. But there are many situations where the objects don't have the methods we need, and we can't (or don't want to) add new methods to the objects.

One example is XML. If you have an XML tree, the tree is just pure data. It's either a node, or a sequence of nodes. XML is a very generic representation. For instance, a DOM is just essentially an array of nodes, and you don't know what the nodes are. Now let's imagine you translate this XML tree into a richer framework, where you have a list of objects of varying types. An element of this list could be, say, a phone number, a memo, or an address. If you want to get at all these things in a statically typed way, you have a problem: you don't know what the type of each element is. The only way you can do this in a traditional object-oriented language is have a bunch of instanceof tests, where you ask: is this element an instance of PhoneNumber, or Memo, or something else? And when one of those instanceof tests succeeds, you need to do a cast. This is rather ugly and unwieldy, and pattern matching helps you there. Pattern matching does the same thing in a much safer and more natural way.

In essence, pattern matching is essential when you have structured object graphs at which you need get from the outside, because you aren't able to add methods to these objects yourself. And there are several situations where this is the case. XML is one. All sorts of parsed data fall into this category. For example, one standard situation where pattern matching is essential is when working with abstract syntax trees in compilers. If you do simplification of expressions, you represent these expressions as trees, and you need to get at them with pattern matching. There are many situations like that. And when they arise, pattern matching is truly essential.

De-constructing objects

Bill Venners: You said a pattern looks like an expression, but it seems kind of like a backwards expression. Instead of plugging values in and getting one result out, you put in one value, and when it matches, a bunch of values pop back out.

Martin Odersky: Yes. It's really the exact reversal of construction. I can construct objects with nested constructors, and maybe I also have some parameters. Let's say I have a method that takes some parameters and constructs some complicated object structure from those parameters. Pattern matching does the reverse. It takes a complicated object structure and pulls out the parameters that were used to construct the same structure.

Two directions of extensibility

Bill Venners: It sounds like what you're saying is that there's an object-oriented solution to the problem of adding new behavior that involves data inside existing objects. Ideally you would add methods to all of those subtypes, Memo, Address, and whatever the other types of nodes are. You would call those methods on the common supertype, and it would do dynamic binding and figure out, well, I'm a Memo so I'm going to do this. But the problem you're saying is that you can't always easily add those methods.

Martin Odersky: Yes, that's right. It's a question of when can you add methods. It's often a question of extensibility. Take the standard object-oriented example of a graphical user interface. You have a lot of different components that can all do the same things. They can display themselves. They can be hidden. They can be redrawn. Things like that. The protocol with which you interact with these components is fixed, but the number of components that you might come up with is unlimited. Users invent new graphical user interface components all the time. In those situations, the object-oriented approach is the right one. It's the only right one. In fact, historically it's not surprising at all that the first object-oriented language was done for simulation. That was Simula-67, which has a very similar usage profile. And the second object-oriented language, Smalltalk, coincided with the development of the first practical graphical user interface. So it was really a language that fit a problem: namely, how do I program these graphical user interfaces in an extensible way.

But that's only one notion of extensibility. The other notion is where the set of structures is relatively fixed. You don't want to change that. But the set of operations you might want to do on those structures is open. You want to add new operations all the time. The typical example for that is a compiler. Compilers work on syntax trees that represent your programs. So long as you don't change your language, the syntax tree will remain constant. It will be the same tree all of the time. But what the compiler might want to do with this syntax tree could change every day. Tomorrow you might think of a new optimization phase that traverses over your trees. So there again, you want to take an approach where the operations are defined outside of your trees, because otherwise everytime you want to add a new optimization or other behavior to your compiler, you have to go to every tree class you have and add a new method, which is very expensive and cumbersome.

So the right tool for the job really depends on which direction you want to extend. If you want to extend with new data, you pick the classical object-oriented approach with virtual methods. If you want to keep the data fixed and extend with new operations, then patterns are a much better fit. There's actually a design pattern—not to be confused with pattern matching—in object-oriented programming called the visitor pattern, which can represent some of the things we do with pattern matching in an object-oriented way, based on virtual method dispatch. But in practical use the visitor pattern is very bulky. You can't do many of the things that are very easy with pattern matching. You end up with very heavy visitors. And it also turns out that with modern VM technology it's way more innefficient than pattern matching. For both of these reasons, I think there's a definite role for pattern matching.

Martin Odersky is coauthor of Programming in Scala: http://www.artima.com/shop/programming_in_scala

The Scala programming language website is at:
http://www.scala-lang.org

For a good overview of what Scala programming is all about, watch The Feel of Scala video on Parleys.com:
http://tinyurl.com/dcfm4c

How Object-Oriented Programming Started, by Ole-Johan Dahl and Kristen Nygaard, provides a nice history of Simula-67 and the birth of object-oriented programming:
http://heim.ifi.uio.no/~kristen/FORSKNINGSDOK_MAPPE/F_OO_start.html

Smalltalk: Getting The Message, by Alan Lovejoy, gives a comprehensive introduction to Smalltalk:
http://www.smalltalk-resources.com/Smalltalk-Getting-the-Message.html

In Defense of Pattern Matching, by Martin Odersky, gives more insight into Odersky's reason for including pattern matching in Scala:
http://www.artima.com/weblogs/viewpost.jsp?thread=166742

Talk back!

Have an opinion? Readers have already posted 35 comments about this article. Why not add yours?

About the authors

Frank Sommers is an editor with Artima Developer. He is also founder and president of Autospaces, Inc., a company providing collaboration and workflow tools in the financial services industry.

Bill Venners is president of Artima, Inc., publisher of Artima Developer (www.artima.com). He is author of the book, Inside the Java Virtual Machine, a programmer-oriented survey of the Java platform's architecture and internals. His popular columns in JavaWorld magazine covered Java internals, object-oriented design, and Jini. Active in the Jini Community since its inception, Bill led the Jini Community's ServiceUI project, whose ServiceUI API became the de facto standard way to associate user interfaces to Jini services. Bill is also the lead developer and designer of ScalaTest, an open source testing tool for Scala and Java developers, and coauthor with Martin Odersky and Lex Spoon of the book, Programming in Scala.