The Artima Developer Community
Sponsored Link

Articles Forum
The Point of Pattern Matching in Scala

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

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 35 replies on 3 pages [ 1 2 3 | » ]
Bill Venners

Posts: 2244
Nickname: bv
Registered: Jan, 2002

The Point of Pattern Matching in Scala Posted: May 25, 2009 1:00 AM
Reply to this message Reply
Advertisement
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 6:57 PM
Reply to this message Reply
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 26, 2009 1:27 AM
Reply to this message Reply
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 10:09 AM
Reply to this message Reply
> 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 2:48 PM
Reply to this message Reply
> 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 11:18 PM
Reply to this message Reply
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 11:46 PM
Reply to this message Reply
> 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 11:06 AM
Reply to this message Reply
> 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 5:13 PM
Reply to this message Reply
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 5:23 PM
Reply to this message Reply
[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 6:02 PM
Reply to this message Reply
> [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 8:46 PM
Reply to this message Reply
[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 9:34 PM
Reply to this message Reply
> 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 9:52 PM
Reply to this message Reply
> 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 11:22 PM
Reply to this message Reply
[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.

Flat View: This topic has 35 replies on 3 pages [ 1  2  3 | » ]
Topic: From JavaOne 2009: Breaking Through JVM Memory Limits Previous Topic   Next Topic Topic: The Goals of Scala's Design


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us