Articles Forum - The Point of Pattern Matching in Scala

Articles |
News |
Weblogs |
Books |
Forums

Artima Forums | Articles | Weblogs | Java Answers | News

Sponsored Link •

Articles Forum
The Point of Pattern Matching in Scala

35 replies on 3 pages. Most recent reply: Jun 2, 2009 8:25 PM by Howard Lovatt

Welcome Guest
Sign In

Back to Topic List

Reply to this Topic

Search Forum

Threaded View


Previous Topic		Next Topic

Flat View: This topic has 35 replies on 3 pages [ 1 2 3 | » ]

Bill Venners

Posts: 2284
Nickname: bv
Registered: Jan, 2002

The Point of Pattern Matching in Scala

Posted: May 24, 2009 10:00 PM

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?

Arnold deVos

Posts: 18
Nickname: arnoldd
Registered: Dec, 2002

Re: The Point of Pattern Matching in Scala

Posted: May 25, 2009 3:57 PM

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.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: The Point of Pattern Matching in Scala

Posted: May 25, 2009 10:27 PM

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.

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: The Point of Pattern Matching in Scala

Posted: May 26, 2009 7:09 AM

> 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.

Carson Gross

Posts: 153
Nickname: cgross
Registered: Oct, 2006

Re: The Point of Pattern Matching in Scala

Posted: May 26, 2009 11:48 AM

> 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

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: The Point of Pattern Matching in Scala

Posted: May 26, 2009 8:18 PM

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).

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: The Point of Pattern Matching in Scala

Posted: May 26, 2009 8:46 PM

> 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.

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: The Point of Pattern Matching in Scala

Posted: May 27, 2009 8:06 AM

> 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.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: The Point of Pattern Matching in Scala

Posted: May 27, 2009 2:13 PM

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.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: The Point of Pattern Matching in Scala

Posted: May 27, 2009 2:23 PM

[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.

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: The Point of Pattern Matching in Scala

Posted: May 27, 2009 3:02 PM

> [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.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: The Point of Pattern Matching in Scala

Posted: May 27, 2009 5:46 PM

[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).

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: The Point of Pattern Matching in Scala

Posted: May 27, 2009 6:34 PM

> 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?

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: The Point of Pattern Matching in Scala

Posted: May 27, 2009 6:52 PM

> 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.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: The Point of Pattern Matching in Scala

Posted: May 27, 2009 8:22 PM

[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
  }
}

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.

Flat View: This topic has 35 replies on 3 pages [ 1 2 3 | » ]

Previous Topic

Next Topic