In this final installment of a four part interview, Scala's designer Martin Odersky talks with Bill Venners and Frank Sommers about the mechanics and purpose of pattern matching in Scala.

http://www.artima.com/scalazine/articles/pattern_matching.html

What is your opinion of pattern matching?

It was this second direction of extensibility that sent me looking for a higher level language than java a while back. I was suffering the pain of repeated instanceof's and casts that you need to graft behaviour onto objects from the outside.

The visitor pattern is one way to wrap this ugliness up but it is tedious to encode everywhere it is needed.

I thought multimethod dispatch was the solution that fitted best with OO concepts. I found this implemented in the Nice language. The python community seems to have flirted with this idea too.

I realised that pattern matching was another solution when I saw it in scala. I asked Martin why he didn't go down the multimethod route. From memory I think he was concerned that multimethods lead to open classes that would ultimately undo OO encapsulation. (Sorry if I misquote you Martin!)

Now that I understand scala a little better I can see how pattern matching fits in with the rest of the language in a number of ways. And it keeps the type system more or less out of sight when dealing with objects from heterogeneous collection or other source.

In my pet project, PEC _ Pattern Enforcing Compiler:

https://pec.dev.java.net/nonav/compile/index.html

Which is an extended Java compiler that allows you to specify design patterns and have the compiler enforce them.

One of the patterns I have written is multiple dispatch. Using multiple dispatch you can add operations to data, the expression problem, but you don't need to use pattern matching. For example the converting of a List to a String example given in the text would be two overloaded toText methods, a default method that returned "was an empty list" and another method that returned "head was " + l.head() + ", tail was " + l.tail().

Pattern matching isn't that far removed from a switch statement on an instanceof test. With multiple dispatch you simply call an overloaded method, which to my eyes is a nicer solution.

> Pattern matching isn't that far removed from a switch
> statement on an instanceof test. With multiple dispatch
> you simply call an overloaded method, which to my eyes is
> a nicer solution.

I actually have been swayed the other way in that I think overloading should not be allowed at all. Multiple-dispatch and operator-overloading in general has a stability problem when it comes to long-term maintenance. The problem is that when you add overloaded methods to a class, it's not obvious what other calls may be affected by that addition. This is especially true with multiple dispatch.

Pattern matching solves a superset of the issues addressed by multi-methods and does so in a way that is explicit. The developer controls the dispatching and the intention is apparent. Overloading depends on rules of the compiler and/or runtime that are implicit and cannot be changed.

> I actually have been swayed the other way in that I think
> overloading should not be allowed at all.

How apropos.

http://guidewiredevelopment.wordpress.com/2009/05/22/i-am-hate-method-overloading-and-so-can-you/

Cheers,
Carson

I haven't have an instability happen to me by adding a method, so I assume the occurrence of such errors is rare. Do you have examples? How often etc.?

On the other hand I have often seen problems with code like this:

class Point {
private final double x, y;
...
public boolean equals( final Object other ) {
if ( !(other instanceof Point) ) { return false; } // Oops, derived classes!
final Point that = (Point) other;
return x == that.x && y == that.y;
}
}

class Point3D extends Point {
private final double z;
...
public boolean equals( final Object other ) {
if ( !(other instanceof Point3D) ) { return false; } // Oops, derived classes!
final Point3D that = (Point3D) other;
return x == that.x && y == that.y && z == that.z;
}
}

The problem is with an instanceof test that will match derived classes as well as the class itself, which in this case is not what is required (that is why Point3dD has an equals method). This is a difficult to deal with problem, e.g. Point3D could be added by a third party who has no ability to modify Point.

When I emailed Josh Bloch about this problem with instanceof, a similar example is in Effective Java, he replied that this problem was raised by many people with him (I think from memory that he said it was by far the most common comment on Effective Java). Therefore there is considerable evidence to suggest that instanceof tests cause problems in real code.

All these problems go away with multiple dispatch and therefore I find this a very effective solution and at least in my own code have not experianced any problems. By the way multiple dispatch isn't that hard to do. I have written up my approach and it should take long, under a week, to get that fully implemented in a language (it took me less than a month from scratch including investigating half a dozen alternative implementation strategies).

> The problem is with an instanceof test that will match
> derived classes as well as the class itself, which in this
> case is not what is required (that is why Point3dD has an
> equals method). This is a difficult to deal with problem,
> e.g. Point3D could be added by a third party who has no
> ability to modify Point.

I don't see how multiple solves anything here. If you add a equals(Point3D) to Point3D, it doesn't change the way that Point.equals(Object) works. It's not symmetric.

The instability comes when you have something like this:

interface A {
    boolean foo(Object o);
}

And then do something like this:

public class B implements A {
    public boolean foo(Object o) {
        // ...
    }
 
    public boolean foo(String s) {
        // ...
    }
}

No big deal right? But what if the foo in Bar is implemented as part of a different contract? But more of a concern is this:

interface A {
    boolean foo(Object o);
}
 
public abstract class B implements A {
}
 
public abstract class C extends B {
    public boolean foo(Object o) {
        // ...
    }
}

Then later, we decide to add foo(String) to B. Now, out of nowhere B is intercepting Strings passed to foo.

> I don't see how multiple solves anything here. If you add
> a equals(Point3D) to Point3D, it doesn't change the way
> that Point.equals(Object) works. It's not symmetric.

Sorry, what I mean here is that it's not transitive.

With symmetric multiple dispatch you have:

static boolean equals( Object lhs, Object rhs ) { return lhs == rhs; } // default for Objects and also nulls
static boolean equals( Point lhs, Point rhs ) { return lhs.x == rhs.x && lhs.y == rhs.y; }

Now when you add Point3D you add:

static boolean equals( Point3D lhs, Point3D rhs ) { return lhs.x == rhs.x && lhs.y == rhs.y && lhs.z == rhs.z; }

and it works as expected.

If you want to compare a Point to a Point3D then you have to add both:

static boolean equals( Point lhs, Point3D rhs ) { return lhs.x == rhs.x && lhs.y == rhs.y && 0 == rhs.z; }
static boolean equals( Point3D lhs, Point rhs ) { return lhs.x == rhs.x && lhs.y == rhs.y && lhs.z == 0; }

If you add just one of these it is flagged as an error.

[snip]
> The instability comes when you have something like this:
>

interface A {
>     boolean foo(Object o);
> }

> And then do something like this:
>

public class B implements A {
>     public boolean foo(Object o) {
>         // ...
>     }
> 
>     public boolean foo(String s) {
>         // ...
>     }
> }

[snip]

I am not saying that something like this can't happen in Java - I am just saying I have never had it happen to me and I am not aware of this being a problem - unlike instanceof which is a well known problem.

> [snip]
> and it works as expected.

The implementation you give works but only because you've limited the usefulness of it. Only points with z of zero can ever be equal to a 2D point which is unlikely to be what is desired.

That's beside the point, however. There's nothing about this that can't be done using explicit instanceofs. Multimethods (as I understand them) are really just implicit instanceof. I'm not really understanding your argument here.

[snip]
> That's beside the point, however. There's nothing about
> this that can't be done using explicit instanceofs.
> Multimethods (as I understand them) are really just
> t implicit instanceof. I'm not really understanding your
> argument here.

The difference is two fold:

1. Point3D can be written and compiled *completely* separately from Point, no access to Point's source is needed. The writer of Point3D simply writes the three equals methods and puts them in Point3D. A call point.equals(point3D) then just works without even recompiling Point (syntax shown is the syntax I use - other syntaxes for multi-methods have been proposed).

2. Yes the multiple dispatch is implemented as a series of instanceof tests. Crucially though this is not a fixed set of tests and if a new class containing new relevant methods, e.g. Point3D, is loaded then the tests are rewritten automatically at load-time (i.e. the instanceof tests are not generated at compile-time but at load-time and the tests are rewritten, if needed, when a new class loads).

> Point3D can be written and compiled *completely*
> separately from Point, no access to Point's source is
> needed. The writer of Point3D simply writes the three
> equals methods and puts them in Point3D. A call
> point.equals(point3D) then just works without even
> recompiling Point (syntax shown is the syntax I use -
> other syntaxes for multi-methods have been proposed).

I guess I don't understand. How does point.equals(point3d) resolve to a method that is not defined on Point?

> I am not saying that something like this can't happen in
> Java - I am just saying I have never had it happen to me
> and I am not aware of this being a problem - unlike
> instanceof which is a well known problem.

It can't happen in Java because Java doesn't support multiple dispatch. There is a related issue with overloading where adding a method causes unexpected changes in behaviors when the calling class is recompiled. But mostly the issues have to do with people expecting overloading to be double-dispatch. And that's why I had thought in the past that multi-methods would be better. But my experience with pattern matching in Scala has shown me that it solves that problem and more without the magic.

[snip]
> But my experience with pattern matching in Scala has
> s shown me that it solves that problem and more without
> the magic.

If you have:

trait Points { def test( p : Points ) : Boolean }
 
case class Point( x : Int, y : Int ) extends Points {
  override def test( p : Points ) = p match {
    case Point( px, py ) => x == px && y == py
    case _ => false
  }
}

And you can't change Point (e.g. third party library) then you have two options for Point3D, either:

case class Point3D( x : Int, y : Int, z : Int ) extends Points {
  override def test( p : Points ) = p match {
    case Point( px, py ) => x == px && y == py && z == 0
    case Point3D( px, py, pz ) => x == px && y == py && z == pz
    case _ => false
  }
}

or

case class Point3D2( override val x : Int, override val y : Int, z : Int ) extends Point( x, y ) {
  override def test( p : Points ) = p match {
    case Point3D2( px, py, pz ) => x == px && y == py && z == pz
    case _ => super.test( p )
  }
}

(For the second case there are a number of options for test - but none of them work).

The following tests should all print true:

    val p = new Point( 2, 1 )
    val p3D = new Point3D( 2, 1, 0 )
    val p23D = new Point3D( 2, 1, 2 )
    println( "Option 1 - Point3D extends Points (note s)" )
    println( p.test( p ) )
    println( p.test( p3D ) )
    println( p3D.test( p ) )
    println( p3D.test( p3D ) )
    println( !p.test( p23D ) )
    println( !p3D.test( p23D ) )
    val p3D2 = new Point3D2( 2, 1, 0 )
    val p23D2 = new Point3D2( 2, 1, 2 )
    println( "Option 2 - Point3D2 extends Point (no s)" )
    println( p.test( p ) )
    println( p.test( p3D2 ) )
    println( p3D2.test( p ) )
    println( p3D2.test( p3D2 ) )
    println( !p.test( p23D2 ) )
    println( !p3D2.test( p23D2 ) )

Unfortunately the output is:

Option 1 - Point3D extends Points (note s)
true
false
true
true
true
true
Option 2 - Point3D2 extends Point (no s)
true
true
true
true
false
true

With multiple dispatch you can get the correct answer by simply writing 3 methods.