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 | » ]
Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: The Point of Pattern Matching in Scala Posted: May 27, 2009 11:39 PM
Reply to this message Reply
Advertisement
[snip]
> I guess I don't understand. How does
> point.equals(point3d) resolve to a method that is not
> defined on Point?

The short answer is that equals uses a dispatcher object to select the correct method to call. This dispatcher object contains a method, dispatch, that does the instanceof tests and calls the appropriate static method. The dispatcher object is replaced each time a new set of methods are loaded and the new dispatcher has the new set of instanceof tests in it. Method equals, which is compiler generated, looks something like:
public static $Equals$Dispatcher$ $equals$Dispatcher$; // in abstract base class
 
public final boolean equals( final Object other ) {
  return $equals$Dispatcher$.dispatch( other );
}

The long answer is given here:

http://pec.dev.java.net/nonav/compile/javadoc/pec/compile/multipledispatch/package-summary.html#package_description

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: The Point of Pattern Matching in Scala Posted: May 28, 2009 11:56 AM
Reply to this message Reply
> [snip]
> > I guess I don't understand. How does
> > point.equals(point3d) resolve to a method that is not
> > defined on Point?
>
> The short answer is that equals uses a dispatcher object
> to select the correct method to call.

If I understand correctly, the point.equals() is effectively overridden by a method that is not part of it's class. If that right, you aren't just adding multi-methods, you are changing the semantics of polymorphism in Java. Again, assuming this is correct, this is IMO a very dangerous and tricky thing to do.

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: The Point of Pattern Matching in Scala Posted: May 28, 2009 12:14 PM
Reply to this message Reply
> With multiple dispatch you can get the correct answer by
> simply writing 3 methods.

Only if you constrain your correct answer to something that is useless. If I want to compare a 2D point to a 3D point, there are a number of ways I might want that to work and none of are that only 3D points on the z == 0 plane can be considered equal to a 2D point. You might as well just say that 2D points and 3D points can't never be equal as it solves the same problems.

The real problem is that equals and polymorphism don't mix. There real solution to this issue is to have a third party do the comparison. In fact, this same problem that the Comparator interface in Java resolves for Comparables.

You definitely have a clever solution here but I don't think it's really going in the right direction. Not for my needs, anyway.

Mark Thornton

Posts: 275
Nickname: mthornton
Registered: Oct, 2005

Re: The Point of Pattern Matching in Scala Posted: May 28, 2009 2:26 PM
Reply to this message Reply
> The real problem is that equals and polymorphism don't
> mix.
The solution outlined in "Programming in Scala", chapter 28 works well.

Bill Venners

Posts: 2242
Nickname: bv
Registered: Jan, 2002

Re: The Point of Pattern Matching in Scala Posted: May 28, 2009 5:19 PM
Reply to this message Reply
> > The real problem is that equals and polymorphism don't
> > mix.
> The solution outlined in "Programming in Scala", chapter
> 28 works well.
>
Yes, it does. Stay tuned as next week I'm planning on publishing an article describing the technique, with the code translated to Java.

However, that's about equality, not about multi-methods versus pattern matching.

Arnold deVos

Posts: 18
Nickname: arnoldd
Registered: Dec, 2002

Re: The Point of Pattern Matching in Scala Posted: May 28, 2009 8:44 PM
Reply to this message Reply
> about multi-methods versus pattern matching.

Let me have a crack at this comparison:

A scala match statement is the equivalent of a family of overriding, open, multimethods. (Where an open multimethod is one declared independently of the argument types dispatched.)

Some comparison points...

1. Introducing a match statement is lighter weight than defining a family of multimethods.

2. The alternatives are all gathered together in a match statement. I can't extend a match "from the outside". But I can add another override to a family of multimethods. (Good or bad?)

3. The dispatch rules for match statements are simpler. The dispatch rules for a family of multmethods resemble overload resolution (albeit at runtime).

4. An open multimethod is written in terms of the public features of its arguments while simple pattern matching systems need access to internal state.

In scala, we have the innovation of extractors which restore encapsulation. An extractor can be separate from the matched type in which case it only has access to public features.

5. Patterns can be nested and may involve values as well as types. Some multimethod systems are limited to dispatching on types.


It is interesting to contemplate extending an existing family of multimethods with new overrides. ie my point (2). Most of this thread seems to be discussing whether this ability is a can of worms in practice.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: The Point of Pattern Matching in Scala Posted: May 28, 2009 11:42 PM
Reply to this message Reply
> > > The real problem is that equals and polymorphism
> don't
> > > mix.
> > The solution outlined in "Programming in Scala",
> chapter
> > 28 works well.

Chapter 28 of the Scala Book is great, particularly since I am a fan of multiple dispatch and the suggested solution is to hand code multiple dispatch :). Quick recap of chapter 28 the recommended solution is:

class Point(val x: Int, val y: Int) { 
  override def hashCode = 41 * (41 + x) + y 
  override def equals(other: Any) = other match { 
    case that: Point => (that canEqual this) && (this.x == that.x) && (this.y == that.y) 
    case _ => false 
  } 
  def canEqual(other: Any) = other.isInstanceOf[Point] 
} 
 
class ColoredPoint(x: Int, y: Int, val color: Color.Value) extends Point(x, y) { 
  override def hashCode = 41 * super.hashCode + color.hashCode 
  override def equals(other: Any) = other match { 
    case that: ColoredPoint => (that canEqual this) && super.equals(that) && this.color == that.color 
    case _ => false 
  } 
  override def canEqual(other: Any) = other.isInstanceOf[ColoredPoint] 
} 


The crucial bit of the solution is the call:

that canEqual this


which you note is *not*:

this canEqual that


IE it is a second dispatch. The solution works and I thought it was widely known, but maybe it isn't widely know since people on this forum have bought it up in the context suggesting that it is novel (there may be some novelty in that canEqual only tests types, but essentially the method is the same as double dispatch or the Visitor pattern). There are a number of limitations:

1. It quickly gets out of hand for multiple arguments, you need can1, can2, etc which rotate the arguments.

2. It can only do the stricter comparison (page 578 says "Making the equals relation more general seems to lead to a dead end").

3. The code is verbose and ugly.

Lets pretend that Scala got multiple dispatch and a method declared with multidef defined a multiple dispatch method, then the above example would become:

class Point(val x: Int, val y: Int) { 
  override def hashCode = 41 * (41 + x) + y 
  override multidef equals(this, that: Any) = false
  override multidef equals(this, that: Point) = (x == that.x) && (y == that.y) 
} 
 
class ColoredPoint(x: Int, y: Int, val color: Color.Value) extends Point(x, y) { 
  override def hashCode = 41 * super.hashCode + color.hashCode 
  override multidef equals(this, that: ColordePoint) = (x == that.x) && (y == that.y) && (this.color == that.color)
} 


Which I think is a lot clearer and address points 1 and 3 that I raised above. With multiple dispatch you can also do a more general comparison (point 2 above), e.g. suppose you want Point to be a Black ColoredPoint, then you can:

class ColoredPoint(x: Int, y: Int, val color: Color.Value) extends Point(x, y) { 
  override def hashCode = 41 * super.hashCode + color.hashCode 
  override multidef equals(this, that: ColoredPoint) = (x == that.x) && (y == that.y) && (this.color == that.color)
  override multidef equals(this, that: Point) = (x == that.x) && (y == that.y) && (this.color == Black)
  override multidef equals(that: Point, this) = (x == that.x) && (y == that.y) && (this.color == Black)
} 


So in summary, the suggested solution in chapter 28 is a hand coded form of limited multiple dispatch. Yes it does overcome some of the limitations of pattern matching, but not all (unlike true multiple dispatch) and it is extra tricky code to write.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: The Point of Pattern Matching in Scala Posted: May 29, 2009 12:47 AM
Reply to this message Reply
[snip]
> 1. Introducing a match statement is lighter weight than
> defining a family of multimethods.

Sure for an instanceof test types alone, but when you then add things like sealed classes and matches on values there isn't much in it.

> 2. The alternatives are all gathered together in a match
> statement. I can't extend a match "from the outside". But
> I can add another override to a family of multimethods.
> (Good or bad?)

That isn't true, see Point example in chapter 28 of the Scalabook.

> 3. The dispatch rules for match statements are simpler.
> The dispatch rules for a family of multmethods resemble
> e overload resolution (albeit at runtime).

Yes, but you do need to generate errors to detect unreachable cases - which is the same procedure as you do with multiple dispatch (so not much in it)

> 4. An open multimethod is written in terms of the public
> features of its arguments while simple pattern matching
> systems need access to internal state.

No, if the multimethod is inside a class then it has access to private data just like any other class member does.

> In scala, we have the innovation of extractors which
> restore encapsulation. An extractor can be separate from
> the matched type in which case it only has access to
> public features.

A multimethod can be outside a class also and then it only has access to public members

> 5. Patterns can be nested and may involve values as well
> as types. Some multimethod systems are limited to
> dispatching on types.

No reason why any method, multiple or single dispatch, can't match on values. EG in Haskell and many functional languages you can write:

def factorial(1) = 1
def factorial(n) = n * factorial(n - 1)

> It is interesting to contemplate extending an existing
> family of multimethods with new overrides. ie my point
> t (2). Most of this thread seems to be discussing whether
> this ability is a can of worms in practice.

Not in my experience, in fact quite the opposite. Take chapter 28 of the Scalabook, it is a long chapter discussing the pitfalls of pattern matching for a well known method, equals. I would suggest that using mutimethods would be much simpler (see previous post).

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: The Point of Pattern Matching in Scala Posted: May 29, 2009 12:59 AM
Reply to this message Reply
Oops typo

>
> class ColoredPoint(x: Int, y: Int, val color: Color.Value) extends Point(x, y) { 
>   override def hashCode = 41 * super.hashCode + color.hashCode 
>   override multidef equals(this, that: ColordePoint) = (x == that.x) && (y == that.y) && (this.color == that.color)
> } 
> 


Should be

class ColoredPoint(x: Int, y: Int, val color: Color.Value) extends Point(x, y) { 
  override def hashCode = 41 * super.hashCode + color.hashCode 
  override multidef equals(this, that: ColordePoint) = (x == that.x) && (y == that.y) && (this.color == that.color)
  override multidef equals(this, that: Point) = false
  override multidef equals(that: Point, this) = false
} 

Arnold deVos

Posts: 18
Nickname: arnoldd
Registered: Dec, 2002

Re: The Point of Pattern Matching in Scala Posted: May 29, 2009 1:44 AM
Reply to this message Reply
> > 2. The alternatives are all gathered together in a match
> > statement. I can't extend a match "from the outside".But
> > I can add another override to a family of multimethods.
> > (Good or bad?)
>
> That isn't true, see Point example in chapter 28 of the
> Scalabook.
>

Actually, I was just referring to the fact that no addition cases can be added to an existing match statement. (Without directly modifying it of course.)

The examples in chapter 28 don't change which pattern is matched by adding new code elsewhere.

But with open multimethods a new override can be written after-the-fact, in a different compilation unit, in such a way that it will affect the dispatch.

Without buying into the debate on whether this is good or bad, I think it is a fundamental difference.

Mark Thornton

Posts: 275
Nickname: mthornton
Registered: Oct, 2005

Re: The Point of Pattern Matching in Scala Posted: May 29, 2009 3:58 AM
Reply to this message Reply
I tried to extend the Rational example from "Programming in Scala" in several respects. In the book it shows how to get 4 * 1/3 and 1/3 * 4 to produce the expected result (4/3). OK, but I also want 4.0 * 1/3 and 1/3 * 4.0 to produce 1.3333..., and here I failed. As I understand it, multimethods should be able to get the right answer for cases like this, but I don't see pattern matching helping.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: The Point of Pattern Matching in Scala Posted: May 29, 2009 4:37 PM
Reply to this message Reply
> > > 2. The alternatives are all gathered together in a
> match
> > > statement. I can't extend a match "from the
> outside".But
> > > I can add another override to a family of
> multimethods.
> > > (Good or bad?)
> >
> > That isn't true, see Point example in chapter 28 of the
> > Scalabook.
> >
>
> Actually, I was just referring to the fact that no
> addition cases can be added to an existing match
> statement. (Without directly modifying it of course.)
>
> The examples in chapter 28 don't change which pattern is
> matched by adding new code elsewhere.
>
> But with open multimethods a new override can be written
> after-the-fact, in a different compilation unit, in such a
> way that it will affect the dispatch.
>
> Without buying into the debate on whether this is good or
> bad, I think it is a fundamental difference.

Sorry I misunderstood your point - yes what you are saying is correct

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: The Point of Pattern Matching in Scala Posted: May 29, 2009 4:41 PM
Reply to this message Reply
> I tried to extend the Rational example from "Programming
> in Scala" in several respects. In the book it shows how to
> get 4 * 1/3 and 1/3 * 4 to produce the expected result
> (4/3). OK, but I also want 4.0 * 1/3 and 1/3 * 4.0 to
> produce 1.3333..., and here I failed. As I understand it,
> multimethods should be able to get the right answer for
> cases like this, but I don't see pattern matching helping.

Yes with multimethods you could do this. (You could also hand code multiple dispatch or use the Visitor pattern.)

Bill Venners

Posts: 2242
Nickname: bv
Registered: Jan, 2002

Re: The Point of Pattern Matching in Scala Posted: May 29, 2009 4:57 PM
Reply to this message Reply
Hi Mark,

> I tried to extend the Rational example from "Programming
> in Scala" in several respects. In the book it shows how to
> get 4 * 1/3 and 1/3 * 4 to produce the expected result
> (4/3). OK, but I also want 4.0 * 1/3 and 1/3 * 4.0 to
> produce 1.3333..., and here I failed. As I understand it,
> multimethods should be able to get the right answer for
> cases like this, but I don't see pattern matching helping.
>
Although any floating point number you can express on the JVM, float or double, could be represented by a rational number (because every floating point number has a finite number of digits), that doesn't mean you could represent them in a Rational as shown in the book, because in the book the numerator and denominators are Ints. Fortunately, you are wanting to go in the other direction. Given a floating point number, multiple it by a Rational number and get another floating point number. You would like to do this either way:


4.0 * (new Rational(1, 3))


and


(new Rational(1, 3)) * 4.0


If you can change class Rational, then you could at *, +, -, /, etc. methods that take Double, and that would give you the latter one. For the former, or the latter if you can't change Rational, you'd need to create an implicit conversion from Rational to Double. Here's what it looks like in the Scala interpreter. Before this code I just copied the final version of Rational shown in chapter 6 (in listing 6.5) and pasted it into the interpreter. Then:


scala> implicit def convert(rat: Rational) = rat.numer.toDouble / rat.denom.toDouble
convert: (Rational)Double

scala> val oneThird = new Rational(1, 3)
oneThird: Rational = 1/3

scala> 4.0 * oneThird
res0: Double = 1.3333333333333333

scala> oneThird * 4.0
res1: Double = 1.3333333333333333

Mark Thornton

Posts: 275
Nickname: mthornton
Registered: Oct, 2005

Re: The Point of Pattern Matching in Scala Posted: May 29, 2009 5:16 PM
Reply to this message Reply
>

> scala> implicit def convert(rat: Rational) =
> rat.numer.toDouble / rat.denom.toDouble
> convert: (Rational)Double
>


Unfortunately then the Int case no longer produces the desired result:

4*(new Rational(1/3))

1.3333...

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