The Artima Developer Community
Sponsored Link

Weblogs Forum
Pattern Matching Wrap-Up

12 replies on 1 page. Most recent reply: Jul 31, 2006 2:09 AM 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 12 replies on 1 page
Martin Odersky

Posts: 84
Nickname: modersky
Registered: Sep, 2003

Pattern Matching Wrap-Up (View in Weblogs)
Posted: Jul 18, 2006 10:41 AM
Reply to this message Reply
Summary
A follow-up on my previous blog on pattern matching, which summarizes the discussions this entailed.
Advertisement

The previous blog In Defense of Pattern Matching has sparked many interesting discussions. I will try to give a quick wrap-up here. Besides some technical questions, most comments fell into two categories: They were wishing for more flexible and abstract schemes how objects can be matched into patterns, or they were proposing a classical object-oriented decomposition with virtual method calls as a better alternative to pattern matching.

More flexible patterns This was very constructive. It's great motivation for us to continue exploring ways to make pattern matching more flexible. In fact there had been a discussion about this on the Scala mailing list before. One thing to note here is that current pattern matching already provides quite a bit of flexibility (this should not imply that we should stop trying to generalize it further). Take, for instance, the prototypical example of points:

case class Point(x: double, y: double)

One might think this would lock us into a specific implementation of Points with cartesian x/y co-ordinates. But in fact, we could create a new sub-class of points with polar coordinates:

class PolarPoint(radius: double, angle: double) extends Point(
  Math.sin(angle) * r, Math.cos(angle) * r )

Even though these points now use internally a polar representation, their pattern matching would be cartesian. So we see that values returned by pattern matching need not correspond to an object's internal data representation. In that sense, encapsulation is preserved.

Multi-methods are a flexible alternative to pattern matching. They are not present in Scala. I think multi-methods would be great if they could replace Java's static overloading, which always seemed a bit ad-hoc to me. The question is whether one can do this without breaking compatibility with Java in too serious ways. Maybe the Nice folks have some experience to offer here? I have noted that some multi-method designs, such as MultiJava, have both static overloading and multi-methods; however I fear this would be too confusing for users.

Philosophy Another class of arguments criticized pattern matching on more fundamental grounds. Basically it goes as follows:

"Sure, pattern matching is a more convenient alternative to Java's instanceof and type casts. But all of these techniques are inferior to a proper object-oriented decomposition, where you use virtual methods to differentiate behavior in subclasses."

I believe this argument is valid in many cases, but not in all. There are situations where an OO decomposition is not easily doable. An example that's right under our noses is the try-catch statement found in Java and many other languages. In Scala it is written like this:

try {
  ...
} catch {
  case ex: IOException => "handle io error"
  case ex: ClassCastException => "handle class cast errors"
  case ex: _ => "generic recovery"
}

Here, every catch clause does a pattern match on the thrown exception (using a so-called "typed pattern"). In the equivalent Java code this is less obvious but in essence Java catch clauses contain pattern matches as well. What would the strict OO alternative be? To choose the correct handler code we'd have to call a virtual method in the thrown exception. The problem is that the exception itself does not not "know" how the handler should react to it; this clearly depends on the context. It is possible to program around this using the visitor pattern, but the result is clumsy and not easily extensible to new kinds of exceptions. That's probably why most languages have opted for exception handling in the pattern-matching style.

There are arguably many more cases where a decomposition from the outside is preferable to a decomposition from the inside using virtual methods. Cases to watch out for are:

  1. when a computation rule involves several objects,
  2. when a computation cannot usefully be defined as a member of the class on which we want to differentiate.

An example of the first kind is the following rule from my term simplification example:

x * l + x * r  ==  x * (l + r)

The corresponding simplification rule in Scala is:

case Add(Mul(x1, l), Mul(x2, r)) if (x1 == x2) => Mul(x1, Add(l, r))

An example of the second kind are exception handlers, discussed above.

In summary, I do believe there is a role for pattern matching in object-oriented languages. But with the added power comes the requirement that programmers now have to choose a style of decomposition. This can sometimes be difficult.


James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: Pattern Matching Wrap-Up Posted: Jul 18, 2006 11:10 AM
Reply to this message Reply
> I think multi-methods would be
> great if they
> could replace Java's static overloading, which always
> seemed a bit
> ad-hoc to me. The question is whether one can do this
> without breaking
> compatibility with Java in too serious ways.

Jython uses multi-dispatch when calling overloaded Java methods which is kind of interesting since neither Python (no overloading) nor Java has this feature.

My experience is that this works pretty well but the problem may be different in Scala.

Martin Odersky

Posts: 84
Nickname: modersky
Registered: Sep, 2003

Re: Pattern Matching Wrap-Up Posted: Jul 18, 2006 11:21 AM
Reply to this message Reply
> Jython uses multi-dispatch when calling overloaded Java
> methods which is kind of interesting since neither Python
> (no overloading) nor Java has this feature.
>
> My experience is that this works pretty well but the
> problem may be different in Scala.

One good test is whether one can still inherit and
use Swing classes. I found that these use static overloading in very interesting ways ;-) Does Jython use Swing as its GUI?
And can you write Swing components in it?

-- Martin

John Cowan

Posts: 36
Nickname: johnwcowan
Registered: Jul, 2006

Re: Pattern Matching Wrap-Up Posted: Jul 18, 2006 12:13 PM
Reply to this message Reply
Anyone who's going to call Java methods from a dynamically typed language using reflection must in essence use multiple dispatch.

You can't just call a method in Java based on its class and its name, thanks to static overloading. In order to get the correct java.lang.reflect.Method object to invoke, you need to specify the static types of the arguments. If (as is typical in a dynamically typed language) all you have is the arguments themselves, then the best you can do is use their dynamic types.

This is a situation that calls for Erik Meijer's principle "static when possible, dynamic when necessary".

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: Pattern Matching Wrap-Up Posted: Jul 18, 2006 12:15 PM
Reply to this message Reply
> > Jython uses multi-dispatch when calling overloaded Java
> > methods which is kind of interesting since neither
> Python
> > (no overloading) nor Java has this feature.
> >
> > My experience is that this works pretty well but the
> > problem may be different in Scala.
>
> One good test is whether one can still inherit and
> use Swing classes. I found that these use static
> overloading in very interesting ways ;-) Does Jython use
> Swing as its GUI?
> And can you write Swing components in it?

Sorry I haven't tried this and wasn't able to find any info on whether it's difficult or not. There's a lost of info on using Swing but not about extending swing classes.

One of the things that is different about extending Java classes in Jython vs. Scala is that you can't overload methods so overriding an overloaded method means overridding all methods of that name.

Can you give an example of one of the "interesting ways" so that I might better understand the problems you are facing?

thanks.

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: Pattern Matching Wrap-Up Posted: Jul 18, 2006 12:23 PM
Reply to this message Reply
> I have noted that some
> multi-method designs, such as MultiJava, have both
> static overloading
> and multi-methods; however I fear this would be too
> confusing for
> users.

I just wanted to second that I don't think this is a good idea. It's realy completely uncesssary because staticly-bound overloading is useless in terms of system design.

void foo(Integer i);
void foo(String s);

and functionally equivalent to:

void fooInteger(Integer i);
vood fooString(String s);

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Pattern Matching Wrap-Up Posted: Jul 18, 2006 7:36 PM
Reply to this message Reply
I think multi-methods would be a great addition to any single-dispatch language, not just Scala. I have added them to Java:

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

You can also use multi-methods for exception handelling:

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

The implementation details of my methods are different than those used in both Nice and MultiJava and I think my implementation has some advantages. The implementation I used is described:

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

Other considerations with multiple dispatch are: execution speed, its interaction with single dispatch, and where in a class heirachy multiple as opposed to single dispatch is introduced, see:

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

This implementation is constrasted with Nice and MultiJava:

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

As suggested in the original post there are some rough edges with Java around primitives, Generics, and inner classes, see:

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

For generics and the section immediately above this Generics section for interaction with primitives and immediately below for inner classes.

Joseph Knecht

Posts: 1
Nickname: spaecious
Registered: Jul, 2006

Re: Pattern Matching Wrap-Up Posted: Jul 18, 2006 11:09 PM
Reply to this message Reply
>
> One good test is whether one can still inherit and
> use Swing classes. I found that these use static
> overloading in very interesting ways ;-) Does Jython use
> Swing as its GUI?
> And can you write Swing components in it?
>
> -- Martin

I've used Jython for quick prototype stuff with Swing and learning the Swing API, and it worked well for that, but I haven't tried anything really complex. It is actually really nice to write Swing in Jython, as it ends up being much more concise and readable. You can write Swing components in Jython just as you would in Java.

Claude Knaus

Posts: 1
Nickname: cknaus
Registered: Jul, 2006

General comment on pattern matching Posted: Jul 19, 2006 3:14 AM
Reply to this message Reply
Pattern matching is fundamental to the specification and implementation of functions over non-trivial domains. Patterns can be seen as a way to provide context information in order to make a decision how to transform one or several values.

Say we have an OO interface to do some transformation. The implementation of such an interface is faced with the problem of accessing context information.

In general, the scope of the context is not limited. It is completely dependent on the implementation. In the worst case, the contextual information is accessed by tidious traversal over the [source] domain (e.g. starting at a singleton).

Now the function which is ought to be concerned only with transformation has to take domain traversal into account, making the implementation less obvious.

Pattern matching can improve this situation, as it allows the separation of the two concerns 'traversal' and 'transformation' of a domain. The contextual information is captured in the pattern.

Note: As the traversal strategy depends on the given patterns, finding an ideal traversal for a given set of patterns may not be trivial. I believe if good traversal strategies cannot be found, then there is a problem with the domain or with the transformation itself.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: General comment on pattern matching Posted: Jul 19, 2006 3:44 AM
Reply to this message Reply
> Pattern matching is fundamental to the specification and
> implementation of functions over non-trivial domains.
> Patterns can be seen as a way to provide context
> information in order to make a decision how to transform
> one or several values.
[cut]
> Pattern matching can improve this situation, as it allows
> the separation of the two concerns 'traversal' and
> 'transformation' of a domain. The contextual information
> is captured in the pattern.

You can do all this with multiple dispatch:

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

Martin Odersky

Posts: 84
Nickname: modersky
Registered: Sep, 2003

Re: Pattern Matching Wrap-Up Posted: Jul 19, 2006 8:55 AM
Reply to this message Reply
> I think multi-methods would be a great addition to any
> single-dispatch language, not just Scala. I have added
> them to Java:
>
> http://pec.dev.java.net/nonav/compile/javadoc/pec/compile/m
> ultipledispatch/package-summary.html#package_description
>
>
Thanks for the info. This is a very useful design point in the space of multiple dispatch solutions.

Kannan Goundan

Posts: 18
Nickname: cakoose
Registered: Nov, 2005

Multiple dispatch vs pattern matching. Are they the same thing? Posted: Jul 29, 2006 2:22 AM
Reply to this message Reply
I think they're the same concept. My understanding of the traditional definitions: "multiple dispatch" is a form of dynamic dispatch where the target function is selected based on the type of more than one parameter; "pattern matching" is when the target code is selected based on the value.

Differences:
- MD occurs at method call boundaries; I don't see why it couldn't also be used in switch blocks, though.
- MD matches types, PM matches values (though the PM in Scala matches on types as well).
- PM does deep matching of structure

All of those differences seem superficial and probably have to do with their lineage (multiple dispatch came from OO land, while pattern matching came from typed functional land). Are there any significant differences between the two?

One potential axis of variation has to do with extensibility. How easy is it to add more types or operations? The Scala expression problem paper [1] has a good survey of the tradeoff between extensibility and static type safety. I think that MD implementations have traditionally been more extensible while PM implementations usually only make it easy to add new operations.

[1] "Independently Extensible Solutions to the Expression Problem" by Mattias Zenger, Martin Odersky. http://scala.epfl.ch/docu/related.html

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Multiple dispatch vs pattern matching. Are they the same thing? Posted: Jul 31, 2006 2:09 AM
Reply to this message Reply
> - MD matches types, PM matches values (though the PM in
> Scala matches on types as well).

This is true. In the example of MD I gave in a previous post (http://www.artima.com/forums/flat.jsp?forum=106&thread=166742&start=28&msRange=15) I made special types for NaN and Zero to accomodate this. You could use dependent typing as a method of unifying MD and PM. Also in a language that had MD you could syntax sugar to allow matching on values.

> - PM does deep matching of structure

Depends on the implementation. My implementation does (http://pec.dev.java.net/nonav/compile/index.html).

> One potential axis of variation has to do with
> extensibility. How easy is it to add more types or
> operations? The Scala expression problem paper [1] has a
> good survey of the tradeoff between extensibility and
> static type safety. I think that MD implementations have
> traditionally been more extensible while PM
> implementations usually only make it easy to add new
> operations.
>
> [1] "Independently Extensible Solutions to the Expression
> Problem" by Mattias Zenger, Martin Odersky.
> http://scala.epfl.ch/docu/related.html

The paper you reference is excelent and heavily influced my design of MD, in particular the paper emphasises a need for a default implementation.

Flat View: This topic has 12 replies on 1 page
Topic: Pattern Matching Wrap-Up Previous Topic   Next Topic Topic: When Reuse Goes Bad


Sponsored Links



Google
  Web Artima.com   

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